Lecture notes for Fall 2008: Algorithms, 22C:031:001

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.