Event Type  Date  Instructor  Topic  References  Announcements 

Lecture  Sep 5  BS  Class overview. Reservoir Sampling 
Presentation1 Link1 
Mini Exercise1 due on Sep 12 
Lecture  Sep 7  BS  Probability Review. Expectation, Variance, Markov Inequality, Chebyshevâ€™s Inequality 
Presentation2 Lecture2 

Lecture  Sep 12  BS  Chernoff Bound 
Presentation3 Lecture2 

Lecture  Sep 14  BS  Sampling  Presentation4 Lecture3 Lecture4 

Lecture  Sep 19  BS  Hashing 
Presentation5 Hashing Lecture5 
Hw1 due on Oct 2 
Lecture  Sep 21  BS  Bloom filter  Presentation6 Bloom Filter1 Bloom Filter2 

No class  Sep 26  Career Fair  
Lecture  Sep 28  DW  MapReduce  Presentation7  
Lecture  Oct 3  DW  MapReduce implementations  Presentation8  Hw2 due on Oct 16 
Lecture  Oct 5  DW  MapReduce Algorithms  mapreducenotes  
No class  Oct 10  Monday Schedule  
Lecture  Oct 12  DW  More advanced, distributed setting  Presentation9  
Exam  Oct 17  Midterm  
Lecture  Oct 19  BS  Data Streaming Algorithms and Heavy Hitter  Presentation10  Mini Exercise2 due Oct 31 
Lecture  Oct 24  BS  CountMin Sketch 
Presentation10 lecture note 

Lecture  Oct 26  BS  Frequency Moment Estimation 
Presentation11 lecture note 

Lecture  Oct 31  BS  Semistreaming and MapReduce revisited  Presentation12  
Lecture  Nov 2  BS  More graph algorithms  
Lecture  Nov 7  BS  Finding similar items  Presentation13  Homework 3 posted, due on Dec 1st 4pm 
Lecture  Nov 9  BS  Locality Sensitive Hashing 
Presentation14 lecture note 

Lecture  Nov 14  BS  Clustering 
Presentation15 lecture note 

Lecture  Nov 16  BS  Correlation Clustering and Interactive Clustering  Presentation16  
No class  Nov 21  Thanksgiving recess  
No class  Nov 23  Thanksgiving recess  
Lecture  Nov 28  DW  Learning Algorithms  
Lecture  Nov 30  DW  Learning Algorithms  MiniExercise 3 posted, due on Dec 7th  
Lecture  Dec 5  DW  Learning Algorithms  
Lecture  Dec 7  BS  Lower bounds  Presentation17 lowerbounds 

No class  Dec 12  No class due to Instructor travel  
Exam  Dec 19  In class final exam between 10:30am  12:30pm 
Some studentwritten mostly unedited class notes from a previous course. If you find any typos/errors, please report to the instructor.