randyttruong/496notes

These are my notes for COMP_SCI 496: Graduate Algorithms at Northwestern University

COMP_SCI 496: Graduate Algorithms Notes

These are my notes for the Graduate Algorithms course offered at Northwestern University Spring 2024. This course is just an introductory course in upper-level algorithm analysis.

Course Prerequisites (imo)

• Discrete Mathematics (of course)
  • Combinatorics
• Probability Theory

Description

This is a repo because it's just more effective for me to type my notes out instead of just writing them down. A lot of the workflow here comes from writing things down in class, scribing them in Typst, then doing more studying in order to better understand the material lol.

Topic List (with Textbooks to Reference)

• ❌ L01: Dictionaries, hash tables, and hash functions
• ❌ L02: Universal hash functions
• ❌ L03: Examples of universal hash functions. Introduction to perfect hash functions
• ❌ L04: Job interview question. Sketching. Solution using hash functions and polynomials.
• ❌ L05: Polynomial identity testing. Schwartz–Zippel lemma.
• ❌ L06: Bloom Filters.
• ❌ L07: Load Balancing. The Power of Two Choices.
• ❌ L08: The Power of Two Choices (part II). Tail Bounds.
• ❌ L09: Introduction to Streaming Algorithms
• ❌ L10: The Misra-Gries Algorithm
• ❌ L11: Count-Min Sketch and the Counting Distinct Elements problem
• ❌ L12: HyperLogLog
• ☑️ L13: Online Algorithms Introduction (3)
• ☑️ L14: Online Algorithms Part 2 (3)
• ☑️ L15: Introducing Approximation Algorithms and FPT Algorithms (Ski Rental + Vertex Cover) (4)
• ☑️ L16: FPT Algorithms Part 2 + Approximation Algorithms Part 1 (Vertex Cover + Set Cover) (4 + 5)
• ☑️ L17: Approximation Algorithms (Weighted Set Cover + Minimum Triangle-Free Edge-Deletion) (5)

Additional funsies

these are some pretty good books for getting up to speed in combinatorics, probability, and probabilistic methods in combinatorics.

1. A Walk Through Combinatorics by Miklos Bona
2. The Probabilistic Method by Joel Spencer and Noga Alon
3. Probability and Computing by Michael Mitzenmacher and Eli Upfal
4. Parameterized Algorithms by Cygan, Fomin, et al.
5. Approximation Algorithms by Vijay Vazirani