Advanced Algorithms

Append a million items to a Python list, one at a time, and the loop finishes in a few hundredths of a second. About sixty of those million appends did something entirely different from the rest: they asked the allocator for a bigger block and copied every element already stored. One of them copied more than 800,000 items on its own. The average append still cost a constant.

The append that copies a million items

That is the whole subject of this lesson. A dynamic array has an operation whose worst case is Theta(n) and whose cost, taken over any sequence of operations, is O(1) each. Both statements are true, they are not in tension, and the second one is the one you build systems on. An amortized bound is a guarantee about a sequence: if the amortized cost of an operation is 3, then any sequence of n operations costs at most 3n, no matter which adversary chose the sequence.

The three techniques below all prove the same bound for the same structure. They are not three flavours of the same argument; they differ in what they make easy. Aggregate analysis is the one you can do in your head. The accounting method is the one that survives when different operations have different costs. The potential method is the one that survives when the structure can also shrink, and it is the only one of the three that generalizes cleanly to union-find, splay trees, and Fibonacci heaps, which is why the next lesson leans on it.

Why this matters: the worst-case cost of a single operation is the wrong number to design with when operations come in sequences, and almost all of them do.

The structure, stated precisely

A dynamic array holds an items buffer of some capacity, and a count n of how many slots are used. Append writes into slot n and increments n. When n equals the capacity, append first allocates a new buffer of twice the capacity, copies all n elements into it, frees the old one, and only then writes.

def append(self, x):
    if self.n == self.capacity:          # full: grow first
        new_cap = max(1, 2 * self.capacity)
        new_buf = allocate(new_cap)
        for i in range(self.n):          # the expensive part
            new_buf[i] = self.items[i]
        self.items, self.capacity = new_buf, new_cap
    self.items[self.n] = x
    self.n += 1

Count one unit for writing an element, whether the write is the new item or a copy. Then the cost of the i-th append is 1 normally, and i if it triggers a resize (i - 1 copies plus the write). Here are the first seventeen appends into an array that starts empty with capacity 1:

Total for seventeen appends: 17 ordinary writes plus copies of 1, 2, 4, 8 and 16 elements, which is 17 + 31 = 48. That is 2.8 per append, and the largest single operation cost 17.

Method one: aggregate analysis

Aggregate analysis adds up the whole sequence and divides. Over n appends the resizes happen exactly when the count reaches a power of two, so the copies total

1 + 2 + 4 + ... + 2^k       where 2^k <= n
  = 2^(k+1) - 1
  < 2n

and the ordinary writes total n. So n appends cost less than 3n, and the amortized cost per append is under 3. Notice what has been proved and what has not: the bound is on the total, so it holds for every n, and it is a worst-case statement about the sequence, not a probabilistic one.

Aggregate analysis is exact and cheap here because every operation is an append. Its weakness shows as soon as the sequence mixes operation types with different costs: one number per operation is no longer the right summary, and you would have to sum a sequence you do not control.

Key idea: the geometric series is the whole trick. Doubling makes the copy work a geometric sum whose total is proportional to the last term, which is n.

Method two: the accounting method

Now charge each append 3 units of an imaginary currency and see whether the bank ever runs dry. Of the 3 units, 1 pays for the immediate write. The other 2 are saved as credit stored on that element.

Claim: when a resize happens at capacity c, the c elements to be copied are paid for by stored credit. Why? The last resize left the array with c/2 elements and no credit anywhere, because a resize spends every credit it can find. Between then and now, exactly c/2 new elements arrived, each depositing 2 units, so 2 times c/2 = c units are on deposit. The copy costs c. The bank hits exactly zero and never goes negative.

after resize to capacity 8:   4 elements, credit 0
append 5th:  pay 1, bank 2      append 6th:  pay 1, bank 4
append 7th:  pay 1, bank 6      append 8th:  pay 1, bank 8
append 9th:  full. copy 8 elements, spend 8, bank 0.
             then pay 1 for the write, deposit 2. bank 2.

Since the bank never goes negative, the total charge is an upper bound on the total real cost, so amortized cost is at most 3. Same answer, different argument. The accounting method earns its keep when a structure has several operations: you can charge a fat rate to the cheap frequent one and let the expensive rare one run on credit, which is exactly how a queue built from two stacks is analyzed.

The point: an accounting argument is only as good as its invariant. Yours is a sentence of the form "at every moment, the stored credit is at least X", and you must prove that sentence, not assert it.

Method three: a potential function

The potential method replaces per-element credit with one number attached to the whole structure. Define

Phi(D) = 2n - capacity

on a data structure D holding n items in a buffer of the given capacity. Two conditions make a potential function legal: Phi(D0) = 0 on the initial structure, and Phi(Di) >= 0 always. Here Phi starts at 0 on an empty array of capacity 0, and stays non-negative because the array is never less than half full (that is the invariant doubling maintains). Amortized cost is defined as

a_i = c_i + Phi(D_i) - Phi(D_i-1)

Now compute a_i in the two cases. No resize. The real cost is 1, n goes up by one, capacity is unchanged, so the potential rises by 2:

a_i = 1 + (2(n+1) - cap) - (2n - cap) = 1 + 2 = 3

Resize. The array was full, so n = cap. The real cost is n copies plus 1 write. Afterwards the count is n + 1 and the capacity is 2n:

a_i = (n + 1) + (2(n+1) - 2n) - (2n - n)
    = n + 1 + 2 - n
    = 3

Three in both cases. And because the amortized costs sum to the real costs plus Phi(final) minus Phi(initial), and Phi(final) is non-negative while Phi(initial) is zero, the sum of real costs is at most 3n. The potential absorbed the spike: right before a resize the potential is at its maximum, n, and the resize spends all of it.

That is the picture worth carrying: potential is stored energy. Cheap operations pump it up, the expensive operation converts it back into work, and the accounting is automatic once you find a Phi that is high exactly when trouble is near.

Deletion, and why shrinking at half capacity is a bug

Add a pop that removes the last element, and make the obvious choice: when the array falls to half full, halve the capacity. Now sit at the boundary. With n = 8 and capacity 8, append forces a grow to 16 and a copy of 8. Pop immediately: the array is now 8 of 16, half full, so it shrinks back to 8 and copies 8 again. Repeat. Every operation costs Theta(n), and n operations cost Theta(n squared). The structure has no amortized guarantee at all.

The fix is to leave a gap between the two thresholds: grow when full, shrink only when the array falls below one quarter full, and shrink to half capacity. After either resize the array is exactly half full, so Theta(n) further operations are needed before another resize can trigger. The potential function that proves it is a two-piece function:

Phi(D) = 2n - capacity           if n >= capacity / 2
       = capacity / 2 - n        if n <  capacity / 2

Check the seam: at n = capacity/2 both branches give 0, so Phi is continuous there, and Phi is non-negative on both sides. Just before a grow, n = capacity and Phi = n. Just before a shrink, n = capacity/4 and Phi = capacity/4 - n... which is capacity/4 - capacity/4 = 0 by the first branch? No: at n = capacity/4 the second branch applies and gives capacity/2 - capacity/4 = capacity/4 = n. In both directions the potential just before the expensive operation equals the number of elements to copy, which is precisely what pays for it. Working that check yourself, on paper, is the fastest way to internalize what a potential function is for.

Worth holding on to: the quarter threshold is not a tuning constant. It is the gap that makes the potential recover between expensive operations, and any pair of thresholds with a constant-factor gap works.

What the growth factor costs

Doubling is a choice, not a law. With growth factor f, the capacities that fill up are roughly n, n/f, n/f squared and so on, so the copies total about n times f/(f - 1), and each append costs about 1 + f/(f - 1) element writes:

Every factor strictly greater than 1 gives an O(1) amortized append; the factor only moves the constant and the memory overhead. Real libraries sit at different points on that curve. Java's ArrayList grows by half, computing the new capacity as the old capacity plus the old capacity shifted right by one. CPython's list over-allocates by about an eighth of the new size, which keeps memory tight and accepts more copying. Growth by a fixed amount rather than a factor, say 1000 slots at a time, is the one choice that breaks the guarantee: the copies then total n squared over 2000, which is Theta(n squared).

Common misconceptions

• "Amortized means average, so an unlucky run could still be slow." No. There is no probability anywhere in this lesson. The bound holds for every sequence, including the one an adversary designed after reading your code. Expected running time, as in randomized quicksort, is a different animal and comes two lessons from now.
• "Amortized O(1) means each operation is fast." It does not, and that difference has real consequences. A single append can still stall for milliseconds while it copies a gigabyte, which is why hard real-time systems and low-latency trading paths preallocate rather than rely on an amortized bound.
• "The potential function is derived from the structure." You guess it, then verify the two conditions and compute the amortized costs. A guess that makes every operation come out constant is a good Phi; one that does not is discarded. Nothing in the method tells you where to look.
• "Any potential function works as long as it is non-negative." It also has to start at zero, or you must account for the initial potential separately. Otherwise you can hide arbitrary work in Phi(D0) and prove nonsense.
• "Shrinking at half capacity is symmetric with growing when full, so it must be fine." Symmetry is exactly the problem: it removes the gap, and the structure oscillates across a threshold at Theta(n) per step.

Putting it together

• An amortized bound is a worst-case statement about a sequence: amortized cost 3 means every sequence of n operations costs at most 3n.
• Aggregate analysis sums the sequence and divides; doubling makes the copies a geometric series bounded by 2n, giving under 3 per append.
• The accounting method charges a flat rate, stores the surplus as credit, and requires an invariant proving the bank never goes negative.
• The potential method attaches Phi to the structure, requires Phi(D0) = 0 and Phi >= 0, and defines amortized cost as actual cost plus the change in Phi. For the doubling array, Phi = 2n - capacity gives exactly 3 in both cases.
• Growing when full and shrinking below one quarter keeps a constant-factor gap, so the potential can recover; shrinking at half capacity produces a Theta(n) per operation oscillation.
• The growth factor moves the constant and the memory waste, not the asymptotics; growing by a fixed number of slots destroys the bound entirely.

Carry one sentence out of this lesson: the potential method is the one to reach for when a structure can both grow and shrink, and the next lesson uses it to bound a data structure whose amortized cost is smaller than any constant you would think to guess.

Sources

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Amortized analysis: aggregate analysis, the accounting method, the potential method, and dynamic tables. In Introduction to algorithms (4th ed., ch. 16). MIT Press.
2. Tarjan, R. E. (1985). Amortized computational complexity. SIAM Journal on Algebraic and Discrete Methods, 6(2), 306-318.
3. Erickson, J. (2019). Algorithms: amortized analysis and the accounting scheme. University of Illinois. jeffe.cs.illinois.edu
4. Morin, P. (2013). Array-based lists and the cost of resizing. In Open data structures. opendatastructures.org
5. Wikipedia contributors. (n.d.). Amortized analysis and Potential method. en.wikipedia.org
6. Demaine, E., & Devadas, S. (2015). 6.046J Design and analysis of algorithms: amortization. MIT OpenCourseWare. ocw.mit.edu

In 1964 Bernard Galler and Michael Fischer published two pages in Communications of the ACM about a compiler chore. FORTRAN let a programmer declare that two variable names referred to the same storage, and the compiler had to work out, from a pile of such declarations, which names ended up sharing a cell. Their answer was a forest of pointers with two small tricks bolted on. Eleven years later Robert Tarjan proved that those two tricks give a running time that is not linear, but is so close to linear that the gap is invisible on any input that will ever exist.

The question the structure answers

Maintain a partition of n elements into disjoint sets, under two operations:

• find(x) returns a canonical name for the set containing x, so that find(x) == find(y) exactly when x and y are in the same set.
• union(x, y) merges the two sets containing x and y.

There is no delete and no split. That restriction is what makes near-linear time possible, and it is the first thing to check before reaching for this structure: union-find handles a partition that only ever gets coarser.

Two naive designs frame the problem. Quick-find stores a set label in an array: find is one array read, but union has to relabel every member of one set, so a sequence of n - 1 unions costs Theta(n squared). Quick-union stores a parent pointer per element and lets each set be a tree: union is one pointer write, but find walks to the root, and an adversary can build a path of length n, so find is Theta(n). Neither is acceptable, and each fails in the operation the other made cheap.

The forest, with two rules

Keep the tree representation and add two rules.

Union by rank. Store an integer rank per root, initially 0. On a union, attach the root of smaller rank under the root of larger rank; on a tie, pick either and increment the winner's rank. (Union by size, attaching the smaller tree under the larger, gives the same asymptotics and is easier to reason about; both are used in practice.)

Path compression. During a find, after locating the root, walk the path again and point every node on it directly at the root. The work is proportional to the walk you already did, so it never more than doubles the cost of a find, and it flattens the tree for everyone who comes later.

def find(self, x):
    root = x
    while self.parent[root] != root:
        root = self.parent[root]
    while self.parent[x] != root:            # second pass: compress
        self.parent[x], x = root, self.parent[x]
    return root

def union(self, a, b):
    ra, rb = self.find(a), self.find(b)
    if ra == rb: return False                # already together
    if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra
    self.parent[rb] = ra                     # smaller rank under larger
    if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
    return True

Trace eight elements through five unions, writing the forest as parent arrays:

start        parent = [0,1,2,3,4,5,6,7]   rank = [0,0,0,0,0,0,0,0]
union(0,1)   1 under 0, rank[0]=1         parent[1]=0
union(2,3)   3 under 2, rank[2]=1         parent[3]=2
union(0,2)   equal ranks, 2 under 0, rank[0]=2
             forest: 0 -> {1, 2}, 2 -> {3}
union(4,5)   5 under 4, rank[4]=1
union(0,4)   rank 2 beats rank 1, so 4 under 0
find(3)      walk 3 -> 2 -> 0, then set parent[3]=0 directly
find(5)      walk 5 -> 4 -> 0, then set parent[5]=0 directly

After those two finds the tree is one root with six children hanging off it. The next find on any of them costs a single pointer read.

Remember: union by rank keeps the tree from getting tall; path compression pays for the tallness that does occur, once, and shares the benefit with every later query.

Proof: union by rank alone gives height at most log base 2 of n

This one is short enough to do in full, and it is the proof that makes the rest believable.

Claim. With union by rank and no path compression, a root of rank k is the root of a tree containing at least 2 to the power k nodes.

Proof by induction on the number of unions. Initially every node is a root of rank 0 with 1 = 2 to the power 0 nodes. A union attaches root b under root a. If rank(b) is strictly less than rank(a), then rank(a) does not change and a's tree only grew, so the claim survives. If rank(a) equals rank(b) equals k, the new rank of a is k + 1, and the new tree has at least 2 to the power k plus 2 to the power k nodes, which is 2 to the power (k + 1). The claim survives. No other case occurs.

Consequence. A rank-k root has at least 2 to the power k nodes, and there are only n nodes, so every rank is at most log base 2 of n. Since a node's rank is strictly greater than the rank of any child, tree height is bounded by the root's rank. Therefore find costs O(log n) worst case, and any sequence of m operations costs O(m log n). No amortization needed yet.

Path compression on its own, with arbitrary unions, also gives O(log n) amortized per operation. The interesting part is what happens when you use both.

The rank-block argument, and the iterated logarithm

Here is the classical Hopcroft and Ullman analysis, which proves an O(log-star n) amortized bound. It is not the tightest result, but unlike the tight one it fits on a page, and the shape of the argument is the same.

Define log-star n as the number of times you must apply log base 2 to n before the result drops to 1 or below. It grows unbelievably slowly:

Now, two facts about ranks that path compression cannot disturb. First, a node's rank never changes once it stops being a root, and ranks strictly increase as you walk up any path. Second, the number of nodes of rank k is at most n divided by 2 to the power k, which follows from the counting proof above: each rank-k node was once a root owning 2 to the power k nodes, and those ownership sets are disjoint.

Partition the ranks into blocks whose boundaries form a tower of powers of two: {0, 1}, {2}, {3, 4}, {5, ..., 16}, {17, ..., 65536}, and so on, where each block ends at 2 raised to the previous block's endpoint. Because ranks only go up to log base 2 of n, the number of blocks is O(log-star n).

Now charge the pointer steps of a find. Walking up from x to the root, classify each step by whether the node and its parent lie in the same rank block:

• Block-crossing steps are charged to the find itself. Ranks increase along the path, and there are O(log-star n) blocks, so a single find pays at most O(log-star n) of these.
• Within-block steps are charged to the node. Here is the payoff of path compression: after the step, the node is re-pointed at the root, whose rank is strictly greater than its old parent's. So the next time this node is charged, its parent's rank is strictly larger. A node in a block of size B can therefore be charged at most B times before its parent's rank escapes the block, after which every future step from it is a block-crossing step.

Summing the second bucket over all nodes gives, for each block ending at rank r, at most (block size) times (number of nodes with rank in that block), and the rank counting fact makes that sum O(n) per block. With O(log-star n) blocks, the total is O(n log-star n). Adding the first bucket over m finds gives O(m log-star n). Divide and the amortized cost per operation is O(log-star n).

The upshot: path compression is what makes the within-block charge finite. Without it a node could be charged forever at the same parent rank, and the argument collapses.

What Tarjan proved, and what cannot be improved

Tarjan sharpened the bound in 1975 to O(m alpha(m, n)) for m operations on n elements, where alpha is an inverse of the Ackermann function. Ackermann's function grows so violently that its inverse is at most 4 for every n that could be written down with atoms available in the observable universe, which is why implementations treat find and union as constant time in practice and why the honest statement is "not constant, but never more than four".

Two follow-ups matter for how you read that result. Tarjan and van Leeuwen showed in 1984 that the same bound holds for the cheaper path-compression variants, path splitting and path halving, and for union by size as well as by rank, so you are free to pick whichever is convenient. And Fredman and Saks proved in 1989 that Omega(alpha) amortized time is a lower bound in the cell-probe model: no cleverer disjoint-set structure will reach linear time. The alpha is not an artifact of the analysis. It is the truth about the problem.

Where you actually meet it

Kruskal's minimum spanning tree algorithm is the standard consumer: sort the edges, then for each edge ask whether its endpoints are already connected, which is exactly a pair of finds, and union when they are not. With m edges the union-find work is O(m alpha(n)), so the sort dominates at O(m log m) and the data structure vanishes into the noise. That is the argument you will make again in Module 4.

Other places the same shape appears: connected components in a graph that only gains edges; percolation and cluster labelling on grids, where the classic Hoshen-Kopelman scheme is union-find in disguise; the union of intervals in a scheduler; and cycle detection while building any spanning structure incrementally. What all of them share is that the partition only ever coarsens. The moment you need to remove an edge, union-find is the wrong structure, and you are in the much harder territory of dynamic connectivity.

Common misconceptions

• "Path compression makes find O(1)." An individual find on a freshly built tall tree still costs Theta(log n). The bound is amortized, and the first find that compresses a long path pays full price for it.
• "alpha(n) is a constant, so the algorithm is linear." alpha grows, just absurdly slowly, and Fredman and Saks proved the growth is real. Saying "effectively constant" is fair engineering; saying "linear" is false.
• "Ranks are tree heights." They are heights only if you never compress. With path compression a rank is an upper bound on the height, and it is deliberately never decreased, because recomputing it would cost more than it saves.
• "You need both tricks or the structure is bad." Either one alone already gives O(log n); the pair is what buys alpha. If you can only afford one, path compression is the easier win, because it needs no extra array.
• "Union-find can undo a merge if I keep a stack." You can, but only if you drop path compression, since compression destroys the information about which pointer used to point where. Rollback union-find is a real structure, and it costs the compression and a log factor.

What to carry forward

• Union-find maintains a partition under merge and query only; there is no split, and that restriction is what buys the running time.
• Quick-find makes union quadratic; quick-union makes find linear; the forest with union by rank and path compression fixes both.
• Union by rank alone bounds every rank, and therefore every tree height, by log base 2 of n, proved by showing a rank-k root owns at least 2 to the power k nodes.
• The rank-block argument charges each find O(log-star n) block crossings and each node a bounded number of within-block steps, giving O(log-star n) amortized.
• Tarjan's tight bound is O(m alpha(m, n)), and Fredman and Saks showed no structure can do better, so union-find is provably not linear.
• The canonical application is Kruskal's algorithm, where the union-find work disappears beneath the cost of sorting the edges.

The through-line from the previous lesson is worth naming: both structures earn their bounds by making the expensive operation rare and by proving, not assuming, that the cheap operations paid for it in advance.

Sources

1. Tarjan, R. E. (1975). Efficiency of a good but not linear set union algorithm. Journal of the ACM, 22(2), 215-225.
2. Hopcroft, J. E., & Ullman, J. D. (1973). Set merging algorithms. SIAM Journal on Computing, 2(4), 294-303.
3. Tarjan, R. E., & van Leeuwen, J. (1984). Worst-case analysis of set union algorithms. Journal of the ACM, 31(2), 245-281.
4. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Data structures for disjoint sets. In Introduction to algorithms (4th ed.). MIT Press.
5. Sedgewick, R., & Wayne, K. (2011). Union-find: quick-find, quick-union, weighting, and path compression. Algorithms, 4th edition booksite, Princeton University. algs4.cs.princeton.edu
6. Wikipedia contributors. (n.d.). Disjoint-set data structure. en.wikipedia.org
7. Wikipedia contributors. (n.d.). Ackermann function, including the inverse and its growth. en.wikipedia.org

