An algorithm exists only relative to a contract: what counts as the input, what a valid answer is, which answers count as optimal, and which parameters a cost is stated in. Two contracts differing only in a tie rule can legitimately select different procedures.

Initialisation, preservation, and exit are the three proof obligations: the invariant is established before the loop, kept by the body, and strong enough at exit to imply the postcondition. Partial correctness still needs a separate termination argument.

A loop that preserves its invariant can still run forever. Naming a measure bounded below — typically a count of remaining candidates or unprocessed elements — turns “it finishes” into a theorem rather than a hope.

The decomposition must name the split point, the base case, and the combine step. The method pays when the subproblems are genuinely independent; overlapping subproblems are the signal for dynamic programming instead.

Each node carries the non-recursive work of one call. Summing level by level exposes whether the total is root-heavy, balanced, or leaf-heavy, which is the derivation the master theorem abbreviates.

Comparing the leaf count n^(log_b a) against the per-call work f(n) selects the case: leaves dominate, all levels equal, or root dominates. It is a bookkeeping device for the recursion-tree argument, not a substitute for it.

A number a has an inverse modulo m exactly when gcd(a, m) = 1. The extended Euclidean algorithm returns coefficients with as + mt = gcd, so s mod m is the inverse; hashing and RSA-style arithmetic both consume it.

Square on even exponents, square-and-multiply on odd ones: each bit of e costs at most two multiplications. The method is the same in any monoid — the modulus, the matrix, or the semiring is a parameter.

The argument is exhaustion: each step discards a candidate that can never pair again, so O(n) moves settle it. The precondition is monotonicity of the predicate in the pointer positions — without it the scan drops real answers.

Both ends move monotonically, so the whole scan is O(n) while recomputing the aggregate from scratch would be O(n²). The window’s aggregate must support its two updates — extend and retract — which is where the monotone-frontier structures pay.

Half-open bounds make empty ranges exact (lo == hi) and keep midpoint selection termination-safe — the overflow-safe midpoint and the never-revisit convention are what make the trace terminate. Boundary answers (first true, last false, insertion point) are all read off the same invariant.

“Can we finish within budget B?” is monotone when extra budget never breaks a feasible plan. Searching the predicate over the parameter space turns an optimisation question into O(log range) feasibility checks — the parameter must be ordered and the test honest about all constraints.

Insertion sort does exactly one swap per inversion, so its running time is Θ(n + inv) — linear on nearly-sorted input. That adaptivity is why it survives inside hybrid sorters as the small-run finisher.

There are n! permutations to separate, so h ≥ lg(n!) = Ω(n log n). The bound is about the model — comparisons only — which is exactly what radix and counting sorts step around.

The scheme’s loop invariant decides both correctness and worst cases: Lomuto is simpler but degenerates on duplicates, Hoare handles them. Pivot choice — median-of-three, random, or median-of-medians — is the only defence against adversarial input.

Heapsort builds the heap in place — O(n) by bottom-up sift-down — then extracts each maximum. The structure’s maintenance internals are the Data Structures course’s binary-heap lesson; here it is a sorting machine.

Groups of five give a pivot discarding at least 3n/10 elements, making the selection recurrence T(n) ≤ T(n/5) + T(7n/10) + O(n) = O(n). Quickselect with a random pivot is simpler and faster in practice; MoM is the deterministic guarantee.

Counting sort emits elements in arrival order within each key class, so sorting digit by digit least-significant-first composes correctly. An unstable digit pass silently scrambles the higher digits’ work.

The queue holds at most two consecutive layers, and a vertex is dequeued before any farther vertex. That is what makes the tree it produces a shortest-path tree in unweighted graphs — the claim is about unweighted edges only.

Edge classification (tree, back, forward, cross) is read off the intervals. White-path theorem and the parenthesis structure are the two lemmas nearly every DFS application consumes.

It exists iff the graph is acyclic; Kahn’s algorithm produces it by repeatedly removing zero-indegree vertices, and a leftover vertex set is the certificate of a cycle. The order is not unique — the choice among ready vertices is free.

Two DFS passes on G and G^T produce the components — the finish-order of the first pass is what makes the second pass peel SCCs in topological order. Every cyclic dependency question reduces to “is it one SCC?”

A tree edge (u, v) is a bridge exactly when low[v] > disc[u]: nothing in v’s subtree escapes back above u. The same low[] computation flags articulation points at the root and internal cases separately.

