Lecture Number  Date  Topic  Notes 
Readings  
Data Compression and Modern Hashing  
1 
Jan. 12  Course organization and logistics Data Compression and Huffman Coding 
Lecture notes 
Chapter 9 in [MU] Guy Blelloch's notes from CMU 

2  Jan. 17  Entropy and Kraft's inequality Move to Front Coding  
3  Jan. 19  Universal Hashing  Miltersen's Notes  
4 
Jan. 24 
Compression via Hashing Bloom filter 
Survey article 
Chapter 5.5.3 in [MU] 

5  Jan. 31  Count Min Sketch  Lecture notes from [RV] 

6 
Feb. 2 
Nearest Neighbors (NN) Problem Similarity measures, Kd Trees  Lecture notes 
Chapter 5.2 in this book  
7 
Feb. 5  Curse of dimensionality Projections onto random coordinates 
Chapter 4 in [MU] Wikipedia article defining CLT 

8 
Feb. 7  Approximate NN: Projections via random vectors 
Lecture notes 
Lecture notes from [RV] 

9 
Feb. 9  Central Limit Theorem Dimensionality reduction for Euclidean Spaces 
Tutorial with simplest proof of JL Lemma 

10 
Feb. 14 
Approximate NN: Locality Sensitive Hashing Estimators for Hamming, Jaccard, Cosine measures 
Lecture notes  Paper1 Paper2 CACM Survey Article 



11 
Feb. 16  Eigenvalues and Eigenvectors 
Lecture notes 

12  Feb. 21  Low Rank Approximations 
Lecture Notes 
Lecture notes from [RV] Shalizi's chapter 

13  Feb. 23 
Principal Components Analysis (PCA) 
Lecture notes from [RV] Tomasi's notes  
14  Feb. 28  Singular Value Decomposition (SVD) 

15  Mar. 2  Applications of Linear Algebra Least Squares via SVD Graph Laplacian 
Lecture Notes 
Tutorial Lecture notes from [RV] 

16  Mar. 7  Spectral Partitioning  
17 
Mar. 9 
Inclass Midterm (till Lecture 14) 

SPRING BREAK  
18 
Mar. 21 
Random walks and Graph centrality  Lecture Notes  Chapter 2 in Matt Jackson's book. A simple description of PageRank 

19  Mar. 23  Other Linear Bases Fourier Transform 
Slides 
Lecture notes from [RV] 

20 
Mar. 28  FFT Algorithm 

Linear Programming and Network Flows 

21 
Mar. 30 
Linear Programming Modeling problems as linear programs 
Chapter 7 in this book 
Michel Goemans' Lecture notes 

22 
Apr. 4 
CLASS CANCELED 

23 
Apr. 6 
Duality: Taking the dual 

24 
Apr .11 
CLASS CANCELED 

25 
Apr. 13 
Zerosum games Simplex Algorithm 

26 
Apr. 18 
Maximum Flow Problem Augmenting paths 
Slides 

27 
Apr. 20 
Maxflowmincut theorem 

28  Apr. 25  Applications of max flow and min cut  Slides 

May 2 
FINAL EXAM: 7  10PM 