In 1980 Jon Bentley, Dorothea Haken and James Saxe published a short note in SIGACT News offering a general method for solving divide-and-conquer recurrences. It became the master theorem, and it is the reason a first algorithms course can dispose of merge sort in one line. It is also, used carelessly, the source of more wrong running times than any other tool in the subject, because its hypotheses are easy to skip and it fails silently when they do not hold.

A recurrence that returns nothing

Start with a case that breaks. Consider

T(n) = 2 T(n/2) + n / log n

It looks like merge sort with a slightly cheaper merge, so the instinct is to answer Theta(n log n) or perhaps Theta(n). Both are wrong, and the master theorem will not tell you so. Work out why, and you will understand the theorem better than a correct application would have taught you.

The theorem, stated with its fine print

For T(n) = a T(n/b) + f(n) with a >= 1 and b > 1, compare f(n) against the watershed function n to the power log base b of a, which is the total work done in the leaves of the recursion tree:

Three details in that table are where the mistakes live.

First, cases 1 and 3 demand a polynomial gap: f must be smaller or larger than the watershed by a factor of n to some positive power, not merely by a logarithm. Second, case 3 carries a regularity condition, a f(n/b) <= c f(n), which says the work does not grow when you push it down a level; without it, case 3 can be false. Third, there is a gap between the cases, and a recurrence can land in it.

Now return to T(n) = 2T(n/2) + n/log n. The watershed is n to the power log base 2 of 2, which is n. Is n/log n = O(n to the power 1 - epsilon)? No: n/log n beats any n to the power 1 - epsilon for large n, because logarithms lose to polynomials. Is it Theta(n)? No, it is asymptotically smaller. Is it Omega(n to the power 1 + epsilon)? Certainly not. All three cases fail. The recurrence lies in the gap between case 1 and case 2.

A recursion tree settles it. At depth i there are 2 to the i subproblems of size n / 2 to the i, each costing (n / 2 to the i) divided by log(n / 2 to the i), so the level costs n / (log n - i). Summing over i from 0 to log n - 1 gives n times the harmonic sum 1/(log n) + 1/(log n - 1) + ... + 1/1, which is n times the harmonic number of log n, and that is Theta(n log log n). Neither of the two guesses was close.

What matters here: the master theorem is a lookup table with hypotheses, not a solver. When a recurrence fails all three cases, draw the tree and sum the levels.

The extended case 2, and what it buys

Modern statements of the theorem widen case 2: if f(n) = Theta(n to the power log_b a, times (log n) to the power k) for some k >= 0, then T(n) = Theta(n to the power log_b a, times (log n) to the power (k + 1)). That single change absorbs a family of recurrences that the original three cases had to refuse. For instance

T(n) = 2 T(n/2) + n log n      watershed n, k = 1
                               T(n) = Theta(n log squared n)

Check it against your intuition: the tree has log n levels, and the levels near the root cost about n log n each, so the total should be a bit less than n log squared n. It is exactly that order. The extension does not rescue the n/log n case, because there k would have to be minus 1, and the extended statement requires k at least 0.

When the pieces are not the same size: Akra-Bazzi

The master theorem assumes every subproblem has the same size n/b. Plenty of real recurrences do not:

T(n) = T(n/3) + T(2n/3) + n

This is what an unbalanced partition produces, and it is also exactly the recurrence a median-of-three quicksort faces in its bad-but-not-worst case. The Akra-Bazzi method handles it. Given T(x) = sum over i of a_i T(b_i x) + g(x), find the unique p solving

sum over i of a_i (b_i to the power p) = 1

and then T(x) = Theta(x to the power p times (1 + the integral from 1 to x of g(u) / u to the power (p+1), du)). For our recurrence, (1/3) to the p plus (2/3) to the p = 1 is solved by p = 1, since 1/3 + 2/3 = 1. The integral becomes the integral of u / u squared, which is the integral of 1/u, which is log x. So T(n) = Theta(n log n).

That answer is worth pausing on. A 1-to-2 split is badly unbalanced, and it still gives n log n, because the tree's depth only changes by a constant factor: the longest root-to-leaf path shrinks n by a factor of 3/2 each step instead of 2, which is log base 1.5 of n levels rather than log base 2 of n. Constant factor in the depth, same asymptotics. Unbalanced splits are survivable; splits that peel off a constant number of elements are not.

In short: if the split ratio is a constant fraction, you keep n log n. If the split leaves n - 1 on one side, you get n squared. The dividing line is whether the subproblem shrinks by a factor or by an amount.

Median of medians, proved linear

Here is the payoff recurrence of the whole lesson. Selection asks for the k-th smallest of n unsorted values. Quickselect does it in expected linear time, and we will analyze that expectation in the next module. Blum, Floyd, Pratt, Rivest and Tarjan showed in 1973 how to do it in worst-case linear time, and the algorithm is a recurrence with two recursive calls of different sizes.

SELECT(A, k):
  1. split A into ceil(n/5) groups of 5 elements
  2. sort each group and take its median          -> n/5 medians
  3. p = SELECT(medians, half of them)            -> the median of medians
  4. partition A around p
  5. recurse into the side containing the k-th element

Why is the pivot good? Half of the n/5 group medians are at least p, and each of those groups contributes at least 3 elements at least as large as p, namely its median and the two above it. So at least 3 times n/10 elements are at least as large as p, which means step 5 recurses on at most 7n/10 elements. Symmetrically for the other side. The recurrence is

T(n) <= T(n/5) + T(7n/10) + a n

Prove T(n) <= c n by substitution. Assume it for all smaller inputs:

T(n) <= c(n/5) + c(7n/10) + a n
      = (2cn/10) + (7cn/10) + a n
      = (9/10) c n + a n

This is at most c n exactly when a n <= c n / 10, that is, when c >= 10a. Pick that c and the induction closes. Selection is Theta(n) in the worst case. Notice what carried the proof: 1/5 plus 7/10 equals 9/10, strictly less than 1. The recursion tree's levels shrink geometrically, so the linear work at the root dominates the whole tree.

Now change one number. Use groups of three instead of five. Each of half the n/3 groups contributes 2 elements on the correct side, so 2 times n/6 = n/3 elements are eliminated and the recursion is on up to 2n/3, giving

T(n) <= T(n/3) + T(2n/3) + a n

and the fractions now sum to exactly 1. That is the Akra-Bazzi recurrence from the previous section, and its answer is Theta(n log n), not Theta(n). One line of the algorithm changed and the running time gained a logarithm. That is the sharpest available demonstration that the constants inside a divide-and-conquer recurrence are not decoration.

Two classics the theorem does handle

Strassen's matrix multiplication. Multiplying two n by n matrices by blocks takes 8 multiplications of n/2 by n/2 blocks plus O(n squared) additions, giving T(n) = 8T(n/2) + O(n squared), watershed n to the power log base 2 of 8 = n cubed. Case 1: Theta(n cubed), no gain. In 1969 Volker Strassen found an identity computing the four output blocks from seven products instead of eight, at the cost of more additions. The recurrence becomes T(n) = 7T(n/2) + O(n squared), watershed n to the power log base 2 of 7, which is about n to the power 2.807. Case 1 again, so T(n) = Theta(n to the power 2.807). The exponent has since been pushed below 2.38 by a line of work descending from Coppersmith and Winograd, none of which is used in practice because the hidden constants are enormous. Strassen's own method does get used, on large dense matrices, with a cutoff to the ordinary algorithm at small sizes.

Closest pair of points. Sort by x, split at the median x, solve both halves, and let d be the smaller of the two returned distances. Any closer pair must straddle the line, and both its points lie in the strip of width 2d around it. Sort the strip's points by y, and the geometric fact that makes the algorithm work is this: a point in the strip need only be compared against the next few points in y order, because more than a constant number of points within distance d of each other cannot fit in a 2d by d rectangle without violating d. That gives O(n) work to merge, so T(n) = 2T(n/2) + O(n) = Theta(n log n) by case 2, provided you presort by y once rather than re-sorting inside the recursion.

The parenthetical matters. Re-sorting the strip at every level would make the merge O(n log n) and the recurrence T(n) = 2T(n/2) + O(n log n), which the extended case 2 solves as Theta(n log squared n). The algorithm is still correct; it is just a logarithm worse, and the fix is a presort.

Common misconceptions

• "If the master theorem gives no answer, the recurrence has no closed form." The theorem is a table of three patterns. Recursion trees, substitution with a strengthened hypothesis, Akra-Bazzi, and generating functions all still work.
• "Case 3 only needs f to be bigger than the watershed." It also needs the regularity condition a f(n/b) <= c f(n) with c < 1. Contrived f that oscillate satisfy the size condition and fail regularity, and for them the conclusion is false.
• "An unbalanced split ruins divide and conquer." A constant-fraction split of any ratio keeps n log n; only splits that remove a constant number of elements degrade to n squared.
• "Median of medians is the fast way to select." It is the way with a worst-case guarantee. Its constant is large enough that randomized quickselect wins in practice, and the standard engineering answer, introselect, runs quickselect and falls back to median of medians only when the recursion gets too deep.
• "Groups of five is arbitrary, and any small odd number works." Three does not work, for the reason proved above. Seven works. Five is the smallest group size that makes the fractions sum to less than one, which is why it is the one in the paper.

The short version

• The master theorem compares f(n) to the watershed n to the power log base b of a, needs a polynomial gap in cases 1 and 3, and needs the regularity condition in case 3.
• T(n) = 2T(n/2) + n/log n falls in the gap between cases 1 and 2 and solves, by summing the recursion tree, to Theta(n log log n).
• The extended case 2 covers f = Theta(watershed times log to the k n) and returns one more logarithm; it does not cover negative powers of log.
• Akra-Bazzi handles unequal subproblem sizes by solving sum of a_i b_i to the p = 1, then integrating; for T(n/3) + T(2n/3) + n it gives p = 1 and Theta(n log n).
• Median-of-medians selection satisfies T(n) <= T(n/5) + T(7n/10) + an, and the substitution closes because 1/5 + 7/10 < 1, giving worst-case linear time. Groups of three make the fractions sum to 1 and cost a logarithm.
• Strassen turns 8 multiplications into 7 and the exponent from 3 to about 2.807; closest pair needs the presort to keep its merge linear.

Every remaining lesson in this course leans on a recurrence at some point. The habit to leave with is checking the hypotheses before quoting the theorem, and drawing the tree when they fail.

Sources

1. Bentley, J. L., Haken, D., & Saxe, J. B. (1980). A general method for solving divide-and-conquer recurrences. SIGACT News, 12(3), 36-44.
2. Blum, M., Floyd, R. W., Pratt, V., Rivest, R. L., & Tarjan, R. E. (1973). Time bounds for selection. Journal of Computer and System Sciences, 7(4), 448-461.
3. Strassen, V. (1969). Gaussian elimination is not optimal. Numerische Mathematik, 13(4), 354-356.
4. Akra, M., & Bazzi, L. (1998). On the solution of linear recurrence equations. Computational Optimization and Applications, 10(2), 195-210.
5. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Divide-and-conquer and the master method. In Introduction to algorithms (4th ed.). MIT Press.
6. Erickson, J. (2019). Algorithms, chapter 1: recursion, recurrences, and the recursion tree method. University of Illinois. jeffe.cs.illinois.edu
7. Wikipedia contributors. (n.d.). Master theorem (analysis of algorithms). en.wikipedia.org
8. Wikipedia contributors. (n.d.). Median of medians. en.wikipedia.org

Tony Hoare invented quicksort in 1959, as a visiting student in Moscow, while trying to sort Russian words for a machine translation project. The version in your standard library differs from his in one line: it does not take the first element as the pivot, it takes a random one. That single line changes what can be proved about the algorithm, from a statement about inputs into a statement about the algorithm's own coin flips, and it is the cleanest example in the subject of what randomization buys.

What the coin is actually for

Deterministic quicksort with a fixed pivot rule has a worst case, and worse, the worst case is a specific input that an adversary can hand you. Sorted data with a first-element pivot is the classic, and it is not exotic: sorted is the single most common shape data arrives in. In 2003 a class of denial-of-service attacks was demonstrated against exactly this pattern in hash tables, and the same logic applies to sorting.

Randomizing the pivot does not remove the quadratic case. It makes the quadratic case depend on your coin flips instead of on the input, so no adversary who knows your code can provoke it. That distinction is the whole point:

deterministic:  for every algorithm, there EXISTS a bad input
randomized:     for every input, MOST coin sequences are good

So what?: a randomized bound is a promise you can keep against an adversary who has read your source code, as long as the adversary cannot read your random numbers.

Las Vegas and Monte Carlo

Two species, and mixing them up leads to claiming the wrong guarantee.

A Las Vegas algorithm can be turned into a Monte Carlo one by cutting it off at a deadline and answering arbitrarily. Going the other way requires a way to check an answer, which is often the hard part. Karger's algorithm, in the next lesson, is Monte Carlo precisely because verifying that a cut is minimum is not obviously easier than finding it.

Counting comparisons with indicator variables

Here is the analysis worth knowing by heart, because the technique transfers everywhere.

Name the sorted order of the input z_1 < z_2 < ... < z_n. Quicksort's total work is dominated by comparisons, so count them. Define, for each pair i < j, the indicator

X_ij = 1 if z_i and z_j are ever compared, else 0

Two facts make this tractable. First, any two elements are compared at most once, because a comparison happens only against a pivot, and the pivot is removed from all later subproblems. Second, the total comparison count is the sum of all X_ij, so by linearity of expectation

E[total] = sum over i < j of Pr[z_i and z_j are compared]

Now the key question: when are z_i and z_j compared? Consider the set S = {z_i, z_i+1, ..., z_j}, all the elements whose values lie between them inclusive, of size j - i + 1. As long as no element of S has been chosen as a pivot, all of S sits in the same subproblem, because a pivot outside S sends the whole of S to the same side. The first pivot chosen from S decides everything:

• If it is z_i or z_j, those two are compared, since one is the pivot and the other is in its subproblem.
• If it is any of the j - i - 1 elements strictly between them, then z_i goes left, z_j goes right, and they are never compared again.

The pivot is uniform among the elements of the current subproblem, so the first pivot from S is equally likely to be any of its j - i + 1 members. Therefore

Pr[z_i and z_j compared] = 2 / (j - i + 1)

Sum it. Let k = j - i, so for each k from 1 to n - 1 there are n - k pairs at that distance:

E[comparisons] = sum over i<j of 2/(j-i+1)
               = sum over k=1..n-1 of (n - k) * 2/(k+1)
               < 2n * sum over k=2..n of 1/k
               = 2n (H_n - 1)
               ~ 2n ln n

The exact value is 2(n + 1)H_n - 4n, where H_n is the n-th harmonic number. Check it on n = 3: H_3 = 1 + 1/2 + 1/3 = 11/6, so the formula gives 8 times 11/6 minus 12, which is 2 and 2/3. Directly: the pairs (z_1, z_2) and (z_2, z_3) are compared with probability 1 each, and (z_1, z_3) with probability 2/3. Total 2 and 2/3. They agree.

Converting to the usual units, 2n ln n is about 1.39 n log base 2 of n, so randomized quicksort makes roughly 39 percent more comparisons than the information-theoretic minimum of n log base 2 of n, and it still outruns merge sort on arrays because it moves no memory around.

The core of it: linearity of expectation lets you sum probabilities of events that are wildly dependent on one another. Whether z_1 and z_5 are compared is not independent of whether z_2 and z_5 are, and the calculation never needed it to be.

Why linearity is the workhorse

E[X + Y] = E[X] + E[Y] holds for all random variables on the same space, dependent or not. That is not true of products, and it is the reason so many randomized analyses take the shape "define an indicator for each thing you want to count, find each probability separately, add". You will use it three more times in this module and again in the streaming lesson.

A second, cheaper analysis of the same algorithm shows another common move. Call a pivot good if it falls in the middle half of the current subproblem, so that neither side exceeds 3/4 of the elements. A uniform random pivot is good with probability exactly 1/2. The expected number of pivots you must draw before getting a good one is therefore 2. Each good pivot cuts the subproblem to at most 3/4, so after O(log n) good pivots any element is alone. That gives expected depth O(log n) and, with O(n) work per level, expected O(n log n) again, without any harmonic sums. It is looser and much faster to write.

Expected linear selection

Randomized quickselect keeps only the side containing the rank you want. The same phase argument gives a linear bound, and it is worth writing out because it is short and complete.

QUICKSELECT(A, k):
  if len(A) == 1: return A[0]
  p = a uniformly random element of A
  L, E, G = elements < p, equal to p, > p
  if k <= len(L):            return QUICKSELECT(L, k)
  if k <= len(L) + len(E):   return p
  else:                      return QUICKSELECT(G, k - len(L) - len(E))

Define phase j as the stretch of the recursion during which the subproblem size lies between n(3/4) to the power (j+1) and n(3/4) to the power j. A good pivot ends the phase, and each pivot is good with probability 1/2, so the expected number of iterations spent in phase j is 2. The work of one iteration in phase j is at most n(3/4) to the power j. So

E[total work] <= sum over j >= 0 of 2 * n * (3/4)^j
              = 2n * (1 / (1 - 3/4))
              = 8n

Expected linear, with an explicit constant, in eight lines. Compare that to the previous lesson's median-of-medians, which achieves worst-case linear with a much larger constant and a more delicate proof. The engineering answer, introselect, runs quickselect and switches to median of medians only if the recursion goes too deep, taking the small constant in the common case and the guarantee in the rare one.

What expectation does not promise

"Expected O(n log n)" is a statement about an average over coin flips. It does not say the bad case is rare in any quantified sense. For that you need a concentration result: a proof that the probability of exceeding, say, twice the expectation is vanishingly small. Randomized quicksort does satisfy such a bound, running in O(n log n) with probability 1 minus 1 over a polynomial in n, but nothing proved in this lesson establishes it. Markov's inequality, applied to what we have, gives only Pr[time > 4 times expectation] <= 1/4, which is a weak statement.

The next lesson builds the tools that make the strong statement possible, and then spends them on an algorithm whose whole design depends on knowing that a small success probability can be amplified.

Common misconceptions

• "Randomized quicksort has no worst case." It does: the sequence of coin flips that always picks an extreme pivot still gives n squared. Its probability is astronomically small, and crucially it is not a property of the input.
• "Random pivots are only useful if the input is adversarial." Real data is full of near-sorted runs, duplicate-heavy fields, and files that were themselves produced by a sort. You do not need an adversary to meet a bad input; you only need a Tuesday.
• "Shuffling the array first is different from picking random pivots." For quicksort they give the same distribution of behaviour, and a single upfront shuffle costs O(n) once rather than a random draw per partition. Sedgewick's implementations shuffle.
• "Expected running time is the same as average-case running time." Average case averages over inputs, assuming a distribution you rarely control. Expectation here averages over the algorithm's own coins, for a worst-case input. Only the second is a guarantee you can offer a caller.
• "A fast pseudorandom generator is good enough for the proof." The proof assumes an adversary cannot predict the pivots. If your generator is seeded predictably and the attacker can see timings, the guarantee is gone, which is exactly the shape of the hash-flooding attacks discussed two lessons from now.

Putting it together

• Randomization converts "there exists a bad input" into "for every input, most coin sequences are good", which is a guarantee that survives an adversary reading your code.
• Las Vegas algorithms are always correct with random running time; Monte Carlo algorithms have fixed running time and may be wrong.
• Two elements at sorted distance k are compared with probability exactly 2/(k + 1), because the first pivot drawn from the interval between them decides it.
• Summing those probabilities gives 2(n + 1)H_n - 4n comparisons, about 2n ln n, or 1.39 n log base 2 of n.
• Linearity of expectation needs no independence, which is why indicator variables are the default tool for counting.
• The phase argument, in which a pivot is good with probability 1/2 and shrinks the problem to 3/4, gives expected 8n for quickselect in a few lines.
• Expectation alone does not bound the tail; Markov gives only a weak statement, and concentration inequalities are next.

The habit to take forward is the first move of every analysis in this module: name the thing you want to count, write it as a sum of indicators, and find one probability at a time.

Sources

1. Hoare, C. A. R. (1962). Quicksort. The Computer Journal, 5(1), 10-16.
2. Motwani, R., & Raghavan, P. (1995). Randomized algorithms. Cambridge University Press.
3. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Probabilistic analysis and randomized algorithms; Quicksort; Medians and order statistics. In Introduction to algorithms (4th ed.). MIT Press.
4. Sedgewick, R., & Wayne, K. (2011). Quicksort: random shuffling and the analysis of comparisons. Algorithms, 4th edition booksite, Princeton University. algs4.cs.princeton.edu
5. Demaine, E., & Devadas, S. (2015). 6.046J Design and analysis of algorithms: randomized algorithms and quicksort analysis. MIT OpenCourseWare. ocw.mit.edu
6. Wikipedia contributors. (n.d.). Quicksort, including the expected comparison count. en.wikipedia.org
7. Wikipedia contributors. (n.d.). Las Vegas algorithm. en.wikipedia.org

A graph on 100 vertices has at most 4,950 distinct minimum cuts. Not roughly, and not on average: at most n(n - 1)/2, for every graph on n vertices. That is a fact about graphs with no obvious graph-theoretic proof, and it falls out as a corollary of a randomized algorithm that David Karger published in 1993, one that works by repeatedly gluing two vertices together and hoping. Getting to it requires the machinery for bounding how far a random quantity strays from its mean, which is the other half of this lesson.

