CSE 417: Algorithms and Computational Complexity
Homework #1
January 7, 2004
due: Wednesday, January 14
In this assignment you will write a program to simulate the randomized
version of Quicksort and count the number of key comparisons it does.
This will actually be much simpler than implementing the full
Quicksort, as you won't actually need the Partition subroutine.
You may use any convenient programming language, as long as it
supports recursion and has a built-in random number generator.
-
Use the built-in random number generator to write a simple subroutine
int uniform(int first, int last);
that returns a random, uniformly chosen integer between first and
last, inclusive. That is, each such integer should be chosen with
probability 1 / (last - first + 1).
-
Write a recursive algorithm
int quickCount(int first, int last);
that counts the number of key comparisons the randomized version of
quickSort(E, first, last) would use. This is very simple: quickCount
uses the subroutine uniform to choose a random pivot i, and then
computes the sum of last - first (the number of key comparisons the
subroutine partition would use), quickCount(first, i-1), and
quickCount(i+1, last). (A technical note: i is actually the rank of
the pivot rather than its index or key. Alternatively, you can
imagine that the keys to be sorted are the integers first, first+1,
..., last.) Notice that each time quickCount(1,n) is invoked, it should
return a different answer, depending on the random numbers returned by
the random number generator. On very unlucky runs, the answer will be
close to n(n-1)/2. On very lucky runs, the answer will be close to n
log n. What we are interested in is the average over many runs.
-
Let TRIALS be a program constant (say, 200).
Write a driver
int quickAverage(int n);
that calls quickCount(1,n) TRIALS times and returns the average of
these TRIALS outputs. If everything went according to plan, this
value should be close to (and slightly below) 2(n+1) ln n, the upper
bound on the expected number of key comparisons we proved in class for
quickSort(E,1,n).
-
Run quickAverage(n) for n=100, 200, 300, ..., 1000 and graph its
outputs against n. On the same graph, plot 2(n+1) ln n (which should
be a little greater than these averages) and also 2(n+1) ln ((2n+3)/5)
(which I believe should be a somewhat better estimate of the averages
if I haven't miscalculated). You may have to increase the value of
TRIALS if things don't look right. For this part you may use any
convenient graphing tool, e.g., Excel. Be sure all three curves are
labeled. Feel free to use more values of n and a greater value of
TRIALS if you are interested; the only thing holding you back is the
amount of computation time for the simulations.
Turn in your program and your graph.
owner-cse417@cs.washington.edu
(Last Update:
)