15-451 MINI #3: due 11:59pm, Feb. 17.
                    =====================================

This mini is due via *email* to your TA, by 11:59pm Tuesday, Feb 17.
Please use the subject line "15-451 MINI #3" in your email.
Also, please copy your answers directly into the email body.
*Do not* include any attachments.

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 | 1   0   1
       h2 | 1   1   0
       h3 | 0   0   1
    
    i.e., h1(1)=1, h1(2)=0, h1(3)=1
          h2(1)=1, h2(2)=1, h2(3)=0
          h3(1)=0, h3(2)=0, h3(3)=1

   a) Is the set H = {h1, h2, h3} a universal hash family? Why or why not?
   b) By complementing just one of the nine bits in the table, create a new
      H' that *is* a universal hash family.

3. Let v1 be the vector [1 0 1 1 0 1], and let v2 be the vector
[1 1 0 0 1 1].  Let r be a *random* vector of 6 bits (with all 2^6
possibilities equally likely). Define random variables X and Y as
X = v1.r and Y = v2.r (here "." refers to the usual dot-product and 
addition is mod 2),

 (a) Show that X and Y are unbiased,i.e., P[X=0] = P[X=1] = 1/2
     and P[Y=0] = P[Y=1] = 1/2.

 (b) Calculate Pr[X = Y]. Explain your answer.