The Art of Computer Programming
Encyclopedia
The Art of Computer Programming (acronym: TAOCP) is a comprehensive monograph
written by Donald Knuth
that covers many kinds of programming algorithm
s and their analysis
.
Knuth began the project, originally conceived as a single book with twelve chapters, in 1962. The first three of what were then expected to be a seven-volume set were published in 1968, 1969, and 1973. The first installment of Volume 4 (a paperback fascicle) was published in 2005. The hardback volume 4A was published in 2010. Additional fascicle installments are planned for release approximately biannually.
After winning a Westinghouse Talent Search scholarship, Knuth enrolled at the Case Institute of Technology (now Case Western Reserve University
), where his performance was so outstanding that the faculty voted to award him a master of science upon his completion of the baccalaureate degree. During his summer vacations, Knuth was hired to write compilers, earning more in his summer months than did full professors all year. Such exploits made Knuth a topic of discussion among the mathematics department, which included Richard S. Varga
.
Knuth started to write a book about compiler design in 1962, and soon realized that the scope of the book needed to be much larger. In June 1965, Knuth finished the first draft of what was originally planned to be a single volume of twelve chapters. His hand-written first-draft manuscript (completed in 1966) was 3,000 pages long: he had assumed that about five hand-written pages would translate into one printed page, but his publisher said instead that about 1½ hand-written pages translated to one printed page. This meant the book would be approximately 2,000 pages in length. The publisher was nervous about accepting such a project from a graduate student. At this point, Knuth received support from Richard S. Varga, who was the scientific advisor to the publisher. Varga was visiting Olga Taussky-Todd and John Todd at Caltech. 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 the material, the plan for Volume 4 has since expanded to include Volumes 4A, 4B, 4C, 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
) was no longer available. In 1977, he decided to spend a few months working up something more suitable. Eight years later, he returned with TeX
, which is currently used for all volumes.
The famous offer of a reward check
worth "one hexadecimal dollar" (100HEX
base 16
cents, in decimal
, 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. Another characteristic of the volumes is the variation in the difficulty of the exercises. The level of difficulty ranges from "warm-up" exercises to unsolved research problems, providing a challenge for any reader. Knuth's dedication is also famous:
computer. (Currently, the MIX computer is being replaced by the MMIX
computer, which is a RISC version.) Software such as GNU MDK
exists to provide emulation of the MIX architecture.
Some readers are put off by the use of assembly language
, but Knuth considers this necessary because algorithms need to be in context in order for their speed and memory usage to be judged. This does, however, limit the accessibility of the book for many readers, and limits its usefulness as a "cookbook" for practicing programmers, who may not be familiar with assembly, or who may have no particular desire to translate assembly language code into a high-level language. A number of more accessible algorithms textbooks using high-level language examples exist and are popular for precisely these reasons.
has included this work among "100 or so Books that shaped a Century of Science", referring to the 20th century, and within the computer science community it is regarded as the first and still the best comprehensive treatment of its subject. Covers of the third edition of Volume 1 quote Bill Gates
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
referred to it as "the profession's defining treatise".
Monograph
A monograph is a work of writing upon a single subject, usually by a single author.It is often a scholarly essay or learned treatise, and may be released in the manner of a book or journal article. It is by definition a single document that forms a complete text in itself...
written by Donald Knuth
Donald Knuth
Donald Ervin Knuth is a computer scientist and Professor Emeritus at Stanford University.He is the author of the seminal multi-volume work The Art of Computer Programming. Knuth has been called the "father" of the analysis of algorithms...
that covers many kinds of programming algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s and their analysis
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...
.
Knuth began the project, originally conceived as a single book with twelve chapters, in 1962. The first three of what were then expected to be a seven-volume set were published in 1968, 1969, and 1973. The first installment of Volume 4 (a paperback fascicle) was published in 2005. The hardback volume 4A was published in 2010. Additional fascicle installments are planned for release approximately biannually.
History
Case Western Reserve University
Case Western Reserve University is a private research university located in Cleveland, Ohio, USA...
), where his performance was so outstanding that the faculty voted to award him a master of science upon his completion of the baccalaureate degree. During his summer vacations, Knuth was hired to write compilers, earning more in his summer months than did full professors all year. Such exploits made Knuth a topic of discussion among the mathematics department, which included Richard S. Varga
Richard S. Varga
Richard Steven Varga is an American mathematician who specializes in numerical analysis and linear algebra. He is currently a University Professor of Mathematical Sciences at Kent State University, Kent, Ohio...
.
Knuth started to write a book about compiler design in 1962, and soon realized that the scope of the book needed to be much larger. In June 1965, Knuth finished the first draft of what was originally planned to be a single volume of twelve chapters. His hand-written first-draft manuscript (completed in 1966) was 3,000 pages long: he had assumed that about five hand-written pages would translate into one printed page, but his publisher said instead that about 1½ hand-written pages translated to one printed page. This meant the book would be approximately 2,000 pages in length. The publisher was nervous about accepting such a project from a graduate student. At this point, Knuth received support from Richard S. Varga, who was the scientific advisor to the publisher. Varga was visiting Olga Taussky-Todd and John Todd at Caltech. 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 the material, the plan for Volume 4 has since expanded to include Volumes 4A, 4B, 4C, and possibly more.
In 1976, Knuth prepared a second edition of Volume 2, requiring it to be typeset
Typesetting
Typesetting is the composition of text by means of types.Typesetting requires the prior process of designing a font and storing it in some manner...
again, but the style of type used in the first edition (called hot type
Hot metal typesetting
In printing and typography, hot metal typesetting refers to 19th-century technologies for typesetting text in letterpress printing. This method injects molten type metal into a mold that has the shape of one or more glyphs...
) was no longer available. In 1977, he decided to spend a few months working up something more suitable. Eight years later, he returned with 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 ....
, which is currently used for all volumes.
The famous offer of a 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...
worth "one hexadecimal dollar" (100HEX
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...
base 16
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...
cents, in decimal
Decimal
The decimal numeral system has ten as its base. It is the numerical base most widely used by modern civilizations....
, 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. Another characteristic of the volumes is the variation in the difficulty of the exercises. The level of difficulty ranges from "warm-up" exercises to unsolved research problems, providing a challenge for any reader. Knuth's dedication is also famous:
This series of books is affectionately dedicated
to the Type 650 computerIBM 650The 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...
once installed at
Case Institute of Technology,
with whom I have spent many pleasant evenings.The dedication was worded slightly differently in the first edition.
Assembly language in the book
All examples in the books use a language called "MIX assembly language", which runs on the hypothetical MIXMIX
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...
computer. (Currently, the MIX computer is being replaced by the 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...
computer, which is a RISC version.) Software such as GNU MDK
GNU MDK
The GNU MIX Development Kit is a free software package for developing, running and debugging programs written in MIXAL, an assembly-like language for programming a fictional computer called MIX....
exists to provide emulation of the MIX architecture.
Some readers are put off by the use of assembly language
Assembly language
An assembly language is a low-level programming language for computers, microprocessors, microcontrollers, and other programmable devices. It implements a symbolic representation of the machine codes and other constants needed to program a given CPU architecture...
, but Knuth considers this necessary because algorithms need to be in context in order for their speed and memory usage to be judged. This does, however, limit the accessibility of the book for many readers, and limits its usefulness as a "cookbook" for practicing programmers, who may not be familiar with assembly, or who may have no particular desire to translate assembly language code into a high-level language. A number of more accessible algorithms textbooks using high-level language examples exist and are popular for precisely these reasons.
Critical response
American ScientistAmerican Scientist
American Scientist is the bimonthly science and technology magazine published since 1913 by Sigma Xi. Each issue includes four to five feature articles written by scientists and engineers. These authors review research in all fields of science...
has included this work among "100 or so Books that shaped a Century of Science", referring to the 20th century, and within the computer science community it is regarded as the first and still the best comprehensive treatment of its subject. Covers of the third edition of Volume 1 quote Bill Gates
Bill Gates
William Henry "Bill" Gates III is an American business magnate, investor, philanthropist, and author. Gates is the former CEO and current chairman of Microsoft, the software company he founded with Paul Allen...
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
The New York Times is an American daily newspaper founded and continuously published in New York City since 1851. The New York Times has won 106 Pulitzer Prizes, the most of any news organization...
referred to it as "the profession's defining treatise".
Volumes
- Volume 1 - Fundamental Algorithms (chapters 1 and 2)
- Volume 2 - Seminumerical Algorithms (chapters 3 and 4)
- Volume 3 - SortingSorting algorithmIn computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...
and SearchingSearch algorithmIn computer science, a search algorithm is an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots...
(chapters 5 and 6) - Volume 4 - CombinatorialCombinatoricsCombinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
Algorithms (chapters 7 and 8)- Volume 4A - EnumerationEnumerationIn mathematics and theoretical computer science, the broadest and most abstract definition of an enumeration of a set is an exact listing of all of its elements . The restrictions imposed on the type of list used depend on the branch of mathematics and the context in which one is working...
and BacktrackingBacktrackingBacktracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c as soon as it determines that c cannot possibly be completed to a valid solution.The classic textbook example...
(chapter 7 part 1) - Volume 4B - GraphGraph theoryIn mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
and NetworkFlow networkIn graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in Operations Research, a directed graph is called a network, the vertices are called nodes and the edges are...
Algorithms, in preparation (chapter 7 part 2) - Volumes 4C and maybe 4D and 4E - OptimizationOptimization (mathematics)In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
and RecursionRecursionRecursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
, in preparation (chapter 7 continued and chapter 8)
- Volume 4A - Enumeration
- Volume 5 - Syntactic Algorithms, planned (as of 2011, estimated in 2020) (chapters 9 and 10)
- Volume 6 - Theory of Context-Free LanguageContext-free languageIn formal language theory, a context-free language is a language generated by some context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.-Examples:...
s, planned - Volume 7 - CompilerCompilerA compiler is a computer program that transforms source code written in a programming language into another computer language...
Techniques, planned
Chapters
- Chapter 1 - Basic concepts (volume 1)
- Chapter 2 - Information structuresData structureIn computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
(volume 1) - Chapter 3 - Random numbersStatistical randomnessA numeric sequence is said to be statistically random when it contains no recognizable patterns or regularities; sequences such as the results of an ideal dice roll, or the digits of π exhibit statistical randomness....
(volume 2) - Chapter 4 - ArithmeticArithmeticArithmetic or arithmetics is the oldest and most elementary branch of mathematics, used by almost everyone, for tasks ranging from simple day-to-day counting to advanced science and business calculations. It involves the study of quantity, especially as the result of combining numbers...
(volume 2) - Chapter 5 - SortingSorting algorithmIn computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...
(volume 3) - Chapter 6 - SearchingSearch algorithmIn computer science, a search algorithm is an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots...
(volume 3) - Chapter 7 - Combinatorial searching (volume 4)
- Chapter 8 - RecursionRecursionRecursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
(volume 4) - Chapter 9 - Lexical scanningLexical analysisIn computer science, lexical analysis is the process of converting a sequence of characters into a sequence of tokens. A program or function which performs lexical analysis is called a lexical analyzer, lexer or scanner...
(volume 5) - Chapter 10 - ParsingParsingIn computer science and linguistics, parsing, or, more formally, syntactic analysis, is the process of analyzing a text, made of a sequence of tokens , to determine its grammatical structure with respect to a given formal grammar...
techniques (also includes string searchString searching algorithmString searching algorithms, sometimes called string matching algorithms, are an important class of string algorithms that try to find a place where one or several strings are found within a larger string or text....
and data compressionData compressionIn computer science and information theory, data compression, source coding or bit-rate reduction is the process of encoding information using fewer bits than the original representation would use....
) (volume 5)
Chapter outline of published volumes
- Volume 1 - Fundamental Algorithms
- Chapter 1 - Basic concepts
- 1.1 AlgorithmAlgorithmIn mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s - 1.2 Mathematical Preliminaries
- 1.3 MIXMIXMIX 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...
- 1.4 Some Fundamental Programming Techniques
- 1.1 Algorithm
- Chapter 2 - Information structures
- 2.1 Introduction
- 2.2 Linear Lists
- 2.3 TreesTree (data structure)In computer science, a tree is a widely-used data structure that emulates a hierarchical tree structure with a set of linked nodes.Mathematically, it is an ordered directed tree, more specifically an arborescence: an acyclic connected graph where each node has zero or more children nodes and at...
- 2.4 Multilinked Structures
- 2.5 Dynamic Storage Allocation
- 2.6 History and Bibliography
- Chapter 1 - Basic concepts
- Volume 2 - Seminumerical Algorithms
- Chapter 3 - Random numbers
- 3.1 Introduction
- 3.2 Generating Uniform Random Numbers
- 3.3 Statistical Tests
- 3.4 Other Types of Random QuantitiesPseudo-random number samplingPseudo-random number sampling or non-uniform pseudo-random variate generation is the numerical practice of generating pseudo-random numbers that are distributed according to a given probability distribution....
- 3.5 What Is a Random SequenceRandom sequenceThe 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 X1,...,Xn be independent random variables...". Yet as D. H. Lehmer stated in...
? - 3.6 Summary
- Chapter 4 - Arithmetic
- 4.1 Positional Number SystemsPositional notationPositional notation or place-value notation is a method of representing or encoding numbers. Positional notation is distinguished from other notations for its use of the same symbol for the different orders of magnitude...
- 4.2 Floating-Point Arithmetic
- 4.3 Multiple Precision ArithmeticArbitrary-precision arithmeticIn computer science, arbitrary-precision arithmetic indicates that calculations are performed on numbers whose digits of precision are limited only by the available memory of the host system. This contrasts with the faster fixed-precision arithmetic found in most ALU hardware, which typically...
- 4.4 RadixRadixIn 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...
Conversion - 4.5 RationalRational numberIn mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...
Arithmetic - 4.6 PolynomialPolynomialIn mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
Arithmetic - 4.7 Manipulation of Power Series
- 4.1 Positional Number Systems
- Chapter 3 - Random numbers
- Volume 3 - Sorting and Searching
- Chapter 5 - SortingSorting algorithmIn computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...
- 5.1 Combinatorial Properties of PermutationPermutationIn mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
s - 5.2 Internal sortingInternal sortAn internal sort is any data sorting process that takes place entirely within the main memory of a computer. This is possible whenever the data to be sorted is small enough to all be held in the main memory. For sorting larger datasets, it may be necessary to hold only a chunk of data in memory at...
- 5.3 Optimal Sorting
- 5.4 External SortingExternal sortingExternal sorting is a term for 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 and instead they must reside in the slower external memory . External sorting...
- 5.5 Summary, History, and Bibliography
- 5.1 Combinatorial Properties of Permutation
- Chapter 6 - SearchingSearch algorithmIn computer science, a search algorithm is an algorithm for finding an item with specified properties among a collection of items. The items may be stored individually as records in a database; or may be elements of a search space defined by a mathematical formula or procedure, such as the roots...
- 6.1 Sequential Searching
- 6.2 Searching by Comparison of KeysUnique keyIn relational database design, a unique key can uniquely identify each row in a table, and is closely related to the Superkey concept. A unique key comprises a single column or a set of columns. No two distinct rows in a table can have the same value in those columns if NULL values are not used...
- 6.3 Digital Searching
- 6.4 HashingHash tableIn computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys , to their associated values . Thus, a hash table implements an associative array...
- 6.5 Retrieval on Secondary Keys
- Chapter 5 - Sorting
- Volume 4A - EnumerationEnumerationIn mathematics and theoretical computer science, the broadest and most abstract definition of an enumeration of a set is an exact listing of all of its elements . The restrictions imposed on the type of list used depend on the branch of mathematics and the context in which one is working...
and BacktrackingBacktrackingBacktracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c as soon as it determines that c cannot possibly be completed to a valid solution.The classic textbook example...
- Chapter 7 - Combinatorial searching
- 7.1 - Zeros and onesBinary numeral systemThe binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
- 7.1.1 - Boolean basics
- 7.1.2 - Boolean evaluation
- 7.1.3 - BitwiseBitwise operationA bitwise operation operates on one or more bit patterns or binary numerals at the level of their individual bits. This is used directly at the digital hardware level as well as in microcode, machine code and certain kinds of high level languages...
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-tupleTupleIn mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...
s - 7.2.1.2 - Generating all permutations
- 7.2.1.3 - Generating all combinationCombinationIn mathematics a combination is a way of selecting several things out of a larger group, where order does not matter. In smaller cases it is possible to count the number of combinations...
s - 7.2.1.4 - Generating all partitionsPartition (number theory)In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered to be the same partition; if order matters then the sum becomes a...
- 7.2.1.5 - Generating all set partitionsPartition of a setIn mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
- 7.2.1.6 - Generating all trees
- 7.2.1.7 - History and further references
- 7.2.1.1 - Generating all n-tuple
- 7.2.1 - Generating basic combinatorial patterns
- 7.1 - Zeros and ones
- Chapter 7 - Combinatorial searching
Outline of unpublished sections
- Volume 4B - GraphGraph theoryIn mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
and NetworkFlow networkIn graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in Operations Research, a directed graph is called a network, the vertices are called nodes and the edges are...
Algorithms, in preparation- Chapter 7 continued
- 7.2 - Generating all possibilities (Cont)
- 7.2.2 - Basic backtrack
- 7.2.3 - Efficient backtracking
- 7.3 - Shortest paths
- 7.4 - Graph algorithms
- 7.4.1 - Components and traversal
- 7.4.2 - Special classes of graphs
- 7.4.3 - Expander graphs
- 7.4.4 - Random graphs
- 7.5 - Network algorithms
- 7.5.1 - Distinct representatives
- 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 matroidMatroidIn combinatorics, a branch of mathematics, a matroid or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces....
algorithms
- 7.2 - Generating all possibilities (Cont)
- Chapter 7 continued
- Volumes 4C and 4D - OptimizationOptimization (mathematics)In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
and RecursionRecursionRecursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
, in preparation- Chapter 7 continued
- 7.7 - Discrete dynamic programmingDynamic programmingIn mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...
- 7.8 - Branch-and-bound techniques
- 7.9 - Herculean tasks (aka NP-hardNP-hardNP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
problems) - 7.10 - Near-optimizationApproximation algorithmIn computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
- 7.7 - Discrete dynamic programming
- Chapter 8 - RecursionRecursionRecursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
- Chapter 7 continued
- Volume 5 - Syntactic Algorithms, planned .
- Chapter 9 - Lexical scanningLexical analysisIn computer science, lexical analysis is the process of converting a sequence of characters into a sequence of tokens. A program or function which performs lexical analysis is called a lexical analyzer, lexer or scanner...
- Chapter 10 - ParsingParsingIn computer science and linguistics, parsing, or, more formally, syntactic analysis, is the process of analyzing a text, made of a sequence of tokens , to determine its grammatical structure with respect to a given formal grammar...
techniques (includes also string search and data compression)
- Chapter 9 - Lexical scanning
Current editions
These are the current editions in order by volume number:- Volume 1: Fundamental AlgorithmAlgorithmIn mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s. Third Edition (Reading, Massachusetts: Addison-Wesley, 1997), xx+650pp. ISBN 0-201-89683-4 - Volume 1, Fascicle 1: MMIXMMIXMMIX 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. (Addison-Wesley, February 14, 2005) ISBN 0-201-85392-2 (will be in the fourth edition of volume 1) - Volume 2: Seminumerical Algorithms. Third Edition (Reading, Massachusetts: Addison-Wesley, 1997), xiv+762pp. ISBN 0-201-89684-2
- Volume 3: SortingSorting algorithmIn computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...
and Searching. Second Edition (Reading, Massachusetts: Addison-Wesley, 1998), xiv+780pp.+foldout. ISBN 0-201-89685-0 - Volume 4A: Combinatorial Algorithms, Part 1. First Edition (Reading, Massachusetts: Addison-Wesley, 2011), xv+883pp. ISBN 0-201-03804-8
Complete volumes
These volumes were superseded by newer editions and are in order by date.- Volume 1, first edition, 1968, xxi+634pp, ISBN 0-201-03801-3.
- Volume 2, first edition, 1969, xi+624pp, ISBN 0-201-03802-1.
- Volume 3, first edition, 1973, xi+723pp+centerfold, ISBN 0-201-03803-X
- Volume 1, second edition, 1973, xxi+634pp, ISBN 0-201-03809-9.
- Volume 2, second edition, 1981, xiii+ 688pp, ISBN 0-201-03822-6.
Fascicles
Volume 4 fascicles 0–4 were revised and published as Volume 4A.- Volume 4, Fascicle 0: Introduction to combinatorial algorithmsCombinatoricsCombinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
and Boolean functions, (Addison-Wesley Professional, April 28, 2008) vi+240pp, ISBN 0-321-53496-4 - Volume 4, Fascicle 1: Bitwise tricks & techniques; Binary decision diagrams (Addison-Wesley Professional, March 27, 2009) viii+260pp, ISBN 0-321-58050-8
- Volume 4, Fascicle 2: Generating All tupleTupleIn mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...
s and permutationPermutationIn mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
s, (Addison-Wesley, February 14, 2005) v+127pp, ISBN 0-201-85393-0 - Volume 4, Fascicle 3: Generating all combinationCombinationIn mathematics a combination is a way of selecting several things out of a larger group, where order does not matter. In smaller cases it is possible to count the number of combinations...
s and partitionPartition (number theory)In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered to be the same partition; if order matters then the sum becomes a...
s. (Addison-Wesley, July 26, 2005) vi+150pp, ISBN 0-201-85394-9 - Volume 4, Fascicle 4: Generating all treeTree (graph theory)In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
s—History of combinatorial generation, (Addison-Wesley, February 6, 2006) vi+120pp, ISBN 0-321-33570-8
External links
- Overview of topics (Knuth's personal homepage)
- Oral history interview with Donald E. Knuth at Charles Babbage InstituteCharles Babbage InstituteThe 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, Minneapolis. Knuth discusses software patenting, structured programmingStructured programmingStructured 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 TeXTeXTeX is a typesetting system designed and mostly written by Donald Knuth and released in 1978. Within the typesetting system, its name is formatted as ....
. The oral history discusses the writing of The Art of Computer Programming. - "Robert W Floyd, In Memoriam", by Donald E. Knuth -(on the influence of Bob FloydRobert FloydRobert W Floyd was an eminent computer scientist.His contributions include the design of the Floyd–Warshall algorithm , which efficiently finds all shortest paths in a graph, Floyd's cycle-finding algorithm for detecting cycles in a sequence, and his work on parsing...
) - Who is Bill Gosper? (on the influence of Bill GosperBill GosperRalph William Gosper, Jr. , known as Bill Gosper, is an American mathematician and programmer from Pennsauken Township, New Jersey...
on the 2nd Edition of Volume 2.) - TAoCP and its Influence of Computer Science(Softpanorama)