Slides from the [KT] book are available online.
Course notes from CS261 at Stanford (courtsey Serge Plotkin).
Lecture Number  Date  Topic  Notes 
Readings  
Linear Programming  
1 
Aug. 29 
Shortest Paths and Dynamic Programming  [KT], Chapter 6 Slides 


2 
Aug. 31 
Space efficient Dynamic Programming 

3 
Sep. 5 
Maximum Flow Problem Augmenting paths, Maxflowmincut theorem 
[KT], Chapter 7 Slides 

4 
Sep. 7 
Applications of max flow and min cut  Slides  
5 
Sep. 12 
Linear Programming Modeling problems as linear programs 
[DPV], Chapter 7 
Michel Goemans' Lecture notes Plotkin's lecture notes 

6 
Sep. 14 
Simplex Algorithm 

7 
Sep. 19 
Duality Complementary Slackness 

8 
Sep. 21 

9 
Sep. 26 
The Experts Problem  Notes, Chapter 8 

10 
Sep. 28 
Multiplicative weight method  
11 
Oct. 3 
Approximating multicommodity flows 
Notes, Chapter 9 
Plotkin's lecture notes  
Approximation algorithms 

12 
Oct. 5 
MIDTERM 1 (Lec. 1  8)  
Oct. 10 
FALL BREAK  
13 
Oct. 12 
Submodular maximization and greedy algorithms  Notes, Chapter 3  
14 
Oct. 17 
Random variables and large deviations  
15 
Oct. 19 
Linear program lower bounds: Randomized rounding and VLSI Layout Primaldual method and Vertex cover 
Lecture Notes Plotkin's lecture notes Slides 

Hashing 

16  Oct. 24  Universal Hashing  Miltersen's Notes  
17 
Oct. 26 
Bloom filters  Survey article 
Chapter 5.5.3 in [MU] Countmin Sketch (Lecture notes) 

18 
Oct. 31 
Similarity search Nearest neighbor problem and Kd Trees  Lecture notes 
Chapter 5.2 in this book  
19 
Nov. 2 
The random projection method  Lecture notes  Chapter 4 in [MU] Lecture notes Tutorial with simplest proof of JL Lemma 

20 
Nov. 7 
Locality Sensitive Hashing Estimators for Hamming, Jaccard, Cosine measures 
Lecture notes  Paper1 Paper2 CACM Survey Article 

21 
Nov. 9 
MIDTERM 2 (Lec. 13  21) 



22 
Nov. 14 
Eigenvalues and Eigenvectors 
Lecture notes 
Lecture notes Lecture notes 

23 
Nov. 16 
Principal Components Analysis (PCA) 
Lecture Notes 
Shalizi's chapter Tomasi's notes 

24
 Nov. 21  Graph Laplacian Spectral Partitioning  Lecture Notes  Tutorial Lecture notes  
Nov. 23 
THANKSGIVING  
25  Nov. 28  Random walks: Markov Chains, Graph centrality  Lecture Notes  Chapter 2 in Matt Jackson's book. A simple description of PageRank 

26 
Nov. 30 
MonteCarlo Methods: DNF Counting, Metropolis 

Dec. 5 
MIDTERM 3 (In Class; Lec. 16  26) 