Due date Feb.27.
1. Suppose you have the following set of strings with their hashcodes in
We insert these strings in the given order, into a hash table of size 16.
a) Show the resulting table when using separate chaining (each bucket is a
b) Show the resulting table when using open addressing a linear probing, where
the probe adds 1 at each step.
c) Show the resulting table when using linear probing with an increment of 7.
2. Two sets of numbers S and T are equal if S is a subset of T and T is a
subset of S. Suppose that S has n elements and T has m elements. Show that
one can check set equality in O (n + m). Suppose that you wanted to check
set equality by first sorting the elements of each set. What would be the
complexity of set equality in that case?
3. We have a hash table with separate chaining. Sketch (in the pseudo-code of
your choice) a method that prints all the elements in the table. Provide
simplified declarations for the data structure for the table and the buckets.