# 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 <NAME>
2. `The Probabilistic Method` by <NAME> and <NAME> 
3. `Probability and Computing` by <NAME> and <NAME> 
4. `Parameterized Algorithms` by Cygan, Fomin, et al. 
5. `Approximation Algorithms` by <NAME> 
