The Art of Computer Programming, Volume 1: Fundamental Algorithms

✍ Scribed by Knuth, Donald Ervin

• Publisher: Addison-Wesley
• Year: 1997;2013
• Tongue: English
• Leaves: 677
• Edition: 3. ed., 31. print
• Category: Library

✦ Synopsis

The bible of all fundamental algorithms and the work that taught many of today's software developers most of what they know about computer programming.-Byte, September 1995I can't begin to tell you how many pleasurable hours of study and recreation they have afforded me! I have pored over them in cars, restaurants, at work, at home... and even at a Little League game when my son wasn't in the line-up.-Charles LongIf you think you're a really good programmer... read [Knuth's] Art of Computer Programming... You should definitely send me a resume if you can read the whole thing.-Bill GatesIt's always a pleasure when a problem is hard enough that you have to get the Knuths off the shelf. I find that merely opening one has a very useful terrorizing effect on computers.-Jonathan Laventhol This first volume in the series begins with basic programming concepts and techniques, then focuses more particularly on information structures-the representation of information inside a computer, the structural relationships between data elements and how to deal with them efficiently. Elementary applications are given to simulation, numerical methods, symbolic computing, software and system design. Dozens of simple and important algorithms and techniques have been added to those of the previous edition. The section on mathematical preliminaries has been extensively revised to match present trends in research.
Ebook (PDF version) produced by Mathematical Sciences Publishers (MSP), http: //msp.org

✦ Table of Contents

Cover......Page 1
Title Page......Page 5
Preface......Page 7
Preface to the Third Edition......Page 13
Procedure for Reading......Page 15
Notes on the Exercises......Page 17
Contents......Page 20
Algorithms......Page 23
Mathematical Preliminaries......Page 32
Mathematical Induction......Page 33
Numbers, Powers, and Logarithms......Page 43
Sums and Products......Page 49
Integer Functions and Elementary Number Theory......Page 61
Permutations and Factorials......Page 67
Binomial Coefficients......Page 74
Harmonic Numbers......Page 97
Fibonacci Numbers......Page 101
Generating Functions......Page 109
Analysis of an Algorithm......Page 118
* The O-notation......Page 129
* Euler's summation formula......Page 133
* Some asymptotic calculations......Page 138
Description of MIX......Page 146
The MIX Assembly Language......Page 166
Applications to Permutations......Page 186
Subroutines......Page 208
Coroutines......Page 215
Interpretive Routines......Page 222
A MIX simulator......Page 224
* Trace routines......Page 234
Input and Output......Page 237
History and Bibliography......Page 251
Introduction......Page 254
Stacks, Queues, and Deques......Page 260
Sequential Allocation......Page 266
Linked Allocation......Page 276
Circular Lists......Page 295
Doubly Linked Lists......Page 302
Arrays and Orthogonal Lists......Page 320
Trees......Page 330
Traversing Binary Trees......Page 340
Binary Tree Representation of Trees......Page 356
Other Representations of Trees......Page 370
Basic Mathematical Properties of Trees......Page 384
Free trees......Page 385
Oriented trees......Page 394
* The ``infinity lemma''......Page 404
* Enumeration of trees......Page 408
Path length......Page 421
* History and bibliography......Page 428
Lists and Garbage Collection......Page 430
Multilinked Structures......Page 446
Dynamic Storage Allocation......Page 457
History and Bibliography......Page 479
Answers to Exercises......Page 488
1. Fundamental Constants (decimal)......Page 641
2. Fundamental Constants (octal)......Page 642
3. Harmonic Numbers, Bernoulli Numbers, Fibonacci Numbers......Page 643
Appendix B: Index to Notations......Page 645
Appendix C: Index to Algorithms and Theorems......Page 650
Index and Glossary......Page 652

✦ Subjects

Computer Science;Programming;Science;Technology;Nonfiction;Computers;Technical;Reference;Software;Algorithms