2-universal hash functions, which have collision probability 1/n for any two items. A k-universal hash function h: U [n] is any random hash function that satisfies, for any inputs x1, ..., xk U, Pr[h(x1) = h(x2) = . . . = h(xk)] s 1 nk-1. 1. (2 points) Suppose you hash n balls into n hash buckets using a 2-universal hash function. Show that for t = 5n, the number of pairwise collisions exceeds t with probability at most 1/10. 2. (2 points) Use the above to argue that for t = 4 n, that the maximum load on any bin exceeds t with probability at most 1/10. Hint: Don't use a union bound. 3. (2 points) Generalize this result to k-universal hash functions for k> 2. Show that if t = cn1/k for large enough constant c, that the probability of the maximum load exceeding t at most 1/10. Hint: Instead of pairwise collisions, consider the expected number of k-wise collisions.