Donald Knuth and the Art of Programming

Donald E. Knuth, photo: October 25, 2005 Flickr user Jacob Appelbaum, uploaded to en.wikipedia by users BeSherman, Duozmo, CC BY-SA 2.5, via Wikimedia Commons

On January 10, 1938, computer scientist Donald Knuth, developer of the seminal computer science textbooks ‘The Art of Computer Programming‘, was born. He is also widely known for his development of the TeX typesetting framework and the METAFONT font definition language. Actually, Donald Knuth is one of my personal heroes in computer science. The very day I started to study this subject, his textbooks had already become a sort of ‘holy bible’ when it comes to algorithms and esp. the analysis of algorithms, i.e. the very heart of theoretical computer science. However, about the person behind the seminal book, I knew almost next to nothing…

“Beware of bugs in the above code; I have only proved it correct, not tried it.”
– Donald Knuth (1977)

Youth and Education

Donald Ervin Knuth was born in Milwaukee, Wisconsin, where his father owned a small printing business and taught bookkeeping at Milwaukee Lutheran High School, where Donald enrolled, earning achievement awards. He applied his intelligence in unconventional ways, winning a contest set up by the confectionary manufacturer Ziegler when he was in eighth grade by finding over 4,500 words that could be formed from the letters in “Ziegler’s Giant Bar”. However, the judges had only about 2,500 words on their master list. This won him a television set for his school and a candy bar for everyone in his class.

At high school Knuth’s interests were more directed towards music than they were to mathematics. His musical interests involved both playing and composing music and he decided at that stage that he would study music after graduating from high school. Knuth played the saxophone, and later the tuba, in his school band. However, in 1956 he graduated from High School with the highest grade point average that anyone had ever achieved at his school. He decided to take physics as his major at Case Institute of Technology (now part of Case Western Reserve University), where he was introduced to the IBM 650 computer, one of the early mainframes. After reading the computer’s manual, he decided to rewrite the assembler and compiler code for the machine used in his school, because he believed he could do it better.

In 1958, Knuth constructed a program based on the value of each player that could help his school basketball team win the league. This was so novel a proposition at the time that it got picked up and published by Newsweek and also covered by Walter Cronkite on the CBS Evening News. Knuth was one of the founding editors of the Engineering and Science Review, which won a national award as best technical magazine in 1959. He then switched from physics to mathematics, and in 1960 he received his bachelor of science degree, simultaneously receiving his master of science degree by a special award of the faculty who considered his work outstanding. Knuth was awarded two Fellowships, a Woodrow Wilson Fellowship and a National Foundation Fellowship in the year of his graduation.[6]

Academic Career and The Art of Computer Programming

“I can’t be as confident about computer science as I can about biology. Biology easily has 500 years of exciting problems to work on. It’s at that level.”
– Donald Knuth (1993)

In the autumn of 1960 Knuth entered the California Institute of Technology and, in June 1963, he was awarded a Ph.D. in mathematics for his thesis ‘Finite semifields and projective planes‘. In fact in addition to the work for his doctorate in mathematics, Knuth had from 1960 begun to put his very considerable computing expertise to uses other than writing papers becoming a software development consultant to the Burroughs Corporation in Pasadena, California. Besides, knowledge of his computing expertise was so well established by 1962 that, although he was still a doctoral student at the time, Addison-Wesley approached him and asked him to write a text on compilers.

He began to work at CalTech as associate professor and the commission from Addyson-Wesley turned out into the writing of his seminal multivolume book ‘The Art of Computer Programming‘. This work was originally planned to be a single book, and then planned as a six- and then seven-volume series. Originally, the publisher had commissioned Knuth, who was still a master student by that time, to write a single book about compilers. However, Knuth wanted to present all the necessary knowledge on this subject in a mature form. After completing his studies, he wrote to the publisher asking permission to describe things in more detail. The first handwritten draft from 1967 comprised 3900 pages. This led to the plan to write a seven-part series covering the essential basics of computer programming. In 1968, just before he published the first volume, Knuth was appointed as Professor of Computer Science at Stanford University.

As of 2012, the first three volumes and part one of volume four of his series have been published. At the end of each chapter there is a section on history and bibliography with historical information. The exercises are divided into levels of difficulty (and marked accordingly), ranging from extremely simple (00) to the unresolved research problem (50).

TeX and METAFONT

“Science is what we understand well enough to explain to a computer. Art is everything else we do.”
– Donald Knuth (1996)

