1 Random Cuckoo Hashing Cuckoo birds are parasitic beasts. They are known for hijacking the nests of other bird species and evicting the eggs already inside. Cuckoo hashing is inspired by this behavior. In cuckoo hashing, when we get a collision, the element that was already there gets evicted and rehashed. We study a simple (but ineffective, as we'll see) version of cuckoo hashing, where all hashes are random. Let's say we want to hash 11 pieces of data d1,d2, . . . ,dn into n possible hash buckets labeled 1,. ..,n. We hash the all, . . . ,dn in that order. When hashing 03,-, we assign it a random bucket chosen uniformly from 1, . . . ,n. If there is no collision, then we place di into that bucket. If there is a collision with some other d j, we evict dj and assign it another random bucket uniformly from 1, . . . , n. (It is possible that d j gets assigned back to the bucket it was just evicted from!) We again perform the eviction step if we get another collision. We keep doing this until there is no more collision, and we then introduce the next piece of data, all-+1 to the hash table. (a) What is the probability that there are no collisions over the entire process of hashing d1, . . . ,dn to buckets 1,. ..,n? What value does the probability tend towards as n grows very large? (b) Assume we have already hashed d1, . . . ,dn_1, and they each occupy their own bucket. We now introduce dn into our hash table. What is the expected number of collisions that we'll see while hashing dn? (Him: What happens when we hash dn and get a collision, so we evict some other di and have to hash di? Are we at a situation that we've seen before?) (c) Generalize the previous part: Assume we have already hashed d1, . . . ,dk_1 successully, where l g k S 11. Let Ck be the number of collisions that we'll see while hashing dk. What is E[Ck] ? ((1) Let C be the total number of collisions over the entire process of hashing d1, . . . ,dn. What is 1E[C]? You may leave your answer as a summation