Donald Ervin Knuth Biography

American mathematician and computer scientist Donald Ervin Knuth is widely considered one of the world's leading computer scientists, and he is best known for writing the authoritative "Bible" of computer programming: The Art of Computer Programming. Knuth first demonstrated his ability to recognize and manipulate patterns when he formed 4,500 different words from a local candy maker's brand name, thus winning first prize in an eighth-grade contest. Knuth was more interested in composing and playing music than in the sciences in high school. However, upon graduation with the school's highest grade-point-average, Knuth was offered a physics scholarship at Case Institute of Technology (now Case Western Reserve), and during his freshman year in 1956 he encountered his first computer, an IBM-650. Knuth taught himself the basic program from the manual, and soon was writing better programs than the manual's examples. Knuth's accomplishment was featured in Newsweek magazine, and later appeared in IBM-650 manuals. Knuth turned toward mathematics during his sophomore year when a professor assigned a difficult problem whose solution would give an immediate "A" in the class. Knuth quickly solved the problem and skipped class for the rest of the semester. Knuth graduated summa cum laude from Case Institute of Technology (B.S. and M.S., 1960), and California Institute of Technology (Ph.D., 1963).

During Knuth's illustrious career he specialized in five major areas: (1) compilers, (2) attribution grammar, (3) algorithms, (4) digital mathematical typography, and (5) structured documentation and literate programming.

Compilers are intermediate languages that translate between a higher-level language and the binary machine language. During the early 1960s Knuth did pioneering work in composing new compilers, an extremely difficult task at that time. His best-known effort in this area was the development of "parsing," a method that breaks input into grammatical rules so that a program can more easily act upon it. His theoretical work led to the parser generators that power almost all modern compilers. His 3,000-page draft eventually turned into his most-famous work about algorithms.

Knuth's next project involved delineating what does or does not constitute a programming language; in other words, what exactly is meant by "programming language." He found an economical way to associate rules of interpretation, what he called "attribution rules," thus founding at the same time a sub-field of computer science called attribution grammar.

Perhaps Knuth's most original contribution to the field of computer science was his monumental work on the analysis of algorithms, which was an offshoot of his work with compilers (as mentioned earlier). An algorithm is the most basic set of instructions written into a program in order to perform a particular task, such as sorting or searching. In coordination with one of his graduate students at California School of Technology, Knuth developed the Knuth-Bendix algorithm for exploring the consequences of mathematical axioms. In 1968 while at Stanford, Knuth and one of his students developed the Knuth-Morris-Pratt algorithm that streamlined the process by which a computer searches for a string of characters within a text. Published during the period from 1968 to 1976, The Art of Computer Programming (TAOCP) is (so far) a three-volume book that summarizes and mathematically analyzes the practice and science of programming algorithms for sequential computers. It is a standard reference on every good programmer's bookshelf. Indeed, in a 1995 interview, Microsoft founder Bill Gates said that in order to be "a really good programmer" one must read its first volume and solve all of its problems before sending his company a resume. According to Knuth, The Art of Computer Programming is his life's major work, and says that his intention is "to organize and summarize what is known about the fast subject of computer methods and to give it firm mathematical and historical foundations."

In the introduction to an early article on digital mathematical typography, Knuth wrote, "Mathematical books and journals do not look as beautiful as they used to." He had become annoyed with the declining quality of the typesetting programs available for printing his work, so Knuth took ten years off from writing his (intended) seven-volume TAOCP to develop digital typography. During that time he created two software systems that are used today in a majority of the world's scientific publications--and he wrote five books to explain them. The systems grew into the TeX document compiler (for complete control in document typesetting of scientific publishing), and the METAFONT character compiler (for alphabet design and font generation). TeX (taken from the Greek term for "art") uses text-embedded codes to initiate changes in layout including the ability to describe scientific formulas.

Knuth's typography work led him to develop two languages, one for the structured documentation of programs, and another for a parallel methodology called literate programming. This combination of two separate languages, WEB and CWEB, for document formatting and programming, enabled programmers to simultaneously create two different system routines; one for people that clearly describes the program, and one for machines that produces an easily executable program. Knuth specifically wrote these languages to further his goal of making programming understandable, and even "beautiful" for readers

Knuth taught mathematics at the California Institute of Technology from 1962 until 1968, when he joined the faculty at the computer science and electrical engineering department at Stanford University. He was endowed with the university's first chair in computer science nine years later (1977). In 1993 he became Professor Emeritus at Stanford. His writings include Surreal Numbers (1974), Literate Programming (1992), and Digital Typography (1999). He has published at least 17 books and over 150 papers on subjects ranging from computer science to Babylonian algorithms, biblical research, and the history of the letter "s."

Among the many awards and honors that Knuth has received are the 1974 Turing Award, the 1979 National Medal of Science, and the 1996 Kyoto Prize. He is a National Academy of Sciences member. He has more recently returned to composing the fourth volume of TAOCP. In 1999 The Art of Computer Programming was named among the best twelve scientific books of the century by American Scientist magazine.