Three inequalities, in increasing order of price

Every concentration bound trades assumptions for sharpness. Buy nothing and you get almost nothing; buy independence and you get an exponential.

Markov is one line. For non-negative X and a > 0, E[X] is at least the contribution from the event that X is at least a, which is at least a times Pr[X >= a]. Rearrange. Notice how weak it is: knowing the average household has 2 occupants tells you at most half of households have 4 or more, and nothing at all about the distribution's shape.

Chebyshev is Markov applied to the non-negative variable (X - mu) squared, with a = t squared. That is the entire proof. The price is that you must compute a variance, and the payoff is quadratic rather than linear decay.

Chernoff applies when X is a sum of independent variables each in [0, 1]. The bound comes from applying Markov to exp(sX) and optimizing over s, which is why it is sometimes called the exponential moment method. The two standard forms, with mu = E[X]:

Pr[X >= (1 + delta) mu] <= exp( -delta^2 mu / (2 + delta) )     for delta > 0
Pr[X <= (1 - delta) mu] <= exp( -delta^2 mu / 2 )              for 0 < delta < 1

Put numbers on the difference. Flip a fair coin 1000 times; mu = 500. What is the chance of 600 or more heads?

The true probability is about 0.0000000014. Markov is useless here, Chebyshev is loose, Chernoff is in the right universe. Each step of sharpness was paid for with an assumption.

Why this matters: when you read a claim that an algorithm succeeds "with high probability", meaning with probability at least 1 minus 1 over a polynomial in n, there is almost always a Chernoff bound and a union bound underneath it.

Balls into bins, worked end to end

Throw n balls into n bins uniformly and independently. Expected load per bin is 1. What is the maximum load?

Fix a bin. Its load X is a sum of n independent indicators each with probability 1/n, so mu = 1. Take the threshold to be 3 ln n / ln ln n... or, for a cruder and easier result, take the threshold c log base 2 of n. Setting (1 + delta) mu = c log n with mu = 1 gives delta = c log n - 1, and the Chernoff bound becomes roughly exp(-c log n), which is n to the power minus c for a suitable constant. Now apply the union bound: the probability that some bin exceeds the threshold is at most n times that, or n to the power (1 - c). Choose c = 3 and the failure probability is at most 1/n squared.

So the maximum load is O(log n) with high probability, from two lines of work. The exact answer, Theta(log n / log log n), takes a sharper calculation, and the celebrated refinement is that giving each ball two random bins and putting it in the emptier one drops the maximum load to Theta(log log n). That is the power of two choices, proved by Azar, Broder, Karlin and Upfal in 1994, and it is the theoretical justification for a load balancer that samples two backends instead of one.

Karger's contraction algorithm

Now the algorithm. A global minimum cut of a connected undirected graph is a partition of the vertices into two non-empty sides minimizing the number of edges crossing. The obvious approach is n - 1 maximum-flow computations, one per choice of sink. Karger's is stranger:

CONTRACT(G):
  while G has more than 2 vertices:
      pick an edge (u, v) uniformly at random
      merge u and v into a single vertex
      keep parallel edges, delete self-loops
  return the set of edges between the two remaining vertices

Each contraction reduces the vertex count by one, so there are n - 2 of them, and the surviving edges between the last two supernodes form a cut of the original graph, because every original vertex ended up on one side or the other. The algorithm always outputs a cut. The question is whether it is a minimum one.

Trace a square with a diagonal, vertices a, b, c, d, edges ab, bc, cd, da, ac. The minimum cut has size 2, isolating b or isolating d. If the first random edge is ac, then a and c merge, and afterwards b and d each have two parallel edges to the merged node; every remaining contraction produces a cut of size 2, so we win. If the first edge is ab, the merged node ab has edges to c and d, and the algorithm can still finish with a 2-cut or can stumble into a 3-cut. The randomness is what decides.

The probability it works, proved

Fix one particular minimum cut C, of size k. We compute the probability that no edge of C is ever contracted, because if none is, C survives to the end and is exactly what is returned.

Step 1. Every vertex has degree at least k. If some vertex v had degree less than k, then isolating v would be a cut smaller than k, contradicting minimality.

Step 2. Hence the edge count m is at least nk/2, since the degree sum is 2m and every one of the n degrees is at least k.

Step 3. The first contraction picks a uniformly random edge, so the probability it hits C is k/m, which is at most k/(nk/2) = 2/n. So it misses C with probability at least 1 - 2/n.

Step 4. If it missed, we now have a graph on n - 1 vertices in which C is still a cut, and still a minimum one (contraction never creates a smaller cut, since every cut of the contracted graph corresponds to a cut of the original). So the same argument applies with n - 1 in place of n, and so on.

Multiply the survival probabilities across all n - 2 contractions:

Pr[C survives] >= (1 - 2/n)(1 - 2/(n-1)) ... (1 - 2/3)

               =  (n-2)/n  *  (n-3)/(n-1)  *  (n-4)/(n-2) * ... * 1/3

               =  2 / (n(n-1))

The telescoping in the middle line is the pleasant part: numerators and denominators cancel two positions apart, leaving 2 and 1 on top and n and n - 1 underneath. So a single run finds any fixed minimum cut with probability at least 2/(n(n - 1)), which is 1 divided by the number of vertex pairs.

Remember: the proof never used any structure of the graph beyond "minimum cut size k forces minimum degree k". That one inequality is doing all the work.

Amplification, and where the corollary came from

A success probability of about 2/n squared sounds hopeless. It is not, because failures are independent across runs. Run the algorithm t times independently and return the smallest cut found. The probability that all t runs miss C is at most

(1 - 2/(n(n-1)))^t   <=  exp( -2t / (n(n-1)) )

using 1 - x <= exp(-x). Choosing t = n(n - 1) ln(n) / 2 makes that at most exp(-ln n) = 1/n. So O(n squared log n) runs give a failure probability under 1/n, and since one run costs O(n squared) with a straightforward implementation, the whole thing is O(n to the fourth times log n). Karger and Stein later improved this to O(n squared log cubed n) by noticing that the early contractions are safe and only the late ones need to be repeated, so the recursion should branch near the end rather than restart from scratch.

Now the corollary from the opening. Every distinct minimum cut is returned with probability at least 2/(n(n - 1)), and the events "the algorithm returns cut C" are disjoint for distinct C, since one run returns exactly one cut. Disjoint events have probabilities summing to at most 1, so the number of distinct minimum cuts is at most n(n - 1)/2. A cycle on n vertices attains it: every pair of its n edges is a minimum cut, and there are exactly n(n - 1)/2 such pairs. The bound is tight, and the proof came entirely from analyzing an algorithm.

Common misconceptions

• "Chernoff applies to any sum." It needs independence and bounded terms. For sums with limited dependence you fall back to Chebyshev, or to martingale bounds such as Azuma, or to pairwise-independent constructions, which is exactly the road the next lesson takes with hash functions.
• "A 2/n squared success probability makes an algorithm useless." Any success probability p can be amplified to 1 - epsilon with about ln(1/epsilon)/p independent repetitions. What cannot be amplified cheaply is a low probability paired with an expensive run.
• "Karger's algorithm might return something that is not a cut." It always returns a genuine cut. The failure mode is returning a cut that is not minimum, which is what makes it Monte Carlo rather than Las Vegas.
• "Contraction can create a smaller cut." It cannot. Every cut of a contracted graph is a cut of the original with the merged vertices forced to the same side, so the minimum can only go up, never down.
• "With high probability means with probability 0.99." In this literature it means 1 minus 1 over a polynomial in n, so the failure probability shrinks as the input grows. That distinction is what lets a union bound over n events still leave you with a guarantee.

Where this leaves us

• Markov needs only non-negativity and gives 1/a decay; Chebyshev needs a variance and gives 1/t squared; Chernoff needs independence and gives exponential decay.
• Chebyshev is Markov applied to the squared deviation, and Chernoff is Markov applied to the exponential moment; all three descend from the same one-line inequality.
• Chernoff plus a union bound is the standard route to a with-high-probability claim, as in the O(log n) maximum load for n balls in n bins.
• Karger's algorithm contracts uniformly random edges until two vertices remain and returns the surviving edges as a cut.
• A fixed minimum cut survives with probability at least 2/(n(n - 1)), because minimum cut size k forces minimum degree k, which forces m at least nk/2, which bounds each contraction's risk by 2 over the current vertex count.
• About n squared log n independent runs drive the failure probability below 1/n, and the disjointness of outcomes proves no graph has more than n(n - 1)/2 minimum cuts, a bound the cycle attains.

The move to carry forward is amplification. Once you have any constant-or-better chance of being right and a way to keep the best answer seen, a weak algorithm becomes a strong one, and the only remaining question is the price in repetitions.

Sources

1. Karger, D. R. (1993). Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. In Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms, 21-30.
2. Karger, D. R., & Stein, C. (1996). A new approach to the minimum cut problem. Journal of the ACM, 43(4), 601-640.
3. Mitzenmacher, M., & Upfal, E. (2017). Probability and computing: randomization and probabilistic techniques in algorithms and data analysis (2nd ed.). Cambridge University Press.
4. Azar, Y., Broder, A. Z., Karlin, A. R., & Upfal, E. (1999). Balanced allocations. SIAM Journal on Computing, 29(1), 180-200.
5. Karger, D. R. (n.d.). Selected publications on minimum cuts and randomized algorithms. MIT CSAIL. people.csail.mit.edu
6. Wikipedia contributors. (n.d.). Karger's algorithm. en.wikipedia.org
7. Wikipedia contributors. (n.d.). Chernoff bound. en.wikipedia.org
8. Karp, R. M., et al. (2002). 6.856J Randomized algorithms: concentration and the contraction algorithm. MIT OpenCourseWare. ocw.mit.edu

In 2003 Scott Crosby and Dan Wallach presented a paper at USENIX Security showing that you could stall a server by choosing your input strings carefully. Their targets included Perl's hash tables and the Bro intrusion detection system, and the mechanism was embarrassingly simple: find many strings that the fixed, published hash function sends to the same bucket, submit them, and watch a data structure with O(1) expected lookups degrade to a linked list. In December 2011 Alexander Klink and Julian Waelde repeated the demonstration at 28C3 against PHP, Java, Python and Ruby at once, and every one of those languages shipped a fix within weeks.

The assumption that was never earned

The first course proves that hashing with chaining has expected search time 1 + alpha, where alpha = n/m is the load factor. Read that proof again and find the hypothesis: it is simple uniform hashing, the assumption that each key is equally likely to land in each slot, independently of the others. That is not a property of your hash function. It is an assumption about the distribution of the keys, and the attacks above are what happens when someone else chooses that distribution.

The repair is the same one that fixed quicksort. Stop assuming the input is random and make the algorithm random: choose the hash function itself at random from a carefully designed family, after the code is written and, crucially, in a way the adversary cannot see. Then the expected chain length becomes an expectation over your own coin flips, and it holds for every input, including the one the adversary built.

The point: a fixed hash function has no expected-case guarantee at all against an input chosen by someone who knows it. Randomizing the choice of function is what converts an assumption into a theorem.

What a universal family is

A family H of functions from a universe U into {0, 1, ..., m - 1} is universal if for every pair of distinct keys x and y,

Pr over h drawn uniformly from H [ h(x) = h(y) ]  <=  1/m

That is a modest requirement. It says nothing about individual keys being uniformly distributed, and nothing about triples. It only bounds pairwise collisions, which turns out to be exactly what the chaining analysis needs, because chain length is a sum of pairwise collision indicators.

Two stronger notions get used in the same breath and should be kept apart. A family is strongly universal, also called pairwise independent or 2-universal, if for distinct x, y and any slots i, j, the probability that h(x) = i and h(y) = j is 1 over m squared. And a family is k-wise independent if the same holds for any k distinct keys. Universality is the weakest, cheapest, and sufficient for chaining; linear probing and several sketches need more.

The Carter-Wegman family, and its proof

Carter and Wegman gave the construction in 1979. Fix a prime p larger than every key in the universe. For a in {1, ..., p - 1} and b in {0, ..., p - 1} define

h_ab(x) = ((a x + b) mod p) mod m

The family is all p(p - 1) such functions, so drawing one costs two random numbers.

Proof that it is universal. Take distinct keys x and y, and write r = (a x + b) mod p and s = (a y + b) mod p. Since p is prime and x - y is non-zero mod p, the pair (a, b) determines (r, s) and can be recovered from it: subtracting gives a(x - y) = r - s mod p, and x - y has a multiplicative inverse mod p. So the map from (a, b) to (r, s) is a bijection onto the pairs with r not equal to s. Note that r and s are never equal, because a is non-zero.

Now count. A collision means r = s mod m with r not equal to s. For each choice of r, the values s that agree with it mod m and differ from it number at most ceil(p/m) - 1, which is at most (p - 1)/m. So the number of colliding pairs is at most p(p - 1)/m out of p(p - 1) equally likely pairs, and the collision probability is at most 1/m. That is the definition, so the family is universal.

The proof is worth reading twice, because the trick, turning a probability over function choices into a counting problem over the images of two fixed keys, is the standard move in this area.

What universality buys, exactly

Fix any set S of n keys, chosen by an adversary, and a query key x. Let C be the number of keys in S colliding with x. Write C as the sum over y in S of an indicator for h(y) = h(x). Each indicator has expectation at most 1/m by universality, so by linearity

E[C]  <=  n/m  =  alpha

and the expected cost of a search is 1 + alpha. No independence beyond pairs was used, and no assumption at all was made about the keys. That is the theorem the first course only pretended to have.

Two practical families, both used in production. Multiply-shift hashing computes (a times x) with wraparound in a machine word and takes the top bits, with a an odd random word; it is a couple of instructions and is universal in the appropriate sense. Tabulation hashing splits the key into bytes, looks each byte up in a table of random words, and xors the results; it is 3-wise independent, and Patrascu and Thorup proved in 2011 that it behaves far better than that bound suggests, being good enough for linear probing and several sketches. Cryptographic families such as SipHash cost more but resist an adversary who can observe outputs. Python turned on hash randomization by default in version 3.3 and adopted SipHash for strings and bytes in 3.4.

Perfect hashing, when the set never changes

If S is static, you can do better than expectation. Fredman, Komlos and Szemeredi showed in 1984 how to get worst-case O(1) lookups in O(n) space with a two-level scheme: hash into n buckets with a universal function, then give the bucket holding n_i keys its own table of size n_i squared with its own universal function chosen until it is collision-free. A table of size n_i squared has collision probability under 1/2 by a birthday-style count, so a couple of draws suffice per bucket, and the total secondary space is O(n) in expectation because the sum of n_i squared has expectation O(n) under a universal choice. Construction is randomized; the resulting structure is deterministic and has no bad case at all.

Bloom filters: giving up something to get space

Burton Bloom's 1970 idea trades exactness for memory. Keep m bits, all zero, and k independent hash functions. To insert x, set the k bits h_1(x) through h_k(x). To query x, check whether all k of its bits are set. If any is zero, x is definitely absent. If all are set, x is probably present.

insert("cat"):  set bits  3, 17, 42
insert("dog"):  set bits 17, 29, 55
query("cat"):   bits 3, 17, 42 all set  -> probably present  (correct)
query("emu"):   bit  8 is zero          -> definitely absent (certain)
query("fox"):   bits 3, 29, 55 all set  -> probably present  (WRONG, a false positive
                                            assembled from other keys' bits)

No false negatives, some false positives. That asymmetry is the whole design, and it is what makes the structure useful as a filter in front of an expensive lookup: a negative answer is final and saves the disk read, while a positive answer costs you the read you were going to do anyway.

Now the arithmetic. After inserting n keys with k hash functions into m bits, the probability that a particular bit is still zero is (1 - 1/m) to the power kn, which is about exp(-kn/m). So the false positive rate for a key that was never inserted is approximately

f  =  (1 - exp(-k n / m)) ^ k

Minimizing over k gives k = (m/n) ln 2, at which point about half the bits are set, and the rate becomes f = 2 to the power minus k, or equivalently 0.6185 to the power (m/n). Turn that around to size a filter:

Ten bits per element for a 1 percent error rate, regardless of how large the keys themselves are. A set of 100 million URLs, each averaging 60 bytes, occupies 6 GB exactly and about 120 MB as a Bloom filter. That is why the structure sits in front of on-disk sorted files in Bigtable-derived storage engines, in CDN caches deciding whether an object is worth storing, and in browser malware-URL checks.

The costs are real: you cannot delete without a counting variant that replaces each bit with a small counter, you cannot enumerate the contents, you cannot resize without rebuilding from the original data, and you must know n in advance to size m well. Cuckoo filters and quotient filters address some of these at a modest space cost.

Common misconceptions

• "Universal means the hash values are uniformly distributed." It means only that any two distinct keys collide with probability at most 1/m. A family can be universal while having very structured individual outputs.
• "A good hash function is enough; the family is a formality." There is no such thing as a good fixed hash function against an adversary, because whatever it is, someone can enumerate collisions offline. The randomness of the choice is the defence, which is why the seed must be secret.
• "Bloom filters can produce false negatives if unlucky." Never. Every bit an inserted key set stays set, so all k of its bits are always found. The error is one-sided by construction.
• "More hash functions always means fewer false positives." More functions set more bits, which fills the filter faster. The rate is minimized at k = (m/n) ln 2 and gets worse on both sides of it.
• "A Bloom filter stores the keys." It stores nothing you can read back. You cannot list its members, and you cannot recover a key from the bits, which is occasionally a privacy feature and always an operational limitation.
• "Chaining with a universal family gives O(1) worst case." It gives O(1) expected, over the choice of the hash function. For a worst-case guarantee on a static set you need the two-level FKS construction.

What you now know

• Simple uniform hashing is an assumption about the input; algorithmic complexity attacks are what happens when an adversary supplies the input instead.
• A universal family bounds the collision probability of any two distinct keys by 1/m, which is enough to prove an expected chain length of alpha for any adversarial key set.
• The Carter-Wegman family ((ax + b) mod p) mod m is universal, proved by showing (a, b) maps bijectively onto pairs of distinct residues and counting the pairs that agree mod m.
• Strong universality and k-wise independence are stronger, more expensive properties, needed by linear probing and by several sketches but not by chaining.
• FKS two-level perfect hashing gives worst-case constant lookups in linear space for a static set, using a randomized construction.
• A Bloom filter has no false negatives and a false positive rate of about (1 - exp(-kn/m)) to the k, minimized at k = (m/n) ln 2, giving roughly 10 bits per element for 1 percent error.

The pattern across this module is now visible: in each case the algorithm's own randomness replaced an assumption about the input, and the proof that followed held for every input rather than for typical ones.

Sources

1. Carter, J. L., & Wegman, M. N. (1979). Universal classes of hash functions. Journal of Computer and System Sciences, 18(2), 143-154.
2. Fredman, M. L., Komlos, J., & Szemeredi, E. (1984). Storing a sparse table with O(1) worst case access time. Journal of the ACM, 31(3), 538-544.
3. Bloom, B. H. (1970). Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7), 422-426.
4. Crosby, S. A., & Wallach, D. S. (2003). Denial of service via algorithmic complexity attacks. 12th USENIX Security Symposium. usenix.org
5. Broder, A., & Mitzenmacher, M. (2004). Network applications of Bloom filters: A survey. Internet Mathematics, 1(4), 485-509. eecs.harvard.edu
6. Sedgewick, R., & Wayne, K. (2011). Hash tables: chaining, probing, and load factors. Algorithms, 4th edition booksite, Princeton University. algs4.cs.princeton.edu
7. Wikipedia contributors. (n.d.). Universal hashing. en.wikipedia.org
8. Wikipedia contributors. (n.d.). Bloom filter, including the false positive derivation. en.wikipedia.org

In 1951 David Huffman was a graduate student in Robert Fano's information theory class at MIT. Fano offered the class a choice: sit the final exam, or write a term paper finding the most efficient binary code and proving it optimal. Huffman took the paper, worked on it for months, and was throwing his notes away in frustration when the idea arrived. The algorithm he found in that moment is greedy, it is two paragraphs long, and it is provably optimal. His teacher, who had co-invented the leading code of the day, had been working on the problem for years.

Two ways to prove a greedy algorithm correct

A greedy algorithm makes an irrevocable locally-best choice at each step and never reconsiders. That is a strong constraint, and for most problems it produces a wrong answer. What separates the cases is the existence of a proof, and there are essentially two shapes of proof.

Greedy stays ahead. Define a measure of partial progress. Show by induction that after k choices, the greedy solution is at least as far along by that measure as any other solution is after k choices. Conclude that greedy cannot be beaten at the end.

The exchange argument. Take any optimal solution OPT. Show that if OPT differs from the greedy solution, you can modify OPT, swapping one element for a greedy choice, without making it worse. Repeat, and OPT is transformed into the greedy solution while remaining optimal at every step. So the greedy solution is optimal too.

The exchange argument is the more general of the two and the one worth practising, because it applies to problems where there is no natural notion of "ahead". Both are used below.

Interval scheduling, proved twice

Given n requests, each with a start and finish time, select the largest set of mutually non-overlapping requests. The greedy rule that works is earliest finish time first: repeatedly take the compatible request that finishes soonest.

requests (start, finish):
  A (1, 4)   B (3, 5)   C (0, 6)   D (5, 7)   E (3, 9)
  F (5, 9)   G (6, 10)  H (8, 11)  I (8, 12)

