The syllabus for this course is here.
Proof of correctness techniques: to supplement the text's discussion of loop invariants I have prepared a useful handout. You should read the handout.
Measuring algorithm efficiency: reading is sections 2.2, 3.1, 4.1, and 4.5.
Problems 2-3, 4.1-5 (also prove that your algorithm is correct), and 4.5-1. These problems are due on Friday, September 24.
Chapter 7 - Quicksort
Chapter 8 - Additional Sorting Algorithms
Problems 7.4-2, 7.4-5, 7-4, 8.2-2, 8.3-4, 8-3. These problems are due on Wednesday, September 29.
Chapter 15 - Dynamic Programming
Chapter 16 - Greedy Algorithms
Problems 15.1-3, 15-4, 15-9, 16.1-4, and 16.2-4. These problems are due on Wednesday, October 6.
Chapter 17 - Amortized Analysis
Chapter 19 - Fibonacci Heaps
Problems 17.1-3, 17.3-2, 17-2, 19.2-1, 19-2. These problems are due on Monday, October 11.
Chapter 20 - van Emde Boas trees
Chapter 21 - Data Structures for Disjoint Sets
Problems 20.1-3, 20.3-4, 21.3-2, and 21-1. In addition, do these second chance problems from chapter 15. These problems are due on Monday, October 18.
Chapter 22 - Elementary Graph Algorithms
Chapter 23 - Minimum Spanning Trees
Problems 22.2-3, 22.2-7, 22.3-12, 22.4-3, 22-4, 23.1-3, and 23.2-4. These problems are due on Monday, October 25.
Chapter 24 - Single Source Shortest Path Algorithms. Reading is sections 24.1, 24.3, and 24.5.
Chapter 32 - String Matching Algorithms. Reading is sections 32.1-32.4.
Problems 24.3-2, 24.3-4, 24.3-5, 24.5-7, 24-2, 32.1-2, and 32.3-5. These problems are due on Monday, November 8.
Chapter 27 - Parallel Algorithms.
The second midterm is coming up on Friday, November 5. This exam will cover chapters 19 through 23. For the data structure chapters (19-21) I will expect you to know what each data structure is specialized to do and to have at least a broad understanding of how that data structure works. For the graph chapters (22 and 23), I will expect you to have detailed knowledge of the graph algorithms (breadth-first search, depth-first search, Kruskal's algorithm, and Prim's algorithm).
Section 31.7, the RSA algorithm - here are some self-contained lecture notes. For more detail on the mathematical background, you can also read the rest of chapter 31.
Problems 27.2-5, 27.3-3, 27-5ab, and 31.7-1. These problems are due on Wednesday, November 17.
Chapter 33 - Geometric Algorithms. Reading is sections 33.1 and 33.3.
Chapter 30, the Fast Fourier Transform. Here are lecture notes giving some mathematical background. Here is some C++ code that demonstrates how to use the FFT to solve the problem of multiplying two large integers efficiently.