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?)