Due on Friday, March 7th, 1997 in Pierce or 10DeWolfe #33
1. Counting Sort and its Analysis
The AAA autoclub gives its members free maps and trip planners that include
the distances between each major city on a journey. Suppose you are given
a list of n cities, and the distances between consecutive pairs.
Then you could easily make a grid chart that gives you the distance between
any two cities in O(1) time, but that would take O(n^2) time
to preprocess the data. Devise an O(1) algorithm that gives you
the distance between any two cities on the route, but uses only O(n)
time to preprocess the data.
2. More Sorting
This is a classic CS problem that has several neat solutions. Given a file of 1 million 20-bit words (unsorted), devise an algorithm that finds a 20-bit word that does not occur in the file. Present a deterministic version that is guaranteed to work (even though there is an elegant randomized algorithm that works with high probability). The million words on the file need not be unique. Analyze your algorithm, both in time and space.
3. Lower bounds on sorting
A very common approach to speeding up quicksort is to choose a small cutoff value, c>1, for the bottom of the recursion, and use a fast, hand-coded function to sort these c elements. Your TF has written a very slim piece of assembly that sorts c=5 elements in 6 comparisons. Prove that there is a bug in his code. Now help him out by describing an algorithm that sorts these elements in as few comparisons as possible. (Hint: strive for the lowest bound, it is possible!)
4. Who owes you?
You are a bookie with a large list of n customers. Suppose this information is represented in an array of records, each containing a name and a balance. Devise an algorithm that sorts only on the basis of whether the customer owes you money or not (it does not matter how much the customer owes you, you are just interested in quickly getting a list of people you need to pester). Use as few exchanges as possible.
5. [Knuth] Note that the operations performed in sorting an array of n elements directly correspond to the operations performed in sorting a particular permutation in S_n. Given a permutation P= a_1 a_2 a_3 ... a_n, compute the average value of the function:
6. Exercise [12.3-4] page 232 (Hashing exercise)
7. Problem [12-4] page 242. (Quadratic probing)
8. Problem [18-1] page 375. (Bit Reversed binary counter)