Assignments
Useful References related to various topics. This
will get modified as we go along the course.
Week # 
Topics 
Raw Slides 
References/ Comments 
Scribe Notes 
Week 1  Lecture 1 (Sept. 11) Introduction. What is this course about? Course Logistics Random Sampling Lecture 2 (Sept. 16) CountMin Sketch 
Course
Introduction Randomized Sampling CountMin Sketch 
References are in slides. Topics on Algorithm Design (Section 10.1)+ References in the slides 
Lecture 1 (Prepared By Mohamad+Mario) NONE 
Week 2 
Lecture 3
(Sept. 18) Probability Basics Balls and Bins Experiments Lecture 4 (Sept. 23) Hashing Bloom Filters Frequency Moments (Introduction) 
BallsBins Hashing Bloom Filters 
References in Slide (Mitzenmacher+Upfal, Section 5.5) Topics on Algorithm Design (Section 10.2) + References in Slides 
NONE NONE 
Week 3+4 
Lectures 5 + 6 (Sept 25 & 30 ) Estimating Frequency Moments in a Data Stream Lecture 7 (Oct 2) Counting 1s in Sliding Window 
FrequencyMoments SlidingWindow 
Slides + Reference in Slide + Topics in
Algorithm Design (Section 10.3) Slides + Topics in Algorithm Design (Section 10.4) 
NONE NONE 
Week 4+5 
Lecture 8+9 (Oct. 7+9) LocalitySensitive Hashing LSH Families Applications 
LSH 
NONE 

Week 56 
Lecture 10: Fingerprint via LSH + Polynomial Identity Testing and its applications to bipartite matching. Geometric Algorithms  LocalitySensitive Ordering 
Testing GApprox 
Zoltan + Patrick K 

Week 7 
Locality Sensitive Ordering + Dimensionality Reduction  dreduction (Isometric Embeddings  Universality of L_\infty; Distortion: Embedding in L_\infty with distortion D 
Can Du + Dorsa E. Ordering DimensionalityReduction 

Week 8+9 
JL Lemma + Online Algorithms  Classical Examples  Matching  Analysis via PrimalDual LP 
JL Lemma Proof Introduction to Online Algorithms via Online Bipartite Matching 
Alex G Dimensionality ReductionI 

Week 9 
Online Bipartite Matching,
Fractional Matching 
Greedy Algorithm 
Primal Dual Analysis; Fractional Matching  Waterlevel
Algorithm 
Camille + Keerthana Dimensionality Reduction II 

Week 10 
Randomized Algorithm for
Bipartite Matching Balance Algorithm  Adwords 
Randomized
+ Balance 
Yunkai + Shriya 

Week 11 
Regret
Minimization  Multiplicative Weights Algorithm 
Abdelghny  
Week 12 
Linear
Algebra Review Graph Partitioning Applications in Social Networks 
Ehsan + Tyler  
Week 13 
Project Presentations 