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.
Chapters 2, 3, and 4. Reading is all of chapter 2, section 3.1, and sections 4.1-4.3.
Implement a version of binary search and prove that your algorithm is correct. In addition, do these problems from the text: 2.2-2, 2.3-3, 2.3-6, 4.1-1, 4.2-1, 4.3-1, 4.3-3. This homework is due on Friday, January 16.
Chapter 7 - to understand some of this material you may also need to review chapter 5.
Chapters 6 and 8: heaps and heapsort (chapter 6) is review from CMSC 270 and will not be an official part of this course; there will be no homework problems for chapter 6 and you will not be tested on that material.
7.2-3, 7-4, 8.2-4, 8.3-4, and 8-3. This homework is due on Friday, January 23.
We reviewed different examples and aspects of recursion as a warm-up for chapter 15.
Chapter 15 - dynamic programming. Here are some lecture notes that illustrate the basics of the dynamic programming method. Reading is sections 15-1, 15-3, and 15-4.
Write a program to solve problem 15-2. Due date is Wednesday, Feb. 4.
Chapter 16: reading is sections 16.1 through 16.3. The proof in 16.3 is difficult to follow, so I have constructed an alternative proof.
15.1-1, 15.4-4, 15.4-5, 15-6, 16.1-3, 16.2-2, 16.2-5, 16.3-7, 16-2a. These problems are due on Monday, February 9.
Chapter 17 - lecture notes.
I showed my solution to the first programming assignment. We covered Chapter 19, Binomial Heaps.
Chapter 20, Fibonacci Heaps
17.1-3, 17.2-2, 17.3-3, 17-2, 19.1-2, 19.2-3, 19.2-7, 19.2-8, 20.3-1, 20-2b. These problems are due on Monday, February 23.
Chapter 21, Disjoint set data structures. Reading is sections 21.1-21.3.
Chapter 22, Elementary Graph Algorithms. Most of this material is review of CMSC 270 material.
21-1.2, 21.2-5, 22.1-3, 22.2-6, 22.4-3. These problems are due on Monday, March 2.
Chapter 23, Minimum Spanning Trees.
23.1-1, 23.1-2, 23.1-7, 23.2-4, 23.2-8, 24.1-4, 24.3-2, 24.3-4. These problems are due on Wednesday, March 11.
Chapter 24, Single source shortest path algorithms. Reading is sections 24.1-24.3 and 24.5.
Section 31.5, 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.
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.
Chapter 32 - String Searching