Graduate Algorithms @ Northwestern

Tentative syllabus for Spring 2024

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

  • Graph orienting

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

  • Max Flow and Min Cut

Other topics we may discuss in class

  • Dimensionality reduction
  • Bourgain’s Theorem
  • Cheeger’s Inequality
  • Karger’s algorithm
  • Principal component analysis