Introduction to Algorithms

The first reason: you're taking a course and this is the text. The second reason: you are a working professional and think it might be useful. I have comments for each reason.

If you are taking a course, there is a good chance you will hate this book. This reminds me a lot of the Feynman Lectures of Physics: rapturously admired by people who have already mastered the material; a bit on the brain-numbing side for those who have never seen this stuff before.

This book (despite its bulk) is actually very concise in its treatment of topics. This means that you'll be reading along and suddenly realize it has left you behind. On the other and, it is also very precise, which means your problem is that you missed something. Fortunately, because it is concise, whatever that is is bound to be in the last page or so.

My advice to the student is this: learn to live with the Zen of this book, and you won't hate it. Simply accept that this book will take you on numerous short trips from mystification to epiphany. When you find yourself lost, back up a few paragraphs and really apply yourself. If this were easy stuff, everybody would do it.

For the professional, realize that this is NOT a cookbook. Don't go to this book to examine what an implementation of heap sort in C might look like, although users of languages like Python might be able to use some of the book's treatments of things like graph algorithms that way.

This is a book about designing algorithms, not implementing them. If you need to design an algorithm (much more likely in today's sophisticated, networked, massive data centric applications), this is your text. It is comprehensive, and has useful reviews of things like infinite series and probability that you're probably a bit rusty on.

This is a kind of book a professional wants when his job is giving his company a competitive edge at doing really, really hard stuff. It's not for people who buy books with names like "Visual Basic for Dummies".

If you are a teacher, I would say this: be prepared for students who don't like this book. However this book will get the job done, and will be something students who go on to advanced work will want to keep.

Kleinberg and Tardos, although not the kind of textbook you keep for the rest of your life, may be a better choice on the undergraduate level for several reasons. First, it introduces the material in a more gentle, pedagogical manner. Second, it makes more of an effort to introduce topics using somewhat realistic sounding problems; for me this is neither here nor there but students may be less likely to wonder "why are we studying this?" Third, it has solved exercises. Fourth, it's designed to fit conveniently into an undergraduate curriculum between a data structures course and a computation theory course.

That said, when ten years hence your student runs across a dynamic programming problem and remembers he studied this in school, it is CLRS that will get him back up to speed most quickly.

This book seems to generate strong opinions. I'll try to offer reasons for mine and
base them on examples from the book. I'm sorry this review is so long, but explanations
take more words than emotions. Most of this review was written bit by bit over about
five months, so it might not seem as coherent as I'd like it to be.

There are many errors in this book. It is a big book with a lot of information, so
there is room for a lot of errors. With each printing some of them are corrected.
There is a web site with a list of the errors that have been reported so far, who
reported them, and when they were fixed or will be fixed.
See http://mitpress.mit.edu/algorithms for the error list and other information about the
book. There seems to be fewer errors in each printing, so things are getting better, but
new errors in the first printing (2001), were still being reported in 2006 when the
seventh printing was current. The density of the reported errors decreases toward the back
of the book. I suspect that means fewer readers of the later chapters, rather than fewer
errors, which means the errors will be discovered over a longer time period. But most books
have errors, and based on my experience, computer books have more than most others.
This one is not as bad as some.

Most of my comments here are negative. Balance them against the fact that many instructors
have chosen this text after considering many alternatives. Some of my complaints are general
but supported by only one example. An example, or even several examples do not make the
case. The example documents where "something clicked," when I realized that I had seen
the same flaw several other times.

There were three authors for the first edition, and four for the current, second edition.
It is difficult to make all the chapters seem like they were written by the same person.
The authors did not succeed. Perhaps they did not even try. It does not hurt much.
I noticed the difference only while considering the following problem.

I can not tell what the goal or purpose of the book is. The authors do not seem to have
a clear idea either. The preface tells us it is "a comprehensive introduction" for
"undergraduate or graduate courses in algorithms or data structures" and "equally well
suited for self-study by technical professionals". It claims to be "versatile and
complete", "a mathematical desk reference or an engineering handbook", but "many
interesting algorithms could not be included due to lack of space."

The title is "Introduction to Algorithms" but the book goes well beyond introductory
material, both in depth of treatment and in topics covered. Factoring large integers
and the Fast Fourier Transform are not simple topics. But a little extra is always nice,
so perhaps this really is an introduction.

A lot of the bulk of the book is due to proofs of correctness. This is gold for
some readers and dross for others

There is a lot of math in the book, but it is not uniformly mathematical or uniformly
rigorous. Sometimes it seems the authors do not know what level they are trying for.
Chapter 5 is "Probabilistic Analysis and Randomized Algorithms." It says "If you are
unfamiliar with the basics of probability theory, you should read Appendix C, which
reviews this material." Appendix C says "This chapter reviews elementary combinatorics
and probability theory. If you have a good background in these areas, you may want to
skim the beginning of the chapter lightly and concentrate on the later sections."
Section C.5 is an advanced discussion of the tails of the Bernoulli distribution.

Some of the math sections are fairly advanced. There are subtle points I never saw before
in spite of my BS Math. In other places the math is overly simple. Appendix A is a review
of summations. There is a formula for the sum of the simplest arithmetic and geometric series,
but the general cases are ignored. Overall the level of the math seems close to "right."
If the title were changed to "Introduction to Algorithms and Analysis of Algorithms" then
the level would be fine. Readers uninterested in the mathematical analysis of the algorithms
or unable to follow the analysis need not despair. Most of the results are also presented in
English. This book is probably (just a guess) as good as most of the lighter, thinner,
and less expensive tomes for those readers.

The technique of partial fractions is used several times with the results presented as if by
magic instead of as the result of a simple technique. One sentence "look up partial fractions
in any calculus book" would help some readers. However, there is an extensive bibliography and
many pointers to one or more sources for many topics.

Many reviewers have complained about the pseudocode and I agree it is a weakness of the
book, but it is not a total mess. It is not APL or even similar to APL. It is closest
to Pascal, but there are differences. Variables are local unless otherwise indicated,
and that is fine. Variables are not declared and that is fine. Block structure is
indicated by indentation instead of words or symbols that mean begin and end, and that
would be fine except that the authors do not follow their claim. Instead, an apparently
meaningless keyword "do" introduces many blocks. It may have a meaning, but I could not
find it since it is not in the index. The result of the "do" is a block appears with mixed
indentation. Also, the indentation from one level to the next varies from place to place,
apparently from 3 to 7 spaces. It is hard to tell. I suspect the pseudocode is set in a
variable width typeface with spacing added to make it look fixed width. Perhaps the "do"
is a residue from Pascal where it is used to terminate the test portion of a WHILE or FOR
statement. If so, most style guides would have it with the test, rather than with the
block controlled by the test. I believe most readers would find it easier to understand the
pseudocode if they used a bottle of "whiteout" to erase all the instances of "do".

Assignments are done with an arrow instead of Pascal's ":=", and that is fine.
Comments are introduced by a special triangle symbol instead of any of the common
comment symbols. I can not imagine why.

In Pascal, functions return the value stored in the variable with the name of the function.
The pseudocode uses return statements which can have explicit values, and that is fine, (an
improvement in my opinion) but the return statement is not mentioned in the index.

Arrays are indexed from 1 to n, instead of from 0 to n-1. This is not a fault. The debate
over which is best has gone on for decades. Readers will have to adjust the index if they
compare the algorithms presented here with those in a source that uses Java, C, etc.
In at least one case, they also use zero base. In the section on Bucket Sort, the algorithm
uses both with no reason given for either.

The lack of answers to any of the problems can be a problem to most readers and will be
a major problem to those using the book for self education. Some answers can be found on
the web pages maintained by some CS instructors who use the text. I have no idea what
fraction of the answers are available, and offer no tips for finding them. The lack of
answers is made worse by another characteristic. Many claims are made in the text, with the
proof deferred to a problem. Sometimes the problem makes a further reference, even to a
different chapter. For example, the discussion of double hashing depends on problem 11.4-3,
which contains the hint "See chapter 31." Some readers might be willing to use a result
from a problem without seeing the proof. This is not always possible. Some problems express
something about an algorithm, perhaps a formula for running time, or a post condition, or a
fragment of implementation, or perhaps several alternative claims, and then ask which if any are true.

The authors deserve a star for intellectual honesty. Many authors freely lift historical
notes from elsewhere and repeat the information. Here, the historian (often Don Knuth)
is given credit as well as the inventor.

Some algorithms are presented in a recursive form when an iterative form is well known,
and sometimes much better known, and usually the original form. Merge sort is a good
example. This bias to the recursive form usually makes the analysis of run time easier
but might lead some developers to an inefficient implementation. I found a few cases where
the iterative form was mentioned in an exercise or problem. For example, in quicksort,
which partition to stack and which to sort is not asked, but can be discovered by solving
a problem on p162. Even Euclid's algorithm for the greatest common divisor is presented
as recursive. Exercise 31.2-4 asks for an iterative version.

In spite of the bulk of the book, it is not complete. For most topics it is not complete.
The authors do not claim it is complete; they explicitly state it is not. In general,
they have made a reasonable choice of material. Consider binary trees. There have been
many inventions for keeping binary trees in reasonable balance in spite of biased additions.
The authors ignore most of them. They provide very good coverage of red-black trees, which
may provide the best tradeoff between best possible balance and least effort spent adjusting.
Splay trees and skip lists get a few lines each.

There is a 17 page bibliography of 320 items.

The index is 36 pages of two columns, but it is not complete. It seems to cover some topics
thoroughly, but others less so. Definitions seem to be covered, but uses are often ignored.
For example, Sterling's approximation to n! is indexed where the formula is given, but not
any of the places where it is used. The entropy function is used as an example several times,
but is indexed only where it is defined. Some special notation conventions are explained
where they are introduced, but then not used immediately. The reader wondering what it is
good for is lost. The index does not help.

Some reviewers have berated reviewers that have not read the entire book. I plead guilty.
I'm using the book for a class that covers 20 of the 35 chapters, the first 15 and the five
chapters about graph algorithms. The book is good enough that I will probably read most
of the other chapters when I have the time.

The background of other reviewers seems to greatly influence some of their reviews.
So readers of this one can compensate for any of my biases, here is my background.
I'm a retired software engineer, having programmed digital computers since 1960.
BS math '68, MS CS '93. I wanted to take a class as part of my brain-rot prevention plan.
I picked one about analysis of algorithms because I'd seen a little of it in Knuth's books
and elsewhere, but had never done much of it. I've built and used many of the algorithms
discussed in the book. There may be topics that are poorly presented that I would not notice
because of that familiarity. There may be topics that are presented better than in any other
book that I would not notice because of that familiarity.

This paragraph was added more than a year after I finished the course that used the book.
It has drifted to the dusty end of the shelf. I use Knuth every few weeks and Skiena
occasionally. This tome was touched once, when a three page chapter on the Fast Fourier
Transform seemed too terse. After scanning the 27 pages here I went back to the three page version.

I have been using this book since 1995 (that was the first edition; the second is much better). It is a great book, and presents the subject in an incredibly clear way: too often I found that I didn't have to go back and re-read a paragraph or anything. The authors are excellent writers.

One thing I didn't like was the chapter on NP-completeness. It seems to be less clear than the rest of the book, but then maybe it's just me.

The exercises are good -- there are easy, medium and hard ones.

But even this book being excellent, I would recommend others as well -- some other books have a better coverage of parallel, distributed, approximated algorithms, and the theory of computational complexity is barely scratched in this book.

And one thing that I see people complaining about (and I agree with them) is the total absence of answer to exercises. There are some problems with this:

* People who study on their own have no way to tell if they really got it right. It's not an easy subject, and looking up the answer to get some positive reinfircement after you finished an exercise is an excellent way to enhance and speed up the learning process, as well as spotting mistakes;

* Not making answers available is some kind of message to instructors: "Don't bother creating your own sets of exercises; use those from the book, the students won't know the answers anyway". There are instructors who will use exercises from this book on tests (!) -- this is not good. Teachers should be able to come up with their own exercises and tests, and ***change them every time they teach the course!*** (I once saw a student with a pile of resolved exercises on Compilers. He said the teacher would always use exercises from a certain list in his test)

So, really... Not publicizing answers to at least part of the exercises makes no sense (that's why I am not giving it 5 stars).

The aspect I like the most of CLRS book on algorithm is that, the style of the book is lucid, the authors have made a sincere effort in putting forth the complicated aspects in analyzing the algorithm in way that could be understood by a wider audience taking some course in computer science in under-graduate or graduate level. The mathematical rigor makes s me wonder computer science algorithm analysis is nothing more than applied discrete mathematics for specific problems.

I bought a new copy of the book, and was happy to receive it the way I expected. Got free shipping with this one.