Here are the lecture notes for the course.

- Lecture 1: 08/25/08
- Lecture 2: 08/27/08. And this
- Lecture 3: 09/02/08.
- Lecture 4: 09/04/08.
- Lecture 5: 09/09/08 . And this.
- Lecture 6: 09/11/08.
- Lecture 7: 09/16/08. On page 2, there is a typo in the definition of lateness.
- Lecture 8: 09/18/08.
- Lectures 9 and 10: 09/25/08. And this
- In week 6, we had a review and our first midterm.
- Lecture 11: 10/07/08.
- Lecture 12: 10/09/08. We only complete weighted interval scheduling here. Segmented least squares is for later. There are 2 typos on the last page for segmented least squares-- 0 must be replaced by i - 1 in the final assignment. Also i ranges from 1 to j (and not j-1) in the minimization.
- The algorithm in Lecture 12 for computing the contiguous subsequence with maximum sum is in the last two pages of this.
- In Lecture 13 (10/14/08), we discuss the midterm solutions and exercise 2 of chapter 6.
- In Lecture 14 (10/16/08), we discuss the knapsack problem whose notes can be reached via the previous link.
- In Lecture 15 (10/21/08), we discuss the segmented least squares problem. The notes are part of those for Lecture 12.
- In Lecture 16, we discuss shortest path algorithms for graphs where some edges can have negative costs. This is from Section 6.8 of the book.
- In Lecture 17 (10/28/08), we discuss an algorithm for maintaining frequent elements in a data stream.
- In Lecture 18 (10/30/08), we discuss another algorithm for the same problem. This algorithm gives a stronger guarantee. This lecture is based on the lossy counting algorithm in Manku and Motwani's paper .
- Starting Lecture 19, we discuss topics in Chapter 8. We'll cover material in these four pieces: one , two , three , and four , but not necessarily in the same order.