u is an ancestor of v iff tin[u] ≤ tin[v] and tout[v] ≤ tout[u] — an O(1) answer after one DFS. Lifting tables and sparse-table RMQ build on the same indexing for lowest common ancestor.

Relaxation is safe: it never makes a true distance smaller. The whole theory is ordering — on a DAG, relaxing edges in topological order settles each vertex once; that single pass is the fastest shortest-path algorithm in the course.

The argument needs non-negative weights: the extracted vertex’s distance is a shortest path because every alternative route exits the settled set through a vertex no closer. Negative edges break the proof, not the code.

A shortest path uses at most |V|−1 edges; round k settles all k-edge shortest paths. The (|V|)th pass is pure detection — the algorithm trades Dijkstra’s speed for negative-weight correctness and a cycle witness.

Floyd–Warshall permits intermediate vertices one at a time, Θ(n³) in space-conscious form. Johnson reweights with one Bellman–Ford pass so sparse graphs run n Dijkstras — the choice between them is density.

With h ≤ true remaining cost, first extraction of the goal is optimal; consistency (h(u) ≤ w(u,v) + h(v)) additionally makes reopening impossible. An inadmissible heuristic is fast and wrong — the classic trade.

Take an optimum, swap in the greedy element, and show the result is no worse: then an optimum containing the greedy choice exists, and induction finishes. The argument fails when the swap can degrade the solution — that is where DP takes over.

The exchange is direct: the first interval of any optimal schedule finishes no earlier than the greedy pick, so swapping never shrinks the schedule. Weighted and resource-constrained variants break the argument — the lesson’s counterexamples mark the boundary.

Kruskal applies it to the cut between components; Prim to the cut around the grown tree. Distinct weights make the MST unique; ties need a tie-break argument, and the property is exactly what justifies taking the cheapest crossing edge.

Huffman’s exchange: the two rarest symbols can sit as deepest siblings in an optimal tree, so merging them is safe and recursion finishes. Average length is within a bit of the entropy floor per symbol.

A state is right when the optimal-substructure and overlapping-subproblem properties both hold. Writing the recurrence is easy once the state is honest; most failed DPs are states too small to be self-contained.

Forward iteration lets item i feed the row it is already writing, silently allowing reuse — the 0/1 and unbounded knapsacks differ only in loop direction. The lesson’s counterexample trace makes the failure visible.

The table cell (i, j) is the distance between prefixes; traceback recovers the actual alignment, not just its cost. Space can drop to two rows for the value, but the alignment itself needs the table or a divide-and-conquer reconstruction.

Optimal-matrix-chain and burst-balloons style recurrences try a split point k inside [i, j]. Filling by length guarantees both halves are known before the interval is — evaluation order is the whole correctness argument.

Tree problems decompose along edges without cycles, so the recurrence’s subproblems are the children’s subtrees — one DFS fills the table. On DAGs the same trick needs memoisation since states are shared, not nested.

Memoisation visits only reachable states but pays call overhead; tabulation visits all states predictably and enables space squeezing. The lesson derives when the table can drop dimensions — when the recurrence reads only recent rows.

The bound must be safe: a prune that discards a true optimum is wrongness, not speed. State domination and symmetry breaking are the two sound prunes the lesson derives.

Unlike plain backtracking, the bounding function orders the frontier — the search can stop when the best unexplored bound cannot beat the incumbent. The guarantee is optimality; the cost is whatever the bound quality buys.

The encoding is the algorithm: clause growth, variable count, and propagation cost per decision decide whether the solver finishes. “Heuristic failed” versus “infeasible” is decided by the solver’s completeness, not by the encoding.

Backward edges are what makes greedy augmentation optimal: a path can push flow “back” around a corner. Without them, the first augmenting path could block the maximum — the residual view is the entire correctness story.

When no augmenting path exists, the reachable set from s is a cut of value exactly |f|, proving optimality. Capacity assumptions matter: integral capacities give integral flows and the Ford–Fulkerson iteration bound.

Each augmentation preserves optimality when paths are shortest in the residual graph; negative reduced costs are handled by potentials. The lesson trades the plain max-flow loop for a cost-aware one.

Berge’s theorem: a matching is maximum iff no augmenting path exists — search becomes the algorithm. In bipartite graphs the search is directed and fast; König’s theorem equates matching size and vertex cover there.

