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.
- Discrete Mathematics (of course)
- Combinatorics
- Probability Theory
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.
- ❌ 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)
these are some pretty good books for getting up to speed in combinatorics, probability, and probabilistic methods in combinatorics.
A Walk Through Combinatorics
by Miklos BonaThe Probabilistic Method
by Joel Spencer and Noga AlonProbability and Computing
by Michael Mitzenmacher and Eli UpfalParameterized Algorithms
by Cygan, Fomin, et al.Approximation Algorithms
by Vijay Vazirani