HW 5 Solutions   				MB

1.

a. No, We could have n bins, n elems, all of them in bin 1. Avergae number
of elems per bin is 1, but lookup time is Theta(n).

b. Yes, because when taking modulo 2k, no 2 hash codes that were unequal
modulo k will become equal. Note, however, that is if it was 2k+1 this
would no longer be true.

c. Yes, if the word we inserted has a common prefix of length 10 with K.

d. No, because the longest string may not share prefices with any other
and get compressed to just height 1.

e. Once again no, for the same reason.

f. True. You must search all of the lowest level, and half the elements
are located on that level.

2.

a. Yes. It is actually O(2^h), but that is bounded above by O(2^(2h))

b. Yes. If it is balanced it has height Theta(log n), and if it is not,
the height is larger. Hence the answer is true.

c. Yes. It is actually between 2^(h-2) and 2^(h-1), those are, however
just 2^(h-3)*4 and 2^(h-3)*8.

d. Yes. In the worst case number of inversions in a list of length k is
k*(k-1)/2, and because you added them in front before any of the larger
ones thats the most it could increase.

e. No. If you are only dealing with small inputs Theta(n^2) with a small
constant may work better then Theta(n) with a large constant.

3.

Start at the top right hand corner of the array. Compare that element with
the one you are searching for (x) . If x is greater, you know that x
cannot be in the first row, so you go down one row. If smaller, you know
it can't be in the same column, so you go down one column. Repeat until
you either find the element or get to the bottom left corner. The running
time is O(m+n) because at any step you eliminate either a row or a column.

4. 

repeat the following for each element of the array:

If the stack is empty, push the elem onto the stack.
Else, If it is equal to the element on top of the stack push it as well.
Otherwise pop the top element off the stack and throw it out, together
with the current element. 
Once you are done, if you stack is empty there is no majority element.
If it is not, you pop it, and compare the element to every elem in the
array, counting the number of matches. If it is > K/2, return true, OW
false.

Because we make two passes through the array, the running time is O(k).

5. Think of the matrix as a base 3 number with m*n base-3 digits. Then
just hash the number using any of the standard hash functions for numbers.