Easy Questions. 5 points each. Describe an explicit universal hash function family fromU-(0, 1,2,3,4,5,6,7) to (0,1) 1 Hint: you can do this with a set of 4 functions.] Let H-thbe a universal family of hash functions from U-0. ,u - 1 into 10,1. Could it be that some function h E maps al of U to 0? Explain. Assume that u2 2. . Let H be a universal family of hash functions from U = {0, 1, ,u-1} into a table of size m. Let S-U be a set of m elements we wish to hash. Prove that if we choose h from H at random, the expected number of pairs (r, y) in S that collide is 1 Let H be a universal family of hash functions from U- (0,1,...,u1 into a table of size m. Let S CU be a set of m elements we wish to hash. Prove that with probability at least no list in the table has more than 1 + 2v/m elements [Hint: To solve this question, you should use "Markov's inequality". Markov's inequality is a fancy name for a pretty obvious fact: if you have a non-negative random variable X with expectation E[X], then for any k>0, Pr(X>kEX)S .For instance, the chance that X is more that 100 times its expectation is at most 1/100.] Easy Questions. 5 points each. Describe an explicit universal hash function family fromU-(0, 1,2,3,4,5,6,7) to (0,1) 1 Hint: you can do this with a set of 4 functions.] Let H-thbe a universal family of hash functions from U-0. ,u - 1 into 10,1. Could it be that some function h E maps al of U to 0? Explain. Assume that u2 2. . Let H be a universal family of hash functions from U = {0, 1, ,u-1} into a table of size m. Let S-U be a set of m elements we wish to hash. Prove that if we choose h from H at random, the expected number of pairs (r, y) in S that collide is 1 Let H be a universal family of hash functions from U- (0,1,...,u1 into a table of size m. Let S CU be a set of m elements we wish to hash. Prove that with probability at least no list in the table has more than 1 + 2v/m elements [Hint: To solve this question, you should use "Markov's inequality". Markov's inequality is a fancy name for a pretty obvious fact: if you have a non-negative random variable X with expectation E[X], then for any k>0, Pr(X>kEX)S .For instance, the chance that X is more that 100 times its expectation is at most 1/100.]