Suppose there are m distinct integers a1, ..., Am which are each drawn from the universe U = {0, 1, 2, 3, ..., n 1}. We would like to choose a random hash function h from a family H so that for all i + j, h(ai) # h(az), that is, the set {a1, ..., Am} is perfectly hashed under h. We have seen that if H is universal and has range size M = (m2), then a random h in H has this property with constant probability. However, for the the hash function families we saw, specifying a random h in H requires at least log n bits. We would like to use fewer random bits when m is much less than n. Suppose we pick a random prime p among the first 10m2. log2 n primes. Define the map h:U + {0, 1, 2, ..., 10m2 1} given by h(y) = g(y mod p), where g is a universal hash function with range size 10m. Argue that h has the above perfect hashing property with probability at least 9/10. How many bits do we need to specify h? Suppose there are m distinct integers a1, ..., Am which are each drawn from the universe U = {0, 1, 2, 3, ..., n 1}. We would like to choose a random hash function h from a family H so that for all i + j, h(ai) # h(az), that is, the set {a1, ..., Am} is perfectly hashed under h. We have seen that if H is universal and has range size M = (m2), then a random h in H has this property with constant probability. However, for the the hash function families we saw, specifying a random h in H requires at least log n bits. We would like to use fewer random bits when m is much less than n. Suppose we pick a random prime p among the first 10m2. log2 n primes. Define the map h:U + {0, 1, 2, ..., 10m2 1} given by h(y) = g(y mod p), where g is a universal hash function with range size 10m. Argue that h has the above perfect hashing property with probability at least 9/10. How many bits do we need to specify h