Home      Discussion      Topics      Dictionary      Almanac
Signup       Login
The Art of Computer Programming

The Art of Computer Programming

Discussion
Ask a question about 'The Art of Computer Programming'
Start a new discussion about 'The Art of Computer Programming'
Answer questions from other users
Full Discussion Forum
 
Encyclopedia
The Art of Computer Programming (acronym: TAOCP) is a comprehensive monograph
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


After winning a Westinghouse Talent Search scholarship, Knuth enrolled at the Case Institute of Technology (now Case Western Reserve University
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 computer
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...

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

 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 Scientist
American 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 - Sorting
    Sorting algorithm
    In 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
    Search algorithm
    In 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 - Combinatorial
    Combinatorics
    Combinatorics 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 - Enumeration
      Enumeration
      In 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 Backtracking
      Backtracking
      Backtracking 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 - Graph
      Graph theory
      In 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 Network
      Flow network
      In 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 - Optimization
      Optimization (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 Recursion
      Recursion
      Recursion 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 5 - Syntactic Algorithms, planned (as of 2011, estimated in 2020) (chapters 9 and 10)
  • Volume 6 - Theory of Context-Free Language
    Context-free language
    In 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 - Compiler
    Compiler
    A 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 structures
    Data structure
    In 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 numbers
    Statistical randomness
    A 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 - Arithmetic
    Arithmetic
    Arithmetic 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 - Sorting
    Sorting algorithm
    In 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 - Searching
    Search algorithm
    In 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 - Recursion
    Recursion
    Recursion 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 scanning
    Lexical analysis
    In 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 - Parsing
    Parsing
    In 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 search
    String searching algorithm
    String 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 compression
    Data compression
    In 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 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
      • 1.2 Mathematical Preliminaries
      • 1.3 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...

      • 1.4 Some Fundamental Programming Techniques
    • Chapter 2 - Information structures
      • 2.1 Introduction
      • 2.2 Linear Lists
      • 2.3 Trees
        Tree (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
  • 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 Quantities
        Pseudo-random number sampling
        Pseudo-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 Sequence
        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 X1,...,Xn be independent random variables...". Yet as D. H. Lehmer stated in...

        ?
      • 3.6 Summary
    • Chapter 4 - Arithmetic
      • 4.1 Positional Number Systems
        Positional notation
        Positional 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 Arithmetic
        Arbitrary-precision arithmetic
        In 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 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...

         Conversion
      • 4.5 Rational
        Rational number
        In 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 Polynomial
        Polynomial
        In 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
  • Volume 3 - Sorting and Searching
    • Chapter 5 - Sorting
      Sorting algorithm
      In 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 Permutation
        Permutation
        In 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 sorting
        Internal sort
        An 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 Sorting
        External sorting
        External 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
    • Chapter 6 - Searching
      Search algorithm
      In 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 Keys
        Unique key
        In 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 Hashing
        Hash table
        In 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
  • Volume 4A - Enumeration
    Enumeration
    In 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 Backtracking
    Backtracking
    Backtracking 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 ones
        Binary numeral system
        The 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 - Bitwise
          Bitwise operation
          A 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-tuple
            Tuple
            In 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 combination
            Combination
            In 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 partitions
            Partition (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 partitions
            Partition of a set
            In 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

Outline of unpublished sections

  • Volume 4B - Graph
    Graph theory
    In 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 Network
    Flow network
    In 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 matroid
          Matroid
          In 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
  • Volumes 4C and 4D - Optimization
    Optimization (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 Recursion
    Recursion
    Recursion 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 programming
        Dynamic programming
        In 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-hard
        NP-hard
        NP-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-optimization
        Approximation algorithm
        In 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...

    • Chapter 8 - Recursion
      Recursion
      Recursion 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 5 - Syntactic Algorithms, planned .
    • Chapter 9 - Lexical scanning
      Lexical analysis
      In 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 - Parsing
      Parsing
      In 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)

Current editions


These are the current editions in order by volume number:
  • Volume 1: Fundamental 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
    . Third Edition (Reading, Massachusetts: Addison-Wesley, 1997), xx+650pp. ISBN 0-201-89683-4
  • 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
    . (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: Sorting
    Sorting algorithm
    In 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 algorithms
    Combinatorics
    Combinatorics 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 tuple
    Tuple
    In 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 permutation
    Permutation
    In 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 combination
    Combination
    In 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 partition
    Partition (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 tree
    Tree (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 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, Minneapolis. 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 ....

    . 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 Floyd
    Robert Floyd
    Robert 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 Gosper
    Bill Gosper
    Ralph 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)