Assignment IV

Due date Feb.27.

1. Suppose you have the following set of strings with their hashcodes in octal:
 un      456
 deux    470
 trois   063
 quatre  345
 cinq    761
 six     070
 sept    164
 huit    064
 neuf    446
 dix     070
 onze    245
 douze   345
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 linked list).

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.