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 345We 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.