Class Materials

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

Lectures

1. 01/21/2020: Intro, approximate counting, Morris algorithm. scribe in pdf and tex.
   Morris's algorithm: see these scribes
2. 01/23/2020: Approximate counting, intro to hashing and dictionary problem. scribe in pdf and tex.
3. 01/28/2020: Dictionary via hashing, perfect hashing. scribe in pdf and tex.
   wiki articles: universal hashing and perfect hashing.
4. 01/30/2020: Consistent hashing. Graphs. scribe in pdf and tex.
   this lecture by Tim Roughgarden and Greg Valiant.
5. 02/4/2020: Max-flow problem, Ford-Fulkerson algorithm. 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.
   • lecture 7 and lecture 8 from Karger & Madry's class notes.
   • sections 26.1, 26.2 from CLRS's Introduction to Algorithms.
6. 02/6/2020: Max-flow min-cut theorem. Polynomial-time algorithms for max-flow: max-bottleneck. scribe in pdf and tex.
7. 02/11/2020: More polynomial-time algorithms for max-flow: shortest path, scaling. scribe in pdf and tex.
8. 02/13/2020: Spectral graph algorithms. scribe in pdf and tex.
   • Dan Spielman's class on Spectral graph theory (lecture 1).
9. 02/18/2020: Random walks, largest eigenvalue. scribe in pdf and tex.
   • Dan Spielman's class on Spectral graph theory (lectures 3,4).
10. 02/20/2020: Laplacian, graph visualization. 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).
11. 02/25/2020: Cheeger's inequality, spectral graph partitioning. scribe in pdf and tex.
    • Dan Spielman's class on Spectral graph theory (lecture 6).
12. 02/27/2020: Optimization: Liniar Programming (start). scribe in pdf and tex.
    • sections 2.2-2.4 of the Schrijver's course.
    • lecture 11 from Karger & Madry's class at MIT.
    • Erickson's class notes.
13. 03/3/2020: Liniar Programming. scribe in pdf and tex.
    • sections 2.2-2.4 of the Schrijver's course.
    • lecture 11 from Karger & Madry's class at MIT.
14. 03/5/2020: Simplex algorithm, Duality. scribe in pdf and tex.
    • lecture 12 from Karger & Madry's class at MIT.
    • sections 2.2-2.4 of the Schrijver's course.
15. 03/12/2020: Ellipsoid algorithm (sketch), Gradient descent. 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).
16. 03/26/2020: Gradient descent, continued. scribe in pdf and tex.
17. 03/31/2020: Newton's method. scribe in pdf and tex.
    • Nisheeth Vishnoi mini-course notes (chapter 3).
18. 04/2/2020: Interior point algorithm for LP. scribe in pdf and tex.
    • Nisheeth Vishnoi mini-course notes (chapter 3).
19. 04/7/2020: Multiplicative Weights Update algorithm. scribe in pdf and tex.
    • Nisheeth Vishnoi mini-course notes (chapter 2).
20. 04/9/2020: MWU for LP. Large-scale models. scribe in pdf and tex.
21. 04/14/2020: I/O Model. scribe in pdf and tex.
    • Erik Demaine's lecture notes (L7).
22. 04/16/2020: Cache-oblivious model. scribe in pdf and tex.
    • Erik Demaine's lecture notes (L7).
23. 04/21/2020: Parallel models, MPC model. scribe in pdf and tex.
    • parallel algorithms: lecture 27 from D. Karger and A. Madry's class.
24. 04/23/2020: Nearest Neighbor Search (high-dimensional). scribe in pdf and tex. slides.
25. 04/28/2020: Nearest Neighbor Search 2 (high-dimensional). slides. scribe in pdf and tex.
26. 04/30/2020: Error-correcting codes. lecture notes. scribe in pdf and tex.
    • see this and this lectures from Shachar Lovett's class.

Other resources

• previous iteration of the class (S'17)
• 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/