sort by finish: A(4) B(5) C(6) D(7) E(9) F(9) G(10) H(11) I(12)
take A(1,4). next compatible with finish >= 4: D(5,7). take D.
next compatible: H(8,11). take H.
result: A, D, H  -- three requests

Stays-ahead proof. Let the greedy picks be g_1, g_2, ... in order, and let o_1, o_2, ... be any other compatible set, also in order. Claim: finish(g_k) is at most finish(o_k) for every k. Induction. For k = 1 it holds because greedy took the globally earliest finish. Suppose it holds for k - 1. Then o_k starts after finish(o_k-1), which is at least finish(g_k-1), so o_k was available to greedy at step k; greedy chose the earliest-finishing available request, so finish(g_k) is at most finish(o_k). Now suppose the other set had more requests than greedy, say m > k. Then o_k+1 starts after finish(o_k), which is at least finish(g_k), so o_k+1 was available to greedy, and greedy would not have stopped. Contradiction.

Exchange proof. Let OPT be an optimal set. If its first request is not g_1, replace it with g_1. This is legal, because g_1 finishes no later than OPT's first request, so it cannot conflict with the rest, and the set size is unchanged, so it is still optimal. Recurse on the remaining requests that start after finish(g_1). Each step makes OPT agree with greedy one element further along without shrinking it.

Worth holding on to: the exchange proof never argues that greedy is good. It argues that any optimal solution can be bent toward greedy at no cost, which is a much easier thing to show.

Minimizing maximum lateness

Now a problem where nothing is being counted, so "stays ahead" has nothing to measure. Each job j has a processing time t_j and a deadline d_j; one machine runs them in some order with no preemption. If job j finishes at time f_j, its lateness is f_j - d_j when positive and 0 otherwise. Minimize the maximum lateness.

The greedy rule is earliest deadline first, and notice what it ignores: the processing times. That is exactly the kind of rule that feels wrong.

jobs:  P (t=3, d=6)   Q (t=2, d=8)   R (t=1, d=9)   S (t=4, d=9)

earliest deadline first: P, Q, R, S
  P finishes 3, lateness 0
  Q finishes 5, lateness 0
  R finishes 6, lateness 0
  S finishes 10, lateness 1        maximum lateness = 1

shortest job first: R, Q, P, S
  R finishes 1, Q finishes 3, P finishes 6 (lateness 0), S finishes 10 (lateness 1)
  also 1 here, but try  S, P, Q, R:
  S finishes 4, P finishes 7 (lateness 1), Q finishes 9 (lateness 1), R finishes 10 (lateness 1)

Proof by exchange, in three moves. First, there is an optimal schedule with no idle time, since sliding jobs earlier never increases any finish time. Second, define an inversion as a pair of adjacent jobs scheduled with the later deadline first; a schedule with no idle time and no inversions is exactly the earliest-deadline-first order, up to ties among equal deadlines, and all such orders have the same maximum lateness. Third, the exchange itself.

Take an optimal schedule containing an inversion: job i immediately before job j, with d_i greater than d_j. Swap them and call the time at which the pair finishes f, which is unchanged by the swap. Every job outside the pair keeps its finish time, so only i and j can matter.

• Job j now finishes earlier than it did, so its lateness cannot have increased.
• Job i now finishes at f, giving it lateness f - d_i. Before the swap, job j finished at f and had lateness f - d_j. Since d_i is greater than d_j, we have f - d_i less than f - d_j. So i's new lateness is strictly less than a lateness that was already present in the old schedule.

Neither job's lateness exceeds the old maximum, so the maximum did not increase. Each swap removes at least one inversion, and there are at most n(n - 1)/2 of them, so finitely many swaps carry any optimal schedule to the earliest-deadline order without ever getting worse. Therefore earliest deadline first is optimal.

The structure of that argument, adjacent-swap plus an inversion count that strictly decreases, is the workhorse version of exchange. Look for it whenever a greedy rule is a sort order.

Huffman codes

Given symbol frequencies, build a prefix-free binary code minimizing the expected code length, which is the sum over symbols of frequency times depth. Huffman's rule: repeatedly merge the two least frequent nodes into a new node whose frequency is their sum.

frequencies: A 45, B 13, C 12, D 16, E 9, F 5

merge F(5) + E(9)        -> 14
merge C(12) + B(13)      -> 25
merge 14 + D(16)         -> 30
merge 25 + 30            -> 55
merge A(45) + 55         -> 100

depths: A 1, B 3, C 3, D 3, E 4, F 4
expected length = 45(1) + 13(3) + 12(3) + 16(3) + 9(4) + 5(4) = 224 bits per 100 symbols

The optimality proof has two parts, and the first is a pure exchange. Lemma. There is an optimal prefix code in which the two least frequent symbols x and y are siblings at maximum depth. Proof: take any optimal tree, and let a and b be two siblings at maximum depth. Swap a with x and b with y. Since x has frequency at most a's, and x moves deeper while a moves shallower, the cost change is (freq(a) - freq(x)) times (depth(x) - depth(a)), a product of two non-negative numbers subtracted from the total, so the cost does not increase. The tree was optimal, so it still is.

Induction. Merge x and y into a single symbol z of combined frequency and solve the smaller problem optimally. Any tree for the smaller alphabet expands to a tree for the original with cost increased by exactly freq(x) + freq(y), a constant independent of the tree. So an optimal tree for the merged alphabet gives an optimal tree for the original. Since Huffman's rule performs exactly this merge, induction finishes the proof.

Where greedy fails, and how to notice

Three examples, each failing for a different reason.

The practical test before you trust a greedy rule: try to write the exchange argument. If you cannot say what to swap, or if the swap changes something else you were not tracking, the rule is probably wrong and a small counterexample is usually within reach by hand. Note the fractional version of knapsack is greedy-solvable by the ratio rule, because taking a fraction of an item is exactly the freedom the exchange argument needs.

The exact condition: matroids

There is a complete answer to the question "when is greedy always right", for a particular class of problems. A matroid is a finite ground set E with a family of independent subsets satisfying: the empty set is independent; every subset of an independent set is independent; and the exchange property, that if A and B are independent with |A| < |B|, then some element of B can be added to A keeping it independent.

Rado and Edmonds proved that the greedy algorithm, sorting by weight and taking any element that keeps the set independent, finds a maximum-weight independent set for every weight function if and only if the independence system is a matroid. Kruskal's algorithm is precisely this greedy on the graphic matroid, whose independent sets are the forests, which is why the next module can prove Kruskal correct in a paragraph. Scheduling unit jobs with deadlines is greedy for the same reason. Interval scheduling is not a matroid problem, which is why it needed its own argument.

Bottom line: matroids explain a large family of greedy successes, but not all of them. Huffman and interval scheduling are outside the theory and need their own exchange proofs.

Common misconceptions

• "Greedy means fast and approximate." Greedy here means a specific structure, one irrevocable choice at a time. When it is correct it is exactly optimal, and when it is not correct it can be arbitrarily bad, not slightly off.
• "Testing a greedy rule on examples is evidence it works." Every wrong greedy rule works on most examples. The failures are usually small and specific, and the only reliable check is attempting the proof.
• "Earliest start time is the natural rule for interval scheduling." It fails immediately: one request spanning the entire day is chosen first and blocks everything. Shortest duration also fails, on a short request that straddles two long ones.
• "Earliest deadline first must consider processing times." It provably does not need to for maximum lateness on one machine. The moment you change the objective, to total lateness or to weighted completion time, the correct rule changes.
• "Huffman gives the best possible compression." It gives the best possible prefix code with an integer number of bits per symbol. Arithmetic coding beats it by escaping the integer constraint, which matters most when one symbol has probability well above one half.

Looking back

• Greedy algorithms commit to one locally best choice at a time; correctness is proved by a stays-ahead induction or by an exchange argument.
• Exchange arguments transform an arbitrary optimal solution toward the greedy one without loss, which is easier than showing greedy is good directly.
• Earliest finish time is optimal for interval scheduling, provable both ways; earliest start time and shortest duration both fail on small inputs.
• Earliest deadline first minimizes maximum lateness, proved by removing inversions with adjacent swaps that never increase the maximum.
• Huffman's algorithm is optimal because the two rarest symbols can be exchanged to the deepest sibling positions at no cost, after which merging them reduces the problem by one symbol.
• Greedy fails for coin change with arbitrary denominations, for 0/1 knapsack, and for vertex cover; the Rado-Edmonds theorem says greedy is correct for every weight function exactly on matroids.

The two failures in that list, knapsack and coin change, are not failures of algorithm design but signals that the problem needs a table of subproblems rather than a sequence of commitments. That is the next lesson.

Sources

1. Huffman, D. A. (1952). A method for the construction of minimum-redundancy codes. Proceedings of the IRE, 40(9), 1098-1101.
2. Kleinberg, J., & Tardos, E. (2005). Greedy algorithms: interval scheduling, scheduling to minimize lateness, and the exchange argument. In Algorithm design (ch. 4). Pearson.
3. Edmonds, J. (1971). Matroids and the greedy algorithm. Mathematical Programming, 1(1), 127-136.
4. Erickson, J. (2019). Algorithms, chapter 4: greedy algorithms and exchange arguments. University of Illinois. jeffe.cs.illinois.edu
5. Kleinberg, J., & Tardos, E. (n.d.). Algorithm design: lecture slides and course materials. Princeton University. cs.princeton.edu
6. Wikipedia contributors. (n.d.). Huffman coding. en.wikipedia.org
7. Wikipedia contributors. (n.d.). Matroid, including the greedy characterization. en.wikipedia.org

The word kitten becomes sitting in three edits: substitute s for k, substitute i for e, append g. Try to find two. You cannot, and the reason you cannot is a 7 by 8 table of small integers that can be filled in with a pencil in about two minutes. Vladimir Levenshtein defined this distance in a 1965 paper on codes that survive deletions and insertions; the table is what turns his definition into an algorithm.

The recurrence, and why each case is forced

Let x have length m and y have length n. Define D(i, j) as the edit distance between the first i characters of x and the first j characters of y. The base cases are forced: turning an empty string into j characters costs j insertions, so D(0, j) = j, and symmetrically D(i, 0) = i.

For the general case, look at the last column of the optimal alignment. There are exactly three possibilities, and every alignment ends in one of them:

• x[i] is aligned with y[j]. Cost D(i-1, j-1), plus 1 if the characters differ.
• x[i] is aligned with a gap, so it is deleted. Cost D(i-1, j) + 1.
• y[j] is aligned with a gap, so it is inserted. Cost D(i, j-1) + 1.

D(i, j) = min( D(i-1, j-1) + [x[i] != y[j]],
               D(i-1, j) + 1,
               D(i, j-1) + 1 )

That case analysis is the entire correctness proof, and it is worth naming why it works: the three cases are exhaustive, and each one leaves behind a subproblem of exactly the same form. If an optimal alignment ends by deleting x[i], the rest of it must be an optimal alignment of the two prefixes, because otherwise you could substitute a better one and improve the whole. That is optimal substructure, stated as an exchange rather than assumed.

What matters here: a dynamic program is a recurrence plus a memo. The hard part is never the memo. It is choosing a state, here the pair of prefix lengths, such that the last decision leaves a subproblem in the same family.

Filling the table by hand

Rows are the letters of kitten, columns the letters of sitting. Each cell is the minimum of its upper-left neighbour plus a mismatch penalty, its upper neighbour plus one, and its left neighbour plus one.

The answer sits in the bottom right: 3. Two cells are worth checking by hand. The cell at row i, column i holds 1, because kitten and si differ by one substitution on the first character after aligning the i. And the cell at row e, column i holds 2 by the diagonal route from the cell above-left holding 1, a substitution of e for i.

Every cell depends only on three neighbours, so the fill is O(mn) time, and it is completely regular, which is why this loop vectorizes well and why the anti-diagonal ordering parallelizes.

Reading the alignment back out

The number alone is rarely what you want. Walk backwards from the bottom-right corner, at each step moving to whichever neighbour justified the value:

(6,7)=3 <- (6,6)=2 by the left neighbour + 1   : insert g
(6,6)=2 <- (5,5)=2 diagonal, n matches n        : match
(5,5)=2 <- (4,4)=1 diagonal with mismatch       : substitute e -> i
(4,4)=1 <- (3,3)=1 diagonal, t matches t        : match
(3,3)=1 <- (2,2)=1 diagonal, t matches t        : match
(2,2)=1 <- (1,1)=1 diagonal, i matches i        : match
(1,1)=1 <- (0,0)=0 diagonal with mismatch       : substitute k -> s

k i t t e n -
s i t t i n g

Two things follow. The traceback needs the whole table, so recovering an alignment appears to cost O(mn) space, and for two human chromosomes at 250 million bases each that is a table of 62 quadrillion cells. And the traceback is not unique: where two neighbours tie, either choice yields an optimal alignment, which is why two aligners can report different alignments with identical scores.

When the state has to grow: gap penalties

Biological sequences do not gain and lose single bases at random. A single event deletes a run, so a gap of length 10 is far more likely than ten separate gaps of length 1. Charging 1 per gap position gets this exactly backwards.

The fix is an affine gap penalty: opening a gap costs a large constant o, and each additional position costs a small e. Now the cost of the current cell depends on how you arrived, since extending an existing gap is cheaper than starting one. A single table cannot express that, so the state grows to three:

Osamu Gotoh published this three-table formulation in 1982, and it is still what production aligners use. The running time stays O(mn), with a constant factor of three, because the state space tripled but each state is still O(1) work. That is the general lesson about "harder shapes" of dynamic programming: when the naive recurrence is wrong, the usual repair is not a cleverer recurrence but a larger state that remembers the one extra fact the transition needs.

Two more variants worth knowing by name. Needleman-Wunsch is this same table with arbitrary scores, aligning the sequences end to end. Smith-Waterman changes two lines, clamping negative cell values to zero and starting the traceback at the table's maximum instead of the corner, which finds the best-scoring local region instead of a global alignment.

Hirschberg: the alignment in linear space

Computing only the value in linear space is easy, since each row depends on the previous one alone; keep two rows and the space is O(n). But the traceback needs the table. Daniel Hirschberg showed in 1975 how to have both, using divide and conquer.

Split x at its middle row, i = m/2. Any optimal alignment passes through that row at exactly one column, call it k. Then

forward[j]  = edit distance of x[1..m/2]      to y[1..j]
backward[j] = edit distance of x[m/2+1..m]    to y[j+1..n]

k = the j minimizing forward[j] + backward[j]

Both arrays are single-row computations, so finding k costs O(mn) time and O(n) space. Having found it, the problem splits into aligning x[1..m/2] with y[1..k] and x[m/2+1..m] with y[k+1..n], and you recurse on each half, writing out alignment columns as the pieces become trivial.

The time is still O(mn). The two halves together cover a rectangle of half the area, then a quarter, so the total work is mn(1 + 1/2 + 1/4 + ...) = 2mn. You pay a factor of two in time to drop from O(mn) space to O(m + n). For genome-scale alignment that trade is not close.

The upshot: the geometric series appears again, this time paying for a space reduction rather than a resize. Doubling the work to make memory linear is one of the best trades in the subject.

Is quadratic the end of the road?

Edit distance has been O(mn) since the 1960s, with improvements only in log factors, and it is natural to suspect that a strongly subquadratic algorithm is waiting to be found. In 2015 Arturs Backurs and Piotr Indyk proved that it is not, conditionally: if edit distance can be computed in time O(n to the power 2 minus delta) for any positive delta, then the Strong Exponential Time Hypothesis is false, meaning CNF satisfiability would have an algorithm beating exhaustive search by a polynomial factor in the exponent.

That is a different kind of statement from anything in this course so far. It does not prove a lower bound outright; it shows that a faster edit distance algorithm would collapse a widely believed hardness assumption, which is the same currency in which NP-completeness trades. Module 5 develops the machinery. For now, note the practical consequence: work on sequence alignment has moved to approximation, to heuristics that seed on exact matches such as BLAST, and to bit-parallel tricks that shrink the constant, not to a fundamentally faster exact algorithm.

Common misconceptions

• "Dynamic programming means memoizing recursion." Memoization is the implementation. The design work is choosing a state space in which the last decision leaves a subproblem of the same form, and that is where wrong answers come from.
• "The edit distance table is symmetric." The value D(m, n) is symmetric in the two strings when insertion and deletion cost the same, but the table is not, and it stops being symmetric the moment the costs differ, as they do in most real scoring schemes.
• "Affine gaps need a new algorithm." They need a bigger state: three tables instead of one, with the same O(mn) shape. Reaching for a new paradigm when the state is the problem is the most common wrong turn.
• "Hirschberg's trick makes alignment faster." It makes it roughly twice as slow, and reduces space from quadratic to linear. Speed and space are separate axes.
• "Two aligners disagreeing means one is buggy." Ties in the traceback are common, and distinct alignments can have identical optimal scores. Only the score is well defined.

The takeaway

• Edit distance is defined by a three-case recurrence on prefix pairs, and the cases are exhaustive, which is why the recurrence is correct rather than merely plausible.
• The table is filled in O(mn) time from three neighbours per cell, and the traceback recovers an actual alignment, though not a unique one.
• Affine gap penalties break the single-table formulation because the cost now depends on the previous move; Gotoh's three-table state space restores it at the same asymptotic cost.
• Needleman-Wunsch is the global version and Smith-Waterman the local one, differing by clamping at zero and starting the traceback from the maximum cell.
• Hirschberg's divide and conquer finds the middle crossing column with two linear-space row sweeps, recurses, and delivers the alignment in O(m + n) space for twice the time.
• Backurs and Indyk showed that a strongly subquadratic exact algorithm would refute the Strong Exponential Time Hypothesis, so the quadratic bound is very likely the truth.

Next comes a dynamic program whose table is not indexed by positions in a string but by a numeric budget, and that single change is what makes its running time look polynomial while it is not.

Sources

1. Levenshtein, V. I. (1966). Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady, 10(8), 707-710.
2. Needleman, S. B., & Wunsch, C. D. (1970). A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48(3), 443-453.
3. Hirschberg, D. S. (1975). A linear space algorithm for computing maximal common subsequences. Communications of the ACM, 18(6), 341-343.
4. Gotoh, O. (1982). An improved algorithm for matching biological sequences. Journal of Molecular Biology, 162(3), 705-708.
5. Backurs, A., & Indyk, P. (2015). Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). arXiv. arxiv.org
6. Erickson, J. (2019). Algorithms, chapter 3: dynamic programming, including edit distance. University of Illinois. jeffe.cs.illinois.edu
7. Wikipedia contributors. (n.d.). Levenshtein distance. en.wikipedia.org
8. Wikipedia contributors. (n.d.). Hirschberg's algorithm. en.wikipedia.org

Here are two knapsack instances. The first has 4 items with weights 5, 4, 6, 3 and a capacity of 10. The second is identical except that every weight and the capacity have six zeros appended: weights 5,000,000 and 4,000,000 and 6,000,000 and 3,000,000, capacity 10,000,000. The answer is the same set of items in both cases. The standard dynamic program solves the first in 44 table cells and the second in 40 million, and it will keep doing that as you add zeros, forever. Nothing about the difficulty of the problem changed. Something about the algorithm did, and giving that phenomenon its proper name is what this lesson is for.

The capacity table

The 0/1 knapsack problem: n items, item i with weight w_i and value v_i, a capacity W, choose a subset of maximum total value whose total weight is at most W. Items cannot be split, which is exactly what defeated the greedy ratio rule in the previous lesson.

Define K(i, c) as the best value obtainable from the first i items with capacity c. The last decision is whether item i is in or out:

K(i, c) = K(i-1, c)                                  if w_i > c
        = max( K(i-1, c),  v_i + K(i-1, c - w_i) )   otherwise

Fill it for capacity 10 and items A (weight 5, value 10), B (weight 4, value 40), C (weight 6, value 30), D (weight 3, value 50):

The answer is 90, and the traceback recovers the set. Start at the bottom right. The value 90 differs from the 70 above it, so D was taken; move to row +C at capacity 10 minus 3 = 7, which holds 40. That equals the cell above it, so C was not taken; move up to row +B at capacity 7, which holds 40 and differs from the 10 above, so B was taken; move to row +A at capacity 3, which holds 0. Chosen: B and D, weight 7, value 90. The greedy ratio rule would have taken D first (ratio 16.7), then B (ratio 10), and here it agrees, but the counterexample from the last lesson shows it need not.

Why O(nW) is not a polynomial-time algorithm

Complexity is measured in the length of the input in bits. That is not a technicality; it is the only definition under which the theory is consistent.

An instance of knapsack with n items and capacity W is written down in about n log(w_max) + n log(v_max) + log W bits, because a number is encoded in binary. So the number W is exponential in the number of bits used to write it: the capacity 10,000,000 takes 24 bits. An algorithm running in O(nW) steps therefore runs in time exponential in the input length, even though the formula contains no exponent.

input length  L  ~  n log(w_max) + log W        (binary encoding)
running time     ~  n W  =  n * 2^(log W)       exponential in L

Such an algorithm is called pseudo-polynomial: polynomial in the numeric value of the input numbers, exponential in their length. Equivalently, it is polynomial if the numbers are written in unary. That is a real distinction with a practical face: knapsack with weights in the thousands is trivial, and the same problem with weights in the billions, or with fractional weights scaled to integers, is not.

