| Event Type | Date | Topic | References | Announcements |
|---|---|---|---|---|
| Lecture | Jan 22 | Class overview. Reservoir Sampling |
Presentation-1 Link-1 |
Mini-Ex 1 due on 1/31 |
| Lecture | Jan 24 | Probability Review. Expectation, Variance, Markov Inequality, Chebyshev’s Inequality |
Presentation-2 Lecture-2 |
|
| Lecture | Jan 29 | Chernoff Bound |
Presentation-3 Lecture-2 |
|
| Lecture | Jan 31 | Sampling/Hashing | Presentation-4 Presentation-5 (Hashing) Lecture-3 Lecture-4 Hashing Lecture-5 |
|
| Lecture | Feb 5 | Bloom filter | Presentation-6 Bloom Filter-1 Bloom Filter-2 |
|
| Lecture | Feb 7 | Data Streaming Algorithms and Heavy Hitter | Presentation-7 | Homework added, Due Date: Feb 19 |
| Lecture | Feb 12 | Count-Min Sketch |
Presentation-7 lecture note |
|
| Lecture | Feb 14 | Lower bounds for Streaming Algorithms |
slides lower-bounds |
|
| Lecture | Feb 19 | No Class, Monday Time-table | Homework Due today | |
| Midterm 1 | Feb 21 | In-class exam | ||
| Lecture | Feb 26 | Frequency Moment Estimation |
Presentation-9 lecture note |
|
| Lecture | Feb 28 | No class | ||
| Lecture | Mar 5 | Frequency Moment Estimation | Presentation-9 | |
| Lecture | Mar 7 | Finding similar items | Presentation-10 | |
| No class | Mar 12 | Spring recess | ||
| No class | Mar 14 | Spring Recess | ||
| Lecture | Mar 19 | Locality Sensitive Hashing |
Presentation-11 lecture note |
|
| Lecture | Mar 21 | Locality Sensitive Hashing |
Presentation-11 lecture note |
Homework 2 Posted |
| Lecture | Mar 26 | Introduction to MapReduce | Presentation-7 | |
| Lecture | Mar 28 | Graph algorithms on MapReduce | Presentation-7 | |
| Lecture | Apr 2 | Graph algorithms on MapReduce | mapreduce-notes | |
| Lecture | Apr 4 | Demo on how to write MapReduce code | mapreduce-demo
RowColumn.py rowcolumntest.txt MST.py testData.txt |
Homework 2 Due |
| Lecture | Apr 9 | Clustering: k-means, k-means++, k-center, k-median |
Presentation-15 lecture note |
MiniExercise 2 Posted |
| Lecture | Apr 11 | Correlation Clustering | Presentation-16 | |
| Lecture | Apr 16 | Exam Overview | ||
| Midterm 2 | April 18 | In-class exam | ||
| Lecture | Apr 23 | Interactive Clustering | Presentation-17 lecture notes |
|
| Lecture | Apr 25 | Learning Algorithms | Presentation-18 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 | Presentation-19 Ch 12 : section 12.3 from textbook by Leskovec et.al. |