Odd cycles break the bipartite alternating search — inside a blossom the path can turn either way. Edmonds’ algorithm contracts the cycle, recurses, and expands it back: the guarantee stays a maximum matching.

The table is built on the pattern alone in O(m); the text pointer never backs up, so matching is O(n + m). The failure function is itself the border structure the prefix-function definition names.

Subtract the outgoing character’s contribution, shift the base, add the incoming one. Matches are verified exactly because fingerprint equality is probable, not certain — the verifier is what makes it a matcher rather than a guesser.

One pass of the text reports every occurrence of every pattern in O(n + total matches). The failure edges are computed breadth-first so a node’s link is always shallower — the same border idea, lifted to a tree.

Simulating all live states makes each character O(m) states — total O(nm) with no exponential blowup. The backtracking alternative in some engines can explode on adversarial patterns; the automaton’s guarantee is the point.

DEFLATE combines LZ77 matches with Huffman-coded literals and lengths; the compressed size is a bound on the parse quality. The lesson derives the factorisation cost and where the entropy bound sits.

The i-th arrival replaces a uniform resident with probability k/i, keeping the invariant at every prefix. The ledger is exact — the fairness contract holds at whatever n the stream ends at.

Deterministic two-sided bound: f̂(x) ≤ f(x) ≤ f̂(x) + n/(c+1). Every key above n/(c+1) survives as a candidate — candidacy, not certification; a verification pass makes the list honest.

Candidacy probability is S(J) = 1 − (1 − J^r)^b, a tunable S-curve: b and r place the knee at the similarity threshold. Independent tables amplify it — the probabilistic candidate contract.

k independent runs of a one-sided estimator turn failure p into p^k; the evaluation protocol reports the distribution of measured recall, not a single run. The discipline separates “the bound” from “the measurement”.

A ≤_p B plus A NP-hard makes B NP-hard; the direction is the common error — you reduce the known-hard problem to the new one. One full worked reduction anchors the lesson.

The ratio is proved against a bound on OPT — often a lower bound like a relaxation — never measured against OPT directly. Different problems have different achievable ρ; the guarantee is the product, not the heuristic.

The adversary chooses requests knowing the algorithm but not its coins — randomized algorithms get expected ratios against oblivious adversaries. Ski rental’s 2 − 1/B is the canonical derivation.

Floating-point evaluation of the determinant can give the wrong sign on near-degenerate inputs, silently inverting the algorithm’s decisions. Expansion arithmetic and filtered evaluation are the fix hierarchy.

Andrew’s monotone chain builds the hull in O(n log n) via sorted input and two passes; containment queries then binary-search the boundary. The lesson separates the point-set hull from half-plane intersection.

Closest pair needs only points within δ of the line — a constant-size candidate strip — so the sweep is O(n log n). Event points and the status invariant are the whole algorithm.

Pointwise multiplication in the transform domain is the convolution in the time domain; the butterfly recursion with roots of unity gives the O(n log n) evaluation and its inverse. Integer convolution needs rounding-care or NTT variants.

Gaussian elimination on an ill-conditioned system loses digits regardless of algorithm quality — κ(A)·ε_mach is the floor on accuracy. Pivoting fixes instability, not conditioning; the lesson separates the two failure modes.

A small step can hide a stagnant iterate; a small residual can hide a flat function near the root. The lesson prices bracketing methods’ guarantees against Newton’s speed and states which criterion certifies which claim.

Brent’s bound T_p ≤ T₁/p + T∞ prices any schedule on p processors; the scan’s two-sweep structure is the example where span and work are both derived. Associativity is the operator contract the whole argument rests on.

Binary search costs Θ(log(N/B)) probes but a B-tree costs Θ(log_B N) — the difference is what a fetched block buys. Cache-oblivious algorithms reach the same bounds without naming B or M.

Correctness is recovered only at exact stages; recall is decided at the probabilistic stage and never improves downstream. The case studies price each stage in its own counters rather than claiming a global sublinear bound.

The envelope C ≤ W/w + (1 − 1/w)·L combines total work and critical path; the case study spends it on a stated DAG, then re-derives it when a job duration is misestimated. Dependency cycles block the schedule entirely before the bound applies.

