All algorithms are in pseudocode

Hash tables

3.1 (5p) For the input 30, 53, 58, 35, 93, 54, 25, 43, 31, 45 and hash function h(k) = k mod 19, construct the open hash table.

3.2 (5p) Find the largest number of key comparisons in a successful search in this table. Find the average number of key comparisons in a successful search in this table.

3.3 (5p) Find the probability of all n keys being hashed to the same cell of a hash table of size m if the hash function distributes keys evenly among all the cells of the table.

3.4 (5p) Explain how to use hashing to check whether all elements of a list are distinct. What is the time efficiency of this application? Compare its with that of the brute-force solution and to the pre-sorting solution (first sort array then traverse to find if all elements are distinct)