(12 points) Collision resolution For parts (a) through (c), assume simple uniform hashing. (a) (3 points) Consider a hash table with m slots that uses chaining for collision resolution. The table is initially empty. What is the probability that, after three keys are inserted, there is a chain of size 3 ? (b) (3 points) Consider a hash table with m slots that uses open addressing with linear probing. The table is initially empty. A key k1 is inserted into the table, followed by key k2. What is the probability that inserting key k3 requires three probes? (c) (3 points) Suppose you have a hash table where the load-factor is related to the number n of elements in the table by the following formula: =1logn1. If you resolve collisions by chaining, what is the expected time for an unsuccessful search in terms of n ? (d) (3 points) Using the same formula relating and n from part (c), if you resolve collisions by open-addressing, give a good upper bound on the expected time for an unsuccessful search in terms of n. For this part, assume Uniform Hashing