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.
A trie fitted to its queries
A bounded nearest-word walk over a trie of 7,709 prefixes, measured on a stream of 2,000 misspelt vocabulary words and 600 misspelt words the vocabulary lacks: how much of the trie a stream visits, how concentrated the visits are, the distances the answers lie at, what a fixed starting bound costs against discovering it and knowing it, and a bound learned from the stream on streams that mix the two kinds of query.
The grain a corpus chooses for itself
A substitution matrix choosing its own precision from the data: the lattice that separates all six fitted costs against the grouping of costs the corpus can distinguish at two standard errors, scored against the generator's own two costs — agreement, churn between resamples, the effect of corpus size, and the threshold.
A second try before any feature
A bounded nearest-word walk over a trie of 7,709 prefixes, on streams mixing 2,000 misspelt vocabulary words with 600 misspelt words the vocabulary lacks: whether a query's first letters, length or unseen letter-triples predict its answer's distance, what a starting bound chosen per class costs against the best a feature allows in hindsight, what a schedule of two or three tries costs, and why a schedule chosen from a price list loses to a fixed one.
The classes held-out pairs cannot rule out
Choosing a substitution matrix's classes inside the fit: all 203 partitions of six substitution pairs scored by five-fold held-out likelihood, by a fixed penalty a class (AIC) and by a penalty that grows with the corpus (BIC), on corpora from 25 to 3,200 pairs drawn from a generator with two cost classes and one with a third class planted half a bit away — how often each finds the generator's classes, what a spurious split gains, and what the choices do to alignments.
A checker that stops at two edits
A spelling checker over a trie of 2,424 words, walked at one edit, then two, then at a cap C, and stopping there, on 2,000 misspellings of vocabulary words and 600 of words the vocabulary lacks, with each query's source word replayed from the stream's seed: cells a query against the cap, what each cap returns for words the vocabulary lacks, the distance to their nearest vocabulary word, what a cap of two returns by the length of the writer's word, and cells against the share of unfamiliar queries.
A cost built from two properties
Corpora from a generator whose six substitution costs are a transversion term plus a term in the difference of a number carried by each letter, fitted two ways at 25 to 3,200 sequence pairs: every partition of the pairs with the best chosen by a growing penalty, and a log-linear model with the two terms: the classes chosen, the six costs of each fit on one line, excess bits on a fresh corpus, alignments optimal under the generator's costs, and both fits on the plain two-class generator.
The triples a typo writes
A spelling checker over a trie of 2,424 vocabulary words, on 2,000 misspelt vocabulary words and 600 misspelt words the vocabulary lacks, each query declined before any walk when it carries at least one to four letter-triples no vocabulary word contains, and otherwise answered under a cap of two edits: how many unseen triples each kind of query carries, where they come from, the corrections kept against the false suggestions removed, the same by the query's length, and the work each threshold saves.
The counts only short words carry
A spelling checker over a trie of 2,424 vocabulary words, its answers capped at two edits and declined when the nearest words' combined count in a 19,279-word corpus, times a tenth for each edit, falls under a threshold: how skewed the counts are by word length, where the scores of corrections and false suggestions fall on streams drawn evenly and drawn by use, the trade at each threshold, the same by length, three weights for an edit, and every test priced in corrections given up a false suggestion removed.
A line the corpus finds
Substitution costs for a four-letter alphabet from a generator whose mismatch costs are a transversion term plus the difference of the letters' values on a graded property, fitted from corpora of 25 to 3,200 aligned pairs, sixteen seeds a size, by the two-term sum told the property, letters' positions on a line fitted freely over every order, six free classes, and the partition a growing penalty chooses: how often the fitted order is the generator's; the fitted positions against the true ones; excess bits on a fresh corpus; alignments optimal under the generator's costs; excess bits on a generator with no property; and the fitted line's length on both generators.