Customer Reviews

Art of Computer Programming, The, Volumes 1-3 Boxed Set (3rd Edition) (Vol 1-3)

5 star:		(38)
4 star:		(5)
3 star:		(4)
2 star:		(0)
1 star:		(3)

 

 

As Knuth himself says, it is impossible for any one person to keep up with all the research in computer science, but these 3 volumes do a remarkably good job of distilling the most important results and explaining them with mathematical rigor.

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.

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"

Twenty five years ago, after five years of experience programming scientific applications (mostly math stuff, not much real programming beyond algorithms) I began a job programming business applications. At that time, there was very little general communal knowledge about very basic stuff we take for granted today like searching, sorting, memory allocation, data structures...

I began my collection with Knuth and another book (no longer in print) dedicated to data structures. These books defined me as a programmer. I learned MIX only because, as a programmer, I felt that I should be able to understand Knuth's abstraction. I admit that I was frustrated by having to do this. Ironically, even back then, the "other book" used, what was the de facto standard for generically describing algorithms, an ALGOL like language-very pretty!

Many of us have looked forward to Knuth rewriting his artful collection to satisfy our sense of aesthetics. We don't consider that he would have to repeat this huge task over and over again. Or (save me from this one) he could produce an obnoxious series of books titled "The Art of Computer Programming in C", "The Art of Computer Programming in C++", "The Art of Computer Programming in JAVA", "The Art of Computer Programming in C#", and (my favorite) "The Art of Computer Programming for Dummies". I thank Knuth for not doing this, although the last would certainly have a wide audience. Publishers know what they are about.

Another reason, in my humble opinion, that Knuth probably holds to MIX is that the latest generation of programmers do not have a clue what it is like to program a machine directly, or what is happening underneath the hood. There is a huge leap from MIX to MACRO, but the basic principles are still relevant.

The bottom line: YOU CAN COMPLETELY IGNORE MIX! All the relevant ideas are explained in simple plane English and the algorithms in structured English. Those who would prefer not to understand, but to simply cut and paste code, you are simply out of luck.

Now, if that isn't insulting enough (you caught me on a good day (after 32 years of programming I have come to hate computers and ...)) you would be amazed at how many self proclaimed senior programmers (programmers with more than three years of experience?) can't write an algorithm to save their lives.

BUY THE BOOKS! THEYRE A BARGAIN!

By the way, you all should read some of Knuth's other works. How many of us know that Knuth was an important player in getting rid of GOTO statements? I haven't written a GOTO statement in over twenty years! If my memory serves me (on a good day) Knuth wrote in an April edition of the ACM a paper titled, "Goto Bad, ComeFrom Good". He would be pleased to know that he anticipated the Publish-Subscribe Architectural Pattern.

