1 and 2 were kinda trivial and I don't remember them that well.

3a) (3 marks) Hashtable with m slots, n keys inserted. Probability of one slot containing exactly 3 keys (I don't remember the wording perfectly for this one)

3b) (3 marks) Same hashtable. Assume n < m. What is the probability that there is at least one collision?

4a) (2 marks) Here's an algorithm that finds the height of a BST. What's the complexity?

4b) (6 marks) Write an algorithm to find the height of an AVL tree, must be asymptotically faster than the algorithm in 4a.

4c) (2 marks) What's the complexity of your answer in b)?

5) (12 marks) You're given a possibly infinite sequence of inputs and some odd number m. The inputs can be either be an integer, query, or median. If it's an integer, process it. If it's query, print out the m smallest numbers encountered so far. If it's median, print out the median of the m smallest numbers encountered so far. Processing must be O(lgn), query must be O(n), median must be O(lgn).

Tbh I thought 3 was the only difficult one...