Search

The Online Encyclopedia and Dictionary

 
     
 

Encyclopedia

Dictionary

Quotes

 

The Art of Computer Programming

The Art of Computer Programming is a comprehensive monograph written by Donald Knuth which covers all kinds of programming algorithms. The first three volumes were published in rapid succession, starting in 1968. Volume 4 is currently in preparation, the first installment of which was published in February 2005, with additional installments planned approximately twice per year. Originally, the work was planned as a single volume, but the plan changed to seven volumes after the publisher saw the size of the first handwritten draft. The plan for Volume 4 has since expanded to include Volumes 4A, 4B, 4C, and possibly 4D. 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 was no longer available. So 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.

  • Volume 1 - Fundamental Algorithms
    • Chapter 1 - Basic concepts
    • Chapter 2 - Information structures
  • Volume 2 - Seminumerical Algorithms
  • Volume 3 - Sorting and Searching
  • Volume 4 - Combinatorial Algorithms, in preparation (fascicle 2 was published February 2005, and alpha-test versions of additional fascicles are downloadable from Knuth's page below).
    • Volume 4A, Enumeration and Backtracking
      • Chapter 7 - Combinatorial searching
    • Volume 4B, Graph and Network Algorithms
      • Chapter 7 cont.
    • Volume 4C and possibly 4D, Optimization and Recursion
      • Chapter 7 cont.
      • Chapter 8 - Recursion
  • Volume 5 - Syntactic Algorithms, planned.
    • Chapter 9 - Lexical scanning
    • Chapter 10 - Parsing techniques
  • Volume 6 - Theory of Context-Free Languages, planned.
  • Volume 7 - Compiler Techniques, planned.

All examples in the books use a language called "MIX assembly language," which runs on the hypothetical MIX computer. (Currently, the MIX computer is being replaced by the MMIX computer, which is a RISC version). Some readers are chagrined at the use of assembly language, but Knuth considers this necessary because algorithms need a context to judge speed and memory usage. Fortunately, there are free MIX emulators available for download.

American Scientist has included this work among the best twelve physical-science monographs of the twentieth century.

The famous offer of a reward check for any errors found, and the correction of these errors in subsequent printings, has contributed to the highly polished and continued authoritative nature of the work, long after its first publication.


English editions

  • Volume 1: Fundamental Algorithms. Third Edition (Reading, Massachusetts: Addison-Wesley, 1997), xx+650pp. ISBN 0-201-89683-4
  • Volume 2: Seminumerical Algorithms. Third Edition (Reading, Massachusetts: Addison-Wesley, 1997), xiv+762pp. ISBN 0-201-89684-2
  • Volume 3: Sorting and Searching. Second Edition (Reading, Massachusetts: Addison-Wesley, 1998), xiv+780pp.+foldout. ISBN 0-201-89685-0
  • Volume 1, Fascicle 1: MMIX -- A RISC Computer for the New Millennium. ISBN 0-201-85392-2
  • Volume 4, Fascicle 1: Boolean Techniques (in preparation).
  • Volume 4, Fascicle 2: Generating all Tuples and Permutations. ISBN 0-201-85393-0
  • Volume 4, Fascicle 3: Generating all Combinations and Partitions. ISBN 0-201-85394-9
  • Volume 4, Fascicle 4: Generating all Trees (preview available).

External links

The contents of this article are licensed from Wikipedia.org under the GNU Free Documentation License. How to see transparent copy