Programming 1
Week 10: Exercises

1. Recursive Palindrome

Write a recursive function that determines whether a string is a palindrome.

2. Map

Write the built-in function map:

>>> list(map(lambda i: i + 1, [2, 4, 6]))

[3, 5, 7]

3. Filter:

Write the built-in function filter:

>>> list(filter(lambda i: i % 2 == 1, range(10)))
[1, 3, 5, 7, 9]

4. 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]

5. Deep Flatten

Write a function deepFlat 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:

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

6. Double-Ended Queue

Write a class implementing a double-ended queue, otherwise known as a deque. The queue should provide these operations:

• q.prepend(x)

• q.append(x)

• q.removeFirst()

• q.removeLast()

• q.isEmpty()

All of these operations should run in constant time. Use a doubly-linked list.

7. Polynomial Class

Write a class Polynomial representing a polynomial of a single variable. Your class should include the following:

• an initializer that takes a variable number of floats, yielding a polynomial with those coefficients. For example,

      Polynomial(1.0, 4.0, 5.0)

  should yield the polynomial x² + 4x + 5.

• The '+' operator should add two polynomials.

• The '*' operator should multiply two polynomials.

• Provide a method p.eval(x) that evaluates a polynomial for a given value of x.

• Provide a method p.deriv(k) that returns the k-th derivative of a polynomial for a given k. k should default to 1.

• A polynomial should have a string representation such as "x^2 + 4x + 5".

8. Finding Files

Write a function find(dir, pattern) that prints the names of all filenames in dir or its subdirectories that match the given pattern. A pattern may include wildcards, e.g.

• *.txt

• project*

• abc*_def.*

9. Birthday Experiment

Write a function that takes a number N and returns an estimated probability that in a room with N people at least two will have the same birthday. To accomplish this, the function should run 1000 random experiments. In each experiment, the program should generate N random birthdays and test whether any two are the same.

10. Birthday Probability

Write a function that computes the probability in the previous exercise mathematically, without performing random experiments.