For details of standard term assessment timelines and exam structures, visit our Academics page.
WEEK 1
Greedy Algorithms: Storing Files on Tape; Scheduling Classes; Stable Matchings
WEEK 2
Matroids: A Generic Optimization Problem, Motivating the Definition, Examples of Matroids, Scheduling with Deadlines
WEEK 3
Dynamic Programming: Longest Increasing Subsequence, Edit Distance, Subset Sum, Optimal BSTs
WEEK 4
Maximum Flows: Flows, Cuts, Maxflow-Mincut, Augmenting Paths, Bipartite Matchings, Other Settings
WEEK 5
Applications of Flows: Exam Scheduling, Baseball Elimination, Project Selection
WEEK 6
NP-hardness: P, NP, NP-hardness, NP-completeness, Reductions and SAT, 3SAT, Maximum Independent Set, Graph Coloring, Subset Sum
WEEK 7
Approximation Algorithms: Introduction to Approximation Frameworks, Vertex Cover via Maximal Matchings, Vertex Cover via LP rounding, TSP, Set Cover
WEEK 8
Randomized Algorithms – Monte Carlo v. Las Vegas, Min-Cut Algorithm, MAX SAT via the Probabilistic Methods, 2SAT via Markov Chains, Primality Testing
WEEK 9
Exact Algorithms – Branch and Bound, An Inclusion-Exclusion approach to Hamiltonian Path, Dynamic Programming for TSP, Local Search
WEEK 10
Parameterized Algorithms – Closest String, Iterative Compression for FVS, Randomized Algorithm for k-Path, DP over subsets - Set Cover
WEEK 11
Kernelization – Vertex Cover, Matrix Rigidity, Feedback Arc Set on Tournaments, Max Sat, Edge Clique Cover
WEEK 12
Practical Approaches to Coping with Hardness – SAT Solvers, SAT reductions, LP solvers, LP reductions
