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 
Introduction 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 
CMS CMS Table, Construction + Proofs Heaps Markov's inequality for discrete random variables 

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

9 (Mar 16 ) 
Analysis of Frequency Moment F_2 DGIM Algorithm 
F2Estimation Analysis Counting 1s DGIM Algorithm 
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. 