Donald Knuth

Donald Knuth

Overview
Donald Ervin Knuth is a computer scientist
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

 and Professor Emeritus at Stanford University
Stanford University
The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is a private research university on an campus located near Palo Alto, California. It is situated in the northwestern Santa Clara Valley on the San Francisco Peninsula, approximately northwest of San...

.

He is the author of the seminal multi-volume work The Art of Computer Programming
The Art of Computer Programming
The Art of Computer Programming is a comprehensive monograph written by Donald Knuth that covers many kinds of programming algorithms and their analysis....

. Knuth has been called the "father" of the analysis of algorithms
Analysis of algorithms
To analyze an algorithm is to determine the amount of resources necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length...

. He contributed to the development of the rigorous analysis of the computational complexity of algorithms and systematized formal mathematical techniques for it. In the process he also popularized the asymptotic notation
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...

.

In addition to fundamental contributions in several branches of theoretical computer science
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....

, Knuth is the creator of the TeX
TeX
TeX is a typesetting system designed and mostly written by Donald Knuth and released in 1978. Within the typesetting system, its name is formatted as ....

 computer typesetting system, the related METAFONT
METAFONT
Metafont is a programming language used to define vector fonts. It is also the name of the interpreter that executes Metafont code, generating the bitmap fonts that can be embedded into e.g. PostScript...

 font definition language and rendering system, and the Computer Modern
Computer Modern
Computer Modern is the family of typefaces used by default by the typesetting program TeX. It was created by Donald Knuth with his METAFONT program, and was most recently updated in 1992. However, the family font was superseded by CM-Super , the latest release dating 2008...

 family of typefaces.

As a writer and scholar, Knuth created the WEB
WEB
WEB is a computer programming system created by Donald E. Knuth as the first implementation of what he called "literate programming": the idea that one could create software as works of literature, by embedding source code inside descriptive text, rather than the reverse , in an order that is...

/CWEB
CWEB
CWEB is a computer programming system created by Donald Knuth and Silvio Levy as a follow up to Knuth's WEB literate programming system, using the C programming language instead of Pascal....

 computer programming systems designed to encourage and facilitate literate programming
Literate programming
Literate programming is an approach to programming introduced by Donald Knuth as an alternative to the structured programming paradigm of the 1970s....

, and designed the MIX
MIX
MIX is a hypothetical computer used in Donald Knuth's monograph, The Art of Computer Programming . MIX's model number is 1009, which was derived by combining the model numbers and names of several contemporaneous, commercial machines deemed significant by the author...

/MMIX
MMIX
MMIX is a 64-bit RISC instruction set architecture designed by Donald Knuth, with significant contributions by John L. Hennessy and Richard L. Sites...

 instruction set architectures
Instruction set
An instruction set, or instruction set architecture , is the part of the computer architecture related to programming, including the native data types, instructions, registers, addressing modes, memory architecture, interrupt and exception handling, and external I/O...

.

Knuth was born in Milwaukee, Wisconsin
Wisconsin
Wisconsin is a U.S. state located in the north-central United States and is part of the Midwest. It is bordered by Minnesota to the west, Iowa to the southwest, Illinois to the south, Lake Michigan to the east, Michigan to the northeast, and Lake Superior to the north. Wisconsin's capital is...

, where his father owned a small printing business and taught bookkeeping at Milwaukee Lutheran High School
Milwaukee Lutheran High School
Milwaukee Lutheran High School is a secondary school located in Milwaukee, Wisconsin. The school was originally known as Lutheran High School . LHS was established in 1903, making Milwaukee Lutheran an offshoot of the oldest Lutheran high school in America...

, where he enrolled, earning achievement awards.
Discussion
Ask a question about 'Donald Knuth'
Start a new discussion about 'Donald Knuth'
Answer questions from other users
Full Discussion Forum
 
Unanswered Questions
Quotations

The whole thing that makes a mathematician’s life worthwhile is that he gets the grudging admiration of three or four colleagues.

Jack Woehr. An interview with Donald Knuth. Dr. Dobb's Journal, pages 16-22 (April 1996)

A mathematical formula should never be "owned" by anybody! Mathematics belong to God.

