Programming 1, 2020-21
Week 10: Exercises

1. Tree Values

Write a function that prints out all values in a binary search tree in order, separated by spaces.

2. Rebalancing a Tree

Write a function that takes a binary tree and constructs a second tree that contains all the values from the first tree and is as balanced as possible.

3. Non-Recursive Tree Sum

Write a function that computes the sum of all values in a binary tree without using recursion.

4. Twice

Write a function twice(f) that takes a function f(x) of a single variable, and returns a function g(x) such that g(x) = f(f(x)).

5. Power of a Function

Write a function fpower(f, n) that takes a function f(x) of a single variable, and return a function g(x) such that g(x) = f(f(...(f(x)))), where f is applied n times.

6. 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.

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

8. Deep Flatten

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

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

9. Largest Product in a Grid

Solve Project Euler's problem 11.

10. Number Spiral Diagonals

Solve Project Euler's problem 28.

11. Connect Four

Write a program that allows two players to play Connect Four. At each step, print out a picture of the game board.