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

- 01/12/2021:
**Intro, approximate counting, Morris algorithm.**notes. scribe in pdf and tex.-
Morris's algorithm: see
these scribes

- 01/14/2021:
**Approximate counting, intro to hashing and dictionary problem.**notes. scribe in pdf and tex. - 01/19/2021:
**Universal hashing, perfect hashing.**notes. scribe in pdf and tex.-
wiki articles:
universal
hashing
and perfect hashing.

- 01/21/2021:
**Perfect hashing. Streaming: Distinct elements count.**notes. scribe in pdf and tex. - 01/26/2021:
**Heavy hitters.**notes. scribe in pdf and tex.-
lecture
5 from Jelani Nelson's class.

- 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.

- 02/2/2021:
**Dimension reduction (JL lemma).**notes. scribe in pdf and tex. - 02/4/2021:
**Nearest Neighbor Search: via JL.**notes. scribe in pdf and tex.-
see
these slides.

- 02/9/2021:
**Nearest Neighbor Search: Locality Sensitive Hashing.**notes. scribe in pdf and tex.-
see
this survey.

- 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.

- 02/16/2021:
**Max Flow: Ford-Fulkerson, Max-flow min-cut duality.**notes. scribe in pdf and tex. - 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.

- 02/23/2021:
**Spectral graph theory: intro.**notes. scribe in pdf and tex.- Dan Spielman's class on Spectral graph theory (lecture 1).

- 02/25/2021:
**Random walks, largest eigenvalue.**notes. scribe in pdf and tex.- Dan Spielman's class on Spectral graph theory (lectures 3,4).

- 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).

- 03/11/2021:
**Cheeger inequality, spectral partitioning. Optimization.**notes. scribe in pdf and tex.- Dan Spielman's class on Spectral graph theory (lecture 6).

- 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.

- 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.

- 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.

- 03/25/2021:
**Ellipsoid algorithm. Gradient descent.**notes. scribe in pdf and tex. - 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).

- 4/1/2021:
**Strong convexity, Newton's method.**notes. scribe in pdf and tex.- Nisheeth Vishnoi mini-course notes (chapter 3).

- 4/6/2021:
**Interior point method.**notes. scribe in pdf and tex.- Nisheeth Vishnoi mini-course notes (chapter 3).

- 4/8/2021:
**Multiplicative Weights Update.**notes. scribe in pdf and tex.- Nisheeth Vishnoi mini-course notes (chapter 2).

- 4/13/2021:
**LP via MWU. Large-scale models: IO model.**notes.- Erik Demaine's lecture notes (L7).

- 4/15/2021:
**Large-scale models: cache-oblivious model.**notes.- Erik Demaine's lecture notes (L7).

#### Other resources

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