Data structure and Algorithm Analysis

1.Consider a hash table with collisions resolved by chaining. Assume simple uniform hashing.

(a) Consider the case that the number of keys (corresponding to elements) n stored in the hash

table is 100 times the number of slots m. What is the average time for an unsuccessful search?

(b) Consider the case that there are m slots in the hash table, and that the number of keys stored

in the hash table is . What is the average time for an unsuccessful search?

2. [5 points] Explain why the average search time in a hash table with collisions resolved by

chaining is not always O(1).

3. [5 points] Demonstrate what happens when we insert the keys 5; 28; 19; 15; 20; 33; 12; 17; 10

into a hash table with collisions resolved by chaining. Let the table have 9 slots, and let the hash

function be h(k) = k mod 9.

4. [5 points] Consider an open-address hash table with uniform hashing.

(a) What is the expected number of probes (at most) in an unsuccessful search when the load

factor is 7/8?

(b) What is the expected number of probes (at most) in an unsuccessful search when the number

of keys in the array are 5 and the number of slots 8?

5. [5 points] Consider inserting the keys 10; 22; 31; 4; 15; 28; 17; 88; 59 into a hash table of

length m = 11 using open addressing. Illustrate the result of inserting these keys using double

hashing with h1(k) = k and h2(k) = 1 + (k mod (m− 1)).