If we hash a set S of n keys into a table of size n with a universal hash function h, what is the expected mazimum number of keys that collide? In other words, what is the maximum number of keys that are expected to hash to the same location? We break down this computation into a sequence of easier steps, as follows Let Aj be the event that at least one slot in the hash table has 2 j keys. We compute the largest j for which ProblA] 1/2; that j is our answer. Calculating A, directly is not straightforward, so we proceed as follows. In all cases, explain your reasoning (a) Let Aj be the event that the table slot 1 gets 2 j keys under h. Supposing you know ProblA, give an upper bound on Prob[A] (b) Let B be the event that a fired subset C C S of size IC-J hashes into slot 1 That is, each key of C maps to slot 1 under h. Calculate the probability Prob B (c) Use ProblB] to get an upper bound on the probability Prob A] (d) Compute the largest value of j for which Prob[4] . Explain how in combi- nation with (a), this j is the expected maximum number of collisions If we hash a set S of n keys into a table of size n with a universal hash function h, what is the expected mazimum number of keys that collide? In other words, what is the maximum number of keys that are expected to hash to the same location? We break down this computation into a sequence of easier steps, as follows Let Aj be the event that at least one slot in the hash table has 2 j keys. We compute the largest j for which ProblA] 1/2; that j is our answer. Calculating A, directly is not straightforward, so we proceed as follows. In all cases, explain your reasoning (a) Let Aj be the event that the table slot 1 gets 2 j keys under h. Supposing you know ProblA, give an upper bound on Prob[A] (b) Let B be the event that a fired subset C C S of size IC-J hashes into slot 1 That is, each key of C maps to slot 1 under h. Calculate the probability Prob B (c) Use ProblB] to get an upper bound on the probability Prob A] (d) Compute the largest value of j for which Prob[4] . Explain how in combi- nation with (a), this j is the expected maximum number of collisions