1. O(sqrt n).

2. (a) The probability that an individual cell is empty is 1/2, and the probability that the search stops at step i is Pr[empty]*(1-Pr[empty])^i = 1/2^{i+1}.

(b) The probability that the search stops at a cell whose number is greater than i is 1/2^{i+2} + 1/2^{i+3} + ... = 1/2^{i+1}. This probability is less than 1/p(n) when 2^{i+1} >= p(n), true when i >= log_2 p(n) - 1 = O(log n).  More specifically, for polynomials p(n) of the form n^k, log_2 p(n) = k log_2 n, so we may take c to be the degree of the polynomial.

(c) The first empty cell is found at h(k,i) with probability 1/2^{i+1} (from part a), and for any i <= log_2 n - 1 this is at least 1/n. So we may take d = 1.

3. (a) 4n words: two words for each key-value pair, and two words for each empty slot in the table. By the assumption on the fill factor the number of empty slots equals the number of key-value pairs.

(b) It's reasonable to assume that each table slot takes one word (to point to the first entry in its linked list, or for a null pointer if the list is entry) and that each node in a hash chain takes three words (for a key, a value, and a next pointer). With these assumptions, the data structure takes 4n words: n words for the table, and 3n words for the n hash chain nodes.

(c) (4+2epsilon)n words: two words for each filled or empty hash table slot, as in part (a), with n(1+epsilon) slots in each of the two arrays.

4. (a) The contents of cell i+1 need to be moved downward if the cell is nonempty and the key stored there does not hash to position i+1.

(b) This part is a little tricky. What I intended as the answer is to loop over the cells from i+1 onward, testing the condition in 4(a) and moving the contents of each cell downward by one if the condition is met. Since the question was worded with that answer as the expected answer, it should probably get full or nearly full credit, but it's actually not quite correct. The problem is that we could have a situation where the key in cell i hashes to i, the key in cell i+1 hashes to i+1, and the key in cell i+2 hashes to i again. If we perform the answer I intended, nothing moves down, but then we can't find the key in cell i+2 when we look for it.

Here's a corrected answer. If anyone actually figured this out, they should get extra credit:

def delete(k):
   /* find and empty the location of key k in the table */
   i = h(k)
   while cell i does not contain key k:
       if cell i is empty:
           raise an exception (the key is not in the table)
        i = i + 1 (mod table size)
   set cell i to empty
   
   /* find elements that need to be moved down */
   j = i + 1 (mod table size)
   while cell j is not empty:
       if h(key in cell j) is not in the range from i+1 to j:
           swap contents of cells i and j
           i = j
       j = j + 1 (mod table size)