A bounded-memory pipeline is a budget split: ε, covered share, and sample size are each bought with bytes. Components sharing a stream keep private contracts; merging adds the sketch exactly, doubles the counter bound, and preserves the reservoir’s marginal.

Problem: a passed test suite does not exclude a wrong case nobody tried. Preconditions: the loop and its exit can be stated as predicates. Guarantee: initialisation + preservation + exit give partial correctness; a strictly decreasing non-negative measure gives termination. Cost: the analysis is free — it runs at proof time, not run time. Failure case: an invariant too weak to imply the postcondition, or none covering the exit path.

Problem: a recursive call’s total work is not visible in its own body. Preconditions: the recurrence is known, including how the problem shrinks. Guarantee: the level sum gives the closed form; root-heavy, balanced, and leaf-heavy each collapse to a different dominant term. Cost: counted in the unit the lesson names (comparisons, moves, multiplications). Failure case: unequal splits or data-dependent depth, where a guessed balanced bound is simply wrong.

Problem: “clean up these records” has no algorithm until the contract exists. Preconditions: none — that is the work. Guarantee: a contract makes correctness and cost checkable statements. Cost: contract choices change which procedures are even legal. Failure case: an underspecified identity rule discovered after the algorithm ships.

Problem: hashing and cryptographic arithmetic need gcd, inverses, and huge powers mod m. Preconditions: integer (or fixed-width) inputs; an inverse exists only when gcd(a, m) = 1. Guarantee: Euclid takes O(log min(a, b)) steps; exponentiation by squaring takes O(log e) multiplications. Cost: counted in multiplications of bounded integers. Failure case: fixed-width overflow inside the multiply — Python’s unbounded integers hide it, u64 does not.

Problem: a natural recursion re-solves shared subproblems exponentially often. Preconditions: subproblems are parameterisable by a small state. Guarantee: independent splits give divide-and-conquer bounds; overlapping ones give a DP whose size is the state count. Cost: the memo or table is the state space, not the recursion depth. Failure case: a “subproblem” that isn’t self-contained — it needs context the state doesn’t carry.

Problem: pairwise questions default to Θ(n²) enumeration. Preconditions: the predicate is monotone in the pointer positions — moving a pointer can only shrink the candidate set one way. Guarantee: each step discards a candidate that can never matter again, so the scan terminates with the answer or its absence. Cost: O(n) moves. Failure case: a predicate that isn’t monotone — the pointers skip real answers silently.

Problem: “longest/shortest subarray with property P” costs O(n²) evaluated per range. Preconditions: P is such that extending the window can be undone, and the aggregate supports extend and retract in O(1) amortised. Guarantee: both ends move monotonically, so the scan is linear in the sequence. Cost: one pass plus the structure’s update cost. Failure case: aggregates that can’t retract (no inverse operation) — they need a different structure.

Problem: off-by-one at range edges is where search code dies. Preconditions: a monotone predicate over a finite ordered range. Guarantee: the [lo, hi) invariant shrinks to exactly the boundary asked, with termination from strict shrinkage. Cost: O(log n) probes. Failure case: the two-boundary convention mixed with closed intervals — pick one convention and the invariant decides for you.

Problem: minimising a parameter by trial is expensive when trials are exact. Preconditions: “works at x ⇒ works at all larger x” (or the reverse) over an ordered parameter domain. Guarantee: the search returns the exact boundary value. Cost: log(range) feasibility evaluations; each evaluation must itself be correct. Failure case: a feasibility test that lies — the search then optimises the wrong problem perfectly.

Problem: a quadratic sort can beat n log n on the right input. Preconditions: input is nearly sorted (inv small) or very short. Guarantee: insertion sort runs Θ(n + inv) — linear where the comparison bound allows it. Cost: Θ(n²) worst case when inv is large. Failure case: using it blind on adversarial input; hybrid sorters keep it only for small runs.

Problem: the Θ(n log n) worst case is not the whole story. Preconditions: merge sort needs O(n) auxiliary space; quicksort needs a pivot scheme that survives hostile input. Guarantee: merge sort is Θ(n log n) always and stable; quicksort is expected Θ(n log n) with better locality. Cost: measured in comparisons and moves. Failure case: a fixed-pivot quicksort on adversarial input degrades to Θ(n²).