Remember: when you see a running time containing an input number rather than a count of input items, check whether that number could be astronomically large while the input stays short. If it can, the algorithm is pseudo-polynomial.

Weak and strong NP-hardness

Knapsack is NP-hard, so a genuinely polynomial algorithm would imply P equals NP. But the existence of the O(nW) table separates it from the hardest problems, and the distinction has a name.

The test for strong hardness is whether the problem stays hard with small numbers. Travelling salesman is hard on graphs whose edge weights are all 1 or 2, so shrinking the numbers does not help. Subset sum with all numbers bounded by a polynomial in n is solvable by the table in polynomial time, so its hardness lives entirely in the size of the integers.

The other table: index by value

Nothing forces the table to be indexed by capacity. Turn the recurrence inside out and define M(i, p) as the minimum weight needed to achieve a total value of exactly p using the first i items:

M(i, p) = min( M(i-1, p),  w_i + M(i-1, p - v_i) )

with M(0, 0) = 0 and M(0, p) infinite for p > 0. The answer is the largest p with M(n, p) at most W. The table has n rows and one column per achievable value, so its size is O(n times V) where V is the total value, which is at most n times v_max. Running time O(n squared times v_max).

This is pseudo-polynomial too, in the values instead of the weights, and on its own it is merely a curiosity: use whichever of W and V is smaller. Its real purpose is that values can be rounded and weights cannot. Rounding a weight can turn a feasible solution infeasible; rounding a value only perturbs the objective. That asymmetry is the whole idea of what follows.

An FPTAS, proved

A fully polynomial-time approximation scheme takes an accuracy parameter epsilon and returns a solution within a factor (1 - epsilon) of optimal, in time polynomial in both the input size and 1/epsilon. Ibarra and Kim gave one for knapsack in 1975. Here it is in four lines.

1. discard any item with w_i > W        (it can never be used)
2. K = epsilon * v_max / n
3. round each value down: v'_i = floor(v_i / K)
4. solve exactly with the value-indexed table on the v'_i, return that item set

Why it is fast. Each rounded value is at most v_max/K = n/epsilon, so the total rounded value is at most n squared / epsilon. The value table therefore has O(n) rows and O(n squared / epsilon) columns, giving O(n cubed / epsilon) time. Both n and 1/epsilon appear polynomially, which is what "fully" means.

Why it is accurate. Let S be the set returned and O an optimal set. Rounding down loses less than K per item, that is v_i - K < K times v'_i, and at most n items are involved. Chain it:

value(S)  >=  K * sum over S of v'_i        (rounding lost at most K each)
          >=  K * sum over O of v'_i        (S is optimal for the rounded values)
          >=  sum over O of (v_i - K)       (definition of the floor)
          =   OPT - n K
          =   OPT - epsilon * v_max
          >=  OPT - epsilon * OPT           (since the single best item fits, v_max <= OPT)
          =   (1 - epsilon) * OPT

Read the second line again, because it is where the argument turns: the algorithm is exactly optimal on the rounded instance, so it beats the optimal set O measured on that same rounded instance. Everything else is bookkeeping about how much the rounding could have cost.

The point: approximation here is not a heuristic that usually does well. It is an exact algorithm run on a deliberately coarsened instance, with a proof bounding the coarsening's cost.

What this buys, and what it does not

Put epsilon = 0.01 and n = 1000. The scheme runs in about 10 to the 11th operations, which is slow, and returns a solution provably within 1 percent. In practice nobody runs the textbook FPTAS at that size; they run branch and bound with the fractional relaxation as a bound, which is fast on almost all instances and has no guarantee. The FPTAS matters because it draws a line in the theory: knapsack is NP-hard, and yet it can be approximated to any fixed accuracy in polynomial time.

Not every NP-hard problem admits that. General travelling salesman cannot be approximated within any constant factor unless P equals NP, and set cover cannot be approximated better than a logarithmic factor under standard assumptions. Module 5 proves the first of those and states the second. The lesson to carry there is that NP-hardness is one bit of information about a problem, and the approximability of a problem is a much finer classification.

Common misconceptions

• "The O(nW) algorithm shows knapsack is in P." It does not, because W is a value and not a length. This is the single most common misreading in the subject, and it is why the term pseudo-polynomial exists.
• "Pseudo-polynomial means approximately polynomial." It means polynomial in the numeric values, which for binary-encoded inputs is exponential. The word pseudo is doing real work.
• "Knapsack is as hard as travelling salesman because both are NP-hard." Both are NP-hard, but knapsack has a pseudo-polynomial algorithm and an FPTAS while general TSP has neither. NP-hardness is a floor, not a full description.
• "You could round the weights instead of the values." Rounding weights can make a solution infeasible or make an infeasible solution look feasible; the capacity constraint is hard while the objective is soft. The asymmetry is the reason the value table exists.
• "Fractional knapsack is easier because the numbers are smaller." Fractional knapsack is easier because splitting items restores the exchange argument, so the greedy ratio rule is provably optimal. The numbers have nothing to do with it.

Summing up

• The 0/1 knapsack table K(i, c) decides item by item and fills in O(nW) time, with the traceback recovering the chosen set.
• O(nW) is pseudo-polynomial: W is a value written in log W bits, so the running time is exponential in the input length.
• Weakly NP-hard problems such as knapsack, subset sum and partition have pseudo-polynomial algorithms; strongly NP-hard problems such as bin packing and TSP stay hard with small numbers.
• The value-indexed table M(i, p), minimum weight for value exactly p, runs in O(n squared v_max) and is what makes rounding possible, because values can be perturbed and weights cannot.
• Rounding values down by K = epsilon v_max / n and solving exactly gives a (1 - epsilon) approximation in O(n cubed / epsilon) time, proved by chaining four inequalities.
• An FPTAS is a strong positive result that not every NP-hard problem admits, which is why approximability is a finer classification than hardness.

That closes the design paradigms. The next module returns to graphs and proves, rather than describes, the algorithms most readers have already used.

Sources

1. Bellman, R. (1957). Dynamic programming. Princeton University Press.
2. Ibarra, O. H., & Kim, C. E. (1975). Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM, 22(4), 463-468.
3. Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman. (Sections on pseudo-polynomial time and strong NP-completeness.)
4. Williamson, D. P., & Shmoys, D. B. (2011). The design of approximation algorithms: rounding and scaling for knapsack. Cambridge University Press. designofapproxalgs.com
5. Erickson, J. (2019). Algorithms, chapter 3: dynamic programming, including subset sum and knapsack. University of Illinois. jeffe.cs.illinois.edu
6. Wikipedia contributors. (n.d.). Pseudo-polynomial time. en.wikipedia.org
7. Wikipedia contributors. (n.d.). Knapsack problem, including the dynamic programs and the approximation scheme. en.wikipedia.org

Edsger Dijkstra designed his shortest path algorithm in 1956, in about twenty minutes, sitting on a cafe terrace in Amsterdam while shopping with his fiancee. He was trying to demonstrate a new computer, the ARMAC, on a problem an audience without mathematics could follow: the shortest route between two Dutch cities. He published it three years later in a three-page paper. It is probably the most-implemented algorithm in this course, and a surprising number of those implementations are run on graphs where it is not valid.

The invariant that makes it work

Dijkstra's algorithm maintains a set S of vertices whose shortest distance from the source s is known for certain, and a tentative distance d[v] for everything else. Repeatedly move the vertex of smallest tentative distance into S, then relax its outgoing edges:

d[s] = 0; d[v] = infinity for all other v; S = empty
while S does not contain every reachable vertex:
    u = the vertex not in S with the smallest d[u]
    add u to S
    for each edge (u, v):
        if d[u] + w(u, v) < d[v]:
            d[v] = d[u] + w(u, v)          # relax

The claim to prove is exactly one sentence: when a vertex u is added to S, d[u] already equals the true shortest distance from s to u. Everything else follows, because once d[u] is correct the relaxations out of u are correct too.

Work a small example first. Vertices s, a, b, c, t with edges s to a of weight 4, s to b of weight 1, b to a of weight 2, b to c of weight 5, a to c of weight 1, c to t of weight 3.

init      d = {s:0, a:inf, b:inf, c:inf, t:inf}
take s    relax: d[a]=4, d[b]=1
take b    (smallest, 1)   relax: d[a]=min(4, 1+2)=3, d[c]=1+5=6
take a    (smallest, 3)   relax: d[c]=min(6, 3+1)=4
take c    (smallest, 4)   relax: d[t]=4+3=7
take t    done.           d = {s:0, b:1, a:3, c:4, t:7}

Note that d[a] was lowered after a had a value but before a was extracted. That is the algorithm working as designed; a vertex is only frozen when it comes out of the queue.

The proof, and where it leans on non-negativity

Claim. With all edge weights non-negative, d[u] = delta(s, u) at the moment u is added to S, where delta denotes the true shortest distance.

Proof by contradiction. Suppose not, and let u be the first vertex extracted with d[u] greater than delta(s, u). Consider a true shortest path P from s to u. Since s is in S and u is not, P must cross the boundary somewhere: let (x, y) be the first edge of P with x in S and y not in S.

Now three steps:

• x was extracted before u, so by the choice of u as the first failure, d[x] = delta(s, x).
• When x was extracted, the edge (x, y) was relaxed, so d[y] is at most d[x] + w(x, y) = delta(s, y), because the prefix of a shortest path is a shortest path. So d[y] = delta(s, y).
• y lies on P at or before u, and the rest of P has non-negative total weight, so delta(s, y) is at most delta(s, u).

Putting these together: d[y] = delta(s, y) is at most delta(s, u), which is strictly less than d[u]. But the algorithm chose u as the vertex of minimum tentative distance, so d[u] is at most d[y]. Contradiction.

The core of it: the third bullet is the only place non-negativity is used, and it is used decisively. If edges may be negative, a path can get cheaper as it gets longer, and the inequality delta(s, y) at most delta(s, u) simply fails.

One negative edge, and the wreck

Here is the smallest counterexample worth memorizing. Three vertices, three edges:

s -> a   weight  2
s -> b   weight  5
b -> a   weight -4

true shortest distance to a:  s -> b -> a  =  5 - 4  =  1

Dijkstra: extracts a with d[a] = 2 (it is the smallest), freezes it,
          later discovers b -> a would give 1, but a is already in S.
          Reported answer: 2. Wrong.

Note that the graph has no negative cycle. The algorithm is not confused by an ill-posed problem; it is simply invalid on this input. That distinction matters because a common workaround, adding a large constant to every weight to make them non-negative, is also wrong: adding c to every edge adds c times the number of edges to a path, which penalizes paths with more hops and can change which path is shortest.

Bellman-Ford, and induction on path length

Bellman-Ford abandons the priority queue and relaxes every edge, V - 1 times.

d[s] = 0; d[v] = infinity otherwise
repeat V - 1 times:
    for each edge (u, v):
        if d[u] + w(u, v) < d[v]: d[v] = d[u] + w(u, v)

Proof. The inductive claim is that after i passes, d[v] is at most the weight of the lightest path from s to v using at most i edges. For i = 0 that is true by initialization. For the step, take a lightest path to v using at most i edges, whose last edge is (u, v); its prefix uses at most i - 1 edges, so after pass i - 1 we have d[u] at most that prefix's weight, and pass i relaxes (u, v), so d[v] is at most the whole path's weight.

Now, if there is no negative cycle, some shortest path from s to any v is simple, and a simple path has at most V - 1 edges. So V - 1 passes suffice. The running time is O(VE), which for a dense graph is far worse than Dijkstra, and that is the price of admitting negative weights.

A useful practical note that costs one line: if a full pass changes nothing, every d is final and you can stop early. On many real graphs this happens long before pass V - 1.

The extra pass, and what a negative cycle means

Run one more pass, the V-th. If any edge still relaxes, there is a negative cycle reachable from s. The argument is short: if no negative cycle exists, the claim above says every d is already the true distance, and true distances satisfy d[v] at most d[u] + w(u, v) for every edge, which is exactly the condition for no relaxation to fire.

Why does a negative cycle break the problem rather than the algorithm? Because with one on a path from s to v, there is no shortest path: go around the cycle again and the walk gets cheaper, without limit. The natural repair, "find the shortest simple path", is not a repair at all: that problem is NP-hard, since a Hamiltonian path can be encoded in it. This is a case where the honest answer is that the question is ill-posed and the algorithm should report it, which is exactly what the extra pass does.

Johnson's reweighting

Suppose you want all-pairs shortest paths on a sparse graph with some negative edges. Floyd-Warshall costs O(V cubed) regardless of sparsity. Running Bellman-Ford from every vertex costs O(V squared E). Donald Johnson found in 1977 how to get Dijkstra's speed anyway.

Add a new vertex q with a zero-weight edge to every vertex, run Bellman-Ford once from q, and let h(v) be the resulting distance. Then define

w'(u, v) = w(u, v) + h(u) - h(v)

Every reweighted edge is non-negative. Bellman-Ford's output satisfies h(v) at most h(u) + w(u, v) for every edge, since otherwise that edge would still relax. Rearranged, that is exactly w(u, v) + h(u) - h(v) at least 0.

Shortest paths are unchanged. Sum w' along any path from vertex a to vertex b:

w'(p) = sum of [ w(edge) + h(tail) - h(head) ]
      = w(p) + h(a) - h(b)          (everything in between telescopes)

The correction h(a) - h(b) is the same for every path between the same endpoints, so the ordering of paths by weight is untouched and the minimizer is the same. Run Dijkstra from each vertex on the reweighted graph and subtract the correction. Total O(VE + V squared log V) with a Fibonacci heap, which beats Floyd-Warshall whenever the graph is sparse.

In short: a potential function on vertices can make edge weights non-negative without changing which path is shortest. That is the same idea as the potential method in Module 1, reappearing in a different costume, and it is also the mechanism behind A star search, where h is a heuristic estimate rather than an exact distance.

Choosing among them

The Fibonacci heap row deserves a caveat. Fredman and Tarjan's structure gives the better asymptotic bound by making decrease-key O(1) amortized, using the potential method again, but its constants and memory behaviour are poor enough that binary heaps or pairing heaps usually win in practice.

Common misconceptions

• "Dijkstra fails only when there is a negative cycle." The three-vertex example above has no cycle at all and still defeats it. The invalidating condition is a single negative edge.
• "Add a constant to every weight to remove negatives." This changes the answer, because it penalizes each path in proportion to its number of edges. Johnson's reweighting is the correct version, and it is per-vertex rather than uniform.
• "Dijkstra finds the shortest path to the target, so you can stop early." You can stop when the target is extracted, and that is a genuine optimization, but not when it is first assigned a tentative distance.
• "Bellman-Ford needs exactly V - 1 passes." V - 1 is the worst case bound from simple-path length. Stopping when a pass makes no change is both correct and usually much faster.
• "A negative cycle just means the answer is negative." It means no shortest path exists. Asking for the shortest simple path instead makes the problem NP-hard.
• "A star is a different algorithm from Dijkstra." With a consistent heuristic, A star is Dijkstra on a graph reweighted by a potential exactly as in Johnson's method, which is why consistency is the condition that keeps it correct.

What to remember

• Dijkstra's correctness claim is that a vertex is correct when it leaves the queue, proved by taking the first failure and following a true shortest path to where it crosses the frontier.
• Non-negativity is used at exactly one step: that the rest of the path beyond the crossing point cannot reduce the distance.
• A single negative edge, with no cycle anywhere, is enough to make Dijkstra report a wrong answer.
• Bellman-Ford relaxes every edge V - 1 times; after pass i, every d is at most the best path using i edges, and simple paths have at most V - 1 edges.
• A relaxation on the V-th pass proves a reachable negative cycle, in which case no shortest path exists and the simple-path version is NP-hard.
• Johnson reweights by w' = w + h(u) - h(v) with h from a single Bellman-Ford run, which makes weights non-negative and shifts every path between a fixed pair by the same constant.

The next lesson stays on graphs and proves a different kind of claim: that a greedy choice, made with no lookahead at all, always belongs to an optimal spanning tree.

Sources

1. Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.
2. Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87-90.
3. Johnson, D. B. (1977). Efficient algorithms for shortest paths in sparse networks. Journal of the ACM, 24(1), 1-13.
4. Fredman, M. L., & Tarjan, R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3), 596-615.
5. Erickson, J. (2019). Algorithms, chapter 8: single-source shortest paths, relaxation, and negative cycles. University of Illinois. jeffe.cs.illinois.edu
6. Sedgewick, R., & Wayne, K. (2011). Shortest paths: Dijkstra, Bellman-Ford, and negative cycles. Algorithms, 4th edition booksite, Princeton University. algs4.cs.princeton.edu
7. Wikipedia contributors. (n.d.). Johnson's algorithm. en.wikipedia.org
8. Wikipedia contributors. (n.d.). Bellman-Ford algorithm. en.wikipedia.org

In 1926 Otakar Boruvka published the first minimum spanning tree algorithm in a Czech journal. He was not doing graph theory for its own sake: a colleague had asked him how to lay out an electrical network for Moravia using as little wire as possible. The algorithm he gave is still the most parallelizable of the three in common use, and it was rediscovered at least twice before anyone noticed his paper. All three standard algorithms turn out to be the same theorem wearing different clothes, and this lesson proves the theorem first.

The cut property

A cut is a partition of the vertices into a set S and its complement. An edge crosses the cut if exactly one endpoint is in S.

Cut property. For any cut, a minimum-weight edge crossing it belongs to some minimum spanning tree.

Proof. Let e be a minimum-weight crossing edge and let T be an MST that does not contain e. Add e to T. Since T is spanning and acyclic, adding any edge creates exactly one cycle C. That cycle starts in S and returns to S, so it crosses the cut an even number of times, at least twice; therefore C contains some crossing edge f other than e. Because e was a minimum-weight crossing edge, w(f) is at least w(e). Now remove f. The result T - f + e is connected, has V - 1 edges, and so is a spanning tree, with weight w(T) - w(f) + w(e), which is at most w(T). Since T was minimum, the new tree is also minimum, and it contains e.

Every greedy MST algorithm is an application of that one sentence.

Why this matters: the property tells you that a locally minimal choice across any cut is globally safe. No lookahead is required, and that is exactly why greedy works here and fails for knapsack.

The cycle property

Cycle property. For any cycle, if one edge on it is strictly heavier than every other edge on that cycle, it belongs to no minimum spanning tree.

Proof. Let e be that heaviest edge on cycle C and suppose some MST T contains it. Delete e from T, splitting T into two components and defining a cut. The path C - e connects e's two endpoints, so it must contain at least one edge f crossing that same cut. Since e was strictly heaviest on C, w(f) is less than w(e). Then T - e + f is a spanning tree of strictly smaller weight, contradicting minimality.

The two properties are duals in a useful sense: the cut property tells you which edges you may safely add, and the cycle property tells you which you may safely discard. Kruskal uses both, implicitly.

Three algorithms, one theorem

Read the third row and the whole table collapses. Each algorithm differs only in which cut it applies the cut property to. Boruvka applies it to every component simultaneously, which is why a round can be executed in parallel and why the component count at least halves per round, giving log V rounds. Prim applies it to one growing tree, so it never needs union-find at all. Kruskal applies it to whichever cut its next edge happens to cross.

Kruskal, correct in three lines

sort the edges by weight
for each edge (u, v) in order:
    if find(u) != find(v):     # they are in different components
        add (u, v) to the tree
        union(u, v)

Suppose Kruskal adds edge e = (u, v). Let S be the set of vertices in u's current component, which defines a cut. Every edge crossing that cut that is lighter than e was already examined and rejected, and an edge crossing the cut cannot have been rejected for connecting two vertices already in the same component, since one endpoint is inside S and the other outside. So no lighter edge crosses this cut, e is a minimum-weight crossing edge, and by the cut property e is safe. Since every added edge is safe and the process ends with V - 1 edges forming a spanning tree, that tree is minimum.

The running time is the sort, O(E log E), which is O(E log V) since E is at most V squared. The union-find work is O(E alpha(V)) by Module 1, invisible beside the sort. If the edges arrive already sorted, or the weights are small integers that can be radix sorted, Kruskal becomes essentially linear.

Uniqueness, and what ties do

If all edge weights are distinct, the minimum spanning tree is unique. Here is the argument in one exchange: suppose T1 and T2 are distinct MSTs, and let e be the lightest edge in exactly one of them, say in T1. Adding e to T2 creates a cycle, which must contain an edge f not in T1 (otherwise T1 would contain the cycle). By the choice of e as the lightest edge lying in exactly one tree, w(f) is greater than w(e), so T2 - f + e is lighter than T2, contradicting minimality.

With ties, several MSTs may exist, all of the same total weight. That has a practical consequence in testing: two correct implementations can output different trees on the same input, and comparing edge sets is the wrong equality check. Compare total weights. A standard trick when you need determinism is to break ties by edge index, which is equivalent to perturbing all weights by distinct infinitesimals and restores uniqueness.

Worth holding on to: the cut property as stated says a minimum crossing edge is in some MST. When crossing weights are distinct, the minimum crossing edge is in every MST. Which version you need depends on whether you are proving an algorithm correct or proving uniqueness.

A spanning tree is not a shortest path tree

This confusion is common enough to be worth a picture. Take three vertices with edges s to a of weight 1, s to b of weight 2, and a to b of weight 1.5.

MST:                s-a (1) + a-b (1.5)  = 2.5 total weight
shortest path tree: s-a (1) + s-b (2)    = 3.0 total weight