Digital Typography, ch. 1, p. 8 (1999)

I define UNIX as 30 definitions of regular expressions living under one roof.

Digital Typography, ch. 33, p. 649 (1999)

I can’t go to a restaurant and order food because I keep looking at the fonts on the menu.

Encyclopedia
Donald Ervin Knuth is a computer scientist
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

 and Professor Emeritus at Stanford University
Stanford University
The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is a private research university on an campus located near Palo Alto, California. It is situated in the northwestern Santa Clara Valley on the San Francisco Peninsula, approximately northwest of San...

.

He is the author of the seminal multi-volume work The Art of Computer Programming
The Art of Computer Programming
The Art of Computer Programming is a comprehensive monograph written by Donald Knuth that covers many kinds of programming algorithms and their analysis....

. Knuth has been called the "father" of the analysis of algorithms
Analysis of algorithms
To analyze an algorithm is to determine the amount of resources necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length...

. He contributed to the development of the rigorous analysis of the computational complexity of algorithms and systematized formal mathematical techniques for it. In the process he also popularized the asymptotic notation
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...

.

In addition to fundamental contributions in several branches of theoretical computer science
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....

, Knuth is the creator of the TeX
TeX
TeX is a typesetting system designed and mostly written by Donald Knuth and released in 1978. Within the typesetting system, its name is formatted as ....

 computer typesetting system, the related METAFONT
METAFONT
Metafont is a programming language used to define vector fonts. It is also the name of the interpreter that executes Metafont code, generating the bitmap fonts that can be embedded into e.g. PostScript...

 font definition language and rendering system, and the Computer Modern
Computer Modern
Computer Modern is the family of typefaces used by default by the typesetting program TeX. It was created by Donald Knuth with his METAFONT program, and was most recently updated in 1992. However, the family font was superseded by CM-Super , the latest release dating 2008...

 family of typefaces.

As a writer and scholar, Knuth created the WEB
WEB
WEB is a computer programming system created by Donald E. Knuth as the first implementation of what he called "literate programming": the idea that one could create software as works of literature, by embedding source code inside descriptive text, rather than the reverse , in an order that is...

/CWEB
CWEB
CWEB is a computer programming system created by Donald Knuth and Silvio Levy as a follow up to Knuth's WEB literate programming system, using the C programming language instead of Pascal....

 computer programming systems designed to encourage and facilitate literate programming
Literate programming
Literate programming is an approach to programming introduced by Donald Knuth as an alternative to the structured programming paradigm of the 1970s....

, and designed the MIX
MIX
MIX is a hypothetical computer used in Donald Knuth's monograph, The Art of Computer Programming . MIX's model number is 1009, which was derived by combining the model numbers and names of several contemporaneous, commercial machines deemed significant by the author...

/MMIX
MMIX
MMIX is a 64-bit RISC instruction set architecture designed by Donald Knuth, with significant contributions by John L. Hennessy and Richard L. Sites...

 instruction set architectures
Instruction set
An instruction set, or instruction set architecture , is the part of the computer architecture related to programming, including the native data types, instructions, registers, addressing modes, memory architecture, interrupt and exception handling, and external I/O...

.

Early education


Knuth was born in Milwaukee, Wisconsin
Wisconsin
Wisconsin is a U.S. state located in the north-central United States and is part of the Midwest. It is bordered by Minnesota to the west, Iowa to the southwest, Illinois to the south, Lake Michigan to the east, Michigan to the northeast, and Lake Superior to the north. Wisconsin's capital is...

, where his father owned a small printing business and taught bookkeeping at Milwaukee Lutheran High School
Milwaukee Lutheran High School
Milwaukee Lutheran High School is a secondary school located in Milwaukee, Wisconsin. The school was originally known as Lutheran High School . LHS was established in 1903, making Milwaukee Lutheran an offshoot of the oldest Lutheran high school in America...

, where he enrolled, 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." 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.

Education


