Customer Reviews

Introduction to Algorithms (MIT Electrical Engineering and Computer Science)

5 star:		(46)
4 star:		(13)
3 star:		(2)
2 star:		(5)
1 star:		(3)

 

 

I was the instructor for a junior/senior course on Algorithms at the University of Southern California and I used this book as the textbook. Unfortunately, many of the students didn't like this book because they did not appreciate the mathematical flavor of the book. A course on Algorithms is useless without a sound background in discrete mathematics. Hence, this book assumes that you are reasonably strong in Discrete Mathematics.

I haven't seen a better textbook ! Here are some reasons:

1. The discrete mathematics foundations are present in the first few chapters of this book and so, you can quickly brush up on any discrete math background that you may require while using this book.

2. The style of writing is very light and at the same time, rigorous - almost as if you are in the middle of a lecture while reading the book.

3. The material is comprehensive and serves as an excellent reference for other courses and in your future career.

4. The exercises and problems provide a very good learning experience.

5. It's a good-looking book !

It's a good thing that this book has a hard cover (make sure you get the hard cover edition, huh?), because otherwise mine would be in pieces. This book is my favourite book on algorithms. All the others seem somewhat unsatisfactory to me -- they are tied to particular programming languages, they are paperback, and they are for the most part less comprehensive than this book. (except Knuth, which is somewhat more advanced). See the summary of the TOC below for an outline of what the book covers. I guess Sedgewicks new title has been getting better reviews, but it's still not hard cover (-;

This covers a lot of topics, and covers them in some level of mathematical rigor. For example, all assertions about algorithm efficiency are backed up with *proofs*, and key concepts like asymptotics, and big-O notation are covered. To those who think proofs are not essential -- as a mathematician, I'd counter that proofs are absolutely necessary, because you don't know something until you've proven it -- it's easy to make wrong "guesses", or even wrong hand-waving arguments. The examples are all in pseudo-code. Personally, I liked this as it makes implementing the data structures an interesting exercise that forces the reader to think.

The subject matter covered is quite broad, see below. There are some interesting topics that don't get covered (eg AVL trees), but this book does a good job at laying down the foundation.

Some might be intimidated by the theoretical approach, but I for one like it. It's written for computer scientists (or "software engineers"), not get-rich-quick wannabees. This book will force you to think, and if you don't like that, well you can (and should) buy "learn algorithms in 21 seconds" from SAMS or something.

You'll need some background to digest this material. Someone with a year of programming and some discreet math should be ready for it. Note that you won't learn any programming *language* from this book (unless you count pseudo-coed), so you'd better know some before starting !

Summary: PartI: Intro, Growth of functions,Summations, Recurrences, Sets, Counting and Probability

Part II: Heapsort,Quicksort, Sorting in linear time, Medians/order statistics

Part III: Stacks/Queues/Linked lists, Hash tables, Binary search trees, Red-Black trees, Augmented data structures

Part IV: Dynamic programming,Greedy algorithms, Amortized analysis

Part V: B-trees, Binomial heaps, fibonacci heaps, data structures for disjoint sets

Part VI: Elementary graph algorithms, Minimal spanning trees, single-source shortes paths, all pairs shortest paths, maximum flow

Part VII: sorting networks, arithmatic circuits, algorithms for parallel computers, matrix operations, polynomials and fft, number theoretic algorithms, string matching, computational geometry, NP-completeness, Approximation algorithms.

I personally bought this book in preparation for the International Olympiad in Informatics (IOI), and it helped me immensely in getting off the ground with the algorithms I had to learn, especially the chapter on Dynamic Programming. Since then, however it has remained a priceless companion during my studies and at home.

This is the definitive reference for algorithms with a firm theoretical and mathematical foundation. Algorithms are treated with a thorough theoretical introduction often with a complete mathematical walkthrough, a clearly thought out solution, a discussion of its pros and cons, lots of clear and consisive diagrams, a pseudocode implementation, and a good deal of serious optimisation discussion. It's written in an accessible manner, starting with the elementary issues, progressing to the advanced and complex thinking needed to conquer them, so you'll find you have to give it your full concentration.

This book will not disappoint. Its explanations are rigorous and its coverage spans all the general purpose algorithms with little focus on their applications but rather on the algorithms themselves. The book covers such major areas as sorting, data structures, advanced design and analysis techniques, graphs, each about a hundred pages on average, and a selection of specialised algorithms such as parallel programming, string matching and computational geometry. Because these algorithms are used everywhere, from games, graphics and simulations to electrical engineering it will have a broad audience and will find a home almost anywhere there is serious programming involved. Each chapter is a unit in itself which means you don't need to read it cover to cover, since they all start off smoothly and handhold you through. Clearly written by professionals, this is the book I know contains the information that I can't find elsewhere.

Quote from a previous review:

Instead of touching on new technologies, such as AI, graphics, or anything else remotely relevant to today's demands on programmers and designers, this book, faithful to its MIT roots, gives a pompous, eggheaded distortion to the field of computers as a whole. Its focus is mainly on such trivialities as algorithm analysis, offering about 10 pages of proofs for each simple assertion. The points that the authors hope to make have no relevance whatsoever in a world in which processor power, not meticulous code optimization, reigns.

----------

I've had Cormen (one of the authors) as a professor in class, and my algorithms class uses this book, so admittedly my view might be a bit biased. But if you read the above (quoted) review, you might have gotten the wrong impression about this book. Cormen et. al. *intentionally* left "AI and graphics" algorithms to other authors; this isn't the place to cover those topics enough to do them justice. And as someone who has actually read the book, each proof is *not* 10 pages long. The examples are usually quite good, and concisely (if thoroughly explained). Finally, prof. Cormen always explains to his intro CS students why the study of algorithms is important, even as computers get faster and faster: some problems, poorly implemented, just *will not* run as well on a machine of today compared to a much older machine running a better algorithm. There will *always* be a justified place for the study and analysis of algorithms. Had the previous reviewer actually had met Prof. Cormen, he wouldn't be able to write the book off with the title of "pompous" or "eggheaded" either...

If one were to make a list of the 100 best books in computer science, then winnow that list down to 10 books, and then again down to 1 book, surely this would be that book.

Known in computer science circles as CLR (for the authors) or simply, "The White Book", Introduction to Algorithms by Cormen, Leiserson, and Rivest is the de-facto standard text for algorithms and data structures. It covers all the basic subjects (big-O notation, trees, graphs, etc...) as well as a few intermediate subjects (amortized analysis, matroids, etc...). Of course, this book is not the be-all and end-all of computer science nor does it pretend to be. It touches on NP-completeness only lightly and all but omits randomization; but if you wanted a text on NP-completeness, you would be reading Garey & Johnson and if you wanted randomization you'd go to Motwani & Raghavan. But if you need a reference on data structures and algorithms, this is the book for you.

Now, some have complained that while this book is an excellent reference that it is a poor text to learn from. I beg to differ. I concede that it is certainly more demanding than many other introductory texts, but this is a boon not a curse. By remaining true to computer science's mathematical heritage, Cormen et al. force the reader to become accustomed to rigourous, formal reasoning, something which is unfortunately absent in many computer science curricula. The authors present the concepts cleanly and clearly, without the distraction of any specific programming language/paradigm. Perhaps it is this removal from a familiar C/C++/Java/flavour-of-the-month/etc... milieu which makes some readers nervous. But it is precisely this separation which forces the reader up into the realm of abstraction where computer science truly resides.

I would just like to add a couple points to the review of this book here. First, it is a great introduction to the theoretical foundation of algorithms and computation, and it is not your average algorithm cook book. For that, you can find numerous books on various topics, such as "Algorithms in C" or "Numerical Recipes." Second, the assertion that it is processing power, not code optimization that reigns these days is simply missing the point. It is first of all not true, (just ask any programmers working on games, or serious business processing, or databases, or networks -- you name it -- code optimization is as important as ever; maybe your run of the mill GUI front end needs no optimization, but you wouldn't care about algorithms there anyway). And if you read the book, you will know that a lot of important problems only have exponetial solutions, and exponetial growth in hardware power (aka Moore's law) has a physical limitation. Therefore don't expect improvment in Intel chips to compensate for all of your bad programming. Third, this book pretty much only deals with asymptotic behaviors of algorithms. If you want to learn code optimization, it's by far not enough. You have to optimize the code behavior in each iterative cycle as well, such as reducing the number of comparisons, reducing memory references, reducing floating point multiplications and division etc. However, there seems to be no book on how to reduce such "constants" in algorithms. "Real-world" optimized code often involve techniques that's system dependent, or that uses information/boundary conditions that are not part of the general problem etc. There is no better teacher other than reading some good code or having a discussion with the field warriors - good programmers around you.

In summary, for its purpose - a relatively theoretical treatment of basic algorithms, this book is the best I have seen.

One sure sign of a book's poularity is it being referred to by an abbreviation or a nickname. This book is known as 'CLR', so that tells you something.

I called it the best 'single volume' in deference to Knuth's masterpieces in three volumes (with more planned!) - but if you want one book that provides a clear and rigorous presentation of data structures and algorithms that is optimum in both breadth as well as depth, then this is your book.

As the backcover says, some books on data structres and algorithms are rigorous but leave out many topics (eg Aho et al's excellent book), while others cover masses of material at the expense of rigour and correctness. (too many examples of this kind :-) !! ) This book makes the tall claim of being both rigorous and comprehensive - and it **more than lives up to it**.

This is not exactly meant for novices - but if you are comfortable with introductory college maths and have an analytical bent of mind, you should have little trouble following the material.

Starting with some of the required mathematical background, the authors cover basic data structures and their algorithms, searching and sorting in great detail, followed by a treatment of graph algorithms.

They then move to 'advanced algorithms', presenting an introduction to various specialsed fields, eg computational geometry, string algorithms, number-theoretic NP-completeness, and even Approximation algorithms.

The clarity of exposition is the book's greatest strength, not to mention the encyclopedic scope and the powerful rigorous analysis.

Another 'standout feature' are the illustrations, which will help clarify many concepts that words alone may not be able to.

All algorithms are presented in pseudocode, which can be easily adapted to your favourite programming language.

It is a great preparation for research in any field of computer science, and also an indispensable reference for anyone who does serious programming of any kind.

If you have anything whatsoever to do with algorithms, this is **the** book.

An excellent survey of the field of algorithms. From a mathematical perspective its lighter than Knuth and heavier than Sedgewick. If your algebra is rusty you'll have some problems, but you don't have to be a math whiz either. If your just looking for an algorithm "cookbook" you'd be better off with something else, but if you're looking to gain a very solid "undergraduate" level understanding in algorithms you couldn't do any better.

While this is the undisputed leader in the field and worth every penny you spend on it, the second edition is due in September 2001 - check out the book's website They mention that it's been extensively revised, with practically every section having something new, and they now use the concept of loop invariants throughout the book to analyse algorithm performance. (they also explain the 'Professor jokes' sprinkled throghout the problems).

More motivational material has also been included, perhaps for the benefit of those who think processor power is the cure-all for all computational problems !

Anyway, unless you're in a tearing hurry, i'd suggest that you wait till next month - i sure am going to.

For a detailed review of the first edition, please refer to my review below.

Are you confused by 'recursion'? Do you think NP stands for "Not Polynomial"? Well, then this is probably not the book for you. It's an algorithms text at the intermediate level (for beginners, use Sedgewick's "Algorithms in C++" series; for advanced go to Knuth or Flajolet/Sedgewick).

The coverage is incredible. Of course I have things I wish were in there in places of others, but I won't complain.

Reading the book strengthens the mind; carrying the book strengthens the body. Paying for the book, well, that's what credit cards were made for.