15-451 MINI #3: due midnight Oct 2.
===================================
1. Draw a treap containing the following (key priority) pairs:
(a 5), (b 1), (c 3), (d 6), (e 2), (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 1 1
h2 | 1 1 0
(i.e., h1(1)=0, h1(2)=1, h1(3)=1, h2(1)=1, h2(2)=1, h2(3)=0)
Is the set H = {h1, h2} a universal hash family? Why or why not?
3. Let v be the vector [1 0 1 1 0 1]. Let r be a *random* vector of 6
bits (with all 2^6 possibilities equally likely).
(a) What is the probability that v+r = [0 0 0 0 0 0]? (addition is mod 2)
(b) What is the probability that v+r = [0 0 1 1 0 0]? (addition is mod 2)
(c) 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, 3rd, 4th, and 6th positions?)