Book contents
- Frontmatter
- Introduction
- Dedication
- Contents
- I Classroom-tested Projects
- The Game of “Take Away”
- Pile Splitting Problem: Introducing Strong Induction
- Generalizing Pascal: The Euler Triangles
- Coloring and Counting Rectangles on the Board
- Fun and Games with Squares and Planes
- Exploring Recursion with the Josephus Problem: (Or how to play “One Potato, Two Potato” for keeps)
- Using Trains to Model Recurrence Relations
- Codon Classes
- How to change coins, M&M's, or chicken nuggets: The linear Diophantine problem of Frobenius
- Calculator Activities for a Discrete Mathematics Course
- Bulgarian solitaire
- Can you make the geodesic dome?
- Exploring Polyhedra and Discovering Euler's Formula
- Further Explorations with the Towers of Hanoi
- The Two Color Theorem
- Counting Perfect Matchings and Benzenoids
- Exploring Data Compression via Binary Trees
- A Problem in Typography
- Graph Complexity
- II Historical Projects in Discrete Mathematics and Computer Science
- III Articles Extending Discrete Mathematics Content
- IV Articles on Discrete Mathematics Pedagogy
- About the Editor
A Problem in Typography
from I - Classroom-tested Projects
- Frontmatter
- Introduction
- Dedication
- Contents
- I Classroom-tested Projects
- The Game of “Take Away”
- Pile Splitting Problem: Introducing Strong Induction
- Generalizing Pascal: The Euler Triangles
- Coloring and Counting Rectangles on the Board
- Fun and Games with Squares and Planes
- Exploring Recursion with the Josephus Problem: (Or how to play “One Potato, Two Potato” for keeps)
- Using Trains to Model Recurrence Relations
- Codon Classes
- How to change coins, M&M's, or chicken nuggets: The linear Diophantine problem of Frobenius
- Calculator Activities for a Discrete Mathematics Course
- Bulgarian solitaire
- Can you make the geodesic dome?
- Exploring Polyhedra and Discovering Euler's Formula
- Further Explorations with the Towers of Hanoi
- The Two Color Theorem
- Counting Perfect Matchings and Benzenoids
- Exploring Data Compression via Binary Trees
- A Problem in Typography
- Graph Complexity
- II Historical Projects in Discrete Mathematics and Computer Science
- III Articles Extending Discrete Mathematics Content
- IV Articles on Discrete Mathematics Pedagogy
- About the Editor
Summary
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.
- Type
- Chapter
- Information
- Resources for Teaching Discrete MathematicsClassroom Projects, History Modules, and Articles, pp. 151 - 158Publisher: Mathematical Association of AmericaPrint publication year: 2009