Description

Sundry
Before you start writing your final homework submission, state briefly how you worked on it. Who else did you work with? List names and email addresses. (In case of homework party, you can just describe the group.)
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.
(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? (Hint: 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 1 ≤ k ≤ n. Let Ck be the number of collisions that we’ll see while hashing dk. What is E[Ck]?
2 Geometric and Poisson
Let X ∼ Geo(p) andY ∼ Poisson(λ) be independent. random variables. Compute P(X >Y). Your final answer should not have summations.
3 Exploring the Geometric Distribution
Suppose X ∼ Geometric(p) and Y ∼ Geometric(q) are independent. Find the distribution of min{X,Y} and justify your answer.
4 Lunch Meeting
Alice and Bob agree to try to meet for lunch between 12 PM and 1 PM at their favorite sushi restaurant. Being extremely busy, they are unable to specify their arrival times exactly, and can say only that each of them will arrive (independently) at a time that is uniformly distributed within the hour. In order to avoid wasting precious time, if the other person is not there when they arrive they agree to wait exactly fifteen minutes before leaving. What is the probability that they will actually meet for lunch? (hint: Sketch the joint distribution of the arrival times of Alice and Bob. What parts of the distribution corresponds to them meeting for lunch?)