1 Easy Questions. 5 points each. Describe an explicit universal hash function family from U = {0, 1, 2, 3, 4, 5, 6, 7} to {0, 1} [Hint: you can do this with a set of 4 functions.] Let H [hi, ..., hk be a universal family of hash functions from U 0,1,... ,u -1 into 0, 1). Could it be that some function hi E H maps all of U to 0? Explain. Assume that u 2 2 Let H be a universal family of hash functions from U 0,... u -1} into a table of size m. Let S C 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 (x, y) in S that collide is s 1 Let H be a universal family of hash functions from U 0,... u - 1} into a table of size m. Let S C U 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+2Vm 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 > kEK]) . For instance, the chance that X is more that 100 times its expectation is at most 1/100.] 1 Easy Questions. 5 points each. Describe an explicit universal hash function family from U = {0, 1, 2, 3, 4, 5, 6, 7} to {0, 1} [Hint: you can do this with a set of 4 functions.] Let H [hi, ..., hk be a universal family of hash functions from U 0,1,... ,u -1 into 0, 1). Could it be that some function hi E H maps all of U to 0? Explain. Assume that u 2 2 Let H be a universal family of hash functions from U 0,... u -1} into a table of size m. Let S C 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 (x, y) in S that collide is s 1 Let H be a universal family of hash functions from U 0,... u - 1} into a table of size m. Let S C U 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+2Vm 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 > kEK]) . For instance, the chance that X is more that 100 times its expectation is at most 1/100.]