Based on the course taught by Andreas Galanis in Hilary Term 2021.
- Amortized analysis (aggregate/accounting/potential methods)
- Union-find (disjoint-set forests, link-by-height/rank, path compression)
- Binary search trees (red-black trees, splay trees)
- Flow networks (min-cut, max-flow, Ford-Fulkerson, matchings, circulations)
- Linear programming (primal, dual, polyhedra, simplex)
- Approximation (combinatorial, LP-rounding, greedy, randomization)
- Fixed-parameter (FPT, bounded-search-tree, kernelisation, colour-coding)
NP-complete material not used, see Computational Complexity course.
Resources
Course textbook: Thomas Cormen, Charles Leiserson, Ronald Rivest and Clifford Stein, Introduction to Algorithms, MIT Press, 2009 (third edition).
References to notes are of the form [x.y] where x is the lecture number and y is the slide number.