Lecture notes for Fall 2008: Algorithms, 22C:031:001
Here are the lecture notes for the course.
- Lecture 1:
- 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
- Lecture 8: 09/18/08.
- Lectures 9 and 10: 09/25/08. And
- 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
- 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
- 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
- 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
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.