| Lecture | Subject | Material | References |
| 0 | Introduction to the course | slides | - |
| 1 | Basics of algorithm analysis | slides | - |
| 2 | Sublinear time algorithms, estimating the average degree | slides | U Feige. On sums of independent random variables with unbounded variance and estimating the average degree in a graph. |
| 3 | Concentration bounds (Chebyshev and Chernoff) | slides | See Nick Harvey's notes on Chernoff bound. Benjamin Doerr, Probabilistic Tools. |
| 4 | Estimating the average degree, continued | slides | A. Czumaj and C. Sohler, sublinear time algorithms (survey) |
| 5 | Estimating the number of connected components | slides | B. Chazelle, R. Rubinfeld, and L. Trevisan. approximating the minimum spanning tree weight in sublinear time. 2005. |
| 6 | Approximate median, k-median clustering | slides | - |
| 7 | k-median clustering via sampling | slides | Mishra, Oblinger, Pitt. kmedian clustering in sublinear time. |
| 8 | Estimating metric space properties via sampling | slides | P. Indyk. Sublinear time algorithms for metric space problems. |
| - | Happy Nowruz! | - | - |
| 9 | Dimensionality reduction: Johnson-Lindenstrauss lemma | slides | Johnson, Lindenstrauss. extensions of Lipschitz mappings into a Hilbert space, 1984. See also David Witmer's notes for missing details. |
| 10 | Data stream model: frequency moments | slides | Alon, Matias, Szegedy. Space complexity of approximating the frequency moments. |
| 11 | k-wise independence, distinct elements | slides | See Bernhard Haeupler's notes on k-wise independence. Alon, Matias, Szegedy's paper. |
| 12 | Algorithms for heavy hitters | slides | J. Misra and D. Gries. Finding repeated elements. 1982. |
| 13 | CountMin data structure | slides | Cormode and Muthukrishnan. An improved data stream summary: The Count-Min sketch and its applications. |
| 14 | Sketching, Mergeable summaries | slides | - |
| 15 | Sparse recovery, L0 sampling | slides | Cormode and Jowhari. Lp sampling and its applications: a survey. 2019. |
| 16 | Graph sketches, dynamic spanning forest | slides | Ahn, Guha and McGregor. Analyzing graph structure via linear measurements. 2012 |
| 17 | Space lower bounds | slides | - |
| 18 | Parallel computing and big data | slides | See Alex Andoni's notes on algorithms for massive data. Mohsen Ghaffari, massively parallel algorithms. |
| 19 | Massively Parallel Computing, maximal matching | slides | Mohsen Ghaffari, massively parallel algorithms. |
| 20 | Massively Parallel Computing, sorting | slides | See Alex Andoni's notes on algorithms for massive data. |
| 21 | Three practice problems | - | - |
| 22 | Solutions for practice problems | - | - |
| 23 | Subspace embedding and least square regression | slides | D. Woodruff. sketching as a tool for numerical linear algebra |