Suppose that we are given a sequence S of n elements, each of which is an integer in the range [0; n2 1]. Describe a simple method for sorting S in O(n) time. (Hint: Think of alternate ways of viewing the elements so that you can use Radix-Sort.)
Demonstrate the insertion of the keys 5, 28, 19, 15, 20, 33, 12, 17, 10 into a hash table with collisions resolved by chaining. Let the table have 9 slots and let the hash function be h(k) = (2k + 5) mod 9.
Consider inserting the keys 10, 22, 31, 4, 15, 28, 17, 88, 59 into a hash table of length t = 11 using open addressing with primary hash function h1(k) = k mod t. Illustrate the result of inserting the keys using linear probing, quadratic probing and using double hashing with h2(k) = 1 + (k mod (t 1)).
Suppose we use double hashing to resolve collisons; that is, we use the hash function h(k; i) = (h1(k) + ih2(k)) mod t. Show that if t is even and h2(k) is even for some key k, then the probe sequence for k examines at most half the slots in the table before returning to slot h1(k).
1