Knuth had a difficult time choosing physics over music as his major at Case Institute of Technology
Case Western Reserve University
Case Western Reserve University is a private research university located in Cleveland, Ohio, USA...

 (now part of Case Western Reserve University
Case Western Reserve University
Case Western Reserve University is a private research university located in Cleveland, Ohio, USA...

). He also joined Beta Nu Chapter of the Theta Chi fraternity. While studying physics at the Case Institute of Technology, Knuth was introduced to the IBM 650
IBM 650
The IBM 650 was one of IBM’s early computers, and the world’s first mass-produced computer. It was announced in 1953, and over 2000 systems were produced between the first shipment in 1954 and its final manufacture in 1962...

, one of the early mainframe
Mainframe
Mainframe may refer to either of the following:* Mainframe computer, large and powerful data processing systems* Mainframe Entertainment, a Canadian computer animation and design company* Mainframe , a 1980s Electropop band...

s. After reading the computer's manual, Knuth decided to rewrite the assembly 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
Newsweek
Newsweek is an American weekly news magazine published in New York City. It is distributed throughout the United States and internationally. It is the second-largest news weekly magazine in the U.S., having trailed Time in circulation and advertising revenue for most of its existence...

 and also covered by Walter Cronkite
Walter Cronkite
Walter Leland Cronkite, Jr. was an American broadcast journalist, best known as anchorman for the CBS Evening News for 19 years . During the heyday of CBS News in the 1960s and 1970s, he was often cited as "the most trusted man in America" after being so named in an opinion poll...

 on the CBS Evening News
CBS Evening News
CBS Evening News is the flagship nightly television news program of the American television network CBS. The network has broadcast this program since 1948, and has used the CBS Evening News title since 1963....

. 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.

In 1963, he earned a Ph.D. in mathematics (advisor: Marshall Hall
Marshall Hall (mathematician)
Marshall Hall, Jr. was an American mathematician who made contributions to group theory and combinatorics.- Career :...

) from the California Institute of Technology
California Institute of Technology
The California Institute of Technology is a private research university located in Pasadena, California, United States. Caltech has six academic divisions with strong emphases on science and engineering...

, and began to work there as associate professor and began work on The Art of Computer Programming
The Art of Computer Programming
The Art of Computer Programming is a comprehensive monograph written by Donald Knuth that covers many kinds of programming algorithms and their analysis....

. He had initially accepted a commission to write a book on compilers which would later become the multi-volume 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. In 1968, he published the first volume. That same year, he joined the faculty of Stanford University
Stanford University
The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is a private research university on an campus located near Palo Alto, California. It is situated in the northwestern Santa Clara Valley on the San Francisco Peninsula, approximately northwest of San...

, having turned down a job offer from the National Security Agency
National Security Agency
The National Security Agency/Central Security Service is a cryptologic intelligence agency of the United States Department of Defense responsible for the collection and analysis of foreign communications and foreign signals intelligence, as well as protecting U.S...

 (NSA).

The Art of Computer Programming (TAOCP)



Computer science was then taking its first, hesitant steps. “It was a totally new field”, Knuth recalls, “with no real identity. And the standard of available publications was not that high (…). A lot of the papers coming out were quite simply wrong. (…) So one of my motivations was to put straight a story that had been very badly told”.

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 (especially those that provided input to phototypesetters) that he took time out to work on typesetting and created the TeX
TeX
TeX is a typesetting system designed and mostly written by Donald Knuth and released in 1978. Within the typesetting system, its name is formatted as ....

 and METAFONT
METAFONT
Metafont is a programming language used to define vector fonts. It is also the name of the interpreter that executes Metafont code, generating the bitmap fonts that can be embedded into e.g. PostScript...

 tools.

, the first three volumes and part 1 of volume four of his series have been published.

Other works


He is also the author of Surreal Numbers, a mathematical novelette on John Conway
John Horton Conway
John Horton Conway is a prolific mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory...

's set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...

 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.

Religious beliefs and work


In addition to his writings on computer science, Knuth, a Lutheran, is also the author of 3:16 Bible Texts Illuminated, in which he examines the Bible by a process of systematic sampling
Systematic sampling
Systematic sampling is a statistical method involving the selection of elements from an ordered sampling frame. The most common form of systematic sampling is an equal-probability method, in which every kth element in the frame is selected, where k, the sampling interval , is calculated as:k =...

, 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
Hermann Zapf
Hermann Zapf is a German typeface designer who lives in Darmstadt, Germany. He is married to calligrapher and typeface designer Gudrun Zapf von Hesse....

