- Exercises 24.2-3, 24.2-4, 24.2-5, 25.2-5, 25.4-3.
Due: Friday, June 5.
- Exercises 23.1-6, 23.2-7, 25.1-1, 25.2-1, 26.1-2, 26.1-3, 26.1-6.
Due: Wednesday, May 27.
- Exercises 22.3-1, 22.3-3, 22.3-4, 22.4-1, 22.4-2, 22.4-3.
- Problem 22-1. For b, give a loop invariant proof of correctness. For c, indicate how to perform efficiently other operations than Union and Find.
Due: Monday, May 18.
- Exercises 20.2-7, 21.2-3, 21.2-4, 21.2-5, 21.4-1, 22.2-2
- A familiar problem on amortized time complexity(Postscript) or look at the GIF image.
- Exercises 10.3-5, 10.3-9;
- Problem 10-1;
- Mergeable heaps with lazy deletion.
Due: Wednesday, April 22.
- Exercise 8.4-1, Problem 8.1;
- Exercises 9.1-1, 9.1-2, 9.2-4.
- We will call call an array A[1..n] "indirectly sorted" by an array
X[1..n] that holds a permutation of indices 1..n if
.
Using an array of indices X[1..n], modify QuickSort so that entries of the array A[1..n] to be indirectly sorted are accessed but not moved.
Due: Wednesday, April 15.
Exercises 8.1-1, 8.1-3, 8.2-1, 8.2-3, 8.2-4.
Due: Monday, April 6.