but in the MST, the distance from s to b is 1 + 1.5 = 2.5, not the true 2

The two objectives are different: an MST minimizes total edge weight with no reference to any source, while a shortest path tree minimizes each individual distance from a fixed source and may cost more in total. Prim's algorithm and Dijkstra's algorithm look nearly identical in code, both extracting a minimum-key vertex from a priority queue, and they differ in exactly one line: Prim's key is the weight of the single edge connecting the vertex to the tree, and Dijkstra's key is that weight plus the distance already accumulated. That one addition is the whole difference between the two problems.

Beyond the standard three

The MST problem has been pushed remarkably far. Karger, Klein and Tarjan gave a randomized algorithm in 1995 running in expected O(E) time, using Boruvka steps to shrink the graph and random sampling to discard edges that cannot be in the tree. Chazelle gave a deterministic O(E alpha(E, V)) algorithm in 2000, using soft heaps. Whether a deterministic linear-time algorithm exists is still open. None of these is what you would implement, but their existence is the reason nobody expects a lower bound above linear.

Common misconceptions

• "The MST contains the shortest path between every pair." It usually does not, as the three-vertex example shows. It does contain a path that minimizes the maximum edge weight between any pair, the minimax path, which is a genuinely useful property.
• "The lightest edge in the graph is always in the MST." True, by the cut property applied to any cut it crosses, but the reasoning matters: it is not true because it is lightest overall, it is true because it is the lightest crossing edge of some cut.
• "Prim is Dijkstra." The code shapes match and the keys differ: edge weight versus edge weight plus accumulated distance. Confusing them produces a plausible program that answers the wrong question.
• "Ties mean the algorithm is ambiguous and therefore wrong." Any tie-breaking gives a valid MST, and all MSTs have the same total weight. Determinism, if you need it, is a tie-breaking rule, not a correctness fix.
• "Kruskal needs the cycle property to justify skipping edges." It can, but the cut-property argument above is sufficient on its own; skipped edges are exactly the heaviest edges of cycles that already exist in the forest.

Pulling it together

• The cut property says a minimum-weight edge crossing any cut is in some MST, proved by adding it, finding another crossing edge on the induced cycle, and swapping.
• The cycle property says the unique heaviest edge of a cycle is in no MST, proved by deleting it and reconnecting through the cycle.
• Boruvka, Prim and Kruskal apply the cut property to different cuts; that is the only difference among them.
• Kruskal is correct because when it adds an edge, every lighter edge crossing the corresponding cut has already been rejected, and its running time is dominated by the sort.
• Distinct weights give a unique MST; with ties, all MSTs share the same total weight, so implementations should be compared by weight and not by edge set.
• An MST is not a shortest path tree, and Prim differs from Dijkstra by whether the accumulated distance is added to the key.

The next lesson leaves greedy behind. Flows cannot be built by irrevocable choices, and the mechanism that lets an algorithm change its mind, the residual graph, is what makes the max-flow min-cut theorem provable.

Sources

1. Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1), 48-50.
2. Prim, R. C. (1957). Shortest connection networks and some generalizations. Bell System Technical Journal, 36(6), 1389-1401.
3. Graham, R. L., & Hell, P. (1985). On the history of the minimum spanning tree problem. Annals of the History of Computing, 7(1), 43-57.
4. Karger, D. R., Klein, P. N., & Tarjan, R. E. (1995). A randomized linear-time algorithm to find minimum spanning trees. Journal of the ACM, 42(2), 321-328.
5. Erickson, J. (2019). Algorithms, chapter 7: minimum spanning trees, the cut and cycle properties. University of Illinois. jeffe.cs.illinois.edu
6. Sedgewick, R., & Wayne, K. (2011). Minimum spanning trees: the cut property, Kruskal, and Prim. Algorithms, 4th edition booksite, Princeton University. algs4.cs.princeton.edu
7. Wikipedia contributors. (n.d.). Minimum spanning tree, including uniqueness and the cut property. en.wikipedia.org
8. Wikipedia contributors. (n.d.). Boruvka's algorithm. en.wikipedia.org

In 1955 Ted Harris and General Frank Ross wrote a classified report for the US Air Force on the Soviet railway network. Their map of Eastern Europe carried a heavy line labelled "the bottleneck", cutting the rail system into two pieces at its narrowest point, with a total capacity number attached. In the same period Lester Ford and Delbert Fulkerson at RAND were working out the mathematics of exactly that picture. The theorem they proved says that the bottleneck line and the maximum tonnage the network can move are the same number, always, for every network.

Flows and cuts, defined

A flow network is a directed graph with a non-negative capacity c(u, v) on each edge, a source s and a sink t. A flow f assigns a value to each edge subject to two constraints:

• Capacity: 0 is at most f(u, v), which is at most c(u, v), on every edge.
• Conservation: for every vertex other than s and t, the total flow in equals the total flow out.

The value of the flow, written |f|, is the net flow out of s. An s-t cut is a partition of the vertices into S containing s and T containing t, and its capacity is the sum of capacities of edges going from S to T. Edges going backwards, from T to S, contribute nothing to the capacity.

Weak duality, in three lines

For any flow f and any cut (S, T):

|f| = (flow on edges S -> T) - (flow on edges T -> S)
    <= (flow on edges S -> T)                        since the second term is non-negative
    <= (capacity of edges S -> T)  =  cap(S, T)       by the capacity constraint

The first line needs one moment of thought: summing conservation over every vertex in S makes all internal edges cancel, leaving exactly the net flow across the boundary, which equals the net flow out of s.

Two consequences are immediate and worth noticing before any algorithm exists. Every flow is a lower bound on every cut, so max flow is at most min cut. And if you ever exhibit a flow and a cut with the same number, you have simultaneously proved that the flow is maximum and the cut is minimum. That is a certificate: a piece of evidence that lets a skeptic verify optimality in linear time without rerunning the algorithm.

The point: weak duality alone gives you a proof technique. The hard theorem is that the two numbers always meet, with no gap.

The residual graph, and changing your mind

Greedy fails on flow, and the failure is instructive. Push 1 unit along s to a to b to t on the graph below and there is no way to add more, even though 2 units are achievable.

capacities:  s->a 1,  s->b 1,  a->b 1,  a->t 1,  b->t 1

greedy path s -> a -> b -> t  saturates a->b and b->t
now s->b is unused but b->t is full, and a->t is unused but s->a is full
value 1, while the maximum is 2 (s->a->t and s->b->t)

The repair is to let the algorithm retract earlier decisions. Build the residual graph: for every edge with f(u, v) less than c(u, v), keep a forward residual edge of capacity c - f; and for every edge carrying flow, add a backward residual edge from v to u of capacity f(u, v). Pushing flow along a backward edge means cancelling flow previously sent forward.

In the example, the residual graph after the greedy path contains the backward edge b to a of capacity 1, so the path s to b to a to t exists in the residual graph. Augmenting along it cancels the flow on a to b and produces the two-unit solution. Ford-Fulkerson is nothing more than: while an augmenting path exists in the residual graph, push as much as its bottleneck allows.

The theorem, and its proof

Max-flow min-cut theorem. For any flow network, the maximum value of a flow equals the minimum capacity of an s-t cut. Moreover, for a flow f these three statements are equivalent:

1. f is a maximum flow.
2. The residual graph contains no augmenting path from s to t.
3. |f| = cap(S, T) for some cut (S, T).

Statement 1 implies 2. Contrapositive: if an augmenting path exists, its bottleneck is positive, so pushing along it yields a strictly larger flow, and f was not maximum.

Statement 2 implies 3. This is the substance. Let S be the set of vertices reachable from s in the residual graph, and T the rest. Since no augmenting path exists, t is in T, so (S, T) is a genuine s-t cut. Now examine the boundary:

• Take any original edge (u, v) with u in S and v in T. If f(u, v) were less than c(u, v), there would be a forward residual edge, and v would be reachable, contradicting v in T. So every such edge is saturated: f(u, v) = c(u, v).
• Take any original edge (v, u) with v in T and u in S. If f(v, u) were positive, there would be a backward residual edge from u to v, and v would be reachable. So every such edge carries zero flow.

Substituting into the first line of the weak duality computation: |f| equals the flow S to T minus the flow T to S, which equals cap(S, T) minus 0. So |f| = cap(S, T).

Statement 3 implies 1. By weak duality every flow is at most cap(S, T) = |f|, so f is maximum. And the same equality shows (S, T) is a minimum cut.

The cycle closes, and the theorem follows. Notice that the proof also hands you an algorithm for finding the minimum cut: run any max-flow algorithm, then take the vertices reachable from s in the final residual graph.

Integrality, and why it matters

Integrality theorem. If every capacity is an integer, there is a maximum flow in which every edge carries an integer amount, and Ford-Fulkerson finds one. The reason is that every augmentation pushes the bottleneck value, which stays integral if you begin with integers.

That sounds like a technicality and is in fact the reason flow is so useful for combinatorics. A great many problems can be phrased as "choose a set of objects", which is an integer requirement; encoding them as flow with unit capacities and invoking integrality turns a continuous optimum into a discrete one at no cost. Bipartite matching, below, is the cleanest instance.

How long does it take?

Ford-Fulkerson as stated does not say which augmenting path to choose, and the choice matters enormously.

The pseudo-polynomial row is the familiar trap from the knapsack lesson, and it has a memorable small instance: a diamond with two capacity-1,000,000 edges and a single capacity-1 edge across the middle. Choosing augmenting paths through the middle edge alternately forces 2,000,000 augmentations on a graph with four vertices. Edmonds and Karp's fix is one word long, breadth-first, and it makes the bound depend only on the graph's size.

Bipartite matching, in four extra edges

A matching is a set of edges no two of which share a vertex. In a bipartite graph with sides L and R, finding a maximum matching looks like a fresh problem. It is not.

build a flow network:
  add a source s with an edge s -> u of capacity 1 for every u in L
  keep every original edge u -> v directed L to R, capacity 1
  add a sink t with an edge v -> t of capacity 1 for every v in R

Any integral flow of value k saturates k edges out of s and k edges into t, and the unit capacities force the chosen middle edges to be vertex-disjoint, so an integral flow of value k is exactly a matching of size k. Conversely any matching gives a flow. By the integrality theorem a maximum flow can be taken integral, so maximum flow equals maximum matching. With Dinic's algorithm on this unit-capacity network the running time is O(E times the square root of V), which is precisely the bound Hopcroft and Karp obtained directly in 1973.

Konig and Hall, for free

Now the payoff, two classical theorems that fall out of the min cut.

Konig's theorem. In a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.

Proof. Give the middle edges infinite capacity instead of 1; this changes nothing about maximum flow, since the unit edges at each end already limit it. Take a minimum cut (S, T). No infinite edge can cross from S to T, or the cut would have infinite capacity. Define C = (L intersect T) union (R intersect S). Every original edge (u, v) is covered by C: if u were in S and v in T, that infinite edge would cross the cut. And the capacity of the cut is exactly the number of s-edges crossing, which is |L intersect T|, plus the number of t-edges crossing, which is |R intersect S|, so cap(S, T) = |C|. By max-flow min-cut, |C| equals the maximum flow, which equals the maximum matching. Since any vertex cover must contain at least one endpoint of every matching edge, no cover is smaller. So C is minimum.

Hall's marriage theorem. A bipartite graph has a matching saturating every vertex of L if and only if, for every subset A of L, the neighbourhood N(A) has at least |A| vertices.

The forward direction is obvious: the |A| matched partners live in N(A). For the converse, suppose the maximum matching misses some vertex of L. By Konig there is a vertex cover C smaller than |L|. Let A be the vertices of L not in C. Every neighbour of A must be in C, since the edge from A must be covered and its L endpoint is not in C. So N(A) is contained in C intersect R, giving |N(A)| at most |C| - |L intersect C| = |C| - (|L| - |A|), which is less than |A| because |C| is less than |L|. That violates Hall's condition. Contrapositive done.

Worth holding on to: two theorems that predate flow theory by decades are corollaries of one algorithm's stopping condition. When a min cut is a certificate, its structure is often a combinatorial object you already had a name for.

Common misconceptions

• "Ford-Fulkerson is an algorithm." It is a method with an unspecified choice. Left unspecified, it is pseudo-polynomial with integer capacities and can fail to terminate with irrational ones.
• "A minimum cut is the set of edges the flow saturates." A maximum flow can saturate edges that are not in any minimum cut. The correct construction is the set of vertices reachable from s in the final residual graph.
• "Backward residual edges are a trick for the proof." They are the mechanism that makes the algorithm complete. Without them, greedy augmentation gets stuck at a non-maximum flow, as the five-edge example shows.
• "Max-flow min-cut needs integer capacities." The theorem holds for real capacities. Integrality of the optimal flow is a separate result that does require integer capacities, and it is the one that matters for matching.
• "Minimum cut here is the same as Karger's minimum cut." Different problems: this is a directed s-t cut with specified endpoints, while Karger's is a global undirected cut with no designated vertices.
• "Konig's theorem holds for all graphs." Only bipartite ones. In a triangle the maximum matching is 1 and the minimum vertex cover is 2, and finding a minimum vertex cover in general graphs is NP-hard, as the next module proves.

Recap

• Every flow value is at most every cut capacity, so exhibiting a matching flow and cut is a certificate of optimality for both.
• The residual graph, with backward edges representing cancellable flow, is what lets an augmenting-path algorithm undo earlier commitments.
• The three conditions, maximum flow, no augmenting path, and equality with some cut's capacity, are equivalent; the proof of the middle implication constructs the minimum cut as the residual-reachable set.
• Integer capacities give an integral maximum flow, which is what makes flow a tool for combinatorial selection problems.
• Unspecified path choice makes Ford-Fulkerson pseudo-polynomial and, with irrational capacities, potentially non-terminating; BFS augmentation gives Edmonds-Karp at O(VE squared).
• Bipartite matching becomes flow by adding a unit-capacity source and sink layer, and yields Konig's theorem and Hall's condition directly from the minimum cut.

The certificate idea in the first bullet is about to be generalized. In the next module, weak duality becomes a statement about every linear program, and the max-flow min-cut theorem turns out to be one instance of a much larger theorem.

Sources

1. Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8, 399-404.
2. Edmonds, J., & Karp, R. M. (1972). Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19(2), 248-264.
3. Hopcroft, J. E., & Karp, R. M. (1973). An n to the 5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2(4), 225-231.
4. Zwick, U. (1995). The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate. Theoretical Computer Science, 148(1), 165-170.
5. Schrijver, A. (2002). On the history of the transportation and maximum flow problems. Mathematical Programming, 91(3), 437-445.
6. Erickson, J. (2019). Algorithms, chapter 10: maximum flows and minimum cuts. University of Illinois. jeffe.cs.illinois.edu
7. Erickson, J. (2019). Algorithms, chapter 11: applications of maximum flow, including bipartite matching. University of Illinois. jeffe.cs.illinois.edu
8. Wikipedia contributors. (n.d.). Max-flow min-cut theorem. en.wikipedia.org
9. Wikipedia contributors. (n.d.). Konig's theorem (graph theory). en.wikipedia.org

In 1947 a team using hand-operated desk calculators spent roughly 120 person-days solving one linear program: nine nutritional constraints, seventy-seven foods, minimize the annual cost of a diet that keeps a person alive. George Stigler had attacked the same problem two years earlier with an educated guess and landed within a few cents a year of the true optimum, which he had no way to prove. That gap between having an answer and being able to prove it is optimal is what duality closes, and it closes it for every linear program at once.

The object, in standard form

A linear program maximizes a linear objective subject to linear inequalities:

maximize    c1 x1 + c2 x2 + ... + cn xn
subject to  each of m constraints of the form  a_i1 x1 + ... + a_in xn  <=  b_i
            x1, ..., xn  >=  0

Nothing is integer. That single relaxation is what separates linear programming, solvable in polynomial time, from integer programming, which is NP-hard. Keep the distinction in view: it will do real work in the approximation lesson.

Here is the instance this lesson will follow all the way through.

maximize    3 x1 + 2 x2
subject to    x1 +   x2  <=  4        (constraint 1)
              x1 + 3 x2  <=  9        (constraint 2)
              x1         <=  3        (constraint 3)
              x1, x2 >= 0

The feasible region is a polygon with corners at (0,0), (3,0), (3,1), (1.5, 2.5) and (0,3). Evaluating the objective at each gives 0, 9, 11, 9.5 and 6. So the optimum is 11 at (3, 1), where constraints 1 and 3 are tight and constraint 2 has slack: 3 + 3 = 6, comfortably under 9. That the optimum sits at a corner is not a coincidence of this example; a linear objective on a polyhedron always attains its maximum at a vertex, which is the observation the simplex method is built on.

Constructing the dual by hunting for a bound

Suppose you have the answer 11 but no proof. How would you convince someone that no feasible point does better? Take a non-negative combination of the constraints. Multiply constraint 1 by 2 and constraint 3 by 1, and add:

2 (x1 + x2 <= 4)     gives   2 x1 + 2 x2 <=  8
1 (x1      <= 3)     gives     x1        <=  3
                     sum:     3 x1 + 2 x2 <= 11

The left side is exactly the objective, so no feasible point can score above 11. Combined with the point (3, 1) that achieves 11, that is a complete proof of optimality, checkable in seconds by someone who never runs an algorithm.

Now generalize the hunt. Give constraint i a non-negative multiplier y_i. For the combination to bound the objective, the coefficient of each x_j in the combination must be at least c_j. And the bound you get is the combination of the right-hand sides. Minimizing that bound is itself a linear program:

DUAL:  minimize    4 y1 + 9 y2 + 3 y3
       subject to  y1 + y2 + y3  >=  3        (coefficient of x1)
                   y1 + 3 y2     >=  2        (coefficient of x2)
                   y1, y2, y3 >= 0

In general, the dual of "maximize c dot x subject to Ax at most b, x at least 0" is "minimize b dot y subject to A transpose y at least c, y at least 0". The dual of the dual is the primal again.

Key idea: the dual is not an algebraic curiosity. It is the space of all possible proofs that the primal cannot do better, and the dual optimum is the best such proof.

Weak duality, in one line

For any primal-feasible x and any dual-feasible y:

c dot x  <=  (A transpose y) dot x  =  y dot (A x)  <=  y dot b

The first inequality holds because A transpose y is at least c componentwise and x is non-negative; the last because Ax is at most b componentwise and y is non-negative. Every dual-feasible point is an upper bound on every primal-feasible point.

Strong duality is the deep theorem: if either program has a finite optimum, both do, and the two optimal values are equal. It was established around 1947 to 1951 in work by von Neumann, Gale, Kuhn and Tucker. This course states it without proof; the standard proofs go through Farkas' lemma or through the termination of the simplex method, and both take more space than a lesson.

Notice what you have already seen twice. Weak duality plus a matching pair equals a certificate, which is exactly the structure of max-flow min-cut. That is not an analogy. Maximum flow is a linear program, its dual is a fractional minimum cut, and the max-flow min-cut theorem is strong duality plus the fact that the constraint matrix's structure forces integral solutions.

Complementary slackness

At an optimum the chain of inequalities above must be equalities everywhere. Write out what that forces. From the first inequality being tight:

sum over j of x_j * ( (A transpose y)_j - c_j )  =  0

Every term is a product of two non-negative numbers, so every term is individually zero. The same argument on the second inequality gives the other half. Together:

• If x_j is positive, the j-th dual constraint is tight.
• If the j-th dual constraint is slack, x_j = 0.
• If y_i is positive, the i-th primal constraint is tight.
• If the i-th primal constraint is slack, y_i = 0.

Use these to solve the dual of the running example without any algorithm. At the primal optimum, x1 = 3 and x2 = 1 are both positive, so both dual constraints are tight. Constraint 2 has slack, so y2 = 0. Substituting:

y1 + 3 y2 = 2   with y2 = 0   gives  y1 = 2
y1 + y2 + y3 = 3              gives  y3 = 3 - 2 - 0 = 1

dual objective  4(2) + 9(0) + 3(1)  =  8 + 0 + 3  =  11   -- equal, as promised

The dual solution is (2, 0, 1), and those multipliers are exactly the ones used in the ad hoc proof at the start of the lesson. Complementary slackness found them for us.

Shadow prices, checked

The dual variable y_i has a concrete meaning: it is the rate at which the optimum improves per unit increase in b_i, the shadow price of that constraint. Verify all three by hand.

The zero is the informative entry. Constraint 2 is not binding, so relaxing it buys nothing, which is complementary slackness read in the direction of economics: you pay nothing for a resource you are not using up. This is why sensitivity analysis is a byproduct of solving an LP rather than a separate computation, and why the dual values are the first thing an operations analyst looks at.

So what?: solving the primal gives you an answer; reading the dual tells you which constraints are actually running your business and what it would be worth to loosen them.

Solving linear programs

The gap in the simplex row bothered people for decades: an algorithm with an exponential worst case that essentially never exhibits it. Spielman and Teng resolved it in 2004 with smoothed analysis, showing that simplex runs in expected polynomial time on any instance perturbed by a small random amount. The message generalizes: worst-case analysis and observed behaviour can diverge, and when they do, the right response is a better model of the input rather than a dismissal of either.

Common misconceptions

