Instructions
• No extension will be provided, unless for serious documented reasons.
• Start early!
• Study the material taught in class, and feel free to do so in small groups, but the solutions should be a product of your own work.
• This is not a multiple choice homework; reasoning, and mathematical proofs are required before giving your final answer.
1 Theory problems [70 pts, 10 each]
In the following let p be a prime. For any integer m, define [m] = {0,...,m − 1} and [m]+ = {1,...,m − 1}.
1. Prove that for every a ∈ [p]+ there exists a unique integer x ∈ [p]+ such that
ax mod p = 1.
2. Answer question 1 on slide 5. Specifically, give a family of hash functions that satisfies the uniformity property but maximizes the number of collisions. Your answer should formally prove why the specific family has the two latter properties.
3. Let hab = (ax + b) mod p mod m where a ∈ [p]+,b ∈ [p] and p is a prime such that p ≥ m. Prove that H = {hab} is 2-universal.
4. Consider a 2-universal family of hash functions H that hash the universe U to [m]. Assume you have n keys . Prove that there exists a hash function h ∈H that achieves 0 collisions.
Hint: Let C be the RV of number of collisions. Prove that Prh∈H(C = 0) > 0.
5. Suppose we hash n keys to n slots. Prove that with probability at least 1 there is no slot that receives more than 2logn hashed keys.
6. Explain why estimating F2 requires 4-wise independence. Describe how you can generate such as hash function for integers and explain how many bits are needed to store it?
7. In class, we went over the theoretical guarantees (slide 60) of Count-Min sketch when and )) where ϵ,δ > 0 are the accuracy and confidence parameters.
Your task is the following:
• Write a formal proof of both guarantees 1. and 2. on slide (slide 60). Set the number of buckets .
