Filling the DP table and recovering the alignment

Start with a route you can check by eye. Take intention, delete the i to get ntention, replace n by e to get etention, replace t by x to get exention, insert u to get exenution, and replace n by c to get execution. Five edits, each of cost 1, and the string arrives exactly where it should.

1. intention, delete i, gives ntention
2. ntention, substitute n by e, gives etention
3. etention, substitute t by x, gives exention
4. exention, insert u, gives exenution
5. exenution, substitute n by c, gives execution

SLP3 states that the unit-cost Minimum edit distance between these two words is exactly 5, so this ladder is not merely a route, it is an optimal one. The interesting question is what optimality implies about the middle rungs. Suppose exention really lies on a shortest path. Then the way we reached exention must itself be the shortest way to reach exention: if a cheaper route to exention existed, we could splice it in and get a cheaper route to execution, which contradicts the assumption that our path was shortest. Every prefix of a shortest path is a shortest path. That property is called Optimal substructure, and it is the license for Dynamic programming: instead of remembering whole edit sequences, remember the best cost for every intermediate state once, and build longer answers out of shorter ones.

The states themselves are what part 10 introduced: a pair of prefixes, the first i letters of the source and the first j letters of the target. The naive search over edit sequences explodes because thousands of different sequences pass through the same intermediate string, and each one is scored again from scratch. A table indexed by prefix pairs collapses all of those into one cell, and the Alignment you read from the table at the end is just the ladder above, laid out as a path through cells (SLP3, section 2.9.1).

Compute the top-left corner of the intention to execution table by hand, using the slide's convention where a substitution costs 2. The empty string needs nothing to become the empty string, so D[0,0] = 0. Turning the one-letter prefix i into nothing takes one deletion, D[1,0] = 1. Building e from nothing takes one insertion, D[0,1] = 1. The first interior cell compares i with e: D[1,1] = min(1 + 1, 1 + 1, 0 + 2) = 2, and all three candidates tie.

That small calculation is the whole algorithm, repeated. SLP3's pseudocode (its Fig. 2.21, reproduced on slide 88) makes it precise. Let n be the length of the source and m the length of the target, and create a matrix D with n + 1 rows and m + 1 columns, the extra row and column standing for the empty prefix. The first column is D[i,0] = D[i-1,0] + del-cost(source[i]), because the only way to turn a length-i prefix into nothing is to delete each of its letters. The first row is D[0,j] = D[0,j-1] + ins-cost(target[j]), because the only way to build a length-j prefix from nothing is to insert each letter. With unit insertion and deletion those two lines reduce to D[i,0] = i and D[0,j] = j. Then, row by row and column by column, every interior cell is the minimum of three candidates, and the answer is D[n,m].

The Edit distance recurrence looks only at three neighbors: the cell above (delete the source letter source[i], written x_i in the formula), the cell to the left (insert the target letter target[j], written y_j), and the diagonal cell (substitute one for the other, or match for free when they are equal). Nothing else in the two strings is consulted. That locality is what makes the fill order work: going row by row from the top-left, all three neighbors are already computed when you reach a cell. Any order with that property is fine, including column by column or along anti-diagonals, which is how the hover figure below animates it.

Two conventions, two right answers

Slide 86 defined a unit Substitution cost, but the table on slide 89 is SLP3's Fig. 2.20, which charges 2 for a substitution. SLP3 explains the choice: a substitution can always be simulated by one deletion and one insertion, so charging 2 makes the metric coincide with the version of Levenshtein's distance that allows only insertions and deletions. Under that convention intention to execution costs 8; under unit costs it is 5, the length of the ladder from the previous concept. Both numbers are correct in their own world, and an exam answer is correct only if it names the world it lives in.

Here is the full table from the slide with the source intention down the rows and the target execution across the columns, followed by the same table under unit costs. Compare any substitution cell: D[1,1] is 2 in the first and 1 in the second, and that one-point gap propagates until the corners read 8 and 5.

Now run the same procedure yourself. The simulator fills any pair of short words one cell at a time, prints the three candidates for each new cell, stores the arrows, and keeps both conventions side by side so you can watch the corner change from 5 to 8 with one toggle. The backtrace button belongs to the next concept; try it after reading on.

Put your finger on the 8 in the bottom-right corner of slide 91. That cell holds a single diagonal arrow, because n matches n and the free diagonal was the only candidate that reached 8. Step diagonally to (8,8), still 8, o matches o. Diagonal again to (7,7) for i, and to (6,6) for t. At (5,5) three arrows are drawn; the bold path takes the diagonal, substituting n by u for 2, which is why the value drops from 8 to 6 at (4,4). That cell has only a left arrow: insert c. Then (4,3) matches e for free, (3,2) substitutes t by x, (2,1) substitutes n by e, and (1,0) points up, deleting i, into (0,0).

Reverse the list and you have an edit sequence: delete i, n to e, t to x, match e, insert c, n to u, then four matches. Its cost is 1 + 2 + 2 + 0 + 1 + 2 + 0 + 0 + 0 + 0 = 8, the corner value, and written as rows it is SLP3's Fig. 2.17: INTE*NTION over *EXECUTION with the operation letters d s s i s under the changed columns. This is a different five-edit shape from the ladder in the first concept, yet it costs the same under both conventions, 8 here and 5 at unit costs: the ladder substitutes n by c and then inserts u, the bold path inserts c and then substitutes n by u, and both keep the four free matches at the end. The two diverge exactly at the three-arrow tie in (5,5): the left arrow leads to the ladder, the diagonal to the bold path. That is the tie rule of the next subsection in action.

The general mechanism is what slide 90 states. While filling, each cell records which of its three candidates achieved the minimum, the argmin, as a Backpointer. Up means the source letter was deleted, left means the target letter was inserted, diagonal means substitution or match. After the fill, start at D[n,m] and follow arrows until D[0,0]. SLP3 puts it in one sentence: each complete path between the final cell and the initial cell is a minimum distance Alignment. Every step decreases i, j or both, so the walk takes at most n + m steps, which is why SLP3's lecture slides list the Backtrace as O(n + m).

Ties are alternative alignments

A cell like (1,1) on slide 91 carries three arrows because three candidates reached the same minimum. SLP3 says this directly: some cells have multiple backpointers because the minimum extension could have come from multiple previous cells. Each choice at a tie leads to a different complete path, and every complete path has the same total cost, so ties are exactly the reason multiple optimal alignments exist. For intention to execution there are 134 such paths under the cost-2 convention and 7 under unit costs (both counted for this part by walking every pointer set). Erickson shows a smaller case in his textbook, ALGORITHM to ALTRUISTIC, whose table has exactly three optimal paths. Go back to the simulator, press Backtrace, then Next alignment, and watch the highlighted path change at the teal-dotted cells while the distance stays fixed.

The intention to execution table has 10 x 10 = 100 cells, and each cost a glance at three neighbors. Two documents of 100,000 characters each would need 10^10 cells, which is the scale where the accounting starts to matter and where the Stanford CS 262 notes on alignment begin their discussion of space.

Time is the easy half. There are (n + 1)(m + 1) cells, each computed in constant time from three already-known neighbors, so the fill runs in O(mn), the bound Wagner and Fischer gave in 1974 and the one Erickson states for his edit distance chapter. Space is where the choices begin. Storing the whole table, as the simulator does, also takes O(mn). But look at the recurrence again: row i reads only row i - 1 and the cells to its own left. If all you want is the distance, keep two rows, the previous one and the one being filled, and throw the rest away. Put the shorter string across the columns and the memory is O(min(m,n)), exactly what slide 92 says.

The price of that saving is the third bullet of the slide. The backpointers lived in the rows you discarded, so the two-row version cannot Backtrace. Erickson puts it plainly: by throwing away most of the table, we apparently lose the ability to walk backward. If you need the alignment as well, either keep the full table with its arrows, or recompute cleverly. Hirschberg's 1975 algorithm is the clever recomputation: run the two-row fill forward from the start and backward from the end, meet in the middle column to find which cell of that column the optimal path passes through, then recurse on the two halves. It recovers the full alignment in O(m + n) space while staying O(mn) in time; the CS 262 proof shows the constant roughly doubles, because every level of the recursion refills about half the area of the level above.

Slide 93 closes the lecture with seven lines, and they tell one story. A word is not a universal primitive, so Tokenization is a design decision rather than a fact about text. Whatever units you pick, their frequencies follow a heavy tail (Zipf for rank against frequency, Heaps for vocabulary growth), so a fixed word vocabulary always leaks unseen words, and subwords are the answer.

Morphology shows that words do have meaningful pieces, morphemes, but that segmenting them cleanly is hard and differs across languages. Unicode and UTF-8 make multilingual text representable at all, and their bytes are the universal fallback when nothing else fits. BPE then learns a compact, reusable subword vocabulary from data, with a regex pre-tokenizer doing the practical work of splitting and normalizing before it. Finally, once text has become strings of units, the Minimum edit distance table you just filled is the foundational dynamic program for saying how similar two of those strings are.

• Word is not a universal primitive; tokenization is a design decision.
• Vocabulary growth follows a heavy tail (Zipf, Heaps), which motivates subwords.
• Morphology differs across languages; morphemes are meaningful but not always easy to segment.
• Unicode and UTF-8 make multilingual text possible, and bytes are a universal fallback.
• BPE learns a compact, reusable subword vocabulary.
• Regex is the practical tool for pre-tokenization and normalization.
• Minimum edit distance is the foundational DP algorithm for string similarity.