Randomized Algorithms
- Hashing
- Universal hash functions
- One technical job interview question: How to compare two sets of numbers?
- Schwartz–Zippel lemma
- Bloom filters
- Load balancing — the power of two choices
- Tail bounds — Bernstein, Chernoff, and Hoeffding
- Permutation routing in the hypercube
Streaming Algorithms
- Finding the most frequent elements
- The Misra–Gries algorithm
- Count–Min Sketch
- Counting distinct elements
- HyperLogLog
Online algorithms
- Ski rental problem (deterministic and randomized)
- LRU caching
- Analysis of LRU with resource augmentation
Dynamic Graph Algorithms
Parameterized Algorithms
- Intro to FPT Algorithms
- FPT algorithm for Longest Path
- FPT algorithm for Vertex Cover
Approximation Algorithms
- Approximation algorithm for Vertex Cover
- Linear Programming-based approximation algorithm for Set Cover
Linear Programming
- Overview of Linear Programming
- LP duality
- Karush–Kuhn–Tucker conditions
- Farkas’ Lemma and its physical interpretation
- Proof of Farkas’ Lemma
Applications of linear programming
Other topics we may discuss in class
- Dimensionality reduction
- Bourgain’s Theorem
- Cheeger’s Inequality
- Karger’s algorithm
- Principal component analysis