Problem: repeated max-extraction without full sorting cost. Preconditions: only the extremes matter per step, or the whole sort is wanted and in-place is required. Guarantee: Θ(n log n) worst case with O(1) extra space. Cost: n extractions at O(log n). Failure case: needing stability or good constants — heapsort is neither stable nor cache-friendly.

Problem: full sorting prices a question that only needs one rank. Preconditions: selection needs random access; streaming top-k needs only a heap of k. Guarantee: quickselect expected Θ(n), MoM deterministic Θ(n); the heap holds the top k exactly. Cost: much less than a sort. Failure case: believing a partial sort is free — a heap of k costs Θ(n + k log n) total.

Problem: the lower bound only governs comparison sorts. Preconditions: keys bounded (u small) or structured into O(1) digit passes. Guarantee: counting sort Θ(n + u), radix Θ(n·d/w) word passes. Cost: extra arrays and stability requirements. Failure case: u or digit count larger than assumed — the “linear” sort becomes the expensive one.

Problem: shortest-path machinery is overkill for hop counts. Preconditions: edges unweighted; source given. Guarantee: discovery order is non-decreasing distance, so first visit is shortest. Cost: O(n + m), O(n) extra. Failure case: weighted edges — BFS answers the wrong question, silently and confidently.

Problem: “is it reachable” hides the structure questions underneath. Preconditions: a graph you can afford to recurse through. Guarantee: discovery/finish intervals make ancestor and edge-class queries O(1). Cost: O(n + m) plus recursion depth risk on deep graphs. Failure case: iterative conversions that mislabel the intervals — the invariant is the encoding.

Problem: scheduling under precedence constraints. Preconditions: the constraint graph is explicit. Guarantee: a produced order respects every edge; a stuck algorithm with remaining vertices certifies a cycle. Cost: O(n + m). Failure case: treating “no schedule yet” as “no schedule exists” — the leftover set decides.

Problem: cyclic dependencies defeat schedule and optimisation passes. Preconditions: directed graph; reachability in both directions is the question. Guarantee: the condensation is a DAG — the coarsest faithful acyclic view. Cost: O(n + m). Failure case: treating one big SCC as separately solvable — the whole component is the unit.

Problem: connectivity that survives removing one edge or vertex. Preconditions: undirected connected graph (or run per component). Guarantee: low[v] > disc[u] certifies bridge (u, v) exactly. Cost: O(n + m). Failure case: the root’s separate articulation rule — it needs two children, not the low test.

Problem: per-query walks up the tree are linear each. Preconditions: a rooted tree, static across queries. Guarantee: interval tests and binary lifting are exact on any tree. Cost: O(n) or O(n log n) preprocessing, then per-query constants. Failure case: dynamic trees — the whole encoding goes stale.

Problem: the cheapest correct algorithm depends entirely on the weight contract. Preconditions: check weights and acyclicity first — both are part of the input contract. Guarantee: DAG relaxation is Θ(n + m) and exact; the others add machinery only when the weights demand it. Cost: relaxation count decides. Failure case: running Dijkstra where a negative edge lurks.

Problem: single-source shortest paths at scale. Preconditions: every weight non-negative — that is the settled-set argument’s entire premise. Guarantee: extraction order is distance order; stopping at the target is exact. Cost: Θ((n + m) log n) with a binary heap. Failure case: a negative edge makes the “final” distances wrong without error.

Problem: the weight contract forbids Dijkstra. Preconditions: directed or undirected (undirected negative edges are already negative cycles). Guarantee: after |V|−1 rounds distances are δ-exact; a further improvable edge certifies a reachable negative cycle. Cost: Θ(nm). Failure case: reporting distances when a reachable negative cycle makes them −∞.

Problem: n × n distance answers. Preconditions: Johnson needs one Bellman–Ford pass for potentials; Floyd–Warshall needs none but is Θ(n³) always. Guarantee: both exact; Johnson wins precisely when m ≪ n². Cost: Θ(n³) vs Θ(nm log n). Failure case: Floyd–Warshall’s memory at scale, or paying it on a sparse graph.

Problem: uniform-cost search wastes work away from the goal. Preconditions: a heuristic h with h ≤ true remaining cost (admissible); consistency additionally prevents reopens. Guarantee: first extraction of the goal is optimal. Cost: potentially far less than Dijkstra; a zero heuristic degenerates to it. Failure case: an inadmissible h — fast, confident, wrong.

