1. Do problem 12-2. Why does this sorting algorithm not obey the lower bound for comparison sorting algorithms which we proved in class?

2. As we observed in class, when we store n items into a hash table of size m, even if we have a very good hash function h, the expected number of other items in the chain at h(x) is O(n/m), for any item x. If n gets too large, this means that the search operation cannot be performed in expected time O(1).

Design a data structure in which m, the size of the table, changes in response to fluctuations in n, so that for some constant c, c <= n/m <= 4c, and for which the operations insert, delete and search all require expected time O(1).

3. If we apply the function g(x) = (ax + b) mod p to all the elements x in {0,...,p-1}, getting { g(0), g(1), ... , g(p-1)}, we get a permutation of the set {0,...,p-1} (recall that a belongs to {1,...,p-1} and b belongs to {0,..,p-1}).

• a) Show that this is not always true for non-prime p using p=6. You choose a and b. Do all choices of a,b fail to produce a permutation, or just some of them?
• b) Which of the following propositions we used in class fail for non-prime p?
  • i) If (ax mod p) = (ay mod p) then ((ax - ay) mod p) = 0
  • ii) If (a(x-y) mod p) = 0, then either a = 0 or (x-y) = 0
  • iii) If ((ax + b) mod p) = ((ay + b) mod p) then x=y