Event Type  Date  Topic  References  Announcements 

Lecture  Jan 23  Class overview. Reservoir Sampling 
Presentation1 Link1 
MiniEx 1 due on 1/30 
Lecture  Jan 25  Probability Review. Expectation, Variance, Markov Inequality, Chebyshevâ€™s Inequality 
Presentation2 Lecture2 

Lecture  Jan 30  Chernoff Bound 
Presentation3 Lecture2 

Lecture  Feb 1  Sampling  Presentation4 Lecture3 Lecture4 

Lecture  Feb 6  Hashing 
Presentation5 Hashing Lecture5 

Lecture  Feb 8  Bloom filter  Presentation6 Bloom Filter1 Bloom Filter2 

Lecture  Feb 13  Data Streaming Algorithms and Heavy Hitter  Presentation10  
Lecture  Feb 15  Lower bounds for Streaming Algorithms 
slides lowerbounds 
HW1 out, due on Mar 5 
Lecture  Feb 20  CountMin Sketch 
Presentation10 lecture note 

Lecture  Feb 22  Frequency Moment Estimation 
Presentation11 lecture note 

No class  Feb 27  Class cancelled.  
Lecture  Mar 1  Frequency Moment Estimation 
Presentation11 lecture note 

Lecture  Mar 6  Graph Streaming  Presentation12  
Lecture  Mar 8  Introduction to MapReduce  Presentation7  
No class  Mar 13  Spring recess  
No class  Mar 15  Spring Recess  
Lecture  Mar 20  MapReduce Algorithms  mapreducenotes  MiniEx 2 due on Mar 29 
Exam  Mar 22  Midterm Exam: In class between 11:30am12:45pm.  
Lecture  Mar 27  MapReduce Algorithms  
Lecture  Mar 29  Finding similar items  Presentation13  HW2 due on Apr 16 
Lecture  Apr 3  Locality Sensitive Hashing 
Presentation14 lecture note 

Lecture  Apr 5  Locality Sensitive Hashing 
Presentation14 lecture note 

Lecture  Apr 10  Clustering: kmeans, kmeans++, kcenter, kmedian 
Presentation15 lecture note 

Lecture  Apr 12  Correlation Clustering  Presentation16  
No class  Apr 17  Monday class schedule will be followed  
Lecture  Apr 19  Interactive Clustering  Presentation17 lecture notes 
HW3 due on May 1 
Lecture  Apr 24  Learning Algorithms  Presentation18 Ch 12 : section 12.1,12.2 from textbook by Leskovec et.al. Perceptron ref  
Lecture  Apr 26  Learning Algorithms  Presentation19 Ch 12 : section 12.3 from textbook by Leskovec et.al. 

Lecture  May 1  Course Overview  
Exam  May 3  Final Exam: In Room 119, Engineering & CmpSci Ctr II between 1:00pm  3:00pm. 
Some studentwritten mostly unedited class notes from a previous course. If you find any typos/errors, please report to the instructor.