Art of Computer Programming, The, Volumes 1-3 Boxed Set (2nd Edition) (The Art of Computer Programming Series)

Each volume contains 2 chapters. Ch. 1, Basic Concepts: mathematical foundations and a description of MIX, a hypothetical machine (now available in software emulations). Ch. 2, Information Structures: lists, trees, memory allocation, garbage collection. Ch. 3, Random Numbers: how to produce series of "random" numbers and test their statistical properties. Ch. 4, Arithmetic: algorithms for integer and floating-point arithmetic. Ch. 5, Sorting: both in memory and on disks or tapes. Ch. 6, Searching: sequential, binary, hashing.

Despite the detailed coverage of the topics, which often involves esoteric mathematical notation, the author's lively style makes the algorithms and the main theoretical results relatively easy to grasp. If all you care about is getting a program to run, buy another book; but if you really want to understand how and why software works, there's nothing quite like this.


Excellent, for certain people!   April 4, 2000
106 out of 110 found this review helpful

These books are indisputably classics of the field, and like all classics they have religious adherents and equally firm detractors. The key difference between the two groups is that the adherents are interested in computer SCIENCE, whereas the rest are more taken with computer programming. The books are well written, quite mathematical, and abstract. The books deal with the core subjects of computer science and shy away from the trendy, and so some people tend to see them as anachronistic. Nevertheless, they are deservedly core references in computer science, and a joy for any patient, theoretically minded reader. There are three points I believe should be made. 1) a lot of the detractors of the books are saying correct things: the books don't deal with hot topics, they do present things in greater detail than is necessary in day to day programming, they are books they require a lot of the reader. What they don't recognize is that this is the intention, and that there is nothing wrong with that. The book is targeted at those with a geniune interest in theoretical computer science. 2) many reviewers complain about Knuth's typesetting system, TeX. What they fail to recognize is that TeX is incredibly useful, and about as user friendly as could be expected, for the task for which it was designed: typesetting professional quality mathematics. Anyone who challenges this statement would have to contend with virtually the entire community of people who write papers using higher mathematics, including virtually all professional physicists, mathematicians, and computer scientists. 3) some people accuse Knuth's books of being poorly written. These people are ignorant: either they have not read the works, or they would not recognize skillful writing if they saw it. These books are splendid examples of scientific writing, and are justifiably acclaimed as such. In short, Knuth's books have ensured that the word "science" deserves its place in the phrase "computer science"


THE classic work on Computer Programming Algorithms   July 6, 2005
B. Marold (Bethlehem, PA United States)
55 out of 61 found this review helpful

`The Art of Computer Programming' by Donald Knuth ranks, in its field, at roughly the same level as `Statistical Methods' by Snedecor and Cochrane in statistics, `Mastering the Art of French Cooking' by Julia Child in culinary technique, and William Van Ornim Quine's book on Symbolic Logic. It is instructive to point out that as important as these books are, they are not on the same level as, for example, Isaac Newton's `Principia Mathematica' or Charles Darwin's `The Origin of Species'. That is, these are great teaching manuals whose primary achievement is in their ability to communicate their subject with their audience.

It is also important to distinguish the subject of these books from what is loosely called Software Engineering. The greatest classic of Software Engineering is Fred Brooks' `The Mythical Man-Month', which deals with big issues of software design and allocation of human resources to software projects. Knuth's books deal with algorithms. While Brooks' software engineering is similar to architecture, Knuth is dealing with a subject similar to the subset of civil engineering which deals with the loadbearing capacities of structural materials and shapes.

In my very first course on computer programming, my instructor said that programming had relatively little to do with mathematics (unless you happened to be programming mathematical calculations). The entire math you really needed to know was how to add one to a number. What he neglected to say was that computer programming has a whole lot to do with the related subject of symbolic logic which, by dumb luck, as I happened to be starting in a major in Philosophy, I was quite conversant.

So, Knuth is teaching us about algorithms which are logically based procedures, almost always involving repetition of the same action, and which can be formalized in languages which can then be fed into a computer to perform a function.

In the three volumes of the projected seven that Knuth actually completed, one volume deals with `Seminumerical Algorithms'. What that means is that his mathematical subjects are generally not the ones useful to you and me in daily life or even to a statistician, actuary, or engineer. They are typically tools used by mathematicians from which they can construct the tools used by statisticians, actuaries, and engineers, and you and me. It is highly topical to realize that one of the most important applications of Knuth's algorithms in his second volume are essential to cryptanalysis and the construction of codes. Chapter 3 on computation involving random numbers is an especially important tool of code construction and code breaking. Chapter Four, dealing with some of the basic algorithms of arithmetic is also relevant to the study of codes as it includes algorithms involving primes.

In detailing what this book does not cover, I have gotten a bit off track in dealing with Volume 2 before talking about Volume 1 and the medium in which Knuth presents his ideas. As this series was started in the mid-1960s, the number of commonly known third generation languages could be counted on one hand. In the business world there was COBOL, in the scientific world there was a rudimentary version of FORTRAN, and in the schools, there was Basic. In my first computer programming course, we learned three languages, one of which was literally a machine language punched onto paper tape, one was a second generation language on a pre-IBM 360 mainframe, and one of which was a 2 generation language invented at my school, Lehigh University, called Wiz. It was a distant dialect of FORTRAN and it was strictly constructed as an educational tool. You may recall that the languages Basic, Pascal, and Modula 2 were also designed as training languages which simply busted out of their original use, in spite of serious limitations in language design.

All this is said in order to support the notion that in 1967, Knuth's inventing an assembly language (2nd generation) to teach algorithms was quite an accepted notion. So, this is what he did, and gave us the MIX language, named after the Roman numeral for 1009, which is the sum of the model numbers of sixteen different computers of the day which are similar to MIX and on which the MIX language can be simulated.

This was a time before the invention of C and UNIX when virtually all operating system software was written in assembly language. This included compilers, linkers, sorting utilities, disk management software and ... you name it, it was done in assembly language. Even a lot of applications had some assembly language routines in them for handling real processing bottlenecks.

This defines the application of most assembly language programming in its day. The main algorithms were those used in operating systems that managed the resources of the computer. And, in order to focus on the algorithms without prejudicing the dialogue by reference to a proprietary language, Knuth invented the generic MIX.

The most important contents of Knuth's books for a modern computer science student is his description of the major programming structures such as the tree, the stack, the queue, and the list plus his examples on how to analyze algorithms. Before you very modern students of object oriented programming pooh pooh something written in an assembly language, I should note that I was the hero of a major recent software project where I new how to use C to manipulate linked lists (learned from these very books), a technique for which C is exceptionally well suited, while my colleagues, all of whom, like me, came to programming from some other discipline with no benefit of formal training in programming structures.

There are certainly more modern books on these subjects, but there are probably none which are quite so authoritative and I suggest the effort in wading through the MIX language will pay off big time the next time you hit a particularly sticky application performance problem in you programming project.



Full of little gems   March 8, 2001
19 out of 19 found this review helpful

Knuth is obviously in the eduction business. This is a book written for learning from. It's very easy to ignore the parts that are too detailed for your needs and not feel like you've missed something. My favourite parts are his historical notes. These are the reward for ploughing through a section, some of them quite facinating.

I'm a compiler designer. Compilers like most other big applications are built on stacks, queues, lists, trees, etc. These books will teach you how to implement these structures solidly and effeciently. Alot of my time at work involves reading research papers on optimisations. I need to understand how algorithms are analysed and how to compare two algorithms. These books give the mathematical tools needed to perform that job. Some criticise his using a machine language for examples. I personally think that this is a good thing. Seeing something done in assembly shows you how easy it really is. Sometimes hhigh level languages with all their abstractions make things look more complex than they need be.


Nice to have all, but CS students can benefit mostly from vol 1   November 19, 2005
Nikolai N Bezroukov (Budd Lake, NJ)
18 out of 19 found this review helpful

All three volumes of The Art of Computer Programming (TAOCP), are classic. Each is IMHO a book that every CS student should try to study reimplementing example by example. Not many will succeed to finish even half of one volume, but if you do please buy all three of them :-).

I think it's very important to study Vol 1. It gives enough exposition to the Donald Knuth style and brilliant thinking. It is the level of thinking of the author that represents the main value of the book: you instantly understand the 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)...

Please note that parts of Vol 1 on of TAOCP looks completely out of touch with reality especially MIX assembler.

Actually MIX assembler was outdated even when the book was first published and more reflects unique Knuth's background with IBM 650, not so much the state of hardware development in late 60th, 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.

But actually the statement above is not true: this is a book about timeless truths, not the book about the resent CS fashion like Java or you name it :-).

Each volume is very difficult to read; you really need to work your way thru each chapter by reimplementing the examples that Knuth gives in your favorite language (assembler might help but it is not essential).

Mathematical considerations as for average and worst running time 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. 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.
Actually the differences are so minor that are almost unnoticeable. 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.