.

No email


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.

Health concerns


In 2006, Knuth was diagnosed with prostate cancer
Prostate cancer
Prostate cancer is a form of cancer that develops in the prostate, a gland in the male reproductive system. Most prostate cancers are slow growing; however, there are cases of aggressive prostate cancers. The cancer cells may metastasize from the prostate to other parts of the body, particularly...

. 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.

Computer Musings


Knuth gave informal lectures a few times a year at Stanford University
Stanford University
The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is a private research university on an campus located near Palo Alto, California. It is situated in the northwestern Santa Clara Valley on the San Francisco Peninsula, approximately northwest of San...

, which he called Computer Musings. He was also a visiting professor at the Oxford University Computing Laboratory
Oxford University Computing Laboratory
The Department of Computer Science, until 2011 named the Computing Laboratory , is a department of Oxford University in England...

 in the United Kingdom
United Kingdom
The United Kingdom of Great Britain and Northern IrelandIn the United Kingdom and Dependencies, other languages have been officially recognised as legitimate autochthonous languages under the European Charter for Regional or Minority Languages...

 and an Honorary Fellow of Magdalen College
Magdalen College, Oxford
Magdalen College is one of the constituent colleges of the University of Oxford in England. As of 2006 the college had an estimated financial endowment of £153 million. Magdalen is currently top of the Norrington Table after over half of its 2010 finalists received first-class degrees, a record...

