15-451 MINI #3: due 11:59pm Oct 2
                    =================================

1. 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? 


2. In class we discussed implementing a stack using an array, where we
double the size of the array when it gets full.  Suppose that instead
of doubling the size of the array, we instead do the following.  The
first time the array gets full, we add 1 to its size. The second time
the array gets full, we add 2 to its size.  The third time the array
gets full, we add 3 to its size; and so on (the kth time it gets full,
we add k to its size).  What will be the amortized cost per operation of
such a data structure in a sequence of n pushes starting from an
initially empty stack?   You can use Theta() notation.  Give your
reasoning.  Hint: the answer is not Theta(1), Theta(log n), or Theta(n).