Donald Ervin Knuth ( ) (born
January 10, 1938) is a renowned computer scientist and Professor Emeritus of the Art of Computer
Programming at Stanford University.
Author of the seminal multi-volume work
The Art of Computer
Programming ("TAOCP"), Knuth has been called the "father"
of the
analysis of
algorithms, contributing to the development of, and
systematizing formal mathematical techniques for, the rigorous
analysis of the computational complexity of algorithms, and in the
process popularizing
asymptotic
notation.
In addition to fundamental contributions in several branches of
theoretical computer
science, Knuth is the creator of the
TeX
computer typesetting system, the related
METAFONT font definition language and rendering
system, and the
Computer Modern
family of typefaces.
A prolific writer and scholar, Knuth created the
WEB/
CWEB computer programming
systems designed to encourage and facilitate
literate programming, and designed the
MMIX instruction set
architecture.
Education and academic work
Knuth was
born in Milwaukee,
Wisconsin, where his father owned a small printing business
and taught bookkeeping at Milwaukee Lutheran High
School, which he attended. He was an excellent student,
earning achievement awards. He applied his intelligence in
unconventional ways, winning a contest when he was in eighth grade
by finding over 4,500 words that could be formed from the letters
in "Ziegler's Giant Bar." This won him a television set for his
school and a candy bar for everyone in his class.
Knuth had
a difficult time choosing physics over music as his major at
Case
Institute of Technology (now part of Case Western
Reserve University). He also joined Theta Chi Fraternity. 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. At Case, he managed the basketball team and
applied his talents by constructing a formula for the value of each
player. This novel approach was covered by
Newsweek and by
Walter
Cronkite on the CBS television network.
While doing graduate studies, Knuth worked as a consultant, writing
compilers for different computers.
In 1963, he earned a Ph.D. in mathematics
(advisor: Marshall
Hall) from the California Institute of
Technology, where he became a professor and began work on
The Art of Computer
Programming, originally planned to be a single book, and
then planned as a six, and then seven-volume series. In
1968, he published the first volume.
That same year, he
joined the faculty of Stanford University, having turned down a job offer from the National
Security Agency (NSA).
In 1971, Knuth was the recipient of the first
ACM Grace Murray Hopper Award. He has
received various other awards including the
Turing Award, the
National Medal of Science, the
John von Neumann Medal and
the
Kyoto Prize. After producing the
third volume of his series in 1976, he expressed such frustration
with the nascent state of the then newly developed electronic
publishing tools (esp. those which provided input to
phototypesetters) that he took time out to work on typesetting and
created the
TeX and
METAFONT tools.
In recognition of Knuth's contributions to the field of
computer science, in 1990 he was awarded
the one-of-a-kind academic title of
Professor of The Art of
Computer Programming, which has since been revised to
Professor Emeritus of The Art of
Computer Programming.
In 1992 he became an associate of the
French Academy of Sciences.
Also that
year, he retired from regular research and teaching at Stanford
University in order to finish The Art of Computer
Programming. In 2003 he was elected as a foreign
member of the
Royal Society. , the
first three volumes of his series have been re-issued, and Knuth is
currently working on volume four, excerpts of which are released
periodically on his website.
Meanwhile, Knuth gives informal lectures a
few times a year at Stanford University, which he calls Computer Musings.
He is also
a visiting professor at the Oxford
University Computing Laboratory in the United Kingdom.
In addition to his writings on computer science, Knuth, a devout
Lutheran, is also the author of
3:16 Bible Texts
Illuminated (1991), ISBN 0-89579-252-4, in which he attempts
to examine the Bible by a process of
systematic sampling, namely an analysis
of chapter 3, verse 16 of each book. Each verse is accompanied by a
rendering in calligraphic art, contributed by a group of
calligraphers under the leadership of
Hermann Zapf.
He is also the author of
Surreal
Numbers (1974) ISBN 0-201-03812-9, a mathematical
novelette on
John Conway's
set theory construction of an alternate
system of numbers. Instead of simply explaining the subject, the
book seeks to show the development of the mathematics. Knuth wanted
the book to prepare students for doing original, creative
research.
On January 1, 1990, Knuth announced to his colleagues that he would
no longer have an e-mail address, so that he might concentrate on
his work.
In 2006, Knuth was diagnosed with
prostate cancer. He underwent surgery in
December that year and started "a little bit of radiation therapy
[...] as a precaution but the prognosis looks pretty good," as he
reported in his video autobiography.
Awards
Knuth’s humor
Knuth is known for his "professional humor".
- He used to pay a finder’s fee of $2.56 for any typographical
errors or mistakes discovered in his books, because “256
pennies is one hexadecimal dollar”,
and $0.32 for “valuable suggestions”. (His bounty for errata in
3:16 Bible Texts Illuminated, is, however, $3.16).
According
to an article in the Massachusetts
Institute of Technology’s Technology Review, these Knuth reward checks are “among
computerdom’s most prized trophies”. Knuth had to stop
sending such checks in 2008 due to bank fraud, and instead now
gives each error finder a publicly listed balance in his fictitious
"Bank of San Serriffe".
- Version numbers of his TeX software approach
the transcendental number
π, in that versions increment in the style 3,
3.1, 3.14. 3.141, and so on. Version numbers of Metafont approach the important number e similarly.
- He once warned a correspondent, “Beware of bugs in the
above code; I have only proved it correct, not tried it.”
- All appendices in the Computers and Typesetting series
have titles that begin with the letter identifying the
appendix.
- TAOCP v3 (First Edition) has the index entry “Royalties, use
of, 405”. Page 405 has no explicit mention of royalties, but
however does contain a diagram of an “organ-pipe arrangement” in
Figure 2. Apparently the purchase of the pipe organ in his home was
financed by royalties from TAOCP. (In the second edition of the
work, the relevant page is 407.)
- The preface of Concrete Mathematics includes the
following anecdote: “When Knuth taught Concrete Mathematics at Stanford for
the first time, he explained the somewhat strange title by saying
that it was his attempt to teach a math course that was hard
instead of soft. He announced that, contrary to the expectations of
some of his colleagues, he was not going to teach the Theory of
Aggregates [ Aggregate functions
or Aggregate ], not Stone's
Embedding Theorem, nor even the Stone–Čech
compactification theorem. (Several students from the civil engineering department got up and
quietly left the room.)” (Concrete and aggregates are important
topics in civil engineering.)
Knuth's "Potrzebie System of Weights
and Measures"
- Knuth published his first “scientific” article in a school
magazine in 1957 under the title “Potrzebie System of Weights and Measures.” In it,
he defined the fundamental unit of
length as the thickness of MAD magazine #26, and named the
fundamental unit of force “whatmeworry.”
MAD magazine bought the article and published it in the
#33, June 1957 issue.
- Knuth's first “mathematical” article was a short paper
submitted to a “science talent search” contest for high-school
seniors in 1955, and published in 1960, in which he discussed
number systems where the radix was negative.
He further generalized this to number systems where the radix was a
complex number. In particular, he defined the quater-imaginary base system, which
uses the imaginary number 2i as the base, having the unusual
feature that every complex number can be represented with the
digits 0, 1, 2, and 3, without a sign.
- Knuth’s article about the computational complexity of songs,
"The Complexity of
Songs", was reprinted twice in computer science journals.
- To explain the concept, Knuth intentionally referred 'Circular
definition' and 'Definition, circular' to each other in the index
of The Art of Computer
Programming Vol. 1.
Works
A short list of his works:
- Volume 1: Fundamental Algorithms (3rd edition), 1997.
Addison-Wesley Professional, ISBN 0-201-89683-4
- Volume 2: Seminumerical Algorithms (3rd Edition), 1997.
Addison-Wesley Professional, ISBN 0-201-89684-2
- Volume 3: Sorting and Searching (2nd Edition), 1998.
Addison-Wesley Professional, ISBN 0-201-89685-0
- Volume 4: Combinatorial Algorithms, in preparation
- Donald E. Knuth, The Art of Computer Programming,
fascicles:
- Volume 1, Fascicle 1: MMIX—A RISC Computer
for the New Millennium, 2005. ISBN 0-201-85392-2
- Volume 4, Fascicle 0: Introduction to Combinatorial Algorithms
and Boolean Functions. 2008. ISBN 0-321-53496-4
- Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary
Decision Diagrams. 2009. ISBN 0-321-58050-8
- Volume 4, Fascicle 2: Generating All Tuples and Permutations,
2005. ISBN 0-201-85393-0
- Volume 4, Fascicle 3: Generating All Combinations and
Partitions, 2005. ISBN 0-201-85394-9
- Volume 4, Fascicle 4: Generating All Trees—History of
Combinatorial Generation, 2006. ISBN 0-321-33570-8
- Donald E. Knuth, The TeXbook (Reading, Massachusetts:
Addison-Wesley), 1984. ISBN 0-201-13448-9
- Donald E. Knuth, The METAFONTbook (Reading, Massachusetts:
Addison-Wesley), 1986. ISBN 0-201-13444-6
- Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics: A Foundation for
Computer Science, 2nd edition (Reading, Massachusetts:
Addison-Wesley), 1994. ISBN 0-201-55802-5
- Selected papers series:
- Donald E. Knuth, Literate Programming (Center for the Study of
Language and Information — Lecture Notes), 1992. ISBN
0-937073-80-6
- Donald E. Knuth, Selected Papers on Computer Science (Stanford,
California: Center for the Study of Language and Information —
CSLI Lecture Notes, no. 59), 1996. ISBN 1-881526-91-7
- Donald E. Knuth, Digital Typography (Stanford, California:
Center for the Study of Language and Information — CSLI
Lecture Notes, no. 78), 1999. ISBN 1-57586-010-4
- Donald E. Knuth, Selected Papers on Analysis of Algorithms
(Stanford, California: Center for the Study of Language and
Information — CSLI Lecture Notes, no. 102), 2000. ISBN
1-57586-212-3
- Donald E. Knuth, Selected Papers on Computer Languages
(Stanford, California: Center for the Study of Language and
Information — CSLI Lecture Notes, no. 139), 2003. ISBN
1-57586-381-2 (cloth), ISBN 1-57586-382-0 (paperback)
- Donald E. Knuth, Selected Papers on Discrete Mathematics
(Stanford, California: Center for the Study of Language and
Information — CSLI Lecture Notes, no. 106), 2003. ISBN
1-57586-249-2 (cloth), ISBN 1-57586-248-4 (paperback)
- Donald E. Knuth, Selected Papers on Design of Algorithms
(Stanford, California: Center for the Study of Language and
Information — CSLI Lecture Notes, no. 191), 2010. ISBN
1-57586-583-1 (cloth), ISBN 1-57586-582-3 (paperback)
- Donald E. Knuth, Selected Papers on Fun and Games (publication
planned in late 2010)
- Donald E. Knuth, 3:16 Bible Texts Illuminated (Madison,
Wisconsin: A-R Editions), 1990. ISBN 0-89579-252-4
- Donald E. Knuth, Things a Computer
Scientist Rarely Talks About (Center for the Study of Language
and Information — CSLI Lecture Notes no 136), 2001. ISBN
1-57586-326-X
See also
References
External links
- Donald
Knuth’s home page at Stanford University.
- Oral history interview with Donald E. Knuth at Charles
Babbage Institute, University of Minnesota, Minneapolis. Knuth
discusses software patenting, structured programming, collaboration
and his development of TeX. The oral history
discusses the writing of The Art of Computer
Programming as well as his early education and Lutheran
heritage.
- “Love at First Byte,” Kara Platoni, with
photography by Timothy Archibald, STANFORD
Magazine, May/June 2006. A retrospective of Knuth’s life
and work, with some rare, recent photos.
- Donald Knuth: Leonard Euler of Computer Science
(Softpanorama)
- Videos of presentations w/ Donald Knuth
- The Potrzebie System of Weights and Measures
- Finite Semifields and Projective Planes -
Donald Knuth's Ph.D. dissertation
- Letter sent in February 1994 by Donald Knuth to the
Patent and Trademark Office
- Donald E. Knuth, " Algorithmic Themes", in AMS History of
Mathematics, Volume 1: A Century of Mathematics in America,
AMS, Providence, RI, 1988.
- Donald E. Knuth Knuth email
- A cartoon mentioning Donald Knuth
- Oral History of Donald Knuth
- Donald Knuth video autobiography
- Kill Yr Idols - Donald Knuth - a critique of
Donald Knuth by Adequacy.org
- Waychoff, Richard, "Stories of the B5000 and People Who Were There",
September 27, 1979. Cf. pp.6-8, "The Summer of 1960 (Time spent
with don knuth)".
Interviews and lectures
- Video of Donald Knuth's talk at Google, March 16, 2009 -
On interactions between faith and science
- TUG'95 (St Petersburg, FL, USA) Questions and answers with
Prof. Donald E. Knuth. TUGboat 17 (1), 1996
- Woehr, J. An interview with Donald Knuth Dr. Dobb's
Journal, April 1996, p. 16-22.
- Donald Knuth on The Art of Computer Programming
Addison-Wesley Innovations, 1996
- Questions and Answers with Prof. Donald E. Knuth. Czech TUG, Charles University, Prague,
1996
- Knuth meets
NTG members, Amsterdam, March 13, 1996.
- Knuth Comments on Code, Byte magazine, September 1996.
- Donald Knuth: A life's work in the art of
programming Amazon.com, 1997.
- U.K. TUG, Oxford, September 12, 1999: Question & Answer
Session with Donald Knuth. TUGboat, 22 (1/2),
2001.
- Dr. Dobb's Audio & Video Archive of Knuth's
MMIX and God & Computers Lectures @ MIT, Fall
1999
- Donald Knuth: MMIX, A RISC Computer for the New
Millennium. Audio recording of a presentation at the
monthly meeting of the Boston ACM December 30,
1999
- Wallace, Mark. The art of Don E. Knuth Interview on salon.com,
1999.
- Things A Computer Scientist Rarely Talks About - Lecture
1: Introduction, October 6, 1999
- Advogato, 2000, also available as HTML
Version
- AMS, 2001
- Oslo, 2002
- c't,
2002 (in German)
- NZZ Folio, 2002 (in German)
- Donald Knuth, Founding Artist of Computer
Science. Audio interview by David Kestenbaum on National Public Radio; or Transcript, March 14, 2005.
- Free Software Magazine interview by Gianluca
Pignalberi, August 2005.
- (Donald Knuth, telling his life story, in 2007)
- InformIT Interview by Andrew Binstock, April
2008.
- Communications of the ACM, Vol.51,7 pp.35-39, Interview,
part 1 by Len Shustek, July 2008 (An edited extract from the
2007 interview above.)