5 ms·

The Algorithm Design Manual

183 points by johnwards 12y ago

masta 12y ago
Thats without a doubt the best algorithm book on the market right now.
dmishe 12y ago
It was published in 2008
farresito 12y ago
I was excited thinking it was a new version, but it's been out for a long time.
WhitneyLand 12y ago
Amazon doesn't have a look inside and not seeing any sample content on the site. Is there a sanctioned way to get the flavor of the book?
- derengel 12y ago
  The Look Inside works for me on amazon.com, are you using a country specific amazon website?
- justin66 12y ago
  Take a look at the Stony Brook Algorithm Repository: http://www3.cs.stonybrook.edu/~algorith/ http://www3.cs.stonybrook.edu/~algorith/ A lot of the examples are excerpted from the book.
- Silhouette 12y ago
  It looks like Amazon UK does have a "look inside" preview: http://www.amazon.co.uk/gp/product/1848000693/ http://www.amazon.co.uk/gp/product/1848000693/
derengel 12y ago
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.
- jcurbo 12y ago
  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.
- keeperofdakeys 12y ago
  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.
- jacques_chester 12y ago
  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.
  - metaobject 12y ago
    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)
peferron 12y ago
For anyone going through the book and interested in looking up complete implementations, I've implemented quite a few of them in JS and Go: https://github.com/peferron/algo https://github.com/peferron/algo 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.)
joshvm 12y ago
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.
- sbuccini 12y ago
  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?
  - idle_processor 12y ago
    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. Source: http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html http://steve-yegge.blogspot.com/2008/03/get-that-job-at-goog...
  - joshvm 12y ago
    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.
westoncb 12y ago
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.
- flebron 12y ago
  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 :)
  - westoncb 12y ago
    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.
fsloth 12y ago
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/ 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.
- westoncb 12y ago
  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.
armansu 12y ago
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.

183 points by johnwards 12y ago

masta 12y ago

Thats without a doubt the best algorithm book on the market right now.

dmishe 12y ago

It was published in 2008

farresito 12y ago

I was excited thinking it was a new version, but it's been out for a long time.

WhitneyLand 12y ago

Amazon doesn't have a look inside and not seeing any sample content on the site. Is there a sanctioned way to get the flavor of the book?

derengel 12y ago
The Look Inside works for me on amazon.com, are you using a country specific amazon website?
justin66 12y ago
Take a look at the Stony Brook Algorithm Repository: http://www3.cs.stonybrook.edu/~algorith/ http://www3.cs.stonybrook.edu/~algorith/ A lot of the examples are excerpted from the book.
Silhouette 12y ago
It looks like Amazon UK does have a "look inside" preview: http://www.amazon.co.uk/gp/product/1848000693/ http://www.amazon.co.uk/gp/product/1848000693/

derengel 12y ago

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.

jcurbo 12y ago
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.
keeperofdakeys 12y ago
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.
jacques_chester 12y ago
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.
- metaobject 12y ago
  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)

peferron 12y ago

For anyone going through the book and interested in looking up complete implementations, I've implemented quite a few of them in JS and Go: https://github.com/peferron/algo https://github.com/peferron/algo 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.)

joshvm 12y ago

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.

sbuccini 12y ago
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?
- idle_processor 12y ago
  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. Source: http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html http://steve-yegge.blogspot.com/2008/03/get-that-job-at-goog...
- joshvm 12y ago
  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.

westoncb 12y ago

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.

flebron 12y ago
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 :)
- westoncb 12y ago
  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.

fsloth 12y ago

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/ 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.

westoncb 12y ago
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.

armansu 12y ago

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.