Problem: a plausible greedy rule may be exactly wrong. Preconditions: the problem’s constraint can be stated so the exchange is checkable. Guarantee: if the swap never worsens the optimum, greedy is optimal by induction. Cost: the argument is proof-time. Failure case: the swap degrades some optimum — that counterexample is where DP starts.

Problem: maximum compatible interval set. Preconditions: equal weights, single resource, intervals comparable by finish time. Guarantee: the exchange shows any optimum admits the greedy first pick. Cost: Θ(n log n) for the sort. Failure case: weighted intervals, multiple machines, or release times — each break the exchange differently.

Problem: connect everything minimally. Preconditions: undirected, connected, weighted; distinct weights give a unique MST. Guarantee: the lightest edge across any cut is safe — both algorithms are that theorem iterated. Cost: Θ(m log n) either way; Prim’s constants win on dense graphs. Failure case: applying it to a directed or disconnected graph.

Problem: fixed-width codes waste space on skewed frequencies. Preconditions: a symbol distribution; the code must be prefix-free for streaming decode. Guarantee: the greedy merge is optimal among prefix codes by the deepest-sibling exchange. Cost: Θ(n log n) over the alphabet. Failure case: frequencies that change between encoding and decoding, or needing better-than-symbol-level entropy.

Problem: overlapping recursion explodes exponentially. Preconditions: optimal substructure plus a small state space. Guarantee: each state is solved once — correctness rides on the state being complete. Cost: states × per-state work. Failure case: a state that misses a parameter the answer depends on — every table value is then off.

Problem: pick items under a resource limit. Preconditions: capacities integral (or discretised), item set static. Guarantee: the DP is exact for the stated variant; update order separates 0/1 from unbounded. Cost: Θ(n·C) — pseudo-polynomial, so huge C is the trap. Failure case: forward iteration on 0/1 items silently permitting reuse.

Problem: diff, fuzzy match, alignment. Preconditions: operation costs defined (unit costs or weighted). Guarantee: the table is the true minimum; the path through it is a witness alignment. Cost: Θ(nm) time and space — space can be squeezed to rows, reconstruction can’t. Failure case: needing the alignment but keeping only the last row.

Problem: matrix-chain multiplication and burst-style problems whose subproblems are [i, j] ranges. Preconditions: the combine depends only on the two sides. Guarantee: length-ordered filling makes the O(n³) split search exact. Cost: Θ(n³) typical. Failure case: an interval whose split needs outside context — the state is then wrong, not the order.

Problem: structure-constrained optimisation (independent set on trees, longest path on DAGs). Preconditions: rooted tree or acyclic order available. Guarantee: each subtree/dag state computed once from its sub-states. Cost: Θ(n) states on trees. Failure case: shared substructure treated as nested — an unmemoised DAG recursion explodes.

Problem: a correct DP is too slow or too big. Preconditions: the recurrence’s dependency pattern is fully understood. Guarantee: same answers, smaller cost — the optimisations preserve semantics. Cost: analysis time. Failure case: dropping a dimension the recurrence still reads, or assuming a quadrangle inequality the costs don’t satisfy.

Problem: enumeration space is exponential but constraints kill most of it early. Preconditions: partial solutions extend incrementally; prunes provably preserve an optimum. Guarantee: complete search — infeasibility is a real answer. Cost: bound quality decides. Failure case: a prune that can drop a true optimum — then “infeasible” lies.

Problem: exact optimum wanted, runtime unknown. Preconditions: a bounding function estimating completions’ best possible value. Guarantee: when the best unexplored bound can’t beat the incumbent, the incumbent is optimal — early exit is sound. Cost: bound tightness is the runtime. Failure case: a loose bound explores nearly everything; a bound that overestimates silently loses the optimum.

Problem: hand-rolled search re-derives propagation every time. Preconditions: the problem admits a small clausal/constraint encoding. Guarantee: a complete solver’s UNSAT is a proof, not a heuristic shrug. Cost: encoding size × propagation per decision. Failure case: an encoding whose clause count itself explodes — the solver is fine, the model is the bug.

Problem: routing, assignment, or capacity-allocation phrased as flow. Preconditions: capacities on edges, a source and a sink; integral capacities give an integral optimum. Guarantee: no augmenting path ⟺ flow is maximum — the cut is the certificate. Cost: implementation-dependent; Edmonds–Karp is Θ(nm²). Failure case: irrational/real capacities where naive augmentation may not terminate.

