15-451 MINI #3: due midnight Oct 1.
=====================================
1. Draw a treap containing the following (key priority) pairs:
(a 2), (b 5), (c 3), (d 1), (e 7), (f 4).
Feel free to just do an ascii drawing.
2. Consider the following two hash functions h1 and h2 from {1,2,3} to {0,1}:
1 2 3
---+----------
h1 | 0 0 1
h2 | 1 1 0
(i.e., h1(1)=0, h1(2)=0, h1(3)=1, h2(1)=1, h2(2)=1, h2(3)=0)
a) Is the set H = {h1, h2} a universal hash family? Why or why not?
b) What if we modify h1 so that h1(2)=1. Is H = {h1, h2} a
universal hash family now? Why or why not?
3. Let v be the vector [1 0 0 1 1]. Let r be a *random* vector of 5
bits (with all 2^5 possibilities equally likely).
(a) What is the probability that v+r = [0 0 0 0 0]? (addition is mod 2)
(b) What is the probability that the dot-product v.r = 1 mod 2?
(equivalently, what is the probability that r has an odd number
of 1s looking just at its 1st, 4th, and 5th positions?)