• "The dual is just the transpose." The mechanical rule is a transpose, but the meaning is a search for the cheapest certificate. Reading it as bookkeeping is how people end up unable to interpret a dual solution.
• "Strong duality holds for every optimization problem." It holds for linear programs. For integer programs there is generally a duality gap, and closing that gap is precisely what makes them hard.
• "Complementary slackness is an optimality test only." It is also a solution method: knowing which variables are zero often determines the rest by linear equations, as it did above.
• "A zero dual variable means the constraint is unimportant." It means the constraint is not binding at this optimum. Change the objective and it may become the binding one.
• "Simplex is polynomial because it is fast." Klee and Minty's cube is a genuine exponential worst case for the classical pivot rule. Whether some pivot rule is polynomial is still open.
• "LP solves the same problems as integer programming, just faster." An LP optimum can be fractional and meaningless as a discrete decision. What the relaxation gives you is a bound, and the next two lessons live off that bound.

What to carry forward

• A linear program maximizes a linear objective over linear inequalities with no integrality requirement, and its optimum is attained at a vertex.
• The dual assigns a non-negative multiplier to each primal constraint and asks for the cheapest valid upper bound on the objective.
• Weak duality, that every dual-feasible value bounds every primal-feasible value, is one line; strong duality, that the optima coincide, is the deep theorem.
• Complementary slackness follows from that chain being tight: a positive variable forces the corresponding opposite constraint to be tight, and a slack constraint forces its multiplier to zero.
• Dual variables are shadow prices, and a non-binding constraint has price zero, which makes sensitivity analysis a byproduct of solving.
• Simplex is exponential in the worst case and excellent in practice, ellipsoid and interior-point methods are polynomial, and smoothed analysis explains the discrepancy.

The certificate idea now has its general form. The next lesson asks what happens for problems where no efficient certificate-producing algorithm is known, and what it would take to prove that none exists.

Sources

1. Dantzig, G. B. (1990). The diet problem. Interfaces, 20(4), 43-47.
2. Stigler, G. J. (1945). The cost of subsistence. Journal of Farm Economics, 27(2), 303-314.
3. Chvatal, V. (1983). Linear programming. W. H. Freeman. (Chapters on duality and complementary slackness.)
4. Spielman, D. A., & Teng, S.-H. (2004). Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM, 51(3), 385-463.
5. Bertsimas, D., & Freund, R. (2009). 15.093J Optimization methods: duality theory and sensitivity analysis. MIT OpenCourseWare. ocw.mit.edu
6. Wikipedia contributors. (n.d.). Dual linear program, including the construction and weak duality. en.wikipedia.org
7. Wikipedia contributors. (n.d.). Linear programming, including the simplex, ellipsoid and interior-point methods. en.wikipedia.org

Richard Karp's 1972 paper "Reducibility Among Combinatorial Problems" is about twenty pages and contains a diagram: twenty-one problems joined by arrows, everything descending from satisfiability. Clique, vertex cover, set cover, Hamiltonian circuit, knapsack, chromatic number, and fifteen more, all shown to be as hard as each other. Before that paper the problems were a scattered collection of things nobody could solve. After it, they were one problem in twenty-one disguises, and the question of whether any of them has a fast algorithm had become a single question.

The four definitions, precisely

• P is the class of decision problems solvable by an algorithm running in time polynomial in the input length.
• NP is the class of decision problems for which a "yes" answer has a certificate of polynomial length that can be verified in polynomial time. It is not the class of problems solvable in nondeterministic polynomial time by intuition alone; the two definitions coincide, and the verifier one is the useful one.
• NP-hard means every problem in NP reduces to it in polynomial time. An NP-hard problem need not be in NP, and need not even be a decision problem.
• NP-complete means both: in NP, and NP-hard.

The certificate framing is worth dwelling on, because it is the same idea as the last lesson's. A satisfying assignment certifies satisfiability. A cut certifies a maximum flow. NP is the class of problems whose yes-instances have short certificates; what is unknown is whether the certificates can also be found quickly.

Reductions, and the direction that everyone gets backwards

A polynomial-time reduction from A to B, written A at most p B, is a polynomial-time function f mapping instances of A to instances of B such that x is a yes-instance of A exactly when f(x) is a yes-instance of B.

Read what that buys: an algorithm for B gives an algorithm for A, by transforming and then calling. So B is at least as hard as A. To prove your problem B is hard, you must reduce a known-hard A to B, not the other way around.

to prove B is NP-hard:   known-hard A  --f-->  your B          CORRECT
                         your B  --f-->  known-hard A          WRONG, proves nothing
                                                               about B's hardness

The wrong direction proves that B is no harder than A, which for A already known to be NP-hard is a statement with no content. This error is common enough that it is worth a habit: after writing a reduction, say out loud "an algorithm for B now solves A", and check that the sentence is true.

Remember: reductions flow from the problem you already know is hard into the problem you are accusing.

Where the chain starts: Cook and Levin

Every chain of reductions needs a first link, a problem proved NP-hard from the definition rather than from another problem. Stephen Cook supplied it in 1971 and Leonid Levin independently in 1973.

Cook-Levin theorem. Boolean satisfiability is NP-complete.

This course states it without proof, and the reason is honest: the proof is a careful simulation, not a clever idea. Given any nondeterministic machine that verifies certificates for a problem in NP within p(n) steps, you write a Boolean formula whose variables record the machine's tape contents, head position and state at each of p(n) time steps, and whose clauses assert that the starting configuration is correct, each step follows the transition rules, and the final state accepts. The formula is satisfiable exactly when an accepting computation exists, and it can be written down in polynomial time. Every one of the reductions below rests on that theorem.

3-SAT, the restriction where every clause has exactly three literals, is also NP-complete, and it is the more convenient starting point because its structure is uniform.

Reduction one: 3-SAT to independent set, in full

An independent set is a set of vertices no two of which are adjacent. Decision version: does G contain an independent set of size at least k?

The construction. Given a 3-CNF formula with k clauses:

• For each clause, create a triangle of three vertices, one per literal, with all three edges present.
• Add an edge between any two vertices in different triangles whose literals are complementary, that is x in one and not-x in the other.
• Ask for an independent set of size exactly k, the number of clauses.

Take the formula (x or y or z) and (not-x or not-y or z) and (x or not-y or not-z). The graph has 9 vertices in three triangles. Complementary edges join x in triangle 1 to not-x in triangle 2; y in triangle 1 to not-y in triangles 2 and 3; z in triangle 1 to not-z in triangle 3; and so on.

T1: [x]  [y]  [z]          triangle edges inside each group
T2: [-x] [-y] [z]          plus cross edges x--(-x), y--(-y), z--(-z)
T3: [x]  [-y] [-z]         wherever they appear in different triangles

Forward direction. Suppose the formula is satisfiable. Each clause has at least one true literal; pick exactly one true literal per clause and take its vertex. That is k vertices, one per triangle, so no triangle edge is violated. Could two chosen vertices be joined by a complementary edge? That would require both a literal and its negation to be true under one assignment, which is impossible. So the k vertices are independent.

Reverse direction. Suppose G has an independent set S of size k. A triangle can contribute at most one vertex to an independent set, and there are exactly k triangles, so S contains exactly one vertex from each. Set every literal named in S to true. This is consistent, because a variable and its negation would have been joined by an edge and could not both be in S; any variable not named is set arbitrarily. Every clause now has a true literal, namely the one selected from its triangle, so the formula is satisfied.

Polynomial. The graph has 3k vertices and fewer than 9k squared edges, and is constructed by a double loop over literals.

Both directions and the time bound: that is a complete reduction. In the example, the independent set {z from T1, z from T2, x from T3} has no internal edges, and the assignment z true and x true satisfies all three clauses.

Reduction two: independent set to vertex cover, in two lines

A vertex cover is a set of vertices touching every edge. The reduction is the identity map on the graph, with the size parameter changed.

Claim. S is an independent set if and only if its complement V minus S is a vertex cover.

Proof. S is independent exactly when no edge has both endpoints in S, which is exactly when every edge has at least one endpoint outside S, which is exactly when V minus S covers every edge.

So G has an independent set of size k precisely when it has a vertex cover of size n minus k, and vertex cover is NP-hard. Two problems that sound different are the same problem read from opposite sides, and neither the graph nor the running time changed.

Reduction three: vertex cover to set cover

Set cover: given a universe U and a collection of subsets, is there a subcollection of size k whose union is U?

Given a graph G, let the universe be the edge set E. For each vertex v, create the subset S_v containing exactly the edges incident to v. A collection of k subsets covers E precisely when the corresponding k vertices touch every edge, which is precisely a vertex cover of size k. The map is one pass over the edges, so it is polynomial, and both directions are immediate from the definition.

The chain is now three links long: satisfiability, by Cook-Levin, to 3-SAT, to independent set, to vertex cover, to set cover. Each link took a page or less because the previous link did the hard work.

What matters here: after Cook-Levin, no reduction ever has to reason about machines again. You only ever need to transform one combinatorial structure into another and prove an if-and-only-if.

Numbers, not just graphs

Not every NP-complete problem is a graph problem. 3-SAT reduces to subset sum by an encoding that is worth describing even without carrying it out. Build one decimal number per literal and one pair of slack numbers per clause. Reserve one digit position for each variable and one for each clause. A literal's number carries a 1 in its own variable's position and a 1 in the position of every clause it appears in. The target has a 1 in every variable position, forcing exactly one of x and not-x to be selected, and a 4 in every clause position, which the slack numbers can complete only if at least one selected literal already contributed to that clause. The base is chosen large enough that no column can carry, which is what makes the digit-by-digit reasoning valid.

That reduction is the reason subset sum and knapsack are NP-hard despite the pseudo-polynomial table of Module 3: the numbers it constructs are exponentially large in the input size, which is precisely the regime where O(nW) stops being useful.

What NP-completeness does and does not tell you

• It is a statement about worst case behaviour on arbitrarily large inputs. It says nothing about the instances you actually have.
• Modern SAT solvers routinely dispatch industrial instances with millions of variables. NP-completeness is not a prediction that your instance is hard; it is a proof that no algorithm handles every instance quickly unless P equals NP.
• It does not forbid pseudo-polynomial algorithms, approximation schemes, parameterized algorithms that are exponential only in a small parameter, or heuristics with no guarantee.
• It is a floor, not a ceiling. Knapsack and travelling salesman are both NP-hard, and one has an approximation scheme while the other has no constant-factor approximation at all.

Common misconceptions

• "NP means non-polynomial." It means nondeterministic polynomial. P is a subset of NP, so every polynomial-time problem is in NP.
• "To show B is hard, reduce B to a known hard problem." Backwards. That shows B is no harder than the known problem, which is not a hardness result.
• "A reduction only needs to map yes-instances to yes-instances." It needs both directions. A map sending everything to a fixed yes-instance would otherwise prove anything.
• "NP-complete means exponential time is required." Only if P is not NP, which is unproved. The strongest honest statement is that a polynomial algorithm for one would give polynomial algorithms for all of them.
• "NP-hard problems are unsolvable." Undecidable problems are unsolvable. NP-hard problems are solvable, potentially slowly, and are solved daily on real instances.
• "Proving my problem NP-hard means I should give up." It means you should stop looking for an exact polynomial algorithm and start choosing among approximation, parameterization, restriction to special cases, and heuristics. That choice is the next lesson.

The short version

• NP is the class of problems whose yes-instances have short, quickly checkable certificates; the open question is whether the certificates can be found as quickly as they can be checked.
• A reduction from A to B shows B is at least as hard as A, so hardness proofs must reduce a known-hard problem into the target.
• Cook and Levin proved satisfiability NP-complete by encoding an accepting computation as a formula; every later reduction builds on that single result.
• 3-SAT reduces to independent set with a triangle per clause and edges between complementary literals, and both directions of the equivalence are short.
• Independent set and vertex cover are complements of each other, and vertex cover reduces to set cover by taking edges as elements and vertices as sets.
• NP-completeness is a worst-case statement that leaves room for approximation, pseudo-polynomial algorithms, parameterization, and heuristics.

The last of those is where the course goes next: given that a problem is NP-hard, what can be proved about how close to optimal you can get in polynomial time?

Sources

1. Cook, S. A. (1971). The complexity of theorem-proving procedures. In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 151-158.
2. Karp, R. M. (1972). Reducibility among combinatorial problems. In R. E. Miller & J. W. Thatcher (Eds.), Complexity of computer computations (pp. 85-103). Plenum Press.
3. Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman.
4. Erickson, J. (2019). Algorithms, chapter 12: NP-hardness and reductions. University of Illinois. jeffe.cs.illinois.edu
5. Wikipedia contributors. (n.d.). Cook-Levin theorem. en.wikipedia.org
6. Wikipedia contributors. (n.d.). Karp's 21 NP-complete problems. en.wikipedia.org
7. Demaine, E., & Devadas, S. (2015). 6.046J Design and analysis of algorithms: complexity and NP-hard problems. MIT OpenCourseWare. ocw.mit.edu

In 1976 Nicos Christofides circulated a technical report at Carnegie Mellon giving an algorithm for the travelling salesman problem on metric inputs, with a tour guaranteed to be at most 1.5 times the optimum. The report was never formally published. Its bound stood as the best known for forty-five years, until a 2021 paper improved it by roughly one part in ten to the thirty-sixth. That is the state of the art in this subject: proving a ratio is hard, and improving one is harder.

The difficulty, stated plainly

An algorithm is a rho-approximation for a minimization problem if its output is always at most rho times the optimum. To prove such a claim you must compare your answer to OPT. But OPT is exactly the quantity you cannot compute, because the problem is NP-hard.

The resolution is the same in every proof in this lesson. Find a quantity you can compute that is provably a lower bound on OPT, and compare your answer to that instead. Every approximation proof has this shape:

ALG  <=  rho * LB     (you prove this, by analyzing your algorithm)
LB   <=  OPT          (you prove this, by a structural argument)
--------------------
ALG  <=  rho * OPT     (follows, and never mentions OPT's value)

The art is choosing the lower bound. A minimum spanning tree, a maximal matching, a linear programming relaxation and a counting argument each serve below.

Vertex cover: two proofs of the same factor 2

Algorithm. Find a maximal matching M, meaning a set of disjoint edges that cannot be extended. Output both endpoints of every edge of M.

MATCHING-VC(G):
  C = empty, M = empty
  for each edge (u, v):
      if neither u nor v is already in C:
          add (u, v) to M;  add both u and v to C
  return C

It is a cover. Suppose some edge (x, y) had neither endpoint in C. Then the loop would have added it to M when it was examined. So no such edge exists.

The lower bound. The edges of M are pairwise disjoint, and any vertex cover must contain at least one endpoint of each of them. Distinct matching edges therefore demand distinct cover vertices, so OPT is at least |M|.

The ratio. The algorithm outputs exactly 2|M| vertices, which is at most 2 times OPT. Done, in six lines, with no reference to what OPT actually is.

Now the same factor by a completely different route, which introduces a technique you will meet everywhere. Write vertex cover as an integer program with a variable x_v in {0, 1} per vertex, minimizing the sum of x_v subject to x_u + x_v at least 1 for every edge. Relax the integrality to 0 at most x_v at most 1 and solve the resulting linear program, which is polynomial by the previous lesson. Then round: put v in the cover exactly when x_v is at least 1/2.

• Feasible. For any edge, x_u + x_v is at least 1, so at least one of them is at least 1/2 and gets rounded up.
• Cheap. Each rounded-up vertex had x_v at least 1/2, so the number of chosen vertices is at most twice the LP value.
• Lower bound. The LP optimum is at most the integer optimum, because every integral solution is also a fractional one. So LP is at most OPT.

Chaining, ALG at most 2 times LP at most 2 times OPT. The gap between the LP value and the integer value is called the integrality gap, and for vertex cover it really can approach 2: on the complete graph with n vertices, setting every x_v to 1/2 is feasible with value n/2, while any integral cover needs n - 1 vertices. So no rounding of this LP can prove a ratio better than 2, and finding an algorithm with a ratio below 2 for vertex cover is a well-known open problem.

Key idea: a relaxation gives you both an algorithm and the lower bound its proof needs. That pairing is why linear programming and approximation are inseparable.

What the obvious greedy does instead

The natural greedy for vertex cover, repeatedly take the highest-degree vertex, feels smarter and is provably worse. On carefully built bipartite graphs its ratio grows like the logarithm of the number of vertices. This is worth internalizing: the algorithm with the better intuition has the worse guarantee, and only the proof distinguishes them.

Set cover: the greedy is logarithmic, and that is optimal

For set cover, greedy is the right algorithm, and its analysis is the prettiest counting argument in the subject. Repeatedly choose the set covering the most currently uncovered elements.

The lower bound is implicit. Suppose the optimum uses k sets. At any moment, let R be the number of uncovered elements. Those R elements are covered by the optimum's k sets, so by pigeonhole one of those sets covers at least R/k of them. Greedy chooses the best available set, so it covers at least R/k. Therefore

R_(t+1)  <=  R_t - R_t / k  =  R_t (1 - 1/k)

after t steps:   R_t  <=  n (1 - 1/k)^t  <  n * exp(-t/k)

Set t = k ln n. Then the remaining count is below n times exp(-ln n) = 1, and since it is an integer it is zero. So greedy finishes within k ln n sets, giving a ratio of ln n. A sharper version of the same argument gives H_n, the n-th harmonic number, which is ln n plus about 0.577.

Is that ratio an artifact of a weak analysis? No. Uriel Feige proved in 1998 that no polynomial algorithm achieves a ratio of (1 - epsilon) ln n for any positive epsilon unless NP has slightly superpolynomial algorithms, a hypothesis considered nearly as implausible as P equals NP. Later work strengthened the assumption to P not equal to NP. Greedy set cover is, up to lower-order terms, the best possible.

General TSP: no constant factor at all

Here is a hardness proof short enough to carry out in full, and it is the sharpest demonstration in the course that NP-hardness comes in grades.

Claim. If for some constant rho there is a polynomial rho-approximation for travelling salesman on general weighted complete graphs, then P equals NP.

Proof. Take an instance of Hamiltonian cycle: a graph G on n vertices, does it contain a cycle visiting every vertex exactly once? Build a complete graph H on the same vertices with weights

w(u, v) = 1                if (u, v) is an edge of G
w(u, v) = rho * n + 1      otherwise

If G has a Hamiltonian cycle, that cycle uses n edges of weight 1, so the optimal tour of H costs exactly n. Any rho-approximation must then return a tour of cost at most rho times n, which is strictly less than rho n + 1, so it uses no heavy edge, so it is a Hamiltonian cycle of G.

If G has no Hamiltonian cycle, every tour of H uses at least one heavy edge, so every tour costs more than rho n.

The two cases are separated by the value rho n, so running the approximation and looking at its cost decides Hamiltonian cycle in polynomial time. Since Hamiltonian cycle is NP-complete, P equals NP.

The upshot: approximability is a property of a problem, not of our cleverness. Knapsack has a scheme for any accuracy, set cover is stuck at a logarithm, and general TSP admits no constant at all.

Metric TSP: a factor of 2 from a spanning tree

Add one hypothesis and everything changes. A TSP instance is metric when the weights satisfy the triangle inequality, w(u, w) at most w(u, v) + w(v, w). Real distances do.

Algorithm. Build a minimum spanning tree T. Walk around it, visiting each edge twice, which is a closed walk of cost 2 times w(T). Then take shortcuts: traverse the walk and skip any vertex already visited.

Lower bound. Delete any single edge from an optimal tour and you have a spanning path, which is a spanning tree. So w(T) is at most OPT. That single sentence is the whole reason the algorithm works.

Ratio. Doubling the tree gives 2 w(T), and the shortcuts only shorten the walk, by the triangle inequality. So the tour costs at most 2 w(T), which is at most 2 OPT.

Christofides improved the constant with one further idea. Doubling every edge is wasteful; all you need is to make every degree even so that an Eulerian circuit exists. Let O be the set of vertices of odd degree in T, which has even size because degrees sum to twice the edge count. Add a minimum-weight perfect matching on O, computable in polynomial time. The matching costs at most OPT/2, because the optimal tour, shortcut down to just the vertices of O, is a cycle through them of cost at most OPT, and that cycle splits into two perfect matchings, the cheaper of which costs at most OPT/2. Total: w(T) plus the matching is at most OPT + OPT/2, giving 3/2.

Common misconceptions

• "An approximation ratio is measured empirically." It is proved, and it is a worst-case guarantee. An algorithm that is usually within 1 percent and occasionally 50 times off is a heuristic, not a 1.01-approximation.
• "You need to know OPT to prove a ratio." You never compute OPT. You bound it from below with something computable, and compare against that.
• "The greedy algorithm is always the natural approximation." For set cover it is optimal; for vertex cover the greedy by degree is logarithmically bad while a maximal matching gives 2. Intuition ranks them backwards.
• "Christofides works on any TSP instance." It needs the triangle inequality. Without it, the shortcutting step can increase the cost, and the hardness proof above shows no constant ratio is possible at all.
• "A 2-approximation returns a solution about twice as bad." It returns one no worse than twice the optimum, and typically much better. The ratio is a ceiling, not a forecast.
• "NP-hardness makes all these problems equally intractable." The final table is the refutation: the same complexity class contains problems with schemes for any accuracy and problems with no constant factor at all.

Looking back

• An approximation proof compares the algorithm to a computable lower bound on the optimum, never to the optimum itself.
• Taking both endpoints of a maximal matching gives a vertex cover of size 2|M| while any cover needs at least |M| vertices, for a clean factor of 2.
• Rounding the LP relaxation at 1/2 gives the same factor and introduces the integrality gap, which for vertex cover approaches 2 and blocks better bounds from that relaxation.
• Greedy set cover finishes within k ln n sets because at every step some optimal set covers a 1/k fraction of what remains, and Feige proved this is essentially optimal.
• General TSP admits no constant-factor approximation unless P equals NP, proved by scaling non-edges above the approximation ratio and reading off a Hamiltonian cycle.
• With the triangle inequality, doubling a minimum spanning tree gives 2, and Christofides' odd-degree matching gives 3/2, using the fact that a spanning tree is a lower bound on any tour.

Everything so far has assumed the whole input is available. The final module removes that assumption twice over: once for algorithms that must answer before the input ends, and once for algorithms that cannot store it.

Sources

1. Christofides, N. (1976). Worst-case analysis of a new heuristic for the travelling salesman problem (Report 388). Graduate School of Industrial Administration, Carnegie Mellon University.
2. Feige, U. (1998). A threshold of ln n for approximating set cover. Journal of the ACM, 45(4), 634-652.
3. Vazirani, V. V. (2001). Approximation algorithms. Springer.
4. Williamson, D. P., & Shmoys, D. B. (2011). The design of approximation algorithms. Cambridge University Press. designofapproxalgs.com
5. Karlin, A. R., Klein, N., & Oveis Gharan, S. (2020). A (slightly) improved approximation algorithm for metric TSP. arXiv. arxiv.org
6. Wikipedia contributors. (n.d.). Christofides algorithm. en.wikipedia.org
7. Wikipedia contributors. (n.d.). Set cover problem, including the greedy analysis and hardness. en.wikipedia.org
8. Wikipedia contributors. (n.d.). Vertex cover, including the matching-based approximation. en.wikipedia.org

In February 1985 Daniel Sleator and Robert Tarjan published a paper in Communications of the ACM on two unglamorous problems: how to reorder a linked list as you search it, and which page to evict from a cache. Their contribution was not an algorithm. It was a way of asking the question. Stop measuring an algorithm against typical inputs, they proposed, and measure it, input by input, against an algorithm that already knows the entire future. If your algorithm is never worse than a constant times that clairvoyant one, you have proved something an average-case study never could.

The definition, and what it is not

An online algorithm receives its input as a sequence of requests and must respond to each before seeing the next, with no ability to revise. It is c-competitive if for every request sequence sigma,

ALG(sigma)  <=  c * OPT(sigma)  +  b

where OPT is the best possible cost with full knowledge of sigma in advance, and b is a constant independent of the sequence. The infimum of such c is the competitive ratio.

Three things follow that people often miss. The comparison is against an offline optimum, not against another online algorithm, so a competitive ratio measures the cost of not knowing the future rather than the cost of being unclever. There is no probability distribution over inputs, so this is worst-case analysis. And the additive constant b matters: it lets an algorithm be forgiven for a bounded startup cost.

Ski rental: the whole subject in one problem

Skis cost B to buy or 1 per day to rent. Each morning you learn whether the season is still on. You do not know when it ends. Buy too early and the season stops the next day; rent too long and you have paid more than the purchase price.

The offline optimum is trivial: if the season lasts d days, pay min(d, B). The online problem is the interesting one.

Strategy. Rent for B - 1 days, then buy on day B.

Analysis. If the season ends on day d with d less than B, you rented d times, paying d, which is exactly optimal, ratio 1. If it reaches day B, you have paid B - 1 in rentals plus B to buy, or 2B - 1, while the optimum is B. The ratio is (2B - 1)/B, that is 2 - 1/B, and it never gets worse no matter how long the season runs, because you own the skis.

Lower bound. No deterministic algorithm does better. Any deterministic strategy buys on some fixed day d, determined before the season starts, and the adversary simply ends the season that day.

if d < B:   ALG = (d - 1) + B,  OPT = d,  ratio = 1 + (B-1)/d  >  2 - 1/B
if d > B:   ALG = (d - 1) + B,  OPT = B,  ratio = (d - 1 + B)/B >  2 - 1/B
if d = B:   ratio = 2 - 1/B, exactly

So 2 - 1/B is achievable and optimal. Randomization does better: choosing the purchase day from a carefully weighted distribution gives a competitive ratio of e/(e - 1), about 1.58, and no randomized algorithm improves on that against an adversary who must commit to the sequence in advance. That gap between 2 and 1.58 is exactly the value of being unpredictable, which is the same currency Module 2 traded in.

The point: the break-even rule, spend on a commitment once your accumulated spending equals its price, is the shape of a great many good online strategies, and it usually gives 2.

Paging, and an adversary who reads your code

A cache holds k pages. Requests arrive; a request for a page in the cache is free, a request for one not in the cache is a fault and requires evicting something. Minimize faults.

First the bad news, because it sets the target.

Lower bound. No deterministic paging algorithm is better than k-competitive. Restrict the universe to k + 1 pages. Since the cache holds only k of them, at every step there is exactly one page missing, and the adversary requests that page. The algorithm faults on every single request. Meanwhile, what does the offline optimum do? Belady's rule, evict the page whose next use is furthest in the future, faults at most once every k requests: after a fault it can evict the page not requested again for the longest time, and among the k pages it holds, the next k - 1 requests can be served for free. So ALG is n and OPT is at most n/k, giving a ratio of at least k.

Notice the adversary needs your code, not your data. This is deterministic worst-case analysis with the algorithm fully exposed, which is why randomization will help.

Upper bound: LRU is k-competitive. Least Recently Used evicts the page unused for longest. Partition the request sequence into phases: phase 1 starts at the first request, and each phase is extended until it would contain k + 1 distinct pages, at which point the next phase begins.

• LRU faults at most k times in a phase. A phase touches at most k distinct pages. LRU never evicts a page that has already been requested within the current phase, because such a page is more recently used than anything not yet touched this phase. So each distinct page in the phase causes at most one fault.
• OPT faults at least once per phase. Consider a phase together with the first request of the next phase: that is k + 1 distinct pages. At the moment the phase begins, OPT's cache holds at most k pages, so at least one of those k + 1 requests is a fault for OPT.

Summing over phases, LRU faults at most k times per phase and OPT at least once, so LRU is at most k times OPT plus a constant for the first phase. Combined with the lower bound, LRU is exactly k-competitive, and no deterministic algorithm is better. The same proof works for FIFO, which is a useful sanity check on what competitive analysis does and does not capture, since everyone who has measured them knows LRU beats FIFO on real traces.

Where the model shows its limits, and how it was repaired

That last observation is the standard criticism of competitive analysis. It rates LRU and FIFO identically, rates every deterministic algorithm at k, and offers no way to prefer the one that works. The response was not to abandon the framework but to change what the adversary is allowed to do.

• Randomization. The marking algorithm keeps a mark bit per page, evicting a random unmarked page and clearing all marks when everything is marked. It is 2H_k-competitive against an oblivious adversary, where H_k is the k-th harmonic number, roughly 2 ln k. For a 64-entry cache that is about 8 rather than 64. Fiat and co-authors proved in 1991 both this bound and a matching lower bound of H_k for any randomized algorithm.
• Restricting the adversary. Access graph models and locality-of-reference models forbid the pathological sequence and let LRU separate from FIFO, which is what the traces show.
• Resource augmentation. Compare an online algorithm with a cache of size k to an offline optimum with a smaller cache of size h. LRU's ratio becomes k/(k - h + 1), which for h = k/2 is about 2. This is the honest formalization of the fact that a cache with room to spare behaves well.

Why this matters: when a model gives an answer you know is wrong, the productive move is to find which assumption the real world violates. Here it was the unrestricted adversary, and naming that produced three separate research programmes.

Two more, briefly

The secretary problem: n candidates arrive in random order, you learn each one's rank relative to those seen, and you must accept or reject irrevocably. The optimal policy observes the first n/e candidates, rejecting all, then accepts the first one better than everything seen. It selects the very best candidate with probability tending to 1/e, about 37 percent. Note the model difference: the arrival order is random rather than adversarial, which is why a bound better than the trivial one is possible at all.

The k-server problem generalizes paging: k servers sit in a metric space, each request is a point that some server must move to, and the cost is the distance moved. Paging is the special case where all distances are 1. The work function algorithm is known to be (2k - 1)-competitive, and whether k is achievable is one of the long-standing open problems of the field.

These models are not academic exercises. Cache eviction, spinning down a disk, when to migrate a virtual machine, and how an ad exchange allocates impressions to budgets are all decisions made without knowing what comes next, and the last of these motivated a substantial literature on online matching.

Common misconceptions

• "The competitive ratio compares against the best online algorithm." It compares against the offline optimum, which knows the whole sequence. That is what makes the number a measure of the cost of ignorance.
• "A 2-competitive algorithm is twice as slow." Competitive ratios are about the cost measure of the problem, faults or dollars or distance, not about running time.
• "Competitive analysis is average-case analysis." It is worst case over sequences, with no distribution assumed, unless the model explicitly randomizes the arrival order as the secretary problem does.
• "LRU is k-competitive, so it is a bad algorithm." Every deterministic algorithm is at best k-competitive. The bound describes the problem's difficulty against an adversary, not LRU's quality on real traces.
• "Randomization helps because the adversary cannot see the input." The adversary sees the input; it cannot see the coin flips. Against an adaptive adversary that observes the algorithm's choices as it goes, randomization gives much less.
• "Belady's rule is what a real cache should implement." It requires knowing the future. It exists as the offline benchmark that the analysis compares against, and as a ceiling for measuring real policies.

Where this leaves us

• An online algorithm answers each request before seeing the next, and c-competitive means its cost never exceeds c times the offline optimum plus a constant.
• Ski rental's break-even rule, rent until your spending equals the purchase price and then buy, is 2 - 1/B competitive, and no deterministic rule is better.
• Randomizing the purchase day improves ski rental to e/(e - 1), about 1.58, which is optimal against an oblivious adversary.
• For paging, an adversary restricted to k + 1 pages makes any deterministic algorithm fault on every request while the optimum faults once per k, so k is a lower bound.
• LRU is k-competitive by a phase argument: at most k faults per phase for LRU, at least one for the optimum, because a phase plus one more request spans k + 1 distinct pages.
• The framework's inability to separate LRU from FIFO was repaired by randomization, by restricting the adversary, and by resource augmentation, rather than by discarding it.

One constraint remains. Everything so far assumed you can store the input, even if you must respond before it ends. The last lesson removes that.

Sources

1. Sleator, D. D., & Tarjan, R. E. (1985). Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2), 202-208.
2. Belady, L. A. (1966). A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal, 5(2), 78-101.
3. Fiat, A., Karp, R. M., Luby, M., McGeoch, L. A., Sleator, D. D., & Young, N. E. (1991). Competitive paging algorithms. Journal of Algorithms, 12(4), 685-699.
4. Borodin, A., & El-Yaniv, R. (1998). Online computation and competitive analysis. Cambridge University Press. cs.technion.ac.il
5. Wikipedia contributors. (n.d.). Competitive analysis (online algorithm). en.wikipedia.org
6. Wikipedia contributors. (n.d.). Ski rental problem. en.wikipedia.org
7. Wikipedia contributors. (n.d.). K-server problem. en.wikipedia.org

In 1978 Robert Morris had a problem at Bell Labs: he needed to count events, many of them, and he had 8-bit registers to count them in. Eight bits reach 255. His solution was to stop storing the count and store its logarithm instead, incrementing the register only with probability 1 over 2 to the current value, so a register holding r represents about 2 to the r events. The estimate is unbiased, the error is controllable, and a single byte can count into the billions. It was published as a two-page note, and Philippe Flajolet later supplied the full analysis. That note is the ancestor of every algorithm in this lesson.

The model, and why it bites

A data stream is a sequence of m items arriving one at a time, from a universe of size n, which you may read once. You have space far below m and below n, usually polylogarithmic. You must answer a query at the end, or continuously.

Nothing about this is exotic. A network switch sees packets faster than it can write them to disk. A search engine sees queries faster than a machine can hold a day of them. A telescope pipeline discards most of what it captures because storing it is impossible.

The first thing to prove is that exactness is off the table. How many distinct items has the stream contained? Any algorithm answering this exactly needs Omega(n) bits in the worst case: with fewer, two different sets of already-seen items must map to the same memory state, and a suitably chosen next item makes the correct answers differ while the algorithm cannot. The same style of argument, formalized through communication complexity, underlies the lower bounds in Alon, Matias and Szegedy's 1996 work on frequency moments.

So every result below relaxes something: the answer is approximate, or it is probably right, or usually both.

Remember: in streaming you buy space by selling exactness. The engineering question is always which of the two relaxations, error and failure probability, your application can absorb.

Warm-up: majority in two words of memory

If some item appears more than m/2 times, this finds it, using one candidate and one counter:

candidate = none;  count = 0
for each item x:
    if count == 0:            candidate = x;  count = 1
    elif x == candidate:      count += 1
    else:                     count -= 1
return candidate

Why it works. Think of each decrement as destroying a pair: the incoming item and one stored copy of the candidate, which are different items. Every pair destroyed contains at most one copy of the true majority element. Since the majority element accounts for more than half the stream, it cannot be exhausted by pairing, so it must be what remains.

The catch, and it is the standard trap: if no item has a strict majority, the algorithm returns something anyway, and the something is meaningless. A second pass is needed to verify. In a strict one-pass model you cannot have that pass, which is why the generalization below reports estimates with error bars instead of a name.

Misra-Gries: k counters, error m/k

Generalize to finding all items appearing more than m/k times, the heavy hitters. Keep at most k - 1 counters, each labelled with an item.

for each item x:
    if x is labelled:              increment its counter
    elif fewer than k-1 labels:    add label x with counter 1
    else:                          decrement ALL counters by 1
                                   drop any that reach 0

The guarantee. Let c_x be the final counter for item x, or 0 if absent, and f_x its true frequency. Then

f_x - m/k   <=   c_x   <=   f_x

Proof. The upper bound is immediate, since a counter only increments on an actual occurrence. For the lower bound, count decrement rounds. Each round decrements k - 1 counters and discards the incoming item, so it accounts for k stream items in total, and the stream has m items, so there are at most m/k rounds. Each round reduces any given item's counter by at most 1. Hence no counter is short of the truth by more than m/k.

Set k = 1/epsilon and you get every frequency within epsilon m, using O(1/epsilon) counters, deterministically. Everything appearing more than epsilon m times is guaranteed to have a label at the end, which is what makes the structure useful: it produces a small candidate set with no false negatives.

Count-Min: a sketch with a probabilistic bound

Count-Min, from Cormode and Muthukrishnan in 2005, answers the same question with hashing, and unlike Misra-Gries it supports merging two sketches by simple addition, which is what a distributed system needs.

Keep a d by w table of counters and d hash functions from a universal family. On each item x, increment cell (j, h_j(x)) in every row j. To estimate f_x, take the minimum across the rows.

row 1:  [ .. ][ ..+f_x+noise.. ][ .. ]        h_1(x) = 5
row 2:  [ ..+f_x+noise.. ][ .. ][ .. ]        h_2(x) = 1
row 3:  [ .. ][ .. ][ ..+f_x+noise.. ]        h_3(x) = 9

estimate(x) = min over rows of the three cells

The analysis. Each row's cell holds f_x plus the frequencies of everything else that collided with x in that row. Since the hash is universal, any particular other item collides with probability at most 1/w, so the expected collision mass in one row is at most (m - f_x)/w, which is at most m/w. By Markov's inequality,

Pr[ noise in one row >= epsilon m ]  <=  (m/w) / (epsilon m)  =  1 / (epsilon w)

Choose w = ceiling of e/epsilon and that probability is at most 1/e. The rows use independently chosen hash functions, so the probability that every row is that noisy is at most e to the minus d. Choose d = ceiling of ln(1/delta) and it is at most delta. Since the estimate is the minimum, it exceeds f_x + epsilon m only if every row does. So with probability at least 1 - delta,

f_x  <=  estimate(x)  <=  f_x + epsilon m

Put numbers on it: epsilon = 0.001 and delta = 0.001 give w = 2,719 and d = 7, that is about 19,000 counters, or 76 KB with 32-bit counters, to estimate the frequency of any item in a stream of any length to within a tenth of a percent of the total. The universe size never appears.

The core of it: Markov on one row, independence across rows, and a minimum to combine them. That three-step pattern, from Module 2, is the entire proof.

Counting distinct items

How many distinct users visited today? Exact answers need linear space, so estimate. The idea, from Flajolet and Martin in 1985: hash each item to a uniform bit string and track the maximum number of leading zeros seen. A uniformly random string starts with r zeros with probability 2 to the minus r, so seeing r leading zeros suggests roughly 2 to the r distinct items. Hashing rather than using the item directly is what makes duplicates free: the same item always hashes to the same string, so repeats change nothing.

A single estimator of this kind is very noisy. HyperLogLog, from Flajolet and co-authors in 2007, splits the hash into a bucket index and a payload, keeps one small register per bucket, and combines them with a harmonic mean and a bias correction. Its relative standard error is about 1.04 divided by the square root of the number of registers. In Redis the implementation uses about 12 kilobytes and reports a standard error of 0.81 percent, for cardinalities up to the order of 2 to the 64. Twelve kilobytes to count billions of distinct items to within one percent is the single most striking space bound in practical computing.

Sampling instead of sketching

Sometimes you want the items themselves rather than a statistic. Reservoir sampling keeps a uniform random sample of size k from a stream of unknown length:

keep the first k items
for item i > k:
    with probability k/i, replace a uniformly random reservoir item with it

Why it is uniform. By induction, suppose after i - 1 items every item is present with probability k/(i - 1). Item i enters with probability k/i, correctly. An older item survives if either the new item is rejected, probability 1 - k/i, or it is accepted but a different reservoir slot is overwritten, probability (k/i) times (k - 1)/k. Adding these gives 1 - 1/i, and multiplying by its previous probability k/(i - 1) gives exactly k/i. The induction closes at every step, so the sample is uniform at all times, not only at the end.

Choosing among them

Two properties in that table decide most architecture arguments. Mergeability means two sketches built on different machines combine into the sketch of the union, which is what lets a hundred servers each summarize their own traffic and a coordinator add them up. And one-sidedness, an estimator that only ever overestimates or only ever underestimates, is what lets you reason about a downstream decision safely.

Common misconceptions

• "Sketches are lossy compression." They do not store the data at all, in any recoverable sense. You cannot list a Count-Min sketch's contents any more than you can list a Bloom filter's.
• "Count-Min can underestimate." It never underestimates, because collisions only add. That one-sidedness is what makes the min a safe combination rule.
• "The error is per item, so rare items are estimated well." The error term is epsilon times m, the total stream length. For an item appearing 3 times in a stream of a billion, the guarantee is worthless. Sketches are for heavy hitters.
• "More hash functions always improve accuracy." Rows control the failure probability delta; columns control the error epsilon. Adding rows to a narrow table buys confidence in a bad bound.
• "The majority algorithm finds the most frequent item." It finds a strict majority when one exists, and returns garbage otherwise. Without a verification pass its output is unusable.
• "HyperLogLog's space depends on how many distinct items there are." It is fixed by the register count, chosen for a target error. Counting a thousand or ten billion distinct items uses the same twelve kilobytes.

What you now know

• The streaming model allows one pass and sublinear space, and exact answers to even simple questions such as distinct counting need linear space, so approximation is mandatory rather than optional.
• The majority algorithm works by destroying pairs of unequal items, and generalizes to Misra-Gries, whose counters underestimate by at most m/k because each decrement round consumes k stream items.
• Count-Min hashes into d rows of w counters and reports the minimum, giving an overestimate of at most epsilon m with probability 1 - delta for w about e/epsilon and d about ln(1/delta).
• The Count-Min proof is Markov on one row plus independence across rows, the same pattern as the concentration lesson.
• HyperLogLog estimates distinct counts from the maximum number of leading zeros per bucket, reaching about 1 percent relative error in kilobytes regardless of cardinality.
• Reservoir sampling maintains an exactly uniform sample of size k, provable by a one-line induction, and mergeability plus one-sided error are the two properties that make sketches deployable.

That closes the course. Across seventeen lessons the same few moves have recurred: pay for an expensive operation in advance, replace an assumption about the input with randomness of your own, find a computable bound to compare against, and be precise about what your guarantee actually promises. Those four habits outlast any particular algorithm in this file.

Sources

1. Morris, R. (1978). Counting large numbers of events in small registers. Communications of the ACM, 21(10), 840-842.
2. Misra, J., & Gries, D. (1982). Finding repeated elements. Science of Computer Programming, 2(2), 143-152.
3. Cormode, G., & Muthukrishnan, S. (2005). An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1), 58-75.
4. Flajolet, P., Fusy, E., Gandouet, O., & Meunier, F. (2007). HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. In Proceedings of Analysis of Algorithms 2007, 137-156.
5. Vitter, J. S. (1985). Random sampling with a reservoir. ACM Transactions on Mathematical Software, 11(1), 37-57.
6. Chakrabarti, A. (2020). Data stream algorithms: lecture notes. Dartmouth College. cs.dartmouth.edu
7. Redis. (n.d.). HyperLogLog: probabilistic cardinality estimation and its standard error. Redis documentation. redis.io
8. Wikipedia contributors. (n.d.). Count-min sketch. en.wikipedia.org
9. Wikipedia contributors. (n.d.). HyperLogLog. en.wikipedia.org