The Art of Computer Programming: Sorting and Searching. Volume 3 (Addison Wesley Series in Computer Science and Information Processing)

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

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.

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"

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.

The book is quite beneficial for all programmers in all ages. Not only the foundations of the programmer be improved, some techniques are also introduced in the best fashion yet