the art of computer programming the art of computer programming the art of computer programming volume 1 fundamental algorithms author donald knuth country united states language english genre nonfiction monograph publisher addison wesley publication date 1968 the book is still incomplete media type print hardcover dewey decimal 519l cclassqa 7675 the art of computer programming sometimes known by its initials taocp is a comprehensive monograph written by donald knuth that covers many kinds of programming algorithms and their analysis knuth began the project originally conceived as a single book with twelve chapters in 1962 the first three volumes of what was then expected to be a sevenvolume set were published in 1968 1969 and 1973 the first published installment of volume 4 appeared in paperback as fascicle 2 in 2005 the hardback volume 4a combining volume 4 fascicles 04 was published in 2011 volume 4 fascicle 6 satisfiability was released in december 2015 to be followed by volume 4 fascicle 5 mathematical preliminaries redux backtracking dancing links in december 2018 fascicles 5 and 6 are expected to comprise the first two thirds of volume 4b history donald knuth in 2005 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 by the burroughs corporation to write compilers 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 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 handwritten firstdraft manuscript completed in 1966 was 70033000000000000003000 pages long he had assumed that about five handwritten pages would translate into one printed page but his publisher said instead that about 1 handwritten pages translated to one printed page this meant the book would be approximately 70032000000000000002000 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 adviser to the publisher varga was visiting olga tausskytodd and john todd at caltech with vargas enthusiastic endorsement the publisher accepted knuths 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 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 was no longer available in 1977 he decided to spend some time creating something more suitable eight years later he returned with tex which is currently used for all volumes the offer of a socalled knuth reward check worth one hexadecimal dollar 100hex base 16 cents in decimal is 256 for any errors found and the correction of these errors in subsequent printings has contributed to the highly polished and stillauthoritative 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 warmup exercises to unsolved research problems knuths dedication reads this series of books is affectionately dedicatedto the type 650 computer once installed atcase institute of technologywith whom i have spent many pleasant evenings assembly language in the book 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 software such as gnu mdk exists to provide emulation of the mix architecture knuth considers the use of assembly language necessary for the speed and memory usage of algorithms to be judged critical response knuth was awarded the 1974 turing award for his major contributions to the analysis of algorithms 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 volume 3 sorting and searching chapter 5 sorting chapter 6 searching volume 4a combinatorial algorithms chapter 7 combinatorial searching part 1 planned volume 4b combinatorial algorithms chapters 7 8 released in several subvolumes chapter 7 combinatorial searching continued chapter 8 recursion volume 5 syntactic algorithms as of 2017 estimated for release in 2025 chapter 9 lexical scanning also includes string search and data compression chapter 10 parsing techniques volume 6 the theory of contextfree languages volume 7 compiler techniques chapter outlines completed volume 1 fundamental algorithms chapter 1 basic concepts 11 algorithms 12 mathematical preliminaries 121 mathematical induction 122 numbers powers and logarithms 123 sums and products 124 integer functions and elementary number theory 125 permutations and factorials 126 binomial coefficients 127 harmonic numbers 128 fibonacci numbers 129 generating functions 1210 analysis of an algorithm 1211 asymptotic representations 12111 the onotation 12112 eulers summation formula 12113 some asymptotic calculations 13 mmix mix in the hardback copy but updated by fascicle 1 131 description of mmix 132 the mmix assembly language 133 applications to permutations 14 some fundamental programming techniques 141 subroutines 142 coroutines 143 interpretive routines 1431 a mix simulator 1432 trace routines 144 input and output 145 history and bibliography chapter 2 information structures 21 introduction 22 linear lists 221 stacks queues and deques 222 sequential allocation 223 linked allocation 224 circular lists 225 doubly linked lists 226 arrays and orthogonal lists 23 trees 231 traversing binary trees 232 binary tree representation of trees 233 other representations of trees 234 basic mathematical properties of trees 2341 free trees 2342 oriented trees 2343 the infinity lemma 2344 enumeration of trees 2345 path length 2346 history and bibliography 235 lists and garbage collection 24 multilinked structures 25 dynamic storage allocation 26 history and bibliography volume 2 seminumerical algorithms chapter 3 random numbers 31 introduction 32 generating uniform random numbers 321 the linear congruential method 3211 choice of modulus 3212 choice of multiplier 3213 potency 322 other methods 33 statistical tests 331 general test procedures for studying random data 332 empirical tests 333 theoretical tests 334 the spectral test 34 other types of random quantities 341 numerical distributions 342 random sampling and shuffling 35 what is a random sequence 36 summary chapter 4 arithmetic 41 positional number systems 42 floating point arithmetic 421 singleprecision calculations 422 accuracy of floating point arithmetic 423 doubleprecision calculations 424 distribution of floating point numbers 43 multiple precision arithmetic 431 the classical algorithms 432 modular arithmetic 433 how fast can we multiply 44 radix conversion 45 rational arithmetic 451 fractions 452 the greatest common divisor 453 analysis of euclids algorithm 454 factoring into primes 46 polynomial arithmetic 461 division of polynomials 462 factorization of polynomials 463 evaluation of powers 464 evaluation of polynomials 47 manipulation of power series volume 3 sorting and searching chapter 5 sorting 51 combinatorial properties of permutations 511 inversions 512 permutations of a multiset 513 runs 514 tableaux and involutions 52 internal sorting 521 sorting by insertion 522 sorting by exchanging 523 sorting by selection 524 sorting by merging 525 sorting by distribution 53 optimum sorting 531 minimumcomparison sorting 532 minimumcomparison merging 533 minimumcomparison selection 534 networks for sorting 54 external sorting 541 multiway merging and replacement selection 542 the polyphase merge 543 the cascade merge 544 reading tape backwards 545 the oscillating sort 546 practical considerations for tape merging 547 external radix sorting 548 twotape sorting 549 disks and drums 55 summary history and bibliography chapter 6 searching 61 sequential searching 62 searching by comparison of keys 621 searching an ordered table 622 binary tree searching 623 balanced trees 624 multiway trees 63 digital searching 64 hashing 65 retrieval on secondary keys volume 4a combinatorial algorithms part 1 chapter 7 combinatorial searching 71 zeros and ones 711 boolean basics 712 boolean evaluation 713 bitwise tricks and techniques 714 binary decision diagrams 72 generating all possibilities 721 generating basic combinatorial patterns 7211 generating all ntuples 7212 generating all permutations 7213 generating all combinations 7214 generating all partitions 7215 generating all set partitions 7216 generating all trees 7217 history and further references planned volume 4b 4c 4d combinatorial algorithms chapter 7 combinatorial searching continued 72 generating all possibilities continued 722 backtrack programming 7221 dancing links 7222 satisfiability 7223 constraint satisfaction 7224 hamiltonian paths 7225 cliques 7226 covers 7227 squares 7228 a potpourri of puzzles 7229 estimating backtrack costs 723 generating inequivalent patterns 73 shortest paths 74 graph algorithms 741 components and traversal 742 special classes of graphs 743 expander graphs 744 random graphs 75 network algorithms 751 distinct representatives 752 the assignment problem 753 network flows 754 optimum subtrees 755 optimum matching 756 optimum orderings 76 independence theory 761 independence structures 762 efficient matroid algorithms 77 discrete dynamic programming 78 branchandbound techniques 79 herculean tasks aka nphard problems 710 nearoptimization chapter 8 recursion volume 5 syntactic algorithms as of 2017 estimated for release in 2025 chapter 9 lexical scanning includes also string search and data compression chapter 10 parsing techniques volume 6 the theory of contextfree languages volume 7 compiler techniques english editions current editions these are the current editions in order by volume number the art of computer programming volumes 14a boxed set third edition reading massachusetts addisonwesley 2011 3168pp isbn9780321751041 0321751043 volume 1 fundamental algorithms third edition reading massachusetts addisonwesley 1997 xx650pp isbn9780201896831 0201896834 errata 2011 volume 2 seminumerical algorithms third edition reading massachusetts addisonwesley 1997 xiv762pp isbn9780201896848 0201896842 errata 2011 volume 3 sorting and searching second edition reading massachusetts addisonwesley 1998 xiv780ppfoldout isbn9780201896855 0201896850 errata 2011 volume 4a combinatorial algorithms part 1 first edition reading massachusetts addisonwesley 2011 xv883pp isbn9780201038040 0201038048 errata 20170918 printing volume 1 fascicle 1 mmix a risc computer for the new millennium addisonwesley 20050214 isbn0201853922 will be in the fourth edition of volume 1 errata 20160802 volume 4 fascicle 5 mathematical preliminaries redux backtracking dancing links addisonwesley 20181231 320pp isbn9780134671796 will become part of volume 4b volume 4 fascicle 6 satisfiability addisonwesley 20151208 xiii310pp isbn9780134397603 errata 20170601 will become part of volume 4b previous editions complete volumes these volumes were superseded by newer editions and are in order by date volume 1 fundamental algorithms first edition 1968 xxi634pp isbn0201038013 volume 2 seminumerical algorithms first edition 1969 xi624pp isbn0201038021 volume 3 sorting and searching first edition 1973 xi723ppfoldout isbn020103803x errata volume 1 fundamental algorithms second edition 1973 xxi634pp isbn0201038099 errata volume 2 seminumerical algorithms second edition 1981 xiii 688pp isbn0201038226 errata the art of computer programming volumes 13 boxed set second edition reading massachusetts addisonwesley 1998 pp isbn9780201485417 0201485419 fascicles volume4s fascicles 04 were revised and published as volume4a volume 4 fascicle 0 introduction to combinatorial algorithms and boolean functions addisonwesley professional 20080428 vi240pp isbn0321534964 errata 20110101 volume 4 fascicle 1 bitwise tricks techniques binary decision diagrams addisonwesley professional 20090327 viii260pp isbn0321580508 errata 20110101 volume 4 fascicle 2 generating all tuples and permutations addisonwesley 20050214 v127pp isbn0201853930 errata 20110101 volume 4 fascicle 3 generating all combinations and partitions addisonwesley 20050726 vi150pp isbn0201853949 errata 20110101 volume 4 fascicle 4 generating all trees history of combinatorial generation addisonwesley 20060206 vi120pp isbn0321335708 errata 20110101 prefascicles volume4s prefascicles 5a5c and 6a were revised and published as fascicles 5 and 6 volume 4b prefascicle 5a mathematical preliminaries redux available for download volume 4b prefascicle 5b introduction to backtracking available for download volume 4b prefascicle 5c dancing links available for download volume 4b prefascicle 6a a draft of section 7222 satisfiability available for download introduction to algorithms notes citations sources slater robert 1987 portraits in silicon mit press isbn0262192624 shasha dennis lazere cathy 1995 out of their minds the lives and discoveries of 15 great computer scientists copernicus isbn0387979921 overview of topics knuths personal homepage oral history interview with donald e knuth at charles babbage institute university of minnesota minneapolis knuth discusses software patenting structured programming collaboration and his development of tex 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 taocp and its influence of computer science softpanorama vtedonald knuthpublications the art of computer programming the complexity of songs computers and typesetting concrete mathematics surreal numbers things a computer scientist rarely talks about selected papers series software tex metafont mixal mix mmix gnu mdk fonts ams euler computer modern concrete roman literate programming web cweb algorithms knuths algorithm x knuthbendix completion algorithm knuthmorrispratt algorithm knuth shuffle robinsonschenstedknuth correspondence trabb pardoknuth algorithm generalization of dijkstras algorithm knuths simpath algorithm other dancing links knuth reward check knuth prize man or boy test quaterimaginary base yllion potrzebie system of weights and measures 