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.