Reading: Chapters 6-9
1. (4 pts) Solve the following recurrence for exact powers of 3.
2. (4 pts) Solve the following recurrence for exact powers of 2.
From the text
3. (2 pts) Page 129 6.1-2
4. (2 pts) Page 132 6.2-6
5. (2 pts) Page 142 6.5-7
6. (3 pts) Page 148 7.1-2
7. (2 pts) Page 153 7.2-2
8. (4 pts) 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. (3 pts) Page 167 8.1-1
10. (2 pts) Page 170 8.2-4
11. (8 pts) Page 178 8.1
12. (3 pts) Page 192 9.3-5
13. (4 pts) Page 193 9.3-9
14. (4 pts) Give an algorithm for sorting n keys by comparisons which
has as large an asymptotic lower bound on its time complexity
as you can. Each step in your algorithm should be useful in the sense that
leaving out any consecutive sequence of steps could result in an incorrect
output. (By definition, your algorithm must always terminate with the
correct answer.) Justify the time complexity of your algorithm.
Solutions
(pdf)
Access to Solutions