Introduction to Big Data Algorithms
Schedule
| Date | Topic | Material | Further Reading |
|---|---|---|---|
| 03.03. | Preliminary Meeting / Probability Theory | Slides Introduction Slides Probability Theory | |
| 05.03. | Probability Theory | Slides Probability Theory | |
| 10.03. | Probability Theory / Discussion of Homework | Slides Probability Theory | |
| 12.03. | Streaming Model / Reservoir Sampling | Handwritten notes | Lecture notes by Ali Vakilian |
| 17.03. | Reservoir Sampling / Median Estimation | Handwritten notes | Lecture notes by Ali Vakilian Lecture notes by Ali Vakilian |
| 19.03. | Discussion of Homework | Handwritten notes | |
| 24.03. | Morris Counter / Variance Reduction | Handwritten notes | Lecture notes by Ali Vakilian Lecture notes by Amit Chakrabarti |
| 26.03. | No class | ||
| 14.04. | Median Trick / Distinct Elements | Handwritten notes | Lecture notes by Ali Vakilian Lecture notes by Amit Chakrabarti |
| 16.04. | Distinct Elements / Majority Element | Handwritten notes | Lecture notes by Amit Chakrabarti Lecture notes by Ali Vakilian |
| 21.04. | Frequent Elements (Misra Gries) | Handwritten notes | Lecture notes by Ali Vakilian |
| 23.04. | Discussion of Homework | ||
| 28.04. | Count-Min Sketch | Handwritten notes | Lecture notes by Ali Vakilian |
| 30.04. | Discussion of Homework | Handwritten notes | |
| 05.05. | Multiplicative Spanners | Lecture notes | |
| 07.05. | Multiplicative Spanners | Lecture notes | |
| 12.05. | Multiplicative Spanners | Lecture notes | |
| 19.05. | More Spanner Constructions | Handwritten notes | [Dor, Halperin, Zwick 1997] |
| 21.05. | Discussion of Homework | ||
| 28.05. | Karger's Contraction Algorithm | Slides | Lecture Notes by Luca Trevision (Section 13.1.2) |
| 02.06. | Cut Sparsification | Handwritten notes | |
| 09.06. | Cut Sparsification | Handwritten notes | |
| 11.06. | Cut Sparsification | ||
| 16.06. | Discussion of Homework | ||
| 18.06. | Q&A Session | ||
| 23.06. | Exam |