Summary

This project shows how a problem in computerized typesetting can be viewed as a problem in finding the shortest path from the beginning to the end of a weighted acyclic graph. Students are shown how to construct such a graph from the diagnostic information provided by Donald Knuth's typesetting program, TEX.

Notes for the instructor

This project uses a very special case of the general Knuth-Plass algorithm in order to make it manageable. The actual algorithmas implemented in [1] is general enough to handle unjustified text and mathematical expressions, but including all of the details would turn this into a course rather than a project. This treatment emphasizes the general idea of the algorithm, so the actual formulas for such things as badness and demerits are omitted. The details can be found in [2, 5, 4, 3, 6].

Bibliography

[1] Knuth, Donald E. Computers & Typesetting, volume B. TEX: The Program, Addison-Wesley, Reading, 1986.

[2] Knuth, Donald E. The TEXbook. Addison-Wesley, Reading, third edition, 1986.

[3] Knuth, Donald E. Digital Typography, CSLI Publications, Stanford, California, 1999.

[4] Knuth, Donald E. and Michael F. Plass. “Breaking paragraphs into lines,” Software—Practice and Experience 11 (1981) 1119–1184.

[5] Salomon, David D. The Advanced TEXbook, Springer-Verlag, New York, 1995.

[6] Thomas, Larry E. “The Knuth-Plass Line-breaking Algorithm,” to appear.