Class Materials

Lectures

1. 01/18/2022: Intro, approximate counting, Morris algorithm. notes.
   • Morris's algorithm: see these scribes
2. 01/20/2022: Approximate counting, Morris++. notes.
3. 01/25/2022: Dictionary problem, Hashing. notes.
• wiki articles: universal hashing and perfect hashing.
• For 2-universal scheme in particular, see also this blog post (in addition to the above wiki article).
4. 01/27/2022: Perfect hashing. Streaming, distinct elements count. notes.
• Perfect hashing: wiki article; see this ACM SIGACT news article on dynamic dictionary problem (open problem 1).
• Distinct elements count: these notes, or lecture 4/5 from here.
5. 02/1/2022: Distinct elements count, bottom-k algorithm.
• Distinct elements count: lecture 4/5 from here.
6. 02/3/2022: Heavy hitters, CountMin algorithm.
   • Heavy hitters: lecture 5 from Jelani Nelson's class; lecture 5/6 from here.
7. 02/8/2022: 2nd moment: Tug-Of-War sketch.
   • Tug-of-War (AMS sketch): lecture 2 from Jelani Nelson's class; lecture 6 from here.
8. 02/10/2022: Dimension reduction, Johnson-Lindenstrauss lemma.
   • lecture 7 from here.
9. 02/15/2022: Nearest Neighbor Search.
   lectures 9,10 from here.
10. 02/17/2022: Locality-Sensitive Hashing.
    see this survey.
11. 02/22/2022: Graphs: max-flow problem.
    • lecture 7 and lecture 8 from Karger & Madry's class notes.
    • lectures 11, 12 from here.
12. 02/24/2022: Ford-Fulkerson, min-cut problem.
13. 03/1/2022: FF with max-width, scaling, BFS.
14. 03/3/2022: Spectral graph theory.
    • Dan Spielman's class on Spectral graph theory (lecture 1).

Other resources

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