CMP.3:11 - SoTA-Echoing

Erickson, Algorithms, chapter 3 develops memoization, deliberate evaluation order, space saving and reconstruction of sequence-editing answers. Adopt the progression from a meaningful recurrence to distinct subproblems and their evaluation. Extend the identity question explicitly to changing inputs and effectful operations. The CAB example is a small independent derivation of that general design approach.

Hirschberg’s linear-space reconstruction is a historical but still useful counterexample to the assumption that reconstructing a sequence requires retaining a complete table. Its middle-split method also applies to edit paths. Adopt reconstruction as a choice between storage and additional calculation; do not claim its cost is optimal for every input representation or modern machine.

Current JAX checkpointing documentation shows the same storage/recomputation choice in automatic differentiation. Adopt its substantive distinction between saved intermediates and recomputed pure operations. Compiler behavior and hardware costs affect the best schedule; a particular library interface is an example of realization rather than a prerequisite of this method.

The working choice in :4.3–4.5 is between retaining all needed intermediate answers, recomputing them when requested, and retaining selected answers from which others can be reconstructed. Full retention is simpler when memory is ample and reconstruction would dominate. Recalculation avoids maintaining entries whose results are cheap or rarely reused. Selective retention pays extra scheduling or reconstruction work when it preserves the required answer under a tighter memory limit; the edit-script construction supplies one such choice. Reconsider it when effects change which calls can be shared, the recipient needs a different witness, readout costs change, or a competing reconstruction method improves the same resource trade-off.