Useful References related to various topics. This
will get modified as we go along the course.
Lecture # & Date 
Slides 
Video Recording/Slides 
References/Comments 
1 (Feb 9th) 
Course
Introduction CountMin Sketch 
L1 Topics Covered:  Introduction  Majority Element  Heavy Hitters  CMS Algorithm 
CountMin Sketch Article See also Section 10.1 in My Notes 
2 (Feb 16) 
CountMin
Sketch 
L2 CMS Table, Construction + Proofs Heaps Markov's inequality for discrete random variables 

3 (Feb 18) 
CountMin
Sketch Probability Basics 
L3(CMS) CMSScribbled Slides L3(Probability Basics) 
Probability Basics 
4 (Feb 23) 
Balls and Bins Bloom Filter 
L4Balls and Bins L4Bloom Filters 
See also Section 10.2 in My Notes 
5 (Feb 25) 
Bloom Filters Hashing 
L5Bloom
Filters L5Hashing 
Chapter in CLRS Algorithms Book. 
6 (Mar 2) 
Universal Hashing 
L6Universal
Hashing 
Chapter in CLRS Algorithms Book. 
7 (Mar 4) 
Perfect Hashing FrequencyMoments 
L7Perfect
Hashing L7F_0 Estimation 
Chapter in CLRS Algorithms Book. See Chapter 10 in my notes. 
8 (Mar 9) 
FrequencyMoments  L8F0/F2Estimation 

9 (Mar 16 ) 
Analysis of Frequency Moment F_2 DGIM Algorithm 
F2estimate Counting 1s 
See Chapter 10 in my notes. See Chapter 10 in my notes. 
10 (Mar 23) 
DGIM Algorithm Polynomial Testing 
Counting1s
and Variants Checking Bit Strings 

11 (Mar 25) 
Polynomial Testing 
Multivariate
Polynomials, Determinants, and Perfect Matchings 

12 (Mar 30) 
Finding Perfect Matching Geometric Approximation: Approximate Nearest Neighbor 
Isolation
Lemma + Matching ApproxNearestNeighbor 
Chan, HarPeled and Jones, LocalitySensitive Orderings, SIAM Jl. Computing 49(3):583600, 2020 
13 (Apr 1) 
Geometric Approximation: Approximate Nearest Neighbor 
Quadtrees,
Orderings, ANN 

14 (Apr 13) 
Approximate Nearest Neighbors 
Orderings +
Applications 

14 (Apr 13) 
LocalitySensitive
Hashing 
Documents,
Minhash Signatures 
STOC98
paper of IndykMotwani on "Approximate Nearest Neighbor:
Towards Removing the Curse of Dimensionality. Chapter on LSH in My Notes on Topics in Algorithm Design 
15 (Apr 15) 
Signature Matrix, SCurve, Sensitive Family,
Applications Fingerprint Matching 
Banding
Technique, Metric Spaces and Sensitive Families 
Chapter on LSH in My Notes on Topics in Algorithm Design 
16 (Apr 20) 
ANDOR Sensitive Family Fingerprinting Dimensionality Reductions  Isometric Embeddings  
ANDOR Family + Fingerprinting Isometric Embedding 
Chapter on Dimensionality Reduction in My Notes on Topics in Algorithm Design 
17(Apr 22) 
Dimensionality Reductions  Universality of L_\infty  Distortion  Embeddings Metric Spaces in L_\infty Normed Spaces  JL. Lemma 
 Universality of L_\infty  Distortion  Embeddings Metric Spaces in L_\infty Normed Spaces 

18 (Apr 27) 
 Embeddings Metric Spaces in L_\infty Normed
Spaces  JL. Lemma 
Embeddings Metric Spaces in
L_\infty Normed Spaces Normal Distribution and JL Theorem 
Chapter on Dimensionality Reduction in My Notes on Topics in Algorithm Design 
19 (Apr 29) 
Proof of JL Theorem Introduction to Online Matching and Adwords Problem 
Proof of JL Theorem Introduction to Online Algorithms 
Chapter on Online Algorithms in My Notes on Topics in Algorithm Design 
20 (May 4) 
Online
Bipartite Matching  Analysis via PrimalDual 
Analysis of Greedy Online
Bipartite Matching via PrimalDual Matching LP 
Chapter on Online Algorithms in My Notes on Topics in Algorithm Design 
21 (May 6) 
Online Matching  Fractional Matching  Randomized Matching 
Fractional Matching 
Primal Dual Analysis 
Karp, Vazirani and Vazirani, An optimal
algorithm for online bipartite matching, STOC 1990  Devanur, Jain and Kleinberg, Randomized PrimalDual Analysis of RANKING for Online Bipartite Matching, SODA 2013 Chapter on Online Algorithms in My Notes on Topics in Algorithm Design 
22 (May 11) 
 Balance Algorithm  Adwords Introduction to MWU 
Analysis of Balance
Algorithm Predicting Stock Market Index 
 Mehta, Saberi, Vazirani and Vazirani,
AdWords and generalized online matching, JACM 54(6), 2007  Kalyanasundaram and Pruhs, An optimal deterministic algorithm for bmatching, TCS 233: 319325, 2000 Chapter on Online Algorithms in My Notes on Topics in Algorithm Design 
23 (May 13) 
Proof of Balance Algorithm Multiplicative Weight Update Method  Regret Minimization  Application 
Proof of Balance via
Complementary Slackness Deterministic Methods for MWU 
Chapter on Online Algorithms in My
Notes on Topics in Algorithm Design Arora, Hazan, and Kale, MultiplicativeWeight Update Method: A MetaAlgorithm and Applications, Theory of Computing 6:121164, 2012. 
24 (May 18) 
Multiplicative Weight Update Method 
Randomization 
Randomized MWU
Methods 
Chapter on Online Algorithms in My Notes on Topics in Algorithm Design 
25 (May 20) 
kmeans Clustering Algorithms  Clustering  kMeans&
k++Means Introduction to Recommender System 
David Arthur and Sergei Vassilvitskii,
kMeans++: the advantage of careful seeding, SODA 2007 https://cseweb.ucsd.edu/~dasgupta/291geom/kmeans.pdf mmds.org chapter on Dimensionality Reduction 
26 (May 25) 
Recommender System Applications of SVD 
Completing Proof of
k++Means SVD and its Applications to Recommender System 
See My Notes  Chapter on Matrices for CS for SVD. 
27 (May 27) 
SVDs Course Summary 
SVD+Comments on CUR 

Topics Not Covered 
Maximum Weight Independent
Set (Recoverable Values) FPT  Vertex Cover Page Rank Graph Partitioning using Laplacian MinCost Bipartite Matching Graph Algorithms on Social Networks Randomized Linear Algebra 
Feige and Reichman, Recoverable Values for Independent Sets, Random Structures and Algorithms 46(1): 142159, 2015. 