Computer Science 477/677: Design and Analysis of Algorithms

Fall 1998

Homework Assignment, due October 27, 1998

You may discuss this assignment with other students in the class, or other persons. But you must actually write the assignment in your own hand. You must turn in the homework on letter-sized paper, with your name at the top of each page. Use pen or pencil, any color.

Do not write your homework as a computer file and turn in a printout.

1. In the pseudocode on page 154 of your textbook, the left portion of the array is sorted first, then the right portion. In the worst case, the recursion stack for Quicksort has depth Theta(n). Give an example where this worst case happens.

   Modify the pseudocode so that the recursion stack is never deeper than lg(n), and explain why that works. (The running time could still be quadratic even with your modification, though.)

2. Work Exercise 10.3-6 on page 192 of your textbook.

3. Work Exercise 10.3-9 on page 192 of your textbook.