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