Problem: throughput with per-unit cost (shipping with prices, assignment with costs). Preconditions: costs per edge, required flow value; potentials keep reduced costs non-negative. Guarantee: augmenting along shortest residual paths preserves optimality. Cost: shortest-path computation per augmentation. Failure case: negative cycles in the residual — they must be cancelled first.

Problem: bipartite matching or assignment. Preconditions: the bipartition is real — edges only across. Guarantee: no augmenting path ⟺ maximum matching; König gives a vertex cover of equal size as the certificate. Cost: Hopcroft–Karp Θ(√n·m); Hungarian for weighted. Failure case: general graphs — odd cycles break the directed search.

Problem: pairing in a general undirected graph. Preconditions: undirected only; weights or unweighted both have versions. Guarantee: blossom contraction preserves maximum matchings — the algorithm stays exact. Cost: Θ(n³) classical implementations. Failure case: assuming the bipartite alternating search works — an odd cycle is a silent counterexample.

Problem: matching with worst-case guarantees. Preconditions: pattern and text over the same alphabet; pattern preprocessable. Guarantee: every occurrence reported, text never rescanned. Cost: Θ(m) table, Θ(n) scan. Failure case: pattern updates invalidate the table — per-query patterns may prefer a rolling hash.

Problem: many-length-equal windows or multiple probes. Preconditions: a hash family; verification available (fingerprints are probable, not certain). Guarantee: no occurrence is missed; false positives are caught by the verifier — expected Θ(n + m). Cost: worst case degrades under adversarial hash inputs. Failure case: skipping verification — collisions then report false matches.

Problem: thousands of patterns per document (AV signatures, keyword filters). Preconditions: pattern set static enough to amortise the build. Guarantee: all matches reported in Θ(n + |matches|). Cost: build proportional to total pattern length. Failure case: patterns changing per query — the build must be paid again.

Problem: regex on untrusted or huge text where backtracking engines can explode. Preconditions: pattern compiles to an automaton; features like backreferences leave the NFA world. Guarantee: per-character simulation is exact — match iff some path accepts. Cost: Θ(m) automaton, Θ(nm) worst scan. Failure case: needing captures/backrefs — that is a different (backtracking) machine.

Problem: lossless compression of text-like data. Preconditions: repeated substrings exist — the factorisation finds them. Guarantee: decompressible exactly; the compressed size is a bound the parse earns. Cost: sliding-window match search is the work. Failure case: already-compressed or entropy-dense input — expansion instead of compression.

Problem: bounded-memory uniform sampling without knowing n. Preconditions: stream arrives once; fairness defined per position. Guarantee: the invariant is exact at every prefix — not asymptotically, exactly. Cost: Θ(n) time, Θ(k) state. Failure case: needing weighted or stratified fairness — the plain reservoir answers position-fairness only.

Problem: find keys above φn in bounded memory. Preconditions: insertions only (deletions break the decrement logic); a replay or recount for certification. Guarantee: every key above n/(c+1) survives candidacy — the protocol emits exactly the certified set. Cost: Θ(c) state. Failure case: treating candidacy as certification — false candidates are the design, not a bug.

Problem: all-pairs similarity is quadratic. Preconditions: Jaccard (or another LSH-able) similarity; the candidate contract accepts probabilistic misses. Guarantee: candidacy probability 1 − (1 − J^r)^b per table, amplified by independent tables. Cost: signature length × bands per item. Failure case: needing guaranteed recall — LSH’s misses are silent by contract.

Problem: a probabilistic answer needs a confidence, not a vibe. Preconditions: independent repetitions possible; an exact baseline exists for evaluation. Guarantee: k independent runs bound failure by p^k; evaluation reports recall distributions against ground truth. Cost: multiplicative in runs. Failure case: correlated runs — repetition of the same seed amplifies nothing.

Problem: effort is wasted optimising an NP-hard problem. Preconditions: a known-hard source problem and a valid instance map. Guarantee: A ≤_p B with A NP-hard makes B NP-hard — the reduction is the proof. Cost: the mapping must be polynomial. Failure case: reducing the wrong way (B ≤_p A proves nothing about B).

