Purdue University Fundamental Algorithms (Fall 2026)
Professor Kent Quanrud · Purdue University · 9 lectures with notes
Students in this class: ask your lecturer for the class code, and these lectures will already be in your library when you sign up.
SAT: A different kind of search problem
Auxiliary variables reduce general Boolean SAT and circuit SAT to 3-SAT without polynomial-size blowup.
Negative-length shortest paths and all-pairs shortest paths
Bounded-edge dynamic programming handles negative cycles, while Floyd–Warshall computes all-pairs shortest paths in O(n³).
Shortest Paths
BFS and Dijkstra solve shortest paths efficiently; expanded-state graphs turn edge-count constraints into ordinary shortest-path problems.
Searching and Sorting Graphs
DFS finishing times and reversed edges combine to find every strongly connected component in linear time.
Edit Distance and Matrix Chain Multiplication
Memoization turns recursive edit distance into O(mn), and interval splits solve matrix-chain ordering in O(k³).
Multiplication and Fast Fourier Transforms
Karatsuba and FFT use algebraic structure to replace quadratic multiplication with near-linear or subcubic divide-and-conquer algorithms.
Selection and closest pair
Groups of five yield a guaranteed linear-time selection algorithm; geometric packing makes planar closest pair solvable in O(n log n).
Induction and recursion
A clear recursive specification turns induction into a practical method for designing and proving algorithms.
Searching and sorting
Merge sort achieves O(n log n), matching the Ω(n log n) lower bound for comparison-based sorting.