Seems like the other book people recommend is "Introduction to Algorithms" by Cormen et al, so that the main problem in choosing an algorithms book is really deciding between that one and this one.
I've spent more time with the Cormen book so far and only a little with "The Algorithm Design Manual", but have to say I've been disappointed with Cormen and very impressed by the ADM.
I think the Cormen book has a reputation for being more serious, and it does give more in-depth mathematical treatments of the algorithms covered—but honestly, I think it's a mistake to consider it more serious for that reason. There's a time where I would have stopped reading this comment and ordered the Cormen book, but I think it's worthwhile to consider criteria for a book being serious. In the realm of software, I'll argue that the most important measure is how much the book improves your ability to create serious software—and under those conditions, The Algorithm Design Manual takes the prize.
In case there's still ambiguity on what 'serious software' might mean, I'll point out that the ADM is not a recipe book—I'm not trying to say, "practically speaking the algorithm problems in software are solved, you just have to copy and paste the source for the required algorithm." For crafting difficult, original algorithms, I still think ADM will be more useful.
I also spent more time with CLRS, I've had my copy for close to a decade now :)
I found ADM to be much less useful. It was mostly a small bit of code per concept, with little explanation or proofs or information about why it worked. If I wanted to copy and paste code, I wouldnt've gotten a book, I'dve searched Google. I'm much more comfortable with the knowledge I obtained from CLRS, because I know not just how to code the things (since there's pseudocode for them) but why they work, and how to debug things when they break. Overall, whereas I'd class CLRS as one of the best purchases I've ever made (in terms of dollars/use of the product), I'd class ADM as one of the worst, and that's even considering it was like $5 used :)
I think this sample exemplifies what ADM is quite good at:
"Why is sorting worth so much attention? There are several reasons:
• Sorting is the basic building block that many other algorithms are built around. By understanding sorting, we obtain an amazing amount of power to solve other problems.
• Most of the interesting ideas used in the design of algorithms appear in the context of sorting, such as divide-and-conquer, data structures, and randomized algorithms.
• Computers have historically spent more time sorting than doing anything else. A quarter of all mainframe cycles were spent sorting data [Knu98]. Sorting remains the most ubiquitous combinatorial algorithm problem in practice.
• Sorting is the most thoroughly studied problem in computer science. Literally dozens of different algorithms are known, most of which possess some particular advantage over all other algorithms in certain situations.
In this chapter, we will discuss sorting, stressing how sorting can be applied to solving other problems. In this sense, sorting behaves more like a data structure than a problem in its own right. We then give detailed presentations of several fundamental algorithms: heapsort, mergesort, quicksort, and distribution sort as examples of important algorithm design paradigms."
This kind of information on context is much more difficult to find than proofs. The idea that sorting algorithms are good, stripped down exemplars of general purpose algorithm concepts is something I've never heard pointed out elsewhere—and the text is full of these golden, context-related insights. Once you have a firm grasp of the principles involved, then CLRS or google become useful references (though, tbh, it's extraordinarily rare I find myself reaching for CLRS over google). I just tested and it took me less than 15 seconds to find a proof for the running time of mergesort, which is basically all that CLRS offers over ADM.
>This kind of information on context is much more difficult to find
Yes, but its also highly subjective & imho useless information. Emanuel Derman often writes about this problem, and it is something I have observed very frequently at workplaces - this present generation seems to be obsessed with meta-knowledge rather than actual knowledge. He points out its better to know a few things but know them indepth, rather than have an ability to talk about everything without actually knowing what those things really are. When I ask people to implement ordinary least squares from scratch, literally like 5% of the people interviewed manage to do that, & they are very, very good. The remaining 95% "know about ols" but don't "know ols" ie. they will give me lots of mumbo jumbo about how ols is the building block of statistics & how it is affected by outliers & so forth - but can't implement one to save their lives. When it comes to sorting, I vastly prefer somebody who can implement atleast one of O(n) ( postman sort), O(n^2) ( bubblesort) or O(nlogn) ( mergesort, several others ) rather than somebody who can give me all this context & then say I will google the actual algorithm. CLRS teaches you how things actually work. ADM is imho good for acing interviews conducted by managerial types (PMs/EMs) who want you to namedrop & give lots of context & color without actually doing any real work.
I can understand your complaint here, and I agree with you that people can easily go too far in the direction of 'when to implement' versus 'how to implement'—but I'm pretty sure the key is (1) Both are required, (2) it makes more sense for one of these things to precede the other.
However, I think that you’re also conflating two approaches to learning ‘context.’ One gives people an elaborate index for finding implementations when required, so that they become capable ‘solution googlers.’ This is unquestionably an inadequate approach to education. However, there is another approach to context which emphasizes principles. ‘Principles’ can be a vague word itself, but I’ll try to be more precise about it: you have understood something ‘by principles’ when you first understood a more general structure, then, in order to learn the more particular thing, you understood which parameters must be supplied to the more general structure in order to get the more particular one. E.g., you learn principles of programming languages first, then can understand new languages as parameterizations of your prior, more general knowledge. I think the context material in ADM serves as a nice guide for acquiring principles in this sense. The bit I quoted is largely significant because of their emphasis on principles.
It’s interesting that you think ADM would be the book for faking an interview. I have the exact opposite stance. If I wanted to impress a typical software person (e.g. a yet to be determined interviewer), I’d learn a lot of the details from CLRS, rather than going for ADM.
I think you're overlooking that whys and whens are still knowledge leading to understanding of a concept, and they tend to come before the hows. You want to understand why you're using the algorithm before you begin working on how to implement the algorithm. As an extreme example, consider us teaching the Quicksort and the Bogosort as pure implementation but without explanation on usage. Granted, this is unlikely to ever happen, but it serves to illustrate that this kind of knowledge is part of the understanding of any algorithm, or even further, any concept.
Now the context you're referring to regarding your "implementing ols" example seems to be largely assorted trivia to be honest. They don't know the answer, they're filling in something, and have done so through highschool and then college because something might get mercy marks. I'd like to disagree on giving that the moniker meta-knowledge, it's losely tied factoids at best.
I completely agree that deep understanding of concepts is incredibly important, but i think it's unlikely we'll see large scale change in that attitude. The way I see incentive structures for students, making that shift unconsciously is disincentivised, since moving from a cramming schedule to a more thourough approach puts you even further behind temporarily which hurts your grades. The fact that any kind of disaster or holdup could push you into the former style of learning is what I think causes the entire thing to tilt.
Whilst there are a couple more points I'd love to adress, I kinda want to question your assertion that this is a current generation thing. That is an awfully easy assertion to make, can usually be said about the asserters generation as well and all generations before that. Unless there's more concrete data to back that part up, i think it does the present generation plenty of injustice.
I think it's better to know about the existence of a problem, that it has solutions, and that the solutions can be applied to similar problems, than it is to know any given problem and solution in depth.
When you have a breadth of knowledge, you know where to look to start your implementation - or better yet, use someone else's implementation, until it's not good enough, which may never happen.
The risk with knowing a few things well is that you may be ignorant of of the existence of similar problems and know that they already have good solutions. Meta-knowledge, as you put it, is generally more likely to be useful than specific knowledge, unless you have specific knowledge about a lot of things - which is unlikely unless you've got a lot of experience.
Also, in attempt to be more objective about this divide, I've found it useful to note that there's a general tendency in intellectuals to be in one camp or the other: unifier or multiplier. I've seen this issue taken up by William James, talking about 'rationalists and empiricists' and by Freeman Dyson in an essay about 'Manchester and Athens'. At the highest heights of intellectual accomplishment, you find people who revel in particulars, and others who love only principles, each typically having an amount of disdain for the other approach. Both are necessary, though.
I have had strong opinions about the same, which have fluctuated drastically over time and now settled on less stronger opinion.
I was from an EE background and didn't have an algorithms course in our curricula (did my bachelors in India, so you don't usually have a lot of options of taking the courses you like). So I hated CLRS and like Skiena (though couldn't appreciate it well enough). Later on, went to grad school and had a amazing teacher and I was hung over theoretical text books (CLRS etc) and swore by them. Now I was teaching algorithms to couple of colleagues (again from non-CS) background, and initially tripped by suggesting CLRS. They are way more happier with Skiena. I guess, for some people applications inspire the theory and then theory take over. For others, they fall in love with theory naturally (or with good teachers). So my current take is, you probably want to go thru both the books if you want to code/think in algorithmic way. The order is going to depend on the person.
The '2nd Edition' is misleading in the title, this edition has been out for around three years.
Amazon reviews are quite scathing for this book, people complain about poor explanations and lots of mistakes. Apparently there's a long errata, but even in 2012 people were moaning.
Can anyone corroborate this? There's also a camp of people that says it's one of the best books around. I've got Intro to Algorithms on my bookshelf here which is a doorstop, but not bad in a pinch if I want something other than google.
I don't think "scathing" is the appropriate word here. It has 4.3 stars after 80 reviews, which seems pretty good to me.
In any case, to answer your question, I read the book a few years ago and thought it was really good. I don't remember there being many mistakes, and I didn't mention any in my review on Amazon, but I may have just not noticed.
It's definitely my favorite algorithms book, because it's more practical than books like Intro to Algorithms and TAOCP. A large portion of those books are dedicated to proving theorems and big-O run times, and things like that. This book skips over most of the proving and math, tells you what the big-O run time is, gives an implementation in C, walks through the algorithm in a way that actually explains what it's doing, and points to other resources for the deeper math.
If I needed to implement an algorithm, I'd grab this book. If I was curious about the math behind it, I'd grab TAOCP or Intro to Algorithms.
It appears that lot of people consider math in CS book as optional and think it's just there to make book look more serious. I actually LOVE having math in CS books. Without math you only know what is the "fact", but with math you can understand why it is the fact.
On the other end, CLRS is far from perfect. My two issues with CLRS are:
1. Many critical topics are missing entirely while lot of non-critical stuff have gotten in to. There is a discussion started out by Professor Corman at Quora for suggestions for 4th edition here: http://www.quora.com/As-we-start-planning-the-next-edition-o...
2. CLRS doesn't often try to make you understand the topic or algorithm. For example, for BST it will just say this is how you find successor node and it's entirely your job to think why this is the best way or why other alternatives won't be good. The way I deal with this is stop reading after chapter introduction and think about for a while how I would have solved problem and then read explanation in the book. This often illuminates subtle points of algorithms. I ended up annotating huge swath of text in my own PDF copy.
Personally, reading through a bunch of math doesn't help me understand how an algorithm is working.
I've always found it far easier to scan through some psuedo-code and read a few paragraphs explaining it. At this point, I can usually look at the loops, recursive calls, and "structure", and get a pretty good idea of how it's working, what it's big-O run time would be, and why. Full blown formal proofs and theorems just don't help my understanding.
I agree the math is important for research and writing papers, and proving one algorithm is better than another, but for practical purposes (i.e. actually implementing an algorithm in real code) it's just not very helpful. And the reality is that most people learning about algorithms are going to spend a lot more time implementing algorithms than they will writing papers and doing algorithm research, so I'm not sure a math heavy book like CLRS is really the best undergraduate text.
Proofs are a means to understanding a topic, not an end in itself. In CS there is often a tendency to do trivial proofs in painstaking detail, because there's a feeling that you need a certain amount of math to be taken seriously. The purpose of a proof is to convey understanding. In most cases an intuitive explanation with pictures & text is much more efficient at that than a formal proof.
Perhaps some bias from the Amazon UK page, fewer reviews and the bad ones are at the top.
I think a good example of this problem is Numerical Recipes. It's got a 4.5 in Amazon UK, slightly lower in Amazon US. Many people agree that it's not a good book - the main issue is that the authors apparently have little expertise in the areas they're professing to claim expertise in.
I'm sure Skiena knows his stuff, so that doesn't worry me, but it's entirely possible that people miss the mistakes. I'd just like to know why people gave such bad reviews.
I don't know anything about the errata but the bit about the poor explanations doesn't ring true. I use this book purely for the explanations.
Specifically, I'll usually look at Sedgwick's Stanford mooc videos if I need a refresher, but if I need a big-picture look to see what algorithms I should consider using, this book is the starting point. There are some bigger, all-inclusive type books but Skiena does a good job of being accessible, covering a lot of ground, and providing references to implementations and further reading.
This is really a great book to read if your prepping up for an interview or in general just want to study algorithms. This book is much more readable as compared to CLRS which is very dense and pedagogical. This book is more like novel as in the author also describes his personal experiences in short snippets called war stories which are pretty fun to read. The second half of the text book describes problems and solutions. If your looking interview prep then the 2nd part of text book would be really helpful.
I'm also curious as to what level of student this targets. Would this be good for brushing up on my sorts and data structures for my interviews, for example?
Steve Yegge (Amazon, Google) of Stevey's Blog Rants seemed to think so.
> My absolute favorite for this kind of interview preparation is Steven Skiena's The Algorithm Design Manual. More than any other book it helped me understand just how astonishingly commonplace (and important) graph problems are – they should be part of every working programmer's toolkit. The book also covers basic data structures and sorting algorithms, which is a nice bonus. But the gold mine is the second half of the book, which is a sort of encyclopedia of 1-pagers on zillions of useful problems and various ways to solve them, without too much detail. Almost every 1-pager has a simple picture, making it easy to remember. This is a great way to learn how to identify hundreds of problem types.
A friend of mine was applying to various large tech companies and recommended Programming Interviews Exposed (Mongan). It's got good coverage of standard interview algorithms as well as broader topics like concurrency, oop, databases and tech-specific interview prep.
He didn't get the job at Google unfortunately, but he did get a job in ESA's flight dynamics team which I think is far cooler.
Having worked with both ADM and CLRS, I still find 'Algorithms' by Robert Sedgewick & Kevin Wayne superior to both of them. Especially for beginners.
Thanks to motivated examples, actual implementations of the algorithms presented, detailed illustrations, cool experiments and intuitive mathematical analysis I felt I was growing after every page. I think, a human being is inductive - it’s easier to comprehend new material if first presented with examples and the practical side, with the theory and generalizations developed afterwards. Unfortunately, many books and courses teach things the other way around.
I'm at chapter 14.4 now, so still a long way to go.
(Note: activity the past 2 months was low because I was relocating and had nearly no free time. But I'm usually updating it actively. Gray code subset generation was added this morning. Integer partition generation and set partition generation are up next.)
I use this and Aho:s "Foundations of Computer science" as an index to computer science.
For that purpose I found this book very useful, but then again, I don't have a formal CS background (my major was physics).
I go for other sources to understand the specifics of an implementation. The practical examples of where, when, and why would I use a particular method were really useful.
It's very hard to imagine a single book that would suffice as a resource.
For a person like myself, who writes lots of performance critical stuff in C++ I would combine this with something like Aho: "Foundations of computer science" and Loudon: "Mastering algorithm with C" and for perfomance Ericson: "Real time collision detection" and Agner Fog's excellent optimization resources (http://www.agner.org/optimize/).
This book helps to bring out the view that isomorphism is the superpower of applied computer science - once we identify that our problem is by formal definition exactly the same as that other problem we read about we can solve it usually very neatly.
For me, this book gave a very valuable practical exposition of several patterns of usage. Like Steve Yegge commented, for example, the content of graphs was enormously useful to me.
I've only read brief parts, but I haven't found another text comparable in apt content selection for computer science in general--and the authors' credentials are of course... the best.
Looking at the table of contents from amazon, it looks like the book covers the basic data structures, but the book's website says the following:
"I assume the reader has completed the equivalent of a second programming course, typically titled Data Structures or Computer Science II."
So its confusing to know the target audience. To me it looks like someone with one language under his belt and some basic math(algebra/precalculus?) can do alright.
The book is designed to teach you where and how to use data-structures and algorithms to solve problems. While it does talk about many of them, the explanations are a bit spotty, and are not a great introductory read. You'd want to read a better introductory book before this if you aren't comfortable with them.
The ACM and IEEE-CS joint curricula for Computer Science suggests that there is a preliminary Data Structures & Algorithms course, followed by an Algorithms course. Many universities follow that pattern.
Look on google and you'll find a noticeable difference in the books on offer for each.
In my experience, the Data Structures and Algorithms course was more applied. You're writing code (in my case C++) that uses linked lists, stacks, etc to solve problems. This work is done in the context of building more solid programming my skills in the language being used.
Then, in the Algorithms course, it is much more math intensive, and you cover more complicated algorithms and data structures. I didn't have to write one line of code in my Algorithms class (although I did so that I could understand some of the concepts surrounding Red Black Trees, AVL trees, etc)
When I went to college (late 90's) my CS curriculum was: intro to programming 1 & 2, data structures, algorithm analysis. That order is what I bet the book is referring to.
I've spent more time with the Cormen book so far and only a little with "The Algorithm Design Manual", but have to say I've been disappointed with Cormen and very impressed by the ADM.
I think the Cormen book has a reputation for being more serious, and it does give more in-depth mathematical treatments of the algorithms covered—but honestly, I think it's a mistake to consider it more serious for that reason. There's a time where I would have stopped reading this comment and ordered the Cormen book, but I think it's worthwhile to consider criteria for a book being serious. In the realm of software, I'll argue that the most important measure is how much the book improves your ability to create serious software—and under those conditions, The Algorithm Design Manual takes the prize.
In case there's still ambiguity on what 'serious software' might mean, I'll point out that the ADM is not a recipe book—I'm not trying to say, "practically speaking the algorithm problems in software are solved, you just have to copy and paste the source for the required algorithm." For crafting difficult, original algorithms, I still think ADM will be more useful.