Problem: NP-hard optimisation where a fast exact answer doesn’t exist. Preconditions: a bound on OPT (relaxation, dual, structure) the argument can compare against. Guarantee: cost ≤ ρ·C* always — on every instance. Cost: the algorithm is polynomial; ρ is the price. Failure case: a “ratio” demonstrated empirically — without the bound it’s a heuristic, not an approximation.

Problem: caching, renting, scheduling where the input streams past. Preconditions: the adversary model named — oblivious for randomized algorithms. Guarantee: cost ≤ ρ·OPT + O(1) against the offline optimum. Cost: the ratio is the price of ignorance. Failure case: measuring against a non-adversarial average — the competitive claim is worst-case.

Problem: collinear or cocircular points break floating-point orientation tests. Preconditions: coordinates bounded; predicates reducible to determinant signs. Guarantee: exact or filtered evaluation gives the right sign every time. Cost: fast float first, exact arithmetic only when the filter is uncertain. Failure case: comparing rounded coordinates — wrong answers with no error raised.

Problem: hull construction or repeated inside/outside questions. Preconditions: points in the plane (higher dimensions are a different problem class). Guarantee: monotone-chain hull is exact in O(n log n); containment is O(log n) per query after it. Cost: the sort dominates. Failure case: assuming containment without the convexity the test leans on.

Problem: pairwise geometric questions over n objects. Preconditions: events sortable by x; a status structure ordered by y. Guarantee: only objects within the strip matter — the invariant discards the rest provably. Cost: O(n log n). Failure case: a status structure that can’t maintain the strip order — the sweep then scans everything.

Problem: polynomial products, signal convolutions, string-with-wildcards tricks. Preconditions: sizes padded to a power of two; rounding care for integer outputs. Guarantee: exact in the transform domain; integer convolution needs NTT or error analysis. Cost: Θ(n log n). Failure case: naive floating-point on huge integers — rounding errors corrupt the result.

Problem: linear solves where inputs carry measurement error. Preconditions: estimate κ(A) or at least detect it; pivoting for stability. Guarantee: error ≈ κ·ε_mach is the floor for any method. Cost: Θ(n³) dense elimination. Failure case: trusting a pivoted solve on an ill-conditioned A — stability ≠ conditioning.

Problem: iterative root-finding needs an exit that means something. Preconditions: a bracket (guaranteed) or a convergent scheme like Newton (fast, unbracketed). Guarantee: bracketing halves the interval — the bound is the interval width; Newton doubles digits when it converges. Cost: iterations × evaluation cost. Failure case: a small step on a stagnant iterate, or a flat function where small residual ≠ near the root.

Problem: reducing or scanning a large sequence on p processors. Preconditions: the combine operator is associative (and the scan additionally tracks order). Guarantee: T_p ≤ T₁/p + T∞; the two-sweep scan is exact. Cost: work overhead vs the sequential Θ(n). Failure case: floating-point fold is not associative — the parallel answer differs from sequential, legitimately but silently.

Problem: performance dominated by memory traffic, not compute. Preconditions: the two-level model fits (fast M, block B); tall-cache M = Ω(B²) where transpose bounds need it. Guarantee: bounds in transfers — merge sort Θ((N/B)lg(N/M)), optimal sort Θ((N/B)log_{M/B}(N/B)). Cost: redesign of data layout. Failure case: optimising comparisons while the real cost is I/O.

Problem: a DAG of jobs on a fixed fleet. Preconditions: durations known (or flagged as estimates), precedence graph acyclic — the SCC check runs first. Guarantee: C ≤ W/w + (1 − 1/w)L for any list schedule. Cost: Θ(n log n) priority list scheduling. Failure case: cycles block everything, and misestimated durations quietly move L — the study re-derives the bound after perturbation.

Problem: conjunctive queries no single structure answers. Preconditions: each stage’s contract stated; an exact scan exists to measure recall against. Guarantee: exactness is terminal — downstream stages cannot recover a candidate the index never emitted. Cost: per-stage counters; breakeven on the index build is computed in queries. Failure case: under-filling the post-filter — a shallow K returns fewer than k answers silently.

Problem: counts, heavy hitters, and a fair sample under a fixed memory cap. Preconditions: the question’s φ and error tolerances stated before the split is priced. Guarantee: each component’s contract is private — merges add the sketch exactly, double the counter bound, keep the reservoir marginal. Cost: the split is the design; degradation stays inside stated bounds. Failure case: an exact map past its silent-eviction cliff — wrongness with no flag.