1. In class we described van Emde Boas trees with a simplifying assumption that each item has a different key from each other item. But what if this assumption is not true? Describe how to modify the data structure to handle the case that more than one item may have the same priority. Your solution should have the same asymptotic running time per operation as the van Emde Boas tree as described in class. (Possible solutions include storing linked lists of items with the same priority, or using a separate data structure to map priorities to the set of items having those priorities. You may assume that hash tables can solve the dictionary problem in constant time per operation. You should describe how your modifications affect the operation of the three basic priority queue operations: insert, delete, and find-min). 2. Slot-size bound for hash chaining (Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, Problem 11-2, page 250): Suppose we have a hash table with n slots, with collisions resolved by chaining -- that is, each slot stores a linked list of the (key,value) pairs that the hash function maps to that slot. Suppose also that n keys are inserted into the table. (That is, the fill ratio is 1). Each key is equally likely to be hashed to each slot, independently of the other keys. Let M be the maximum number of keys in any slot after all the keys have been inserted. Your mission is to prove an O(log n / log log n) upper bound on E[M], the expected value of M. (a) Argue that the probability Q_k that exactly k keys hash to a particular slot is given by Q_k = (1/n)^k (1 - 1/n)^(n-k) (n choose k) (The last term is the binomial coefficient that counts the number of distinct k-tuples that can be formed by n items; it equals n!/k!(n-k)!.) (b) Let P_k be the probability that M = k; that is, the probability that the slot containing the most keys contains k keys. Show that P_k <= n Q_k. (c) Use Stirling's approximation to show that Q_k < e^k / k^k. Stirling's approximation is: n! = sqrt(2 pi n) (n/e)^n (1 + O(1/n)) where e ~ 2.71828 is the base of the natural logarithm. (d) Show that there exists a constant c > 1 such that Q_k0 < 1/n^3 for k0 = c log n / log log n. Conclude that P_k < 1/n^2 for k >= k0. (e) By arguing that E[M] <= n Pr[ M > c log n / log log n] + (c log n / log log n) Pr[ M <= c log n / log log n], conclude that E[M] = O(log n / log log n). 3. In a cuckoo hashing data structure with two hash functions g(x) and h(x), the hash table may still operate successfully if two elements x and y are inserted with g(x)=g(y) and h(x)=h(y), but it will fail if it is given three elements x, y, and z with g(x)=g(y)=g(z) and h(x)=h(y)=h(z). (a) If a cuckoo hashing data structure has n slots in each table, and the hash functions are uniformly random, what is the probability that some particular triple (x,y,z) collides in this way? (b) If n elements are inserted into the structure, what is the expected number of triples that collides in this way? (c) Use Markov's inequality (http://en.wikipedia.org/wiki/Markov%27s_inequality) together with your answer to part (b) to get a bound on the probability that there is at least one triple collision.