''The Art of Computer Programming'' (''TAOCP'') is a comprehensive multi-volume

monograph A monograph is generally a long-form work on one (usually scholarly) subject, or one aspect of a subject, typically created by a single author or artist (or, sometimes, by two or more authors). Traditionally it is in written form and published a ...

written by the computer scientist

Donald Knuth Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist and mathematician. He is a professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of comp ...

presenting programming

algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...

s and their analysis. it consists of published volumes 1, 2, 3, 4A, and 4B, with more expected to be released in the future. The Volumes 1–5 are intended to represent the central core of computer programming for sequential machines; the subjects of Volumes 6 and 7 are important but more specialized. When Knuth began the project in 1962, he originally conceived of it as a single book with twelve chapters. The first three volumes of what was then expected to be a seven-volume set were published in 1968, 1969, and 1973. Work began in earnest on Volume 4 in 1973, but was suspended in 1977 for work on

typesetting Typesetting is the composition of text for publication, display, or distribution by means of arranging physical ''type'' (or ''sort'') in mechanical systems or '' glyphs'' in digital systems representing '' characters'' (letters and other ...

prompted by the second edition of Volume 2. Writing of the final copy of Volume 4A began in longhand in 2001, and the first online pre-fascicle, 2A, appeared later in 2001. The first published installment of Volume 4 appeared in paperback as Fascicle 2 in 2005. The hardback Volume 4A, combining Volume 4, Fascicles 0–4, was published in 2011. Volume 4, Fascicle 6 ("Satisfiability") was released in December 2015; Volume 4, Fascicle 5 ("Mathematical Preliminaries Redux; Backtracking; Dancing Links") was released in November 2019. Volume 4B consists of material evolved from Fascicles 5 and 6. The manuscript was sent to the publisher on August 1, 2022, and the volume was published in September 2022. Fascicle 7 ("Constraint Satisfaction"), planned for Volume 4C, was the subject of Knuth's talk on August 3, 2022 and was published on February 5, 2025.

History

After winning a Westinghouse Talent Search scholarship, Knuth enrolled at the Case Institute of Technology (now

Case Western Reserve University Case Western Reserve University (CWRU) is a Private university, private research university in Cleveland, Ohio, United States. It was established in 1967 by a merger between Western Reserve University and the Case Institute of Technology. Case ...

), where his performance was so outstanding that the faculty voted to award him a

master of science A Master of Science (; abbreviated MS, M.S., MSc, M.Sc., SM, S.M., ScM or Sc.M.) is a master's degree. In contrast to the Master of Arts degree, the Master of Science degree is typically granted for studies in sciences, engineering and medici ...

upon his completion of the

bachelor's degree A bachelor's degree (from Medieval Latin ''baccalaureus'') or baccalaureate (from Modern Latin ''baccalaureatus'') is an undergraduate degree awarded by colleges and universities upon completion of a course of study lasting three to six years ...

. During his summer vacations, Knuth was hired by the

Burroughs Corporation The Burroughs Corporation was a major American manufacturer of business equipment. The company was founded in 1886 as the American Arithmometer Company by William Seward Burroughs I, William Seward Burroughs. The company's history paralleled many ...

to write

compiler In computing, a compiler is a computer program that Translator (computing), translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primaril ...

s, earning more in his summer months than full professors did for an entire year. Such exploits made Knuth a topic of discussion among the mathematics department, which included Richard S. Varga. In January 1962, when he was a graduate student in the mathematics department at Caltech, Knuth was approached by

Addison-Wesley Addison–Wesley is an American publisher of textbooks and computer literature. It is an imprint of Pearson plc, a global publishing and education company. In addition to publishing books, Addison–Wesley also distributes its technical titles ...

to write a book about compiler design, and he proposed a larger scope. He came up with a list of twelve chapter titles the same day. In the summer of 1962 he worked on a FORTRAN compiler for

UNIVAC UNIVAC (Universal Automatic Computer) was a line of electronic digital stored-program computers starting with the products of the Eckert–Mauchly Computer Corporation. Later the name was applied to a division of the Remington Rand company and ...

, considering that he had "sold my soul to the devil" to develop a FORTRAN compiler after

ALGOL ALGOL (; short for "Algorithmic Language") is a family of imperative computer programming languages originally developed in 1958. ALGOL heavily influenced many other languages and was the standard method for algorithm description used by the ...

developments with Burroughs. He remained as a consultant to Burroughs over the period 1960 to 1968 while writing Volume 1 "Fundamental Algorithms". During this time, he also developed a mathematical analysis of linear probing, which convinced him to present the material with a quantitative approach. After receiving his Ph.D. in June 1963, he began working on his manuscript, of which he finished his first draft in June 1965, at hand-written pages. He had assumed that about five hand-written pages would translate into one printed page, but his publisher said instead that about hand-written pages translated to one printed page. This meant he had approximately printed pages of material, which closely matches the size of the first three published volumes. The first volume of "The Art of Computer Programming", "Fundamental Algorithms", took five years to complete between 1963 and 1968 while working at both Caltech and Burroughs. Knuth's dedication in Volume 1 reads:

This series of books is affectionately dedicated
to the Type 650 computer once installed at
Case Institute of Technology,
in remembrance of many pleasant evenings.The dedication was worded slightly differently in the first edition.

In the preface, he thanks first his wife Jill, then Burroughs for the use of B220 and B5500 computers in testing most of the programs, and Caltech, the National Science Foundation, and the Office of Naval Research. Section 2.5 of "Fundamental Algorithms" is on Dynamic Storage Allocation. Parts of this are used in the Burroughs approach to memory management. Knuth claims credit for “The “boundary-tag” method, introduced in Section 2.5, was designed by the author in 1962 for use in a control program for the B5000 computer.” Knuth received support from Richard S. Varga, who was the scientific adviser to the publisher. Varga was visiting

Olga Taussky-Todd Olga Taussky-Todd (August 30, 1906 – October 7, 1995) was an Austrian and later Czech Americans, Czech-American mathematician. She published more than 300 research papers on algebraic number theory, integral matrices, and Matrix (mathematics), ...

and John Todd at

Caltech The California Institute of Technology (branded as Caltech) is a private university, private research university in Pasadena, California, United States. The university is responsible for many modern scientific advancements and is among a small g ...

. With Varga's enthusiastic endorsement, the publisher accepted Knuth's expanded plans. In its expanded version, the book would be published in seven volumes, each with just one or two chapters. Due to the growth in Chapter 7, which was fewer than 100 pages of the 1965 manuscript, per Vol. 4A p. vi, the plan for Volume 4 has since expanded to include Volumes 4A, 4B, 4C, 4D, and possibly more. In 1976, Knuth prepared a second edition of Volume 2, requiring it to be typeset again, but the style of type used in the first edition (called

hot type In printing and typography, hot metal typesetting (also called mechanical typesetting, hot lead typesetting, hot metal, and hot type) is a technology for typesetting text in letterpress printing. This method injects molten type metal into a mo ...

) was no longer available. In 1977, he decided to spend some time creating something more suitable. Eight years later, he returned with T_EX, which is currently used for all volumes. Another characteristic of the volumes is the variation in the difficulty of the exercises including a numerical rating varying from 0 to 50, where 0 is trivial, and 50 is an open question in contemporary research.

Bounty for finding errors

The offer of a so-called Knuth reward check worth "one hexadecimal dollar" (100_HEX base 16 cents, in

decimal The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers (''decimal fractions'') of th ...

, is $2.56) for any errors found, and the correction of these errors in subsequent printings, has contributed to the highly polished and still-authoritative nature of the work, long after its first publication.

Assembly language in the book

All examples in the books use a hypothetical language called " MIX assembly language" (MIXAL), which runs on "a mythical computer called MIX". Currently, the MIX computer is being replaced by the MMIX computer, which is a

RISC In electronics and computer science, a reduced instruction set computer (RISC) is a computer architecture designed to simplify the individual instructions given to the computer to accomplish tasks. Compared to the instructions given to a comp ...

version. The conversion from MIX to MMIX was a large ongoing project for which Knuth solicited volunteers for help. Software such as GNU MDK exists to provide emulation of the MIX architecture. Knuth considers the use of

assembly language In computing, assembly language (alternatively assembler language or symbolic machine code), often referred to simply as assembly and commonly abbreviated as ASM or asm, is any low-level programming language with a very strong correspondence bet ...

necessary for the speed and memory usage of algorithms to be judged. MIX was much like any computer then in existence, but nicer. The name ‘MIX’ is 1009 in Roman numerals and this is given by a formula involving series numbers of several computers of the time: (360 + 650 + 709 + U3 + SS80 + 1107 + 1604 + G2- + B220 + S2000 + 920 + 601 + H800 + PDP-4 + 11)/16 = 1009 or MIX. The name MMIX is 2009 in Roman numerals and Knuth claims MMIX is even nicer than MIX.

Critical response

Knuth was awarded the 1974

Turing Award The ACM A. M. Turing Award is an annual prize given by the Association for Computing Machinery (ACM) for contributions of lasting and major technical importance to computer science. It is generally recognized as the highest distinction in the fi ...

"for his major contributions to the

analysis of algorithms In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that r ...

�� and in particular for his contributions to the 'art of computer programming' through his well-known books in a continuous series by this title." ''

American Scientist ''American Scientist'' (informally abbreviated ''AmSci'') is an American bimonthly science and technology magazine published since 1913 by Sigma Xi, The Scientific Research Honor Society. In the beginning of 2000s the headquarters was moved to ...

'' has included this work among "100 or so Books that shaped a Century of Science", referring to the twentieth century. Covers of the third edition of Volume 1 quote

Bill Gates William Henry Gates III (born October 28, 1955) is an American businessman and philanthropist. A pioneer of the microcomputer revolution of the 1970s and 1980s, he co-founded the software company Microsoft in 1975 with his childhood friend ...

as saying, "If you think you're a really good programmer… read (Knuth's) ''Art of Computer Programming''… You should definitely send me a résumé if you can read the whole thing." ''

The New York Times ''The New York Times'' (''NYT'') is an American daily newspaper based in New York City. ''The New York Times'' covers domestic, national, and international news, and publishes opinion pieces, investigative reports, and reviews. As one of ...

'' referred to it as "the profession's defining treatise".

Volumes

Completed

* Volume 1 – Fundamental algorithms ** Chapter 1 – Basic concepts ** Chapter 2 – Information structures * Volume 2 – Seminumerical algorithms ** Chapter 3 – Random numbers ** Chapter 4 –

Arithmetic Arithmetic is an elementary branch of mathematics that deals with numerical operations like addition, subtraction, multiplication, and division. In a wider sense, it also includes exponentiation, extraction of roots, and taking logarithms. ...

* Volume 3 –

Sorting Sorting refers to ordering data in an increasing or decreasing manner according to some linear relationship among the data items. # ordering: arranging items in a sequence ordered by some criterion; # categorizing: grouping items with similar p ...

and searching ** Chapter 5 –

** Chapter 6 – Searching * Volume 4A –

Combinatorial Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...

algorithms ** Chapter 7 – Combinatorial searching (part 1) * Volume 4B –

algorithms ** Chapter 7 – Combinatorial searching (part 2)

Planned

* Volume 4C, 4D, ... Combinatorial algorithms (chapters 7 & 8 released in several subvolumes) ** Chapter 7 – Combinatorial searching (continued) ** Chapter 8 –

Recursion Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in m ...

* Volume 5 – Syntactic algorithms ** Chapter 9 – Lexical scanning (also includes string search and

data compression In information theory, data compression, source coding, or bit-rate reduction is the process of encoding information using fewer bits than the original representation. Any particular compression is either lossy or lossless. Lossless compressi ...

) ** Chapter 10 –

Parsing Parsing, syntax analysis, or syntactic analysis is a process of analyzing a String (computer science), string of Symbol (formal), symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal gramm ...

techniques * Volume 6 – The Theory of

context-free language In formal language theory, a context-free language (CFL), also called a Chomsky type-2 language, is a language generated by a context-free grammar (CFG). Context-free languages have many applications in programming languages, in particular, mos ...

s ** Chapter 11 – Mathematical linguistics * Volume 7 –

Compiler In computing, a compiler is a computer program that Translator (computing), translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primaril ...

techniques ** Chapter 12 – Programming language translation

Chapter outlines

Completed

Volume 1 – Fundamental algorithms

* Chapter 1 – Basic concepts ** 1.1.

Algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...

s ** 1.2. Mathematical preliminaries *** 1.2.1.

Mathematical induction Mathematical induction is a method for mathematical proof, proving that a statement P(n) is true for every natural number n, that is, that the infinitely many cases P(0), P(1), P(2), P(3), \dots all hold. This is done by first proving a ...

*** 1.2.2. Numbers, powers, and

logarithm In mathematics, the logarithm of a number is the exponent by which another fixed value, the base, must be raised to produce that number. For example, the logarithm of to base is , because is to the rd power: . More generally, if , the ...

s *** 1.2.3. Sums and products *** 1.2.4. Integer functions and elementary

number theory Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...

*** 1.2.5.

Permutation In mathematics, a permutation of a set can mean one of two different things: * an arrangement of its members in a sequence or linear order, or * the act or process of changing the linear order of an ordered set. An example of the first mean ...

s and

factorial In mathematics, the factorial of a non-negative denoted is the Product (mathematics), product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial: \begin n! &= n \times ...

s *** 1.2.6.

Binomial coefficient In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...

s *** 1.2.7.

Harmonic number In mathematics, the -th harmonic number is the sum of the reciprocals of the first natural numbers: H_n= 1+\frac+\frac+\cdots+\frac =\sum_^n \frac. Starting from , the sequence of harmonic numbers begins: 1, \frac, \frac, \frac, \frac, \dot ...

s *** 1.2.8.

Fibonacci number In mathematics, the Fibonacci sequence is a Integer sequence, sequence in which each element is the sum of the two elements that precede it. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted . Many w ...

s *** 1.2.9.

Generating function In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Generating functions are often expressed in closed form (rather than as a series), by some expression invo ...

s *** 1.2.10. Analysis of an algorithm *** 1.2.11. Asymptotic representations **** 1.2.11.1. The O-notation **** 1.2.11.2. Euler's summation formula **** 1.2.11.3. Some asymptotic calculations ** 1.3 MIX (Updated with MMIX in Volume 1 fascicle 1) *** 1.3.1. Description of MIX *** 1.3.2. The MIX assembly language *** 1.3.3. Applications to

permutation In mathematics, a permutation of a set can mean one of two different things: * an arrangement of its members in a sequence or linear order, or * the act or process of changing the linear order of an ordered set. An example of the first mean ...

s ** 1.4. Some fundamental programming techniques *** 1.4.1.

Subroutines In computer programming, a function (also procedure, method, subroutine, routine, or subprogram) is a callable unit of software logic that has a well-defined interface and behavior and can be invoked multiple times. Callable units provide a p ...

*** 1.4.2.

Coroutine Coroutines are computer program components that allow execution to be suspended and resumed, generalizing subroutines for cooperative multitasking. Coroutines are well-suited for implementing familiar program components such as cooperative task ...

s *** 1.4.3. Interpretive routines **** 1.4.3.1. A MIX simulator **** 1.4.3.2. Trace routines *** 1.4.4.

Input and output In computing, input/output (I/O, i/o, or informally io or IO) is the communication between an information processing system, such as a computer, and the outside world, such as another computer system, peripherals, or a human operator. Inputs ar ...

*** 1.4.5. History and bibliography * Chapter 2 – Information structures ** 2.1. Introduction ** 2.2. Linear lists *** 2.2.1. Stacks, queues, and deques *** 2.2.2. Sequential allocation *** 2.2.3. Linked allocation ( topological sorting) *** 2.2.4. Circular lists *** 2.2.5. Doubly linked lists *** 2.2.6.

Arrays An array is a systematic arrangement of similar objects, usually in rows and columns. Things called an array include: {{TOC right Music * In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...

and orthogonal lists ** 2.3.

Trees In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only p ...

*** 2.3.1. Traversing

binary tree In computer science, a binary tree is a tree data structure in which each node has at most two children, referred to as the ''left child'' and the ''right child''. That is, it is a ''k''-ary tree with . A recursive definition using set theor ...

s *** 2.3.2. Binary tree representation of trees *** 2.3.3. Other representations of trees *** 2.3.4. Basic mathematical properties of trees **** 2.3.4.1. Free trees **** 2.3.4.2. Oriented trees **** 2.3.4.3. The "infinity lemma" **** 2.3.4.4. Enumeration of trees **** 2.3.4.5. Path length **** 2.3.4.6. History and bibliography *** 2.3.5. Lists and garbage collection ** 2.4. Multilinked structures ** 2.5. Dynamic storage allocation ** 2.6. History and bibliography

Volume 2 – Seminumerical algorithms

* Chapter 3 – Random numbers ** 3.1. Introduction ** 3.2. Generating uniform random numbers *** 3.2.1. The linear congruential method **** 3.2.1.1. Choice of modulus **** 3.2.1.2. Choice of multiplier **** 3.2.1.3. Potency *** 3.2.2. Other methods ** 3.3. Statistical tests *** 3.3.1. General test procedures for studying random data *** 3.3.2. Empirical tests *** 3.3.3. Theoretical tests *** 3.3.4. The spectral test ** 3.4. Other types of random quantities *** 3.4.1. Numerical distributions *** 3.4.2. Random sampling and

shuffling Shuffling is a technique used to randomize a deck of playing cards, introducing an element of chance into card games. Various shuffling methods exist, each with its own characteristics and potential for manipulation. One of the simplest shuf ...

** 3.5. What Is a

random sequence The concept of a random sequence is essential in probability theory and statistics. The concept generally relies on the notion of a sequence of random variables and many statistical discussions begin with the words "let ''X''1,...,''Xn'' be independ ...

? ** 3.6. Summary * Chapter 4 – Arithmetic ** 4.1. Positional number systems ** 4.2. Floating point arithmetic *** 4.2.1. Single-precision calculations *** 4.2.2. Accuracy of floating point arithmetic *** 4.2.3. Double-precision calculations *** 4.2.4. Distribution of floating point numbers ** 4.3. Multiple precision arithmetic *** 4.3.1. The classical algorithms *** 4.3.2. Modular arithmetic *** 4.3.3. How fast can we multiply? ** 4.4.

Radix In a positional numeral system, the radix (radices) or base is the number of unique digits, including the digit zero, used to represent numbers. For example, for the decimal system (the most common system in use today) the radix is ten, becaus ...

conversion ** 4.5.

Rational Rationality is the quality of being guided by or based on reason. In this regard, a person acts rationally if they have a good reason for what they do, or a belief is rational if it is based on strong evidence. This quality can apply to an ...

arithmetic *** 4.5.1. Fractions *** 4.5.2. The greatest common divisor *** 4.5.3. Analysis of Euclid's algorithm *** 4.5.4. Factoring into primes ** 4.6.

Polynomial In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...

arithmetic *** 4.6.1. Division of polynomials *** 4.6.2. Factorization of polynomials *** 4.6.3. Evaluation of powers ( addition-chain exponentiation) *** 4.6.4. Evaluation of polynomials ** 4.7. Manipulation of

power series In mathematics, a power series (in one variable) is an infinite series of the form \sum_^\infty a_n \left(x - c\right)^n = a_0 + a_1 (x - c) + a_2 (x - c)^2 + \dots where ''a_n'' represents the coefficient of the ''n''th term and ''c'' is a co ...

Volume 3 – Sorting and searching

* Chapter 5 –

** 5.1. Combinatorial properties of

s *** 5.1.1. Inversions *** 5.1.2. Permutations of a multiset *** 5.1.3. Runs *** 5.1.4. Tableaux and involutions ** 5.2. Internal sorting *** 5.2.1. Sorting by insertion *** 5.2.2. Sorting by exchanging *** 5.2.3. Sorting by selection *** 5.2.4. Sorting by merging *** 5.2.5. Sorting by distribution ** 5.3. Optimum sorting *** 5.3.1. Minimum-comparison sorting *** 5.3.2. Minimum-comparison merging *** 5.3.3. Minimum-comparison selection *** 5.3.4. Networks for sorting ** 5.4.

External sorting External sorting is a class of sorting algorithms that can handle massive amounts of data. External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead they must reside i ...

*** 5.4.1. Multiway merging and replacement selection *** 5.4.2. The polyphase merge *** 5.4.3. The cascade merge *** 5.4.4. Reading tape backwards *** 5.4.5. The oscillating sort *** 5.4.6. Practical considerations for tape merging *** 5.4.7. External radix sorting *** 5.4.8. Two-tape sorting *** 5.4.9. Disks and drums ** 5.5. Summary, history, and bibliography * Chapter 6 – Searching ** 6.1. Sequential searching ** 6.2. Searching by comparison of keys *** 6.2.1. Searching an ordered table *** 6.2.2. Binary tree searching *** 6.2.3. Balanced trees *** 6.2.4. Multiway trees ** 6.3. Digital searching ** 6.4. Hashing ** 6.5. Retrieval on secondary keys

Volume 4A – Combinatorial algorithms, Part 1

* Chapter 7 – Combinatorial searching ** 7.1. Zeros and ones *** 7.1.1. Boolean basics *** 7.1.2. Boolean evaluation *** 7.1.3. Bitwise tricks and techniques *** 7.1.4. Binary decision diagrams ** 7.2. Generating all possibilities *** 7.2.1. Generating basic combinatorial patterns **** 7.2.1.1. Generating all ''n''-

tuple In mathematics, a tuple is a finite sequence or ''ordered list'' of numbers or, more generally, mathematical objects, which are called the ''elements'' of the tuple. An -tuple is a tuple of elements, where is a non-negative integer. There is o ...

s **** 7.2.1.2. Generating all

s **** 7.2.1.3. Generating all

combination In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter (unlike permutations). For example, given three fruits, say an apple, an orange and a pear, there are ...

s **** 7.2.1.4. Generating all

integer partition In number theory and combinatorics, a partition of a non-negative integer , also called an integer partition, is a way of writing as a summation, sum of positive integers. Two sums that differ only in the order of their summands are considered ...

s **** 7.2.1.5. Generating all set partitions **** 7.2.1.6. Generating all

trees In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only p ...

**** 7.2.1.7. History and further references

Volume 4B – Combinatorial algorithms, Part 2

* Chapter 7 – Combinatorial searching (continued) ** 7.2. Generating all possibilities (continued) *** 7.2.2. Backtrack programming **** 7.2.2.1. Dancing links (includes discussion of exact cover) **** 7.2.2.2.

Satisfiability In mathematical logic, a formula is ''satisfiable'' if it is true under some assignment of values to its variables. For example, the formula x+3=y is satisfiable because it is true when x=3 and y=6, while the formula x+1=x is not satisfiable over ...

Planned

Volumes 4C, 4D, 4E, 4F – Combinatorial algorithms

* Chapter 7 – Combinatorial searching (continued) ** 7.2. Generating all possibilities (continued) *** 7.2.2. Backtrack programming (continued) **** 7.2.2.3. Constraint satisfaction (released as Pre-Fascicle 7A) **** 7.2.2.4. Hamiltonian paths and cycles **** 7.2.2.5. Cliques **** 7.2.2.6. Covers ( vertex cover,

set cover problem The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory. Given a set of elements (henceforth referred to as the universe, specifying all possible elements under considerati ...

, exact cover, clique cover) **** 7.2.2.7. Squares **** 7.2.2.8. A potpourri of puzzles (includes perfect digital invariant) **** 7.2.2.9. Estimating backtrack costs (chapter 6 of "Selected Papers on Analysis of Algorithms", and Fascicle 5, pp. 44−47, under the heading "Running time estimates") *** 7.2.3. Generating inequivalent patterns (includes discussion of Pólya enumeration theorem) (see "Techniques for Isomorph Rejection", chapter 4 of "Classification Algorithms for Codes and Designs" by Kaski and Östergård) ** 7.3.

Shortest paths In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between t ...

** 7.4. Graph algorithms *** 7.4.1. Components and traversal **** 7.4.1.1. Union-find algorithms **** 7.4.1.2.

Depth-first search Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible al ...

**** 7.4.1.3. Vertex and edge connectivity *** 7.4.2. Special classes of graphs *** 7.4.3.

Expander graph In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several appli ...

s *** 7.4.4.

Random graph In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs l ...

s ** 7.5. Graphs and optimization *** 7.5.1. Bipartite matching (including maximum-cardinality matching, stable marriage problem
mariages stables
*** 7.5.2. The assignment problem *** 7.5.3. Network flows *** 7.5.4. Optimum subtrees *** 7.5.5. Optimum matching *** 7.5.6. Optimum orderings ** 7.6. Independence theory *** 7.6.1. Independence structures *** 7.6.2. Efficient

matroid In combinatorics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid Axiomatic system, axiomatically, the most significant being in terms ...

algorithms ** 7.7. Discrete dynamic programming (see also transfer-matrix method) ** 7.8. Branch-and-bound techniques ** 7.9. Herculean tasks (aka

NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...

problems) ** 7.10. Near-optimization * Chapter 8 –

(chapter 22 of "Selected Papers on Analysis of Algorithms")

Volume 5 – Syntactic algorithms

* Chapter 9 – Lexical scanning (includes also string search and data compression) * Chapter 10 –

techniques

Volume 6 – The theory of context-free languages

* Chapter 11 – Mathematical linguistics

Volume 7 – Compiler techniques

* Chapter 12 – Programming language translation

English editions

Current editions

These are the current editions in order by volume number: * ''The Art of Computer Programming, Volumes 1-4B Boxed Set''. (Reading, Massachusetts: Addison-Wesley, 2023), 3904pp. ** ''Volume 1: Fundamental Algorithms''. Third Edition (Reading, Massachusetts: Addison-Wesley, 1997), xx+650pp. . Errata

(from 2011-01-08)

(from 2022, 49th printing run, printing). Addenda

(2011). ** ''Volume 2: Seminumerical Algorithms''. Third Edition (Reading, Massachusetts: Addison-Wesley, 1997), xiv+762pp. . Errata

(from 2011-01-08)

(from 2022, 45th printing). Addenda

(2011). ** ''Volume 3: Sorting and Searching''. Second Edition (Reading, Massachusetts: Addison-Wesley, 1998), xiv+780pp.+foldout. . Errata

(from 2011-01-08)

(from 2022, 45th printing). Addenda

(2011). ** ''Volume 4A: Combinatorial Algorithms, Part 1''. First Edition (Upper Saddle River, New Jersey: Addison-Wesley, 2011, 24th printing), xv+883pp. . Errata

(from 2011)

(from 2022, 20th printing). ** ''Volume 4B: Combinatorial Algorithms, Part 2''. First Edition (Upper Saddle River, New Jersey: Addison-Wesley, 2023, 2nd printing), xviii+714pp. . Errata

(from 2023, 1st printing). * ''Volume 1, Fascicle 1: MMIX – A RISC Computer for the New Millennium''. (Addison-Wesley, 2005-02-14), 144pp. . Errata

(from 2005, 1st printing) (will be in the fourth edition of volume 1) * ''The MMIX Supplement'' by Martin Ruckert. (Addison-Wesley), 193pp. . A conversion of the MIX problems/programs in volumes 1, 2 & 3 to MMIX. * ''Volume 4, Fascicle 7: Constraint Satisfaction''. (Addison-Wesley, 2025-02-05), xiv+281pp. .

Previous editions

Complete volumes

These volumes were superseded by newer editions and are in order by date. * ''Volume 1: Fundamental Algorithms''. First edition, 1968, xxi+634pp, . * ''Volume 2: Seminumerical Algorithms''. First edition, 1969, xi+624pp, . * ''Volume 3: Sorting and Searching''. First edition, 1973, xi+723pp+foldout, . Errata

* ''Volume 1: Fundamental Algorithms''. Second edition, 1973, xxi+634pp, . Errata

* ''Volume 2: Seminumerical Algorithms''. Second edition, 1981, xiii+ 688pp, . Errata

* ''The Art of Computer Programming, Volumes 1-3 Boxed Set''. Second Edition (Reading, Massachusetts: Addison-Wesley, 1998), pp. * ''The Art of Computer Programming, Volumes 1-4A Boxed Set''. Third Edition (Reading, Massachusetts: Addison-Wesley, 2011), 3168pp.

Fascicles

Volume 4, fascicle (book), Fascicles 0–4 were revised and published as Volume 4A. * ''Volume 4, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions''. (Addison-Wesley Professional, 2008-04-28) vi+240pp, . Errata

(2011-01-01). * ''Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams''. (Addison-Wesley Professional, 2009-03-27) viii+260pp, . Errata

(2011-01-01). * ''Volume 4, Fascicle 2: Generating All Tuples and Permutations''. (Addison-Wesley, 2005-02-14) v+127pp, . Errata

(2011-01-01). * ''Volume 4, Fascicle 3: Generating All Combinations and Partitions''. (Addison-Wesley, 2005-07-26) vi+150pp, . Errata

(2011-01-01). * ''Volume 4, Fascicle 4: Generating All Trees; History of Combinatorial Generation''. (Addison-Wesley, 2006-02-06) vi+120pp, . Errata

(2011-01-01). Volume 4, Fascicles 5–6 were revised and published as Volume 4B. * ''Volume 4, Fascicle 5: Mathematical Preliminaries Redux; Backtracking; Dancing Links''. (Addison-Wesley, 2019-11-22) xiii+382pp, . Errata

(2020-03-27) * ''Volume 4, Fascicle 6: Satisfiability''. (Addison-Wesley, 2015-12-08) xiii+310pp, . Errata

(2020-03-26)

Pre-fascicles

Volume 1 * Pre-fascicl
1
was revised and published as Volume 1, fascicle 1. Volume 4 * Pre-fascicle
0A0B
an
0C
were revised and published as Volume 4, fascicle 0. * Pre-fascicle
1A
an
1B
were revised and published as Volume 4, fascicle 1. * Pre-fascicle
2A
an
2B
were revised and published as Volume 4, fascicle 2. * Pre-fascicle
3A
an
3B
were revised and published as Volume 4, fascicle 3. * Pre-fascicle
4A
an
4B
were revised and published as Volume 4, fascicle 4. * Pre-fascicle
5A5B
an
5C
were revised and published as Volume 4, fascicle 5. * Pre-fascicl
6A
was revised and published as Volume 4, fascicle 6. * Pre-fascicl
7A
was revised and published as Volume 4, fascicle 7. The remaining pre-fascicles contain draft material that is set to appear in future fascicles and volumes. *
Volume 4, Pre-fascicle 8A: Hamiltonian Paths and Cycles
' *
Volume 4, Pre-fascicle 8B: Cliques
' *
Volume 4, Pre-fascicle 9B: A Potpourri of Puzzles
' *
Volume 4, Pre-fascicle 9C: Estimating Backtrack Costs
' *
Volume 4, Pre-fascicle 12A: Components and Traversal(PDF Version)
' *
Volume 4, Pre-fascicle 14A: Bipartite Matching
' *
Volume 4, Pre-fascicle 16A: Introduction to Recursion
'

References

Notes Citations Sources * *

External links

Overview of topics
(Knuth's personal homepage)
Announcement of Volume 1 of 'The Art of Computer Programming'

Oral history interview with Donald E. Knuth
at

Charles Babbage Institute The IT History Society (ITHS) is an organization that supports the history and scholarship of information technology by encouraging, fostering, and facilitating archival and historical research. Formerly known as the Charles Babbage Foundation, ...

, University of Minnesota, Minneapolis, 2001. Knuth discusses software patenting,

structured programming Structured programming is a programming paradigm aimed at improving the clarity, quality, and development time of a computer program by making specific disciplined use of the structured control flow constructs of selection ( if/then/else) and repet ...

, collaboration and his development of

TeX Tex, TeX, TEX, may refer to: People and fictional characters * Tex (nickname), a list of people and fictional characters with the nickname * Tex Earnhardt (1930–2020), U.S. businessman * Joe Tex (1933–1982), stage name of American soul singer ...

. The oral history discusses the writing of ''The Art of Computer Programming''.
"Robert W Floyd, In Memoriam", by Donald E. Knuth
2003 - (on the influence of Bob Floyd)
''TAoCP'' and its Influence of Computer Science (Softpanorama)
{{DEFAULTSORT:Art Of Computer Programming, The 1968 non-fiction books 1969 non-fiction books 1973 non-fiction books 1981 non-fiction books 2011 non-fiction books Addison-Wesley books American non-fiction books Analysis of algorithms Books by Donald Knuth Computer arithmetic algorithms Computer programming books Computer science books English-language non-fiction books Monographs

History

Bounty for finding errors

Assembly language in the book

Critical response

Volumes

Completed

Planned

Chapter outlines

Completed

Volume 1 – Fundamental algorithms

Volume 2 – Seminumerical algorithms

Volume 3 – Sorting and searching

Volume 4A – Combinatorial algorithms, Part 1

Volume 4B – Combinatorial algorithms, Part 2

Planned

Volumes 4C, 4D, 4E, 4F – Combinatorial algorithms

Volume 5 – Syntactic algorithms

Volume 6 – The theory of context-free languages

Volume 7 – Compiler techniques

English editions

Current editions

Previous editions

Complete volumes

Fascicles

Pre-fascicles

See also

References

External links