Contents

39 sections

01 P and NP — the two classes
02 Checking is cheaper than building
03 Reducibility — turning one problem into another
04 Hard, harder, hardest — the labels
05 What if the line collapsed
06 Sorting — almost never your problem
07 Traversing a network
08 Routing — the shortest path through a network
09 Routing when paths can have negative costs
10 Distance from everywhere to everywhere
11 Cheapest network that connects everything
12 Flow, capacity, and bottlenecks
13 Matching two sides
14 Matching with no clean sides
15 Either-or constraints
16 Dependency order — when the graph has no cycles
17 Searching for text patterns
18 How different are these two strings
19 Optimization with continuous numbers
20 Optimization with curves instead of lines
21 Is this number prime
22 When the answer is a matrix
23 Boolean satisfiability — the original hard problem
24 Why three variables per rule changes everything
25 Traveling Salesman — the poster problem
26 Knapsack — which items fit in the budget
27 Picking the right subset under constraints
28 Coloring — the two-versus-three cliff
29 The Hamilton trap
30 Find a subset that sums right
31 Bin packing — fit the items into the fewest containers
32 When the variables must be whole numbers
33 Approximation — provably close to optimal
34 The approximation hierarchy — how good can you get
35 When one dimension is small
36 When everything else fails — heuristics
37 Is this in the cheap category — a checklist
38 Eight twins — one cheap, one expensive
39 Six places teams reach for the wrong category