Seminum Algorithms

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.

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.

This book offers a stringent treatment of random number generators and algorithms not found anywhere else. It is particularly valuable for those that deal with encryption and the analysis of cyphers. The exercises add admirably to the text. References to other books in the field are extensive. The book is written in a non-wordy, but still very readable style, making it accessible to serious computer scientists at all levels. A mathematical background is necessary.