Class Materials

Scribers: please use this LaTeX template as your starting point.

Lectures

1. 01/12/2021: Intro, approximate counting, Morris algorithm. notes. scribe in pdf and tex.
   Morris's algorithm: see these scribes
2. 01/14/2021: Approximate counting, intro to hashing and dictionary problem. notes. scribe in pdf and tex.
3. 01/19/2021: Universal hashing, perfect hashing. notes. scribe in pdf and tex.
   wiki articles: universal hashing and perfect hashing.
4. 01/21/2021: Perfect hashing. Streaming: Distinct elements count. notes. scribe in pdf and tex.
   these notes
5. 01/26/2021: Heavy hitters. notes. scribe in pdf and tex.
   lecture 5 from Jelani Nelson's class.
6. 01/28/2021: Frequency moments: Tug of War sketch. notes. scribe in pdf and tex.
   Tug-of-War (AMS sketch): lecture 2 from Jelani Nelson's class.
7. 02/2/2021: Dimension reduction (JL lemma). notes. scribe in pdf and tex.
8. 02/4/2021: Nearest Neighbor Search: via JL. notes. scribe in pdf and tex.
   see these slides.
9. 02/9/2021: Nearest Neighbor Search: Locality Sensitive Hashing. notes. scribe in pdf and tex.
   see this survey.
10. 02/11/2021: Locality Sensitive Hashing. Graphs. notes. scribe in pdf and tex.
    lectures 1,2,5,6,7 from these lecture notes by Williamson. see also his lectures 3,4 for applications of network flows.
11. 02/16/2021: Max Flow: Ford-Fulkerson, Max-flow min-cut duality. notes. scribe in pdf and tex.
12. 02/18/2021: Max Flow: max width, scaling, and shortest paths. notes. scribe in pdf and tex.
    • lecture 7 and lecture 8 from Karger & Madry's class notes.
13. 02/23/2021: Spectral graph theory: intro. notes. scribe in pdf and tex.
    • Dan Spielman's class on Spectral graph theory (lecture 1).
14. 02/25/2021: Random walks, largest eigenvalue. notes. scribe in pdf and tex.
    • Dan Spielman's class on Spectral graph theory (lectures 3,4).
15. 03/09/2021: Laplacian, drawing graph in 2D. notes. scribe in pdf and tex.
    • Dan Spielman's class on Spectral graph theory (lecture 2).
    • Matlab code to play: main code to draw using eigenvectors of an adjacency matrix A dr.m, 2D grid graph, and from Dan Spielman's class d-dimensional cube and airfoil graph (note that it returns the Laplacian).
16. 03/11/2021: Cheeger inequality, spectral partitioning. Optimization. notes. scribe in pdf and tex.
    • Dan Spielman's class on Spectral graph theory (lecture 6).
17. 03/16/2021: Linear Programming. notes. scribe in pdf and tex.
    • sections 2.2-2.4 of the Schrijver's course.
    • lecture 11 from Karger & Madry's class at MIT.
18. 03/18/2021: Linear Programming (cont). notes. scribe in pdf and tex.
    • sections 2.2-2.4 of the Schrijver's course.
    • lecture 11 from Karger & Madry's class at MIT.
19. 03/23/2021: Linear Programming duality. Start Ellipsoid. notes. scribe in pdf and tex.
    • lecture 12 from Karger & Madry's class at MIT.
    • sections 2.2-2.4 of the Schrijver' s course.
20. 03/25/2021: Ellipsoid algorithm. Gradient descent. notes. scribe in pdf and tex.
21. 03/30/2021: Gradient descent: smoothness, convexity notes. scribe in pdf and tex.
    • gradient descent: Nisheeth Vishnoi mini-course notes (chapter 1).
    • a blog post on gradient descent, with momentum. has a nice tool to play with!
    • Nesterov's notes (which also include lower bounds).
22. 4/1/2021: Strong convexity, Newton's method. notes. scribe in pdf and tex.
    • Nisheeth Vishnoi mini-course notes (chapter 3).
23. 4/6/2021: Interior point method. notes. scribe in pdf and tex.
    • Nisheeth Vishnoi mini-course notes (chapter 3).
24. 4/8/2021: Multiplicative Weights Update. notes. scribe in pdf and tex.
    • Nisheeth Vishnoi mini-course notes (chapter 2).
25. 4/13/2021: LP via MWU. Large-scale models: IO model. notes.
    • Erik Demaine's lecture notes (L7).
26. 4/15/2021: Large-scale models: cache-oblivious model. notes.
    • Erik Demaine's lecture notes (L7).

    Other resources

    • See previous iteration of the class (S'20) for a detailed list of topics covered
    • https://courses.csail.mit.edu/6.854/current/
    • http://web.stanford.edu/class/cs168/index.html,
    • Algorithms for Massive Data, Spring'19
    • http://www.cs.cmu.edu/~odonnell/toolkit13/
    • https://ocw.mit.edu/courses/mathematics/18-409-topics-in-theoretical-computer-science-an-algorithmists-toolkit-fall-2009/syllabus/