.

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
    Hexadecimal
    In mathematics and computer science, hexadecimal is a positional numeral system with a radix, or base, of 16. It uses sixteen distinct symbols, most often the symbols 0–9 to represent values zero to nine, and A, B, C, D, E, F to represent values ten to fifteen...

     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
    Massachusetts Institute of Technology
    The Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...

    's Technology Review, these Knuth reward check
    Knuth reward check
    Knuth reward checks are awarded by computer scientist Donald Knuth for finding mistakes in, or making suggestions for, his publications. In the preface of each of his books and on his website, Knuth offers a reward of $2.56 to the first person to find each error in his published books, whether it...

    s are "among computerdom's most prized trophies". Knuth had to stop sending real checks in 2008 due to bank fraud, and instead now gives each error finder a "certificate of deposit" from a publicly listed balance in his fictitious "Bank of San Serriffe
    San Serriffe
    San Serriffe is a fictional island nation created for April Fools' Day, 1977, by Britain's Guardian newspaper. An elaborate description of the nation, using puns and plays on words relating to typography , was reported as legitimate news, apparently fooling many readers...

    ".
  • Version numbers of his TeX
    TeX
    TeX is a typesetting system designed and mostly written by Donald Knuth and released in 1978. Within the typesetting system, its name is formatted as ....

     software approach the number π
    Pi
    ' is a mathematical constant that is the ratio of any circle's circumference to its diameter. is approximately equal to 3.14. Many formulae in mathematics, science, and engineering involve , which makes it one of the most important mathematical constants...

    , in that versions increment in the style 3, 3.1, 3.14. 3.141, and so on. Similarly, version numbers of Metafont
    METAFONT
    Metafont is a programming language used to define vector fonts. It is also the name of the interpreter that executes Metafont code, generating the bitmap fonts that can be embedded into e.g. PostScript...

     approach the base of the natural logarithm
    Natural logarithm
    The natural logarithm is the logarithm to the base e, where e is an irrational and transcendental constant approximately equal to 2.718281828...

    , e
    E (mathematical constant)
    The mathematical constant ' is the unique real number such that the value of the derivative of the function at the point is equal to 1. The function so defined is called the exponential function, and its inverse is the natural logarithm, or logarithm to base...

    .
  • 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
    Computers and Typesetting
    Computers and Typesetting is a 5-volume set of books by Donald Knuth published 1986 describing the TeX and Metafont systems for digital typography. Knuth's computers and typesetting project was the result of his frustration with the lack of decent software for the typesetting of mathematical and...

     series have titles that begin with the letter identifying the appendix.
  • The Art of Computer Programming, volume 3 (1st ed.) has an index entry "Royalties, use of, 405". Page 405 has no explicit mention of royalties, but does contain a diagram of an "organ-pipe arrangement". Apparently the purchase of the pipe organ in his home was financed by royalties from the book. (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
    Concrete Mathematics
    Concrete Mathematics: A Foundation for Computer Science, by Ronald Graham, Donald Knuth, and Oren Patashnik, is a mathematical textbook that is widely used in computer-science departments. It provides mathematical knowledge and skills for computer science, especially for the analysis of algorithms...

     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 function
    In computer science, an aggregate function is a function where the values of multiple rows are grouped together as input on certain criteria to form a single value of more significant meaning or measurement such as a set, a bag or a list....

    , nor Stone's Embedding Theorem, nor even the Stone–Čech compactification
    Stone–Cech compactification
    In the mathematical discipline of general topology, Stone–Čech compactification is a technique for constructing a universal map from a topological space X to a compact Hausdorff space βX...

     theorem. (Several students from the civil engineering
    Civil engineering
    Civil engineering is a professional engineering discipline that deals with the design, construction, and maintenance of the physical and naturally built environment, including works like roads, bridges, canals, dams, and buildings...

     department got up and quietly left the room.)"

  • Knuth published his first "scientific" article in a school magazine in 1957 under the title "Potrzebie
    Potrzebie
    Potrzebie is a Polish word popularized by its non sequitur use as a running gag in the early issues of Mad not long after the comic book began in 1952...

     System of Weights and Measures." In it, he defined the fundamental unit
    Fundamental unit
    A set of fundamental units is a set of units for physical quantities from which every other unit can be generated.In the language of measurement, quantities are quantifiable aspects of the world, such as time, distance, velocity, mass, momentum, energy, and weight, and units are used to describe...

     of length
    Length
    In geometric measurements, length most commonly refers to the longest dimension of an object.In certain contexts, the term "length" is reserved for a certain dimension of an object along which the length is measured. For example it is possible to cut a length of a wire which is shorter than wire...

     as the thickness of Mad
    Mad (magazine)
    Mad is an American humor magazine founded by editor Harvey Kurtzman and publisher William Gaines in 1952. Launched as a comic book before it became a magazine, it was widely imitated and influential, impacting not only satirical media but the entire cultural landscape of the 20th century.The last...

     #26, and named the fundamental unit of force
    Force
    In physics, a force is any influence that causes an object to undergo a change in speed, a change in direction, or a change in shape. In other words, a force is that which can cause an object with mass to change its velocity , i.e., to accelerate, or which can cause a flexible object to deform...

     "whatmeworry." Mad published the article in issue #33 (June 1957).
  • 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
    Radix
    In mathematical numeral systems, the base or radix for the simplest case is the number of unique digits, including zero, that a positional numeral system uses to represent numbers. For example, for the decimal system the radix is ten, because it uses the ten digits from 0 through 9.In any numeral...

     was negative. He further generalized this to number systems where the radix was a complex number. In particular, he defined the quater-imaginary base
    Quater-imaginary base
    The quater-imaginary numeral system was first proposed by Donald Knuth in 1955, in a submission to a high-school science talent search. It is a non-standard positional numeral system which uses the imaginary number 2i as its base. It is able to uniquely represent every complex number using only...

     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
    The Complexity of Songs
    "The Complexity of Songs" was an article published by Donald Knuth, an example of an in-joke in computer science, namely, in computational complexity theory...

    ", was reprinted twice in computer science journals.
  • To demonstrate the concept, Knuth intentionally referred "Circular definition" and "Definition, circular" to each other in the index of The Art of Computer Programming
    The Art of Computer Programming
    The Art of Computer Programming is a comprehensive monograph written by Donald Knuth that covers many kinds of programming algorithms and their analysis....

     Vol. 1.
  • At the TUG 2010 Conference, Knuth announced an XML
    XML
    Extensible Markup Language is a set of rules for encoding documents in machine-readable form. It is defined in the XML 1.0 Specification produced by the W3C, and several other related specifications, all gratis open standards....

    -based successor to TeX, titled "iTeX" (iː˨˩˦tɛks˧˥, with a bell ringing), which would support features such as arbitrarily scaled irrational units, 3D printing, animation, and stereographic sound.

Awards


In 1971, Knuth was the recipient of the first ACM
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...

 Grace Murray Hopper Award
Grace Murray Hopper Award
The original Grace Murray Hopper Awards have been awarded by the Association for Computing Machinery since 1971. The award goes to a young computer professional who makes a single, significant technical or service contribution.-Recipients:* 1971 Donald E. Knuth* 1972 Paul H. Dirksen* 1972 Paul H...

. He has received various other awards including the Turing Award
Turing Award
The Turing Award, in full The ACM A.M. Turing Award, is an annual award given by the Association for Computing Machinery to "an individual selected for contributions of a technical nature made to the computing community. The contributions should be of lasting and major technical importance to the...

, the National Medal of Science
National Medal of Science
The National Medal of Science is an honor bestowed by the President of the United States to individuals in science and engineering who have made important contributions to the advancement of knowledge in the fields of behavioral and social sciences, biology, chemistry, engineering, mathematics and...

, the John von Neumann Medal, and the Kyoto Prize
Kyoto Prize
The has been awarded annually since 1985 by the Inamori Foundation, founded by Kazuo Inamori. The prize is a Japanese award similar in intent to the Nobel Prize, as it recognizes outstanding works in the fields of philosophy, arts, science and technology...

.

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
Emeritus
Emeritus is a post-positive adjective that is used to designate a retired professor, bishop, or other professional or as a title. The female equivalent emerita is also sometimes used.-History:...

 of The Art of Computer Programming.

In 1992, he became an associate of the French Academy of Sciences
French Academy of Sciences
The French Academy of Sciences is a learned society, founded in 1666 by Louis XIV at the suggestion of Jean-Baptiste Colbert, to encourage and protect the spirit of French scientific research...

. Also that year, he retired from regular research and teaching at Stanford University
Stanford University
The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is a private research university on an campus located near Palo Alto, California. It is situated in the northwestern Santa Clara Valley on the San Francisco Peninsula, approximately northwest of San...

 in order to finish The Art of Computer Programming
The Art of Computer Programming
The Art of Computer Programming is a comprehensive monograph written by Donald Knuth that covers many kinds of programming algorithms and their analysis....

. In 2003 he was elected as a foreign member of the Royal Society
Royal Society
The Royal Society of London for Improving Natural Knowledge, known simply as the Royal Society, is a learned society for science, and is possibly the oldest such society in existence. Founded in November 1660, it was granted a Royal Charter by King Charles II as the "Royal Society of London"...

.

Knuth was elected as a Fellow (first class of Fellows) of the Society for Industrial and Applied Mathematics
Society for Industrial and Applied Mathematics
The Society for Industrial and Applied Mathematics was founded by a small group of mathematicians from academia and industry who met in Philadelphia in 1951 to start an organization whose members would meet periodically to exchange ideas about the uses of mathematics in industry. This meeting led...

 in 2009 for his outstanding contributions to mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

. He is a member of the Norwegian Academy of Science and Letters
Norwegian Academy of Science and Letters
The Norwegian Academy of Science and Letters is a learned society based in Oslo, Norway.-History:The University of Oslo was established in 1811. The idea of a learned society in Christiania surfaced for the first time in 1841. The city of Throndhjem had no university, but had a learned...

.
Honors bestowed on Knuth include:
  • First ACM
    Association for Computing Machinery
    The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...

     Grace Murray Hopper Award
    Grace Murray Hopper Award
    The original Grace Murray Hopper Awards have been awarded by the Association for Computing Machinery since 1971. The award goes to a young computer professional who makes a single, significant technical or service contribution.-Recipients:* 1971 Donald E. Knuth* 1972 Paul H. Dirksen* 1972 Paul H...

    , 1971
  • Turing Award
    Turing Award
    The Turing Award, in full The ACM A.M. Turing Award, is an annual award given by the Association for Computing Machinery to "an individual selected for contributions of a technical nature made to the computing community. The contributions should be of lasting and major technical importance to the...

    , 1974
  • National Medal of Science
    National Medal of Science
    The National Medal of Science is an honor bestowed by the President of the United States to individuals in science and engineering who have made important contributions to the advancement of knowledge in the fields of behavioral and social sciences, biology, chemistry, engineering, mathematics and...

    , 1979
  • Franklin Medal
    Franklin Medal
    The Franklin Medal was a science and engineering award presented by the Franklin Institute, of Philadelphia, PA, USA.-Laureates:*1915 - Thomas Alva Edison *1915 - Heike Kamerlingh Onnes *1916 - John J...

    , 1988
  • John von Neumann Medal, 1995
  • Harvey Prize from the Technion, 1995
  • Kyoto Prize
    Kyoto Prize
    The has been awarded annually since 1985 by the Inamori Foundation, founded by Kazuo Inamori. The prize is a Japanese award similar in intent to the Nobel Prize, as it recognizes outstanding works in the fields of philosophy, arts, science and technology...

    , 1996
  • Fellow of the Computer History Museum
    Computer History Museum
    The Computer History Museum is a museum established in 1996 in Mountain View, California, USA. The Museum is dedicated to preserving and presenting the stories and artifacts of the information age, and exploring the computing revolution and its impact on our lives.-History:The museum's origins...

    , 1998
  • Katayanagi Prize, 2010
  • BBVA Foundation Frontiers of Knowledge Award, 2010
  • Stanford University School of Engineering
    Stanford University School of Engineering
    Stanford University School of Engineering is one of the schools of Stanford University. The school has had eight deans; the current is James D. Plummer.-Previous Deans:# Theodore J. Hoover 1925-1936# Samuel B. Morris 1936-1944...

     Hero Award, 2011


Works


A short list of his works:
  • Donald E. Knuth, The Art of Computer Programming
    The Art of Computer Programming
    The Art of Computer Programming is a comprehensive monograph written by Donald Knuth that covers many kinds of programming algorithms and their analysis....

    , Volumes 1–4, Addison-Wesley Professional
  1. Volume 1: Fundamental Algorithms (3rd edition), 1997. Addison-Wesley Professional, ISBN 0-201-89683-4
  2. Volume 2: Seminumerical Algorithms (3rd Edition), 1997. Addison-Wesley Professional, ISBN 0-201-89684-2
  3. Volume 3: Sorting and Searching (2nd Edition), 1998. Addison-Wesley Professional, ISBN 0-201-89685-0
  4. Volume 4: Combinatorial Algorithms, Part 1, 2011. Addison-Wesley Professional, ISBN 0-201-03804-8
  5. Volume 4: Combinatorial Algorithms (remainder), in preparation

  • Donald E. Knuth, The Art of Computer Programming, fascicles:
  1. Volume 1, Fascicle 1: MMIX
    MMIX
    MMIX is a 64-bit RISC instruction set architecture designed by Donald Knuth, with significant contributions by John L. Hennessy and Richard L. Sites...

    —A RISC Computer for the New Millennium, 2005. ISBN 0-201-85392-2
  2. Volume 4, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions. 2008. ISBN 0-321-53496-4
  3. Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams. 2009. ISBN 0-321-58050-8
  4. Volume 4, Fascicle 2: Generating All Tuples and Permutations, 2005. ISBN 0-201-85393-0
  5. Volume 4, Fascicle 3: Generating All Combinations and Partitions, 2005. ISBN 0-201-85394-9
  6. Volume 4, Fascicle 4: Generating All Trees—History of Combinatorial Generation, 2006. ISBN 0-321-33570-8
    • Donald E. Knuth, Computers & Typesetting:
  7. Volume A, The TeXbook (Reading, Massachusetts: Addison-Wesley, 1984), x+483pp. ISBN 0-201-13447-0
  8. Volume B, TeX: The Program (Reading, Massachusetts: Addison-Wesley, 1986), xviii+600pp. ISBN 0-201-13437-3
  9. Volume C, The METAFONTbook (Reading, Massachusetts: Addison-Wesley, 1986), xii+361pp. ISBN 0-201-13445-4
  10. Volume D, METAFONT: The Program (Reading, Massachusetts: Addison-Wesley, 1986), xviii+566pp. ISBN 0-201-13438-1
  11. Volume E, Computer Modern Typefaces (Reading, Massachusetts: Addison-Wesley, 1986), xvi+588pp.
    • Knuth, Donald E. Selected papers series
      Selected papers series of Knuth
      This is a list of Selected papers series: written by Donald Knuth# Donald E. Knuth, Literate Programming , 1992. ISBN 0-937073-80-6# Donald E...

    • Donald E. Knuth, Surreal Numbers: How Two Ex-Students Turned on to Pure Mathematics and Found Total Happiness. 1974, ISBN 0-201-03812-9. More information can be found at the book's official homepage
    • Donald E. Knuth, The Stanford GraphBase: A Platform for Combinatorial Computing (New York, ACM Press) 1993. second paperback printing 2009. ISBN 0-321-60632-9
    • 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
      Things a Computer Scientist Rarely Talks About
      Things a Computer Scientist Rarely Talks About is a book by Donald E. Knuth, published by CLSI Publications of Stanford, California. The book contains the annotated transcripts of six public lectures given by Donald E. Knuth at MIT on the subject of relations between religion and science...

       (Center for the Study of Language and Information — CSLI Lecture Notes no 136), 2001. ISBN 1-57586-326-X

See also


  • Asymptotic notation
  • Attribute grammar
    Attribute grammar
    An attribute grammar is a formal way to define attributes for the productions of a formal grammar, associating these attributes to values. The evaluation occurs in the nodes of the abstract syntax tree, when the language is processed by some parser or compiler....

  • Dancing Links
    Dancing Links
    In computer science, Dancing Links, also known as DLX, is the technique suggested by Donald Knuth to efficiently implement his Algorithm X. Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm that finds all solutions to the exact cover problem...

  • Knuth–Bendix completion algorithm
  • Knuth–Morris–Pratt algorithm
    Knuth–Morris–Pratt algorithm
    The Knuth–Morris–Pratt string searching algorithm searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing...

  • Knuth -yllion
  • Knuth Prize
    Knuth Prize
    The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after Donald E. Knuth.-History:...

  • Knuth shuffle
  • Knuth's up-arrow notation
    Knuth's up-arrow notation
    In mathematics, Knuth's up-arrow notation is a method of notation for very large integers, introduced by Donald Knuth in 1976. It is closely related to the Ackermann function and especially to the hyperoperation sequence. The idea is based on the fact that multiplication can be viewed as iterated...

  • Man or boy test
    Man or boy test
    The man or boy test was proposed by computer scientist Donald Knuth as a means of evaluating implementations of the ALGOL 60 programming language...

  • Robinson–Schensted–Knuth correspondence
    Robinson–Schensted–Knuth correspondence
    In mathematics, the Robinson–Schensted–Knuth correspondence, also referred to as the RSK correspondence or RSK algorithm, is a combinatorial bijection between matrices with non-negative integer entries and pairs of semistandard Young tableaux of equal shape, whose size equals the sum of the...

  • The Complexity of Songs
    The Complexity of Songs
    "The Complexity of Songs" was an article published by Donald Knuth, an example of an in-joke in computer science, namely, in computational complexity theory...

  • Trabb Pardo–Knuth algorithm
  • List of science and religion scholars


External links


  • Donald Knuth’s home page at Stanford University
    Stanford University
    The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is a private research university on an campus located near Palo Alto, California. It is situated in the northwestern Santa Clara Valley on the San Francisco Peninsula, approximately northwest of San...

    .
  • Oral history interview with Donald E. Knuth at Charles Babbage Institute
    Charles Babbage Institute
    The Charles Babbage Institute is a research center at the University of Minnesota specializing in the history of information technology, particularly the history since 1935 of digital computing, programming/software, and computer networking....

    , University of Minnesota. Knuth discusses software patenting, structured programming
    Structured programming
    Structured programming is a programming paradigm aimed on improving the clarity, quality, and development time of a computer program by making extensive use of subroutines, block structures and for and while loops - in contrast to using simple tests and jumps such as the goto statement which could...

    , collaboration and his development of TeX
    TeX
    TeX is a typesetting system designed and mostly written by Donald Knuth and released in 1978. Within the typesetting system, its name is formatted as ....

    .
  • “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.
  • Videos of presentations w/ Donald Knuth
  • Donald Knuth's Stanford lectures archive