Reading: Chapters 6-9
1. Solve the following recurrence for exact powers of 3.
2. Solve the following recurrence for exact powers of 2.
From the text
3. Page 129 6.1-2
4. Page 132 6.2-6
5. Page 142 6.5-7
6. Page 148 7.1-2
7. Page 153 7.2-2
8. Page 159 7.4-2
(Note that in Section 7.2 it is claimed but not proven that quicksort's
best case occurs when the partitioning procedure produces two regions
of size roughly n/2.)
9. Page 167 8.1-1
10. Page 170 8.2-4
11. Page 178 8.1
12. Page 192 9.3-5
13. Page 193 9.3-8
Solutions
(postscript)
(pdf)
Access to Solutions