When the algorithm is a table
The cost is the number of subproblems
Why a dynamic program's cost is settled before its input is touched, how a recursion graph turns an exponential into a rectangle, and what the ninth counter on this site measures.
The same table, filled two ways
What separates a memoised recursion from a bottom-up fill when the table is the same table, why the evaluation order is a decision the recurrence does not make, and where each strategy wins.
A band as wide as the answer
Ukkonen's banded dynamic program, why the guarantee is one-sided, and the measured gap between a run that has the answer and a run that can certify it.
A cost that is not one
What unit edit cost assumes, how a substitution matrix is derived from a stated mutation process rather than quoted, and the measured consequence — a finer model choosing among twenty-one alignments a coarser one cannot tell apart.
The cells are not the cost
Interval dynamic programs measured in two numbers rather than one — how many subproblems a recurrence has and what each of them costs — and why a table's shape does not reveal its class.
The zero that moves the answer out of the corner
Local alignment as a change of four lines, why its answer leaves the corner, and the statistical precondition that decides whether the region it reports is a region at all.
A cell that has to know where it is
Gotoh's construction measured — why an affine gap needs a cell to know which route it arrived by, what the one-table version silently computes instead, and the alignment it fragments.
The argmin that cannot go backwards
Knuth's monotonicity, measured — why the split point that wins for an interval cannot precede the one that wins for its left neighbour, how the ranges telescope, and what the saving depends on.
The order that has a depth
Work and span on a dynamic-programming table — how many cells a fill computes, how many rounds an order takes, and the longest chain the recurrence itself contains.
A distance divided by a length is not a rate
Why the length-normalised edit distance is a different optimisation from the edit distance, how a parametric search finds it, and what the two disagree about.
The edit that reaches back two rows
The restricted and unrestricted transposition distances, enumerated — where they disagree, why one of them is not a metric, and what a fourth transition does to a recurrence dependency structure.
The cells that were never worth having
Sparse dynamic programming on the matches alone, why the alphabet decides whether it is an improvement, and what it means that the subproblem set is a choice.
The matrix a corpus wrote
A log-odds substitution matrix estimated from corpora of aligned pairs, and what happens to optimal alignments when the corpus changes. Divergence rewrites every entry, a small corpus rewrites several, and more than half of a set of test alignments change between two plausible matrices.
The parameter plane has few answers
The optimal alignment of a fixed pair of strings over a grid of cost settings, coloured by which alignment wins. Hundreds of settings produce a handful of alignments, most of the plane is a single region, and under a linear model the boundaries are lines through the origin whose slopes can be computed by hand.
A triangle stored in a square
One interval dynamic program's reads replayed at the addresses three storage layouts and two fill orders give them. Packing saves space and changes nothing, storing by diagonal doubles the misses, and every layout converges on half its reads missing, because a cell's split scan reads a row and a column and no row-major layout can keep both close.
The split scan cut into blocks
An interval dynamic program over 16 to 256 keys, filled cell by cell in four arrangements, stored twice, and filled by a recursive fill that splits every cell's scan across blocks, each replayed through caches of 8 to 1,024 lines. Reordering whole cells stays on the half-miss floor; cutting the scans goes under it by a factor of ten on every cache from 32 lines up.
The bound the search finds for itself
The nearest word to 300 misspelt queries over vocabularies of 250 to 2,424 words from a fixed corpus of essays on algorithms, found with full tables, with a best-so-far bound in vocabulary order and in length order, and with the true distance supplied in advance. The discovered bound computes a quarter of the full tables' cells, all four strategies grow linearly with the vocabulary, and the gap to knowing the answer narrows from 2.6 times to 1.2 times as the queries carry more errors.
The ties a rounded matrix makes
The distance from each of 200 optimal alignments to its nearest tie under a fitted substitution matrix, measured along random directions in cost space, set against which alignments five refitted matrices move — with the matrices rounded to whole bits and unrounded. The distance ranks alignments by how likely a resample is to move them, and rounding creates most of the ties it finds.
The columns the candidates share
The nearest word to 300 misspelt queries, searched over a vocabulary stored as a list and as a trie, with no bound, with the best distance found so far, and with the true answer supplied. Sharing prefixes changes how the cost grows with the vocabulary rather than dividing it by a constant, and it makes the order the candidates are met in stop mattering.
The bound a block can and cannot have
The monotone bound on an interval table's best split, applied to a cache-oblivious blocked fill rather than to a cell at a time — how often each side of the bound is available, how much work it removes, and why removing work removes almost no transfers.
The lattice that decides the ties
The same substitution matrix fitted at whole, half, quarter, fifth, eighth and twentieth bits and with randomised rounding, set against how many of 200 test alignments sit on a tie and how well the distance to a tie predicts which alignments a resample moves. The grain does not order the ties; the number of distinct costs surviving it does.