- Hardcover: 672 pages
- Publisher: Addison-Wesley Professional; 3 edition (July 17, 1997)
- Language: English
- ISBN-10: 9780201896831
- ISBN-13: 978-0201896831
- ASIN: 0201896834
- Product Dimensions: 6.4 x 1.7 x 9.3 inches
- Shipping Weight: 12.6 ounces (View shipping rates and policies)
- Average Customer Review: 56 customer reviews
- Amazon Best Sellers Rank: #71,355 in Books (See Top 100 in Books)
Enter your mobile number or email address below and we'll send you a link to download the free Kindle App. Then you can start reading Kindle books on your smartphone, tablet, or computer - no Kindle device required.
To get the free app, enter your mobile phone number.
The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd Edition 3rd Edition
Use the Amazon App to scan ISBNs and compare prices.
The Amazon Book Review
Author interviews, book reviews, editors picks, and more. Read it now
Frequently bought together
Customers who bought this item also bought
This magnificent tour de force presents a comprehensive overview of a wide variety of algorithms and the analysis of them. Now in its third edition, The Art of Computer Programming, Volume I: Fundamental Algorithms contains substantial revisions by the author and includes numerous new exercises.
Although this book was conceived several decades ago, it is still a timeless classic. One of the book's greatest strengths is the wonderful collection of problems that accompany each chapter. The author has chosen problems carefully and indexed them according to difficulty. Solving a substantial number of these problems will help you gain a solid understanding of the issues surrounding the given topic. Furthermore, the exercises feature a variety of classic problems.
Fundamental Algorithms begins with mathematical preliminaries. The first section offers a good grounding in a variety of useful mathematical tools: proof techniques, combinatorics, and elementary number theory. Knuth then details the MIX processor, a virtual machine architecture that serves as the programming target for subsequent discussions. This wonderful section comprehensively covers the principles of simple machine architecture, beginning with a register-level discussion of the instruction set. A later discussion of a simulator for this machine includes an excellent description of the principles underlying the implementation of subroutines and co-routines. Implementing such a simulator is an excellent introduction to computer design.
In the second section, Knuth covers data structures--stacks, queues, lists, arrays, and trees--and presents implementations (in MIX assembly) along with techniques for manipulating these structures. Knuth follows many of the algorithms with careful time and space analysis. In the section on tree structures, the discussion includes a series of interesting problems concerning the combinatorics of trees (counting distinct trees of a particular form, for example) and some particularly interesting applications. Also featured is a discussion of Huffmann encoding and, in the section on lists, an excellent introduction to garbage collection algorithms and the difficult challenges associated with such a task. The book closes with a discussion of dynamic allocation algorithms.
The clear writing in Fundamental Algorithms is enhanced by Knuth's dry humor and the historical discussions that accompany the technical matter. Overall, this text is one of the great classics of computer programming literature--it's not an easy book to grasp, but one that any true programmer will study with pleasure.
From the Back Cover
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 1995
I 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.
If 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.
It'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.
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.
Top customer reviews
I'd estimate that about half of this book is made up of exercises, and that's really where the value of it is: as high as the page count is, most of it is actually not published, but left for you to figure out! Some are programming exercises, but most are math exercises. I worked, or at least attempted, every single exercise in the book. In some cases, I had to content myself with just understanding what the question was asking for. Sometimes I wasn't able to succeed even then (don't judge me until you try it yourself). It took me about a year and three months, usually spending about 1/2 hour a day reading or working problems, to complete. Knuth assigns a difficulty rating from 0-50 to each problem where 0 is "trivial" and 50 is "unsolved research problem". The majority of the problems are in the 20 range, which he calls "reasonably difficult". None of these are simple "make sure you read the book" questions. Almost all of them require you to obtain some deeper insight into the material in order to figure out. There are a lot of proofs, and a lot of "design an algorithm" type questions.
The first third or so of the book is all mathematical preliminaries, specifically as they relate to computer programming and algorithmic analysis. Even if you have a strong background in discrete mathematics, there will be a lot you've never really thought about in here. From there he goes on to describe the hypothetical MIX computer whose assembler language all of the code samples (and code exercises) are written in. The second chapter, which starts on page 232 (there are only two chapters, albeit long ones, in this book), finally starts to dig into programming concepts and techniques. You think you know programming? Knuth spends over 200 pages discussing stacks, queues, linked-lists, trees, garbage collection and dynamic memory allocation. I don't care who you are, there's a lot of detail to these relatively fundamental concepts that you've never considered.
One of the biggest complaints that people throw at this book is its use of the MIX assembler for all of the code examples and exercises. I can sympathize: unless you're over 60, even if you have a good background in assembler language programming, MIX is bound to throw you for a loop. The examples are full of self-modifying code, magic numbers and hyper-optimized "tricks". Everything operates in words of five (six-bit!) bytes, and most of the examples rely on partial words; not something that modern programmers are used to dealing with.
There's no discussion in here of things like multithreading or security, just the solid fundamentals that make up every computer programming language or operating environment.
I think the most important is to study the Vol 1. It gives enough exposition to the Donald Knuth style and brilliant thinking. While the content is definitely important it is the level of thinking of the author that represents the main value of the book: you instantly understand the book was written by a great scientist and it does not matter much that now the contents of most chapters can be significantly improved using more modern sources. After all Vol 1 is more then a 30 years old book (it is older then Unix) and as such it should be outdated (we all believe in progress, don't we)... And it is not surprising that parts of Vol 1 on of TAOCP today look completely out of touch with reality especially MIX, the CPU instruction set that is used in all volumes.
Actually MIX instruction set (and thus assembler) was outdated even when the book was first published and more reflects unique Knuth's background with IBM 650. It was far from the state of hardware development even in late 60th when the first volume was published, the period when IBM/360 was the king of the hill.
Now IBM 650, a 1,966 lb machine that consumed almost 30 Kw of electricity looks more like a primitive calculator than a real computer: typical installation has the memory of just 10,000 decimal digits ( 1,000 words; 10 digit per word).
It's really sad that Knuth did not adopt System 360 architecture and PL/360 assembler (Wirth's structured assembler for S/360) for his books but we can do nothing about it. Still this is a book about timeless truths, not the book about the resent CS fashion like Java or you name it :-). It actually can serve as a perfect antidote against any current CS fashion.
And Knuth does provide pseudocode with his natural language algorithm description. And natural language pseudocode has an important advantage over 'structured pseudocode. The problem with a "structured pseudocode" is that the set of control structures is fixed and may not reflect the needs of a particular algorithms (branching out of loop is a common problem that is not addressed by structured programming well). Moreover it can cripple the algorithm by enforcing unnatural control structures, the structures that are absent in it but might be present in more modern languages. For example Perl has an interesting set of control structures that is superior to C. But even "Perl control structures set" can be improved further.
That's why assembler language is preferable: it never obscures "natural" control structures for each algorithms, structures that one day can be mapped into some new elegant language construct. Also as one review noted "sometimes high level languages with all their abstractions make things look more complex than they need be."
I would like to stress it again that each volume is very difficult to read; you really need to work on each chapter by reimplementing the examples that Knuth gives in your favorite language (assembler might help but is not essential).
Mathematical considerations as for average and worst running time of a particular algorithm can be largely ignored during the first couple of years of study of this book. Actually most mathematics in Vol. 1 can (and probably should) be initially completely ignored. See Softpanorama Classic Computer Books for more information.
On the negative side this is an overpriced book, if we are talking about students budget. To save money you can buy one of the first editions: there is not that much difference in content to justify the differences in price. The differences do not interfere with the study of the book. Knuth did an excellent work the first time he published each volume and for a significant improvement we probably need another century and another person.
Most recent customer reviews
For example, the following formula is very interesting for me.Read more