(1) Suppose we perform hashing with hash chaining (each hash table cell stores a linked list of key,value pairs, and each set or get operation scans through all the entries in the list in order to find the one with the matching key). Suppose also that the hash table has n (key,value) pairs in it, but that the length of the hash table is only sqrt(n). What would be the expected time per get or set operation?

(2) Suppose we perform hashing with open addressing -- we have a hash function h(k,i) that takes two arguments, where k is the key being hashed and i is an integer -- and to set a key we scan through the hash table cells indexed by h(k,0), h(k,1), ... until finding an empty cell. To get a key we scan through the same cells until finding either an empty cell or a matching (key,value) pair.
(a) Suppose that our hash table has n (key,value) pairs in it, and that the number of cells in the hash table is exactly 2n. Write a formula for the probability that, when adding a new key k to the hash table, the search finds the first empty cell at h(k,i). Your formula should be a function of both i and n, but not k.
(b) Use your formula to argue that, for any polynomial p(n), there is a constant c such that, with probability at least 1-1/p(n), the first empty cell is found at h(k,i) with i <= c log n.
(c) Use your formula to argue that there is a constant d such that, with probability at least 1/n, the first empty cell is found at h(k,i) with i >= d log n.

(3) Suppose that we wish to hash a set of n (key,value) pairs, where each key and value may be stored in a 32-bit machine word. How many words of memory would be required to store these in
(a) An open-addressed hash table with a fill factor of two?
(b) Hash chaining with a fill factor of one, where the nodes in the hash chain are represented using a singly-linked list?
(c) A cuckoo hash table in which each of the two arrays has size (1+epsilon)n?

(4) Recall that linear probing is a form of open addressing in which we avoid having to compute multiple hash values by placing key-value pair (k,v) in the first empty cell in the sequence h(k), h(k)+1, h(k)+2, ...
In order for retrievals to work correctly, it is necessary that for each pair (k,v) in the hash table, all cells between h(k) and the position where the pair is actually stored must be non-empty.
(a) Suppose that pair (k,v) is stored in cell i, and we wish to delete it from the hash table by making that cell empty and then moving some subsequent pairs downwards by one position to preserve the correctness condition. Under what conditions should we move the contents of cell i+1 into cell i?
(b) Write out pseudocode for deleting a pair (k,v). Your pseudocode should take only k as an argument (it should not start out knowing the position of the pair) and should raise an exception if the pair is not actually stored in the hash table.