Programming 1, 2021-22
Week 9: Exercises

1. Flip a Dictionary

Write a function that takes a dictionary such as { 'green' : 'zelený', 'red' : 'červený' } and returns a corresponding dictionary in which the keys and values have been flipped, e.g. { 'zelený' : 'green', 'červený' : 'red'} .

2. Time Class

Write a class Time that represents a time of day with 1-second resolution, e.g. 11:32:07.

• Include an initializer that takes three integers (hours, minutes, seconds) and returns a Time. Seconds should default to 0 if not provided.

• The '+' operator should add a number of seconds to a Time, yielding a new Time object (wrapping past midnight if necessary).

• The '-' opertator should subtract two Time objects, yielding a (possibly negative) number of seconds.

• A Time object's string representation should look like this: "11:32:07".

3. Date Class

Write a class Date representing a month and day. The class should support these operations:

• Date(m, d) – make a Date representing the given month (1 ≤ m ≤ 12) and day (1 ≤ d ≤ 31)

• d.next() - return the Date after d

• d.prev() - return the Date before d

• d.add(n) – add n days to the given Date, wrapping past Dec 31 to Jan 1 if necessary

• A Date object's string representation should look like this: "May 15".

4. Polynomial Class

Write a class Polynomial representing a polynomial of a single variable. The class should support these operations:

• Polynomial(c) – make a Polynomial with the given coefficients. For example, Polynomial(3, 2, 1) represents the polnomial 3x² + 2x + 1.

• p.degree() - return the degree of this Polynomial

• The '+' operator should add two Polynomials.

• The '*' operator should multiply two Polynomials.

• p.eval(x) – return the value of the Polynomial at the given value of x

• A Polynomial should have a string representation such as "3x^2 + 2x + 1".

5. Matrix Sum

Write a function that computes the sum of two matrices A and B, represented as lists of lists. Assert that the matrices have the same dimensions.

6. Matrix Product

Write a function that computes the product of two matrices A and B, represented as lists of lists. Assert that the matrices have dimensions that are compatible for multiplication.

7. Queue

a) Write a class LinkedQueue that represents a FIFO queue with methods enqueue() and dequeue(). Use a linked list, so that these methods run in O(1).

b) Write a subclass StatQueue that is like LinkedQueue, but also keeps some extra statistics. The class should have these methods:

• q.count() - the number of items currently in the queue

• q.avg() - the average number of items that have been in the queue over its lifetime. (Specifically, if there have been N enqueue/dequeue operations, then the queue has existed in (N + 1) consecutive states, and this is the average number of items across all of those states.)

• q.longest() - the largest number of items that have ever been in the queue

8. Flatten

Write a function flatten that takes a list of lists and returns a list containing all the values from all sublists:

>>> flatten([[5, 2], [6], [8, 3]])
[5, 2, 6, 8, 3]

9. Deep Flatten

Write a function deep_flatten that takes a list that may contain sublists nested to any level. The function should return a list containing all the values from all the sublists:

>>> deep_flatten([ [[5, 2], 6], [8, 3], [[[[10]]]] ])
[5, 2, 6, 8, 3, 10]