Event Type  Date  Topic  References  Announcements 

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

Lecture  Jan 29  Chernoff Bound 
Presentation3 Lecture2 

Lecture  Jan 31  Sampling/Hashing  Presentation4 Presentation5 (Hashing) Lecture3 Lecture4 Hashing Lecture5 

Lecture  Feb 5  Bloom filter  Presentation6 Bloom Filter1 Bloom Filter2 

Lecture  Feb 7  Data Streaming Algorithms and Heavy Hitter  Presentation7  Homework added, Due Date: Feb 19 
Lecture  Feb 12  CountMin Sketch 
Presentation7 lecture note 

Lecture  Feb 14  Lower bounds for Streaming Algorithms 
slides lowerbounds 

Lecture  Feb 19  No Class, Monday Timetable  Homework Due today  
Midterm 1  Feb 21  Inclass exam  
Lecture  Feb 26  Frequency Moment Estimation 
Presentation9 lecture note 

Lecture  Feb 28  No class  
Lecture  Mar 5  Frequency Moment Estimation  Presentation9  
Lecture  Mar 7  Finding similar items  Presentation10  
No class  Mar 12  Spring recess  
No class  Mar 14  Spring Recess  
Lecture  Mar 19  Locality Sensitive Hashing 
Presentation11 lecture note 

Lecture  Mar 21  Locality Sensitive Hashing 
Presentation11 lecture note 
Homework 2 Posted 
Lecture  Mar 26  Introduction to MapReduce  Presentation7  
Lecture  Mar 28  Graph algorithms on MapReduce  Presentation7  
Lecture  Apr 2  Graph algorithms on MapReduce  mapreducenotes  
Lecture  Apr 4  Demo on how to write MapReduce code  mapreducedemo
RowColumn.py rowcolumntest.txt MST.py testData.txt 
Homework 2 Due 
Lecture  Apr 9  Clustering: kmeans, kmeans++, kcenter, kmedian 
Presentation15 lecture note 
MiniExercise 2 Posted 
Lecture  Apr 11  Correlation Clustering  Presentation16  
Lecture  Apr 16  Exam Overview  
Midterm 2  April 18  Inclass exam  
Lecture  Apr 23  Interactive Clustering  Presentation17 lecture notes 

Lecture  Apr 25  Learning Algorithms  Presentation18 Ch 12 : section 12.1,12.2 from textbook by Leskovec et.al. Perceptron ref 
MiniExercise 2 due on April 28 
Lecture  Apr 30  Learning Algorithms  Presentation19 Ch 12 : section 12.3 from textbook by Leskovec et.al. 