#

### 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

#