When full-screen text editors must update the viewer’s screen across a low-capacity channel (such as an RS-232 line) it becomes worthwhile to do extra processing to compute a minimal set of terminal-update commands. Computing a minimum for a single line is termed the row-replacement problem by Myers and Miller in this clear and useful paper. They start with a simplified version of the problem and show how to solve it by dynamic programming and then build up to a complete solution using a greedy algorithm that is asymptotically faster than dynamic programming under restricted but natural assumptions.

The authors present their results in the form of programs written in a C-like language (so close to C that they could be immediately used); the algorithms could have been made clearer by replacing the long “if else if” chains with a pseudo-case statement. The paper could also have been improved by making topic transitions clearer.

The discussion of the programs, the proof that they are correct, and their analysis are all presented informally. Given the brevity of the programs, the authors had an opportunity to apply the formal techniques preached by E. W. Dijkstra and most recently debated in the Communications of the ACM. My guess is that the formal techniques were not used because they would not have contributed to the reader’s understanding. This seems to be the right choice; for the intended audience this informality makes the paper easier to understand.