Description
1. [20 points] Problem 4-2 on Page 107
2. [40 points] Problem 7-2 (a) (b) and (c) on Page 186
3. [40 points] Problem 7-4 on Page 188
(Hint: For subproblem (c) you can choose the smaller subarray to apply recursion so that the O(lgn)
worst-case stack depth can be achieved. You don’t have to explain how to “Maintain the O(nlg n)
expected running time of the algorithm.”.
And (d) write two quicksort programs, one for TAIL-RECURSIVE-QUICKSORT (A, p, r) and one for
Optimized_TAIL-RECURSIVE-QUICKSORT (A, p, r) designed in subproblem (c). Assume each function call
increases the stack depth by one. And each exiting of a function decreases the stack depth by one.
Record the stack depth each time it changes. Run the programs on the array of numbers [5 6 8 10 11 13
8 8 3 5 2 11 8] and plot the changing stack depths for each program’s run as a curve. And draw the two
curves in one figure.
And (d) write two quicksort programs, one for RANDOMIZED_QUICKSORT(A, p, r) (see Page 179) and
one for RANDOMIZED_QUICKSORT’(A, p, r). Run the programs on the array of numbers [5 6 8 10 11 13 8
8 3 5 2 11 8] and report number of recursive calls to RANDOMIZED_QUICKSORT() or
RANDOMIZED_QUICKSORT’().
