Correctness proofs

The **exchange argument** takes any optimal solution and gradually turns it into the greedy solution without making it worse. If that is always possible, the greedy solution is optimal too. The recipe has four steps:

1. Let O be an optimal solution and G the greedy solution; assume they differ. 2. Find the first place where they differ. 3. Exchange: change O at that place to agree with G, and show the result is still feasible and no worse. 4. Repeat; after finitely many exchanges O has become G.

For activity selection, let O be an optimal schedule sorted by finish time, and let g be the greedy interval, the earliest finish overall. If O does not start with g, replace its first interval f by g. Since g finishes no later than f, g cannot overlap the second interval of O. The schedule is still valid and still has the same number of intervals, so an optimal schedule containing g exists: the greedy-choice property.

The **staying-ahead** proof compares the greedy solution with any other solution step by step and shows that, after every step, greedy is at least as far along by a measurable amount. At the end, being as far along as possible means being optimal.

Interval covering is the cleanest example. Cover the range [0, 12] with the fewest intervals. Define the reach after k intervals as the rightmost point covered. Greedy always picks, among intervals that start no later than the current reach, the one that reaches farthest. By induction greedy's reach after k picks is at least the reach of any other selection of k intervals: the base case is trivial, and in the step any other solution's next interval starts at or before its own reach, which is at most greedy's reach, so greedy can pick an interval at least as far-reaching. When some other solution covers the whole range with k intervals, greedy's reach after k picks is at least 12 too.

Run the animation and watch the reach marker: after each pick it moves as far right as any available interval allows.

1static int minCover(int[][] iv, int from, int to) {
2    Arrays.sort(iv, Comparator.comparingInt(a -> a[0]));          // by start
3    int count = 0, reach = from, i = 0;
4    while (reach < to) {
5        int farthest = reach;
6        while (i < iv.length && iv[i][0] <= reach) farthest = Math.max(farthest, iv[i++][1]);   // all intervals that start in time
7        if (farthest == reach) return -1;                            // nothing extends the covered part: a gap
8        count++; reach = farthest;                                   // take the one that reaches farthest
9    }
10    return count;
11}

For graph problems the exchange argument takes the form of the **cut property**. A *cut* splits the vertices into two non-empty sets. Of all edges that cross the cut, the **lightest** one belongs to some minimum spanning tree (every minimum spanning tree if the lightest edge is unique).

Proof by exchange: suppose a minimum spanning tree T does not contain the lightest crossing edge e. Adding e to T creates a cycle, and that cycle must cross the cut again through another edge f, which is at least as heavy as e. Swap f for e: the result is a spanning tree no heavier than T, and it contains e.

Both algorithms in the graph lesson are applications of the cut property. Kruskal's takes the lightest edge overall that joins two different components, a cut that separates one component from the rest. Prim's grows a single tree and takes the lightest edge that leaves it, the cut between the tree and everything else. The animation shows Kruskal's sorted edge list with each accept or reject decision.

1static int kruskal(int n, int[][] edges) {                 // edges[i] = {u, v, weight}
2    Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));  // lightest first
3    int[] parent = new int[n]; for (int i = 0; i < n; i++) parent[i] = i;
4    int total = 0;
5    for (int[] e : edges) {
6        int a = find(parent, e[0]), b = find(parent, e[1]);  // component leaders of the two ends
7        if (a != b) { parent[a] = b; total += e[2]; }        // different components: keep the edge, merge them
8    }                                                         // same component: the edge would close a cycle, skip it
9    return total;
10}

A **greedy invariant** is a statement about the partial solution that is true before every iteration and, together with the loop's exit condition, implies the answer is optimal. It is the loop-invariant technique from earlier chapters applied to optimality. A typical pair for activity selection:

(1) The chosen intervals are pairwise non-overlapping and lastEnd is the finish time of the latest chosen one. (2) Every interval skipped so far overlaps a chosen interval, or is impossible to add without removing a chosen one. (3) There is an optimal solution that agrees with every choice made so far. Part (3) is the invariant the exchange argument establishes one step at a time.

Writing invariants as assert statements while developing is a cheap safety net: run the algorithm on random inputs with the checks on, and a violated invariant points at the decision that was wrong.

1static int selectWithInvariants(int[][] intervals) {
2    int[][] a = intervals.clone();
3    Arrays.sort(a, Comparator.comparingInt(x -> x[1]));
4    List<int[]> chosen = new ArrayList<>();
5    int lastEnd = Integer.MIN_VALUE;
6    for (int[] iv : a) {
7        if (iv[0] >= lastEnd) { chosen.add(iv); lastEnd = iv[1]; }
8        // invariant 1: chosen intervals are sorted and disjoint, lastEnd is the latest finish
9        for (int i = 1; i < chosen.size(); i++) {
10            if (chosen.get(i - 1)[1] > chosen.get(i)[0]) throw new AssertionError("overlap");
11        }
12    }
13    return chosen.size();
14}

Many correct greedy algorithms share one structure. A **matroid** is a ground set together with a family of *independent* sets that satisfies three rules: the empty set is independent, every subset of an independent set is independent, and if one independent set is larger than another, an element can be moved from the larger into the smaller while staying independent (the exchange property).

The payoff is a theorem: on a matroid, the greedy algorithm that scans elements in order of decreasing weight and keeps each element that preserves independence always finds a maximum-weight independent set. Kruskal's algorithm is exactly this algorithm on the *graphic matroid*, where independent sets are the edge sets without cycles. Choosing the k heaviest items is the greedy algorithm on the *uniform matroid*.

You rarely need to prove the matroid axioms in practice, but recognising the structure tells you that greedy works, and failing the exchange property tells you why it does not: the 0/1 knapsack's feasible sets, those whose total weight fits in the bag, do not satisfy it.

1// generic matroid greedy: the oracle says whether a set of element indices is independent
2static List<Integer> matroidGreedy(int[] weight, Predicate<List<Integer>> independent) {
3    Integer[] order = new Integer[weight.length];
4    for (int i = 0; i < order.length; i++) order[i] = i;
5    Arrays.sort(order, (x, y) -> weight[y] - weight[x]);     // heaviest first
6    List<Integer> chosen = new ArrayList<>();
7    for (int i : order) {
8        chosen.add(i);
9        if (!independent.test(chosen)) chosen.remove(chosen.size() - 1);
10    }
11    return chosen;
12}
13// uniform matroid of rank k: independent means size <= k, so this returns the k heaviest elements