Week 14 — Algorithms: Divide-and-Conquer, Graphs, Greedy, DP, and NP-Completeness

Overview

Algorithms is where mathematical structure becomes efficient computation. This week surveys the major design paradigms — divide-and-conquer, graph search, greedy, and dynamic programming — then the theory of intractability: NP-completeness as the boundary of what we can solve efficiently, linear programming as a unifying modeling and duality framework, and the standard ways of coping when a problem is provably hard. The emphasis is on recognizing which paradigm a problem calls for and on reasoning about correctness and running time.

Readings

DPV Ch 2 — Divide-and-conquer. Recurrences and the master theorem, mergesort, the FFT, fast matrix multiplication.
DPV Ch 3 — Graph decompositions. DFS, DAGs, topological sort, strongly connected components.
DPV Ch 4 — Paths in graphs. BFS, Dijkstra, Bellman–Ford, shortest paths in DAGs.
DPV Ch 5 — Greedy algorithms. Minimum spanning trees, Huffman coding, set cover.
DPV Ch 6 — Dynamic programming. Edit distance, knapsack, DAG-structured DP.
DPV Ch 7 — Linear programming. Modeling, duality, reductions to LP.
DPV Ch 8–9 — NP-completeness and coping with it. Reductions, approximation, randomization, local search.

Key Concepts

Divide-and-conquer and recurrences

Break a problem into subproblems, solve recursively, combine. Running time obeys a recurrence solved by the master theorem: \(T(n) = aT(n/b) + O(n^d)\) gives

\[T(n) = \begin{cases} O(n^d) & d > \log_b a,\\ O(n^d \log n) & d = \log_b a,\\ O(n^{\log_b a}) & d < \log_b a.\end{cases}\]

Mergesort (\(O(n\log n)\)), Karatsuba multiplication, Strassen’s matrix multiply, and the FFT (Week 13) are all instances.

Graphs: search and shortest paths

DFS classifies edges, finds topological orders of DAGs, and computes strongly connected components; BFS finds shortest paths in unweighted graphs. For weighted graphs, Dijkstra (\(O((V+E)\log V)\) with a heap) handles nonnegative weights, Bellman–Ford handles negative weights and detects negative cycles, and DAG shortest paths run in linear time via topological order. These primitives underlie routing, planning, and dependency resolution.

Greedy

Make the locally optimal choice and never reconsider; correct only when the problem has the right exchange/matroid structure. Canonical wins: MST (Kruskal/Prim), Huffman coding (the optimal prefix code, tying back to Week 10), and Dijkstra itself.

Dynamic programming

When subproblems overlap, solve each once and reuse. Identify a DAG of subproblems, write a recurrence, evaluate in topological order. Examples: shortest paths, edit distance/sequence alignment, knapsack, chain matrix multiplication. DP is the workhorse for optimal sequence problems.

Linear programming and duality

An LP optimizes a linear objective over linear constraints, solved by simplex or interior-point methods. Every LP has a dual LP, and strong duality (the discrete echo of Week 9) certifies optimality; many combinatorial problems (max-flow/min-cut, matching) reduce to or are illuminated by LP duality.

NP-completeness and coping

A problem is in NP if a solution can be verified in polynomial time; it is NP-complete if every NP problem reduces to it (SAT, via Cook–Levin, is the seed). Showing a problem is NP-complete is a reduction from a known-hard one (3-SAT, independent set, vertex cover, Hamiltonian path, TSP). \(\mathrm{P}\overset{?}{=}\mathrm{NP}\) is open; practically, NP-completeness tells you to stop looking for an exact polynomial algorithm and instead use approximation algorithms (with provable ratios), randomization, local search, or exponential methods with good pruning.

Connections

Forward: Week 15 makes the models of computation and the P/NP classes precise via Turing machines and formal languages.
Across courses: graph search and DP for planning (Courses 1, 2), the FFT shared with DSP (Week 13), and complexity reasoning for performance work (Course 4).