Lecture | Topic | Notes | Reading | Files |
Lecture 1 (03/28/16) | Introduction, Contraction Algorithm |
Latex | MR section 1.1 | |
Lecture 2 (03/30/16) | Sampling, Concentration Bounds |
Latex | A list of concentration inequalities | |
Lecture 3 (04/04/15) | Streaming, uniqueness, 2nd moment |
Latex | [AMS] paper Chapter of 1 of Roughgarden's course | |
Lecture 4 (04/06/15) | , Hash Functions, Streaming Cont'd |
Latex | |
Lecture 5 (04/11/15) | Schwartz-Zippel Lemma, Perfect Matchin |
Latex | Harvey's algebraic algorithm | |
Lecture 6 (04/13/15) | Curse of Dimensionality, Dimesion Reduction |
Latex | Chapter 2 of Hopcroft-Kannan Fast Johnson Lindenstrauss Impossibility of Dimension Reduction in l1 | |
Lecture 7 (04/018/15) | Locally sensitive hashing, Nearest Neighbor Search |
Latex | A survey by Bernard Chazelle Indyk-Motwani's Paper
Charikar's Paper | |
Lecture 8 (04/20/15) | Linear Algebra Background: Spectral Thm, SVD, Det, Trace |
Latex | See Trevisan's notes for more detailed proofs. | |
Lecture 9 (04/25/15) | PCA, Low rank approximation, Volume Sampling |
Latex | Sections 3.1-3.4 of Hopcroft-Kannan | Matlab Code, Image |
Lecture 10 (04/27/15) | Low Rank Approximation in Optimization |
Latex | Section 3.6.5 of Hopcroft-Kannan Chapter 5 of Kannan-Vempala | |
Lecture 11 (05/02/15) | Clustering, Spectral Partitioning |
Latex | Conductance vs Other Clustering Measures Spectral partitioning in Planar graphs Spectral Partitioning and Image Segmentation | A tar file of all Matlab codes Image |
Lecture 12 (05/04/15) | Spectral Graph Theory, Cheeger's inequality |
Latex | Section 4.2 of Kannan-Vempala Hard direction of Cheeger's inequality Spectral Clustering | |
Lecture 13 (05/09/15) | Power Method, Random Walks |
Latex | Section 3.5 of Hopcroft-Kannan | A tar file of Matlob codes for grpah drawing |
Lecture 14 (05/11/15) | Random Walks/Linear programming |
Latex | Chapter 1 and 12 of Markov Chain, Mixing TIme
Great intro to linear programming by Matousek and Gartner | |
Lecture 15 (05/16/15) | Linear Modeling, MDPs |
Latex | A fast intro to Linear Programming by Thomas Ferguson
Chapter from algorithms textbook by DasGupta, Papadimitriou and Vazirani | |
Lecture 16 (05/18/15) | Duality |
Latex |
LPs: an algebraic view
Geometry of LPs
LP examples: max-flow, matching, vertex-cover
Duality
| |
Lecture 17 (05/23/15) | Maximum Flow/Minimum cut |
Latex | Applications of duality
Section 2.2 and 2.3 of Motwani-Raghavan book
| |
Lecture 18 (05/25/15) | LP Rounding and Multipliative weight update |
| Chapters 4,5 of book by Williamson-Shmoys Chapters 1,2,3 of book by Lau, Ravi and Singh | |
(05/30/15) | NO CLASS: Memorial day |
Lecture 19 (06/01/15) | Submodular Functions |
| Jan Vondrak's talk on submodular functions | |