CMP.3:5 - Archetypal Grounding

CMP.3:5.1 - Obtain a sequence-editing answer without expanding repeated calls

Let D(i,j) be the smallest number of unit-cost insertions, deletions and substitutions transforming the first i characters of fixed sequence A into the first j characters of fixed sequence B. Matching characters cost zero. Then:

D(0,j) = j
D(i,0) = i
D(i,j) = min(D(i-1,j)+1,
             D(i,j-1)+1,
             D(i-1,j-1) + (0 if A[i]=B[j] else 1))

Here character positions start at 1. Each alternative identifies the last edit or match. Removing it leaves the corresponding smaller problem; adding it to a best smaller answer supplies a candidate for the whole prefix. Thus the minimum covers the possible last steps.

Naively unfolding this recurrence repeatedly requests the same prefix pairs. Within one fixed pair of sequences and one cost rule, use (i,j) as the key. Dependencies have smaller i+j, so increasing rows and then columns gives a valid order.

For A=CAB and B=AB, the complete table is:

The result is 1; deleting the initial C attains it. There are (m+1)(n+1) states for lengths m,n, with constant work per interior state under constant-cost character comparison and small-integer arithmetic. Full retention uses O(mn) cells. If only the distance is required, the preceding and current row suffice, giving O(n) working cells.

Changed output: the recipient now needs an edit script. The final distance and two surviving rows do not supply the deleted path. One repair stores a minimizing predecessor for each cell and traces back from (m,n). Another computes forward and backward costs to a middle row, chooses a column minimizing their sum, and recursively reconstructs the two halves. Every edit path crosses that row, which justifies the split. This second construction exchanges recomputation for storage; CMP.2 supplies the recursive decomposition. Neither choice alters the meaning of an allowed edit.

Changed reuse scope: for A=CB, B=AB, the value at (2,2) is 1; for A=CA, B=AB, it is 2. A global cache keyed only by (i,j) would conflate them. Restrict the cache to a fixed input pair or include the input identity and relevant conditions.

CMP.3:5.2 - Share an expression while preserving its interpretation

For f(x,y)=(x+y)*(x+y)+(x+y), build one node t=x+y with three uses, then obtain t*t+t. With x=2,y=3, the result is 30. This replaces three additions of x+y by one and shares its stored value until the final addition.

If y changes to 4, t and its consumers must change; the result becomes 42. If each occurrence instead meant “read the next measurement and add x,” the shared expression would change the computation’s meaning. The subproblem must be a fixed pure addition of supplied values for this identification to hold.

In differentiation of a longer expression graph, intermediate values may be needed again in reverse order. Keeping all of them can exceed memory. Retain selected restart values and recompute intervening pure operations when needed, comparing the extra work with reduced storage. This applies the same method to a different receiving algorithm.