`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.

Not snob appeal. Yes, it's not a good first textbook. I taught freshman programming at Caltech for a few years, and I admit I didn't use Knuth to teach, in the sense that I didn't require the students to buy it, nor did I assign problems from it. But I *did* tell all my students to buy it (the box set) if they could afford it. And every now and then I did refer the students to look up some detail in Knuth that I felt our textbook (the also very excellent Aho, Hopcroft, and Ullman) had glossed over.

The reason is that when I prepared my notes, and when I went to class, I held a copy of Knuth in my hand. Full of post-its. It's not the best book for "learners" (i.e., beginners), but it's the ONLY book for the algorithm "pro". Sure, you can teach undergrads out of Sedgewick (Knuth's student by the way). But how do you make sure you're not missing something by using Sedgewick? By reading Knuth of course.

If I knew a bright high school student with an interest in computer programming, I'd get him the box set for Christmas. I have to admit I first ran into Knuth when I was a grade school student in the early 80s. There are lots of books in the library that a kid of say twelve just isn't interested in: whatever they are about is something that is just irrelevant and unknown. Not so with Knuth: I was programming BASIC on my C64 back then and knew what programming was. Knuth was downright scary. Here he is talking about simple things, and .... who would have known there would be so much to say about sorting???

about MIX: One day Knuth will be dead. Any programming language that existed during his lifetime will be dead. TeX will be at version pi(=4 atan 1). The Art of Computer Programming will still be relevant, most of it. This would not be the case if
the examples were coded in any "standard" programming language, with all the special-purpose things they all have (no not even if they were in Ruby on Rails!) With MIX, they will at least be in a programming notation as irrelevant then as it is now.

I have an anecdote... when I was a grad student a fellow grad student of mine had come up with a new cute algorithm using two priority queues to solve some problem in CAD. We did some literature searches.. could this be a new algorithm? Nothing came up. Search the web... nothing came up. Look in the standard books on CAD.. nothing came up. Time to publish?

Then I remembered I had a copy of Knuth (he didn't, as it's not fashionable to have forty-year-old books lying around if you're a CS grad student). Turns out the data structure and algorithm the fellow had come up with were described and analyzed in the answer to one of the exercises in Knuth's vol 3. As I recall it the exercise had difficulty level "30" (on Knuth's scale of 0-50).

I draw the conclusion that "active researchers" in a field that has anything to do with algorithms, who don't use Knuth, are at great risk of attracting ridicule for not having read up.

I re-read this book every now and then. Sometimes I read it in the bathroom. Even though I have read it several times, I always learn something new. Often on every page.

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.

The Art of Computer Programming is a classic work. The three first volumes cover only the basic core of programming techniques. There are enough exercices, with solutions, to keep you busy for the rest of your life. Several reviewers expressed a dislike at the MIX language used in these three volumes. But there is usually a pseudo-code description of the algorithm that can readily be converted to whatever "X" language you prefer or happen to enjoy on a particular day. I would never see Java (ouch!), C, Pascal, as being appropriate for this work. It would simply ruined the whole work. These languages have a semantics that is too imprecise. Knuth has gone one step further of including pseudo-code by providing precise code in a machine language that he has precisely described. What is needed is a new machine language closer to today's machine; and Knuth is working on that...but you will not find it in these three volumes.

Fascicle 1 of volume 1 has been published recently (summer 2005)-- for the final edition of this work with more volumes-- with a new machine language, the MMIX. It is a clear improvement on MIX. But we will have to wait for the final edition to see everything come together with MMIX. Go Don!

Every serious computer science student will see repeated references in other books to this wonderful set by Donald Knuth, professor emeritus of computer science at Stanford. He is acclaimed by many as the foremost computer programmer in progamming's brief sixty-year history. Its the best resource for the typical algorithm problem sets in most, traditional C and C++ courses. Those who see and enjoy programming as applied mathematics will find some spare cash to buy it.

Having this set on the shelf is somewhat like having a set of Shakespeare - its the best but not for everyone. One kind of expects to find Volume 1 of this set in the nightstand drawer at Silicon Valley hotels.

Knuth's set of books on the Art of programming are excellent academic books. However, I should like to warn everyone that they are not practical programming books. For one thing, they examine each subject in extreme detail. Someone looking for a quick review of sorting, for example, will find page after page of mathmatical formulae and definitions, detailing not only sorting in general but total orderings, keys, data structures, etc. Also, don't expect to steal any code from this book. All the algorithms are written in MIX, a hypotheical assembler language for an abstract machine. In fact MIX is so out of date, and the abstract machine so primitive, Knuth is promising to update both - but not very soon.
In short - these are great books. But they're not light reading and they are geared more for academic study rather than practical use.

I love reading technical books, in a wide variety of fields. I typically read technical books cover to cover, as if they were novels. I always enjoy learning a new algorithm or technique.

When I first saw this set in a bookstore (years ago), I thought it would be a great addition to my library. However, when I thumbed through it, I didn't seem to enjoy it as much as I'd hoped. It seemed to be a bit too theoretical, and not enough practical examples for my taste.

Recently, I decided to give it another chance on Amazon, thinking that I would better understand the theory after having more experience. Unfortunately, my first reaction stood-- as much as I tried to read it, I just couldn't find a section that I could enjoy or relate to.

In particular, the MIX code is a bit hard to read / follow. Personally, I would prefer a less precise but higher level pseudo-code. (Having to mentally translate the assembly code detracts from the examples.) In addition, I have a harder time relating to some of the examples, such as optimizing the merging of data from multiple tape drives.

There is no question that Knuth is a legend in Computer Science, and this is a very well written, highly regarded work in that field. I'm sure many people enjoy these books. However, this set just isn't something I personally was able to enjoy as much as I'd hoped to.