Your boss wants you to find a perfect hash function for mapping a known set of n items into a table of size m.

3. Your boss wants you to find a perfect hash function for mapping a known set of n items into a table of size m. A hash function is perfect if there are no collisions; each of the n items is mapped to a different slot in the hash table. Of course, this requires that m = > n. (This is a different definition of perfect hashing than the one considered in the lecture notes.) After cursing your algorithms instructor for not teaching you about perfect hashing, you decide to try something simple: repeatedly pick random hash functions until you find one that happens to be perfect.A random hash function h satisfies two properties: • Pr[h(x) = h( y)] = 1=m for any pair of items x != y. • Pr[h(x) = i] = 1=m for any item x and any integer 1 <_ i <_ m. (a) Suppose you pick a random hash function h. What is the exact expected number of collisions, as a function of n (the number of items) and m (the size of the table)? Don't worry about how to resolve collisions; just count them. (b) What is the exact probability that a random hash function is perfect? (c) What is the exact expected number of different random hash functions you have to test before you find a perfect hash function? (d) What is the exact probability that none of the first N random hash functions you try is perfect? (e) How many random hash functions do you have to test to find a perfect hash function with high probability?