Consider the following static dictionary implementation for storing a set S of n keys from a universe U. We use m linked lists L_o, ...., L_m - 1, where m = O (n^3/2), and two random hash functions h_1, h_2: U rightarrow {0, ..., m - 1}. We insert all n keys x_1, ..., x_n elementof S sequentially. In the i-th iteration, we add the i-th key, x_i, to the shorter one of the lists L_h1(x) and L_h2(x) Let Y be the number of pairs {X, X'} S such that x and x' end up in the same linked list. (a) Prove that E[Y] = O(1), under the assumption that the hash function values h_i (x), i elementof {1, 2} x elementof S, are all uniformly and independently distributed (b) (Bonus) The hash function pair (h_1, h_2) is good for a set S, if we can store each key of S in one of its two designated linked lists such that Y = 0 (i.e., no list contains more than one element). Assume that |U| is polynomial in n. Prove that there exists a family H of hash functions with |H| = n^0(1) such that for every set S of n keys a randomly chosen pair (h_1, h_2) elementof H times H is good for S with constant positive probability