Algorithms & Data Structures
the bound is a claim, and it is checkable
Generator

Edit distance between kitten and sitting: 3

Rendered here at the parameters it defaults to, with every essay that calls it — which is the same list as the blast radius of changing it.
Edit distance between kitten and sitting: 3Each cell holds the distance between a prefix of kitten and a prefix of sitting. The shaded run from the top left to the bottom right is one optimal alignment; where the table has ties there are others, and this one breaks them towards the diagonal. 56 cells, 56 held at once.—sitting—kitten01234567112345672212345633212345443212345543223466543323one unit = one subproblem given a value56 cells, 56 held at once

Edit distance between kitten and sitting: 3

Each cell holds the distance between a prefix of kitten and a prefix of sitting. The shaded run from the top left to the bottom right is one optimal alignment; where the table has ties there are others, and this one breaks them towards the diagonal. 56 cells, 56 held at once.

Drawn at 700 × 330, wide on the page. Everything above is what dp-grid returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

17 essays call dp-grid. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.

Where it is called

Changing this generator changes every one of these figures.

—sitting—kitten012345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455one unit = one subproblem given a value56 cells, filled in row order When the algorithm is a table

The same table, filled two ways

 —abrocadabro—abracadabra012101221012210122112222123321233212332123321233212322one unit = one subproblem given a value54 of 144 cells, 90 skipped When the algorithm is a table

A band as wide as the answer

 01234567891011120123456789101112123456789101112123456789101112345678910123456789123456781234567123456123451234123121one unit = one subproblem given a value91 cells, 364 transitions, 4.0 per cell When the algorithm is a table

The cells are not the cost

 —agcacacggatcag—ccagggagta09101112131415161718192021229110101212141416171819192122101021011121314151718191920221110113101212141516171920192112121012411131314151718202119131312111351214131416181921211414131312146131413151719202115141514131314714151316181921161614161514141571416141719191717171517161515168151615182018171818151816161617816171519one unit = one subproblem given a value495 cells across three tables, 980 transitions When the algorithm is a table

A cell that has to know where it is

 —execution—intention87777776569888888765one unit = one subproblem given a value100 cells computed, 20 held at once The other axis

The table nobody has to keep

 01234567891011120123456789101112122332223333122222332231222222223122222233122222221222222122222122221222122121one unit = one subproblem given a value91 cells, 156 transitions, 1.7 per cell When the algorithm is a table

The argmin that cannot go backwards

 —execution—intention0136101521283645247111622293746555812172330384756649131824313948576572141925324049586673792026334150596774808527344251606875818690354352616976828791944453627077838892959754637178848993969899one unit = one subproblem given a value100 cells, filled in diagonal order When the algorithm is a table

The order that has a depth

 —gactacgat—gattacagt0123456789101234567821012345673211123456432212345554332123456543321234765443222387655432339876554333one unit = one subproblem given a value100 cells, 100 held at once The data that is not a number

A distance that is a path through a grid

 —execution—intention0123456789112345667822234567773333455678434345667854444567776555555678766666656787777776569888888765one unit = one subproblem given a value110 cells for one divide step, 30 held The other axis

The alignment that fits in one line

 —gactacgat—gattacagt112223334244352461647one unit = one subproblem given a value21 matching pairs, 21% of the rectangle When the algorithm is a table

The cells that were never worth having

 —sitting—kitten111111101111110-1111110-1-111110-1-1-11110-1-1-10110-1-1-10-11one unit = one subproblem given a value-1, 0, 1 — 3 values, 2 bits each What the machine does

A column computed in machine words

 —ttacgggacgtaccagt—acgt000000000000000000111011110111011011222101221012101112333210122101211212433321123210122221one unit = one subproblem given a value90 cells, top row zero, answer read from the last row The data that is not a number

The row that starts at zero

 01234567801234567891724303539424410182531364043111926323741122027333813212834142229152316one unit = one subproblem given a valueeach number is a storage offset, of 45 slots When the algorithm is a table

A triangle stored in a square

 SETHno algorithm for k-SAT beats exhaustive search for every korthogonal vectorsno N^(2-e) algorithmedit distanceno n^(2-e) algorithmperformed heresplit and list, checked on 55,754 formulasquoted, not performed herequoted, not performed heresolid: an implication performed here · dashed: one that is quoteda conditional floor The floors

A floor that holds if something else does

 10³10⁴capacity Wsubproblems given a valueBottom-up table · 1.00Top-down, reachable only · 0.14one unit = one subproblem given a valuesubproblems given a value, W from 200 to 3200 What is taught wrongly

A table wider than its input

 10³10⁴10⁵words in the vocabularysubproblems given a valueevery table in full · 1.16best so far · 0.99answer known · 0.96one unit = one subproblem given a valuesubproblems given a value, n from 250 to 2424 When the algorithm is a table

The bound the search finds for itself

 10³10⁴10⁵words in the vocabularysubproblems given a valueevery table in full · 1.16a trie, no bound · 0.99best so far · 0.99a trie, best so far · 0.82one unit = one subproblem given a valuesubproblems given a value, n from 250 to 2424 When the algorithm is a table

The columns the candidates share

The library, page 2 of 5 — where dp-grid sits