4.1 Suppose h Xy is an (N, M)-hash function. For any y y, let h(y)= {x...

 

Transcribed Image Text:

4.1 Suppose h Xy is an (N, M)-hash function. For any y y, let h(y)= {x h(x) = y} and denote sy h (y)]. Define S={{1, 2} h(x) = h(x2)}|. Note that S counts the number of unordered pairs in X that collide under h. (a) Prove that 8y = N, VEY so the mean of the sy's is N 3 = M (b) Prove that (c) Prove that VEY Sy Ey (2) - (sy-5) = 25+ N (d) Using the result proved in part (c), prove that 1 S (N) Further, show that equality is attained if and only if N2 M N Sy= M 4.1 Suppose h Xy is an (N, M)-hash function. For any y y, let h(y)= {x h(x) = y} and denote sy h (y)]. Define S={{1, 2} h(x) = h(x2)}|. Note that S counts the number of unordered pairs in X that collide under h. (a) Prove that 8y = N, VEY so the mean of the sy's is N 3 = M (b) Prove that (c) Prove that VEY Sy Ey (2) - (sy-5) = 25+ N (d) Using the result proved in part (c), prove that 1 S (N) Further, show that equality is attained if and only if N2 M N Sy= M