CSCI 4470/6470 Algorithms (Fall 2006)

Homework Assignment #2 ( Due Tuesday Sept 12, 2006)

1. Problem 7.2-3 on page 153 (note that this is to show Theta).

2. Show that the average time for Quicksort is O(nlogn) using the proof technique of "good" and "bad" splits introduced in the class.

3. Problem 7.2-5 on page 153.

4. Problem 7.4-5 on page 159.
5. Problem 7.3(b) on page 161.