After producing the third volume of his book series in 1976, he expressed such frustration with the nascent state of the then newly-developed electronic publishing tools (especially those that provided input to phototypesetters) that he took time out to work on typesetting and created the TeX and METAFONT tools. Originally, the artwork for the book was set with the Monotype technique. This type of formula set was complex. After the publication of volume 3 in 1973, Knuth’s publisher sold its Monotype machines. The corrected new editions of Volumes 1 and 3, which appeared in 1975, had to be set in Europe, where some Monotype systems were still in use. The new edition of Volume 2 was to be produced in 1976 with phototypesetting, but the quality of the first samples disappointed Knuth. He had put 15 years of work into the series and only wanted to continue them if the books were set accordingly well. In February 1977 there was a way out when Knuth was presented with the output of a digital printing system with 1000 dpi resolution as part of a book evaluation. When Knuth realized this, he interrupted work on Volume 4, of which he had completed the first 100 pages, and decided to write the programs himself that he and his publisher needed to re-set Volume 2. TeX’s design began on May 5, 1977. METAFONT in addition to TeX, is an abstract description language for the definition of vector fonts. One of the characteristics of Metafont is that all of the shapes of the glyphs are defined with geometrical equations. In particular, one can define a given point to be the intersection of a line segment and a Bézier cubic.

In addition to Knuth’s efforts to achieve an appealing aesthetic appearance in text typesetting, correctness is his primary concern. For this reason, he gives a reward of a “hexadecimal dollar” worth $2.56 (100 hexadecimal corresponds to 256 decimal) for every newly found error in his books or programs. Very few of these checks have been cashed so far.[5] Since Knuth no longer considers checks to be safe, the coveted recognition checks have been issued since 2008 as personal deposits at the fictitious bank of San Serriffe.

Later Years

“Science is knowledge which we understand so well that we can teach it to a computer; and if we don’t fully understand something, it is an art to deal with it.”
– Donald Knuth, Computer Programming as an Art (1974)

Knuth was appointed Fletcher Jones Professor of Computer Science in 1977 and in 1990 he was named Professor of The Art of Computer Programming. In 1993 he became Professor Emeritus at Stanford University and continued to live on the University Campus.[5] Knuth has made many contributions to mathematics and computing. One particular contribution we should mention is the Knuth-Bendix algorithm, one of the fundamental algorithms for computing with algebraic structures, particularly with groups and semigroups.

In the autumn of 1999 Knuth gave six lectures at MIT on cross-connections between computer science and religion from his personal point of view as part of a series of lectures on “God and computers” held by prominent scientists over several years, and took part in a concluding panel discussion. Their notes were published in his book Things a computer scientist rarely talks about. He is a multiple honorary doctor; from 1980 to 2005 he was awarded 25 honorary doctorates, including from ETH Zurich (2005) and Eberhard Karls University of Tübingen (2001).

TeX has changed the technology of mathematics and science publishing since it enables mathematicians and scientists to produce the highest quality of printing of mathematical articles yet this can be achieved simply using a home computer. However, it has not only changed the way that mathematical and scientific articles are published but also in the way that they are communicated.[5] Knuth has been retired since 1993 to dedicate himself exclusively to the completion of The Art of Computer Programming. Since February 2011 volume 4A is available, which deals with combinatorics. Volumes 4B and 4C will follow, volume 5 (of seven planned) he hopes to finish by 2025.

Donald Knuth, The Analysis of Algorithms (2015, recreating 1969), [8]

References and Further Reading:

• [1] Donald Knuth at Mac Tutor’s History of Mathematics
• [2] Donald Knuth at wikipedia
• [3] Donald E. Knuth, The Art of Computer Programming, Volumes 1–4, Addison-Wesley Professional
• [4] Donald Knuth at zbMATH
• [5] O’Connor, John J.; Robertson, Edmund F., “Donald Knuth“, MacTutor History of Mathematics archive, University of St Andrews.
• [6] Donald Knuth at Wikidata
• [7] Scholia entry for Donald Knuth
• [8] Donald Knuth, The Analysis of Algorithms (2015, recreating 1969), stanfordonline @ youtube
• [9] Donald Ervin Knuth – Stanford Lectures (Archive)
• [10] Siobhan Roberts, The Yoda of Silicon Valley. The New York Times, 17 December 2018.
• [11] Timeline of works by Donald Knuth, via Wikidata