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.

1. 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).
2. 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.
3. 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).
4. 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.