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