Course organization. Hard problems. Exponential-time, XP, and FPT algorithms. Motivating examples. Subset Sum, TSP, Vertex Cover. Branching algorithms. Bounded search trees.

Branching algorithm for Maximum Independent Set. Kernelization. Simple kernel for Vertex Cover. Feedback Vertex Set. Crown decomposition. Linear kernel for Vertex Cover.

Recap. Iterative compression. Vertex Cover. Feedback Vertex Set.

Measure and conquer. Independent Set. Feedback Vertex Set. Set Cover and Hitting Set.

Set Cover branching wrapup.
Dynamic programming. Permutation problems: TSP, Feedback Arc Set.
Set Cover dynamic programming.

Dynamic programming: Graph coloring.

Counting perfect matchings in bipartite and general graphs.

Ryser formula, inclusion-exclusion.

Pathwidth, treewidth, and algorithmic applications.

Guest lectures by Benjamin Berendsohn.

Inclusion exclusion: graph coloring.

Feedback vertex set (randomized). Color-coding.

Color coding vs. divide and conquer. Local search for satisfiability.

Derandomizing the local search algorithm. Time-space tradeoff.

Time-space tradeoff: TSP, Coloring.

Memorization: Maximum Independent Set. Time-space tradeoff: Subset Sum.
Matrix multiplication-based algorithms.

Two case studies: 1. graph bandwidth, 2. permutation pattern matching.

Lower bounds. ETH, SETH, FPT-reductions, and W-hierarchy.