What do you think?
Rate this book
Algorithm Design
Algorithm Design introduces algorithms by looking at the real-world problems that motivate them. The book teaches students a range of design and analysis techniques for problems that arise in computing applications. The text encourages an understanding of the algorithm design process and an appreciation of the role of algorithms in the broader field of computer science.
August 6, 2009 Author, Jon Kleinberg, was recently cited in the for his statistical analysis research in the Internet age.
August 6, 2009 Author, Jon Kleinberg, was recently cited in the for his statistical analysis research in the Internet age.
864 pages, Hardcover
First published March 16, 2005
134 people are currently reading
2098 people want to read
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
Displaying 1 - 26 of 26 reviews
August 4, 2016
It's an Algorithms book. So I know what you're thinking "why would I read this book, when the standard text on Algorithms is CLRS, which is in fact so popular that nobody even refers to it by name, but simply as 'CLRS'?" Bear with me here; Algorithm Design is better than CLRS.
Now, it's not as COMPREHENSIVE. If you want a reference book to sit on your desk for later use, by all means use CLRS. CLRS is a great book to pick up, flip to the index, find the thing you're curious about, and read the relevant section on it. Virtually everything you encounter in Algorithms is in that book.
Algorithm Design isn't that way. There's tons of stuff in CLRS that isn't even touched on in Algorithm Design. Basic data structures like stacks, queues, heaps, trees, and such are not taught at all. You're expected to already be familiar with these concepts, since they should be covered in a Data Structures course, not an Algorithms course.
Algorithm Design covers exactly 7 things:
1) Basic analysis techniques
2) Graphs
3) Greedy Algorithms
4) Dynamic Programming
5) Divide and Conquer Algorithms
6) Network flows
7) Computational intractability and complexity.
That's it. These topics tend to show up in graduate courses more than undergrad courses, so if you're an undergrad, this probably isn't the right book for you. But if you're taking graduate algorithms, this book is fantastic. The reason why is that Algorithm Design doesn't merely cover those 7 topics, it annihilates them.
The presentation of each topic is so well-covered, so perfectly-paced, so thorough, and so readable, that you almost forget you're reading a textbook. Topics are introduced slowly and gradually. The authors write in a readable style unmatched by any other algorithms book I've ever read. While you are reading, the authors may make a claim. As soon as they do this, they immediately prove it true. The proofs are just as readable and followable as the rest of the text. I never felt lost or confused with this book, it was like having an excellent professor close by at all times. Each section is packed with examples - it's not enough to prove something true, Algorithm Design also delves into enough examples that it makes things extremely clear.
My only real complaint is that, in the name of readability, sometimes the book authors deviate a bit too far from standard terminology. As a quick example, proving a Greedy Algorithm to be correct, one must illustrate that it exhibits a) The Greedy-Choice Property and b) Optimal Substructure. These names don't really tell you what they are, so the authors refer to them as the "staying ahead" properties. This works well within the confines of the book because the argument is that the greedy algorithm "stays ahead" of the optimal solution, but I can easily imagine a student using that terminology getting confused looks from peers who learned with other books.
Otherwise, AD is a fantastic book that I cannot recommend highly enough for people studying algorithms within the confines of the limited subset of what the book covers.
Now, it's not as COMPREHENSIVE. If you want a reference book to sit on your desk for later use, by all means use CLRS. CLRS is a great book to pick up, flip to the index, find the thing you're curious about, and read the relevant section on it. Virtually everything you encounter in Algorithms is in that book.
Algorithm Design isn't that way. There's tons of stuff in CLRS that isn't even touched on in Algorithm Design. Basic data structures like stacks, queues, heaps, trees, and such are not taught at all. You're expected to already be familiar with these concepts, since they should be covered in a Data Structures course, not an Algorithms course.
Algorithm Design covers exactly 7 things:
1) Basic analysis techniques
2) Graphs
3) Greedy Algorithms
4) Dynamic Programming
5) Divide and Conquer Algorithms
6) Network flows
7) Computational intractability and complexity.
That's it. These topics tend to show up in graduate courses more than undergrad courses, so if you're an undergrad, this probably isn't the right book for you. But if you're taking graduate algorithms, this book is fantastic. The reason why is that Algorithm Design doesn't merely cover those 7 topics, it annihilates them.
The presentation of each topic is so well-covered, so perfectly-paced, so thorough, and so readable, that you almost forget you're reading a textbook. Topics are introduced slowly and gradually. The authors write in a readable style unmatched by any other algorithms book I've ever read. While you are reading, the authors may make a claim. As soon as they do this, they immediately prove it true. The proofs are just as readable and followable as the rest of the text. I never felt lost or confused with this book, it was like having an excellent professor close by at all times. Each section is packed with examples - it's not enough to prove something true, Algorithm Design also delves into enough examples that it makes things extremely clear.
My only real complaint is that, in the name of readability, sometimes the book authors deviate a bit too far from standard terminology. As a quick example, proving a Greedy Algorithm to be correct, one must illustrate that it exhibits a) The Greedy-Choice Property and b) Optimal Substructure. These names don't really tell you what they are, so the authors refer to them as the "staying ahead" properties. This works well within the confines of the book because the argument is that the greedy algorithm "stays ahead" of the optimal solution, but I can easily imagine a student using that terminology getting confused looks from peers who learned with other books.
Otherwise, AD is a fantastic book that I cannot recommend highly enough for people studying algorithms within the confines of the limited subset of what the book covers.
July 23, 2008
If you need a handbook on algorithms and data structures get CLR. If you want to truly understand algorithm design and analysis, this is your book. Its one of the few textbooks with a coherent narrative, as opposed to the "step 1, step2, QED" style of so many other textbooks. The problems are all really good, too.
May 19, 2019
A great read for newcomers and more knowledgable readers alike.
The first three chapters introduce the basic concepts of algorithm design and graphs, getting an inexperienced reader up to date with the knowledge required for the most advanced stuff later on. Those advanced desing concepts are explained in simple terms (except a few sections here and there that get bogged down in math and notation) that everyone can follow without much hassle.
The main algorithmic techniques are presented in chapters 4 to 7 (Greedy Algorithms, Divide and Conquer, Dynamic Programming and Network Flow). Those chapters offer very intuitive introductions to the subjects, and as they progress, they take on bigger challenges that are still presented in a neat way. Another cool feature is the tie-in with real problems. The reader not only reads about the theory, but is also shown how to solve algorithmic problems. The methodology presented in those chapters can be easily used to solve a wide range of problems.
The greatest plus of the book is the solved exercises it presents. At the end of every chapter it offers detailed solutions to problems, so the reader can really understand how to go about solving the problems on their own. On top of that, the unsolved exercises come in varied difficulties, from tame to very challenging.
All in all, I highly suggest this book to aspiring Computer Scientists.
The first three chapters introduce the basic concepts of algorithm design and graphs, getting an inexperienced reader up to date with the knowledge required for the most advanced stuff later on. Those advanced desing concepts are explained in simple terms (except a few sections here and there that get bogged down in math and notation) that everyone can follow without much hassle.
The main algorithmic techniques are presented in chapters 4 to 7 (Greedy Algorithms, Divide and Conquer, Dynamic Programming and Network Flow). Those chapters offer very intuitive introductions to the subjects, and as they progress, they take on bigger challenges that are still presented in a neat way. Another cool feature is the tie-in with real problems. The reader not only reads about the theory, but is also shown how to solve algorithmic problems. The methodology presented in those chapters can be easily used to solve a wide range of problems.
The greatest plus of the book is the solved exercises it presents. At the end of every chapter it offers detailed solutions to problems, so the reader can really understand how to go about solving the problems on their own. On top of that, the unsolved exercises come in varied difficulties, from tame to very challenging.
All in all, I highly suggest this book to aspiring Computer Scientists.
November 17, 2019
Great book on algorithms
October 11, 2021
no code nothing, feel like taking english class.
September 8, 2014
Good selection of topics in good organization and order! Too thick! Can be more succinct!
October 6, 2024
I bought this while taking an algorithms class earlier this year, because it was a recommended supplemental text. I didn’t end up needing it for the class, but having unread books lying around the house weighs on my conscience, so I made time to read it afterward.
Students who were struggling in the aforementioned class often complained that they didn’t know how to build the ‘intuition’ needed for coming up with algorithms. The gap between understanding how a solution works once it’s been explained to you, versus understanding how you could come up with that solution if you’d never seen the problem before, can be substantial. (It makes sense that the latter would be difficult to teach—after all, if we had a clear algorithm for designing algorithms, we’d just have computers do the designing instead of bothering to teach humans in the first place.) This book promises to walk you through the process, not just show you the end result:
I’m not sure it really does this consistently—I suspect many of my classmates would still have felt they were being asked to ‘draw the rest of the owl’ even if they had read this book.
I’ll probably remember this more for its discussions of how to prove things (like time/space complexity, or that an algorithm’s output is optimal, or bounds on how far from optimal it is). Strategies include:
- Finding a “progress measure for the algorithm”[2]
- Proving “the greedy algorithm stays ahead”[3]—e.g., proving that the ith element of the greedy solution is at least as desirable as the ith element of any optimal solution
- Devising an “exchange argument” where “one considers any possible solution to the problem and gradually transforms it into the solution found by the greedy algorithm without hurting its quality”[4]
- The “pricing method” where you “consider a price one has to pay to enforce each constraint of the problem”[5]
- Creating a “potential” (as in “potential energy”) function to use as a progress measure[6]
- Using the simpler “Union Bound” instead of trying to precisely calculate the probability of a union of non-independent events[7]
- Using the “probabilistic method” to prove stuff like “every instance of 3SAT has an assignment satisfying at least 7/8 of the clauses”[8]
I appreciated the sections on co-NP, PSPACE, approximation algorithms for NP-Complete problems, and randomized algorithms, among others, for going into topics where my previous education had stopped short.
[1] Jon Kleinberg and Éva Tardos, Algorithm Design (Boston: Pearson/Addison-Wesley, 2006), xiv.
[2] Ibid., 7.
[3] Ibid., 115.
[4] Ibid., 116.
[5] Ibid., 599.
[6] Ibid., 697.
[7] Ibid., 712.
[8] Ibid., 793.
(crosspost)
Students who were struggling in the aforementioned class often complained that they didn’t know how to build the ‘intuition’ needed for coming up with algorithms. The gap between understanding how a solution works once it’s been explained to you, versus understanding how you could come up with that solution if you’d never seen the problem before, can be substantial. (It makes sense that the latter would be difficult to teach—after all, if we had a clear algorithm for designing algorithms, we’d just have computers do the designing instead of bothering to teach humans in the first place.) This book promises to walk you through the process, not just show you the end result:
Sophisticated algorithms are often best understood by reconstructing the sequence of ideas—including false starts and dead ends—that led from simpler initial approaches to the eventual solution.[1]
I’m not sure it really does this consistently—I suspect many of my classmates would still have felt they were being asked to ‘draw the rest of the owl’ even if they had read this book.
I’ll probably remember this more for its discussions of how to prove things (like time/space complexity, or that an algorithm’s output is optimal, or bounds on how far from optimal it is). Strategies include:
- Finding a “progress measure for the algorithm”[2]
- Proving “the greedy algorithm stays ahead”[3]—e.g., proving that the ith element of the greedy solution is at least as desirable as the ith element of any optimal solution
- Devising an “exchange argument” where “one considers any possible solution to the problem and gradually transforms it into the solution found by the greedy algorithm without hurting its quality”[4]
- The “pricing method” where you “consider a price one has to pay to enforce each constraint of the problem”[5]
- Creating a “potential” (as in “potential energy”) function to use as a progress measure[6]
- Using the simpler “Union Bound” instead of trying to precisely calculate the probability of a union of non-independent events[7]
- Using the “probabilistic method” to prove stuff like “every instance of 3SAT has an assignment satisfying at least 7/8 of the clauses”[8]
I appreciated the sections on co-NP, PSPACE, approximation algorithms for NP-Complete problems, and randomized algorithms, among others, for going into topics where my previous education had stopped short.
[1] Jon Kleinberg and Éva Tardos, Algorithm Design (Boston: Pearson/Addison-Wesley, 2006), xiv.
[2] Ibid., 7.
[3] Ibid., 115.
[4] Ibid., 116.
[5] Ibid., 599.
[6] Ibid., 697.
[7] Ibid., 712.
[8] Ibid., 793.
(crosspost)
August 19, 2023
the book is the chosen textbook so I am more or less forced to read this through.
For readers like me who is used to understand problems graphically, pick another book. The book explains reasonably easy problems with drowning notations that are so distracting that by the end of following through the proofs built on those notations, I more often than not found myself getting lost with the main idea.
It is commonly the case that algorithms are not proved in a mathematical way, so I don't see the reason to rely this heavily on notations when the ideas behind are, and should be intuitive.
Also for someone expecting textbooks to be written in plain English, this book is more old school, and in some case, I almost feel a tiny hint of arrogant in explaining the ideas to the readers.
For readers like me who is used to understand problems graphically, pick another book. The book explains reasonably easy problems with drowning notations that are so distracting that by the end of following through the proofs built on those notations, I more often than not found myself getting lost with the main idea.
It is commonly the case that algorithms are not proved in a mathematical way, so I don't see the reason to rely this heavily on notations when the ideas behind are, and should be intuitive.
Also for someone expecting textbooks to be written in plain English, this book is more old school, and in some case, I almost feel a tiny hint of arrogant in explaining the ideas to the readers.
April 23, 2025
About as good as an algorithms book can be lmao. thought some of the theory was a bit verbose (although now that I write this maybe some topics would be hard to follow if they were more concise), and the Dynamic Programming section focused more on classic DP than top down approaches but I guess that’s just cause of how old this book is.
So really both of these criticisms are pretty invalid — I take back everything I said this book is a great resource for algorithm design and analysis
So really both of these criticisms are pretty invalid — I take back everything I said this book is a great resource for algorithm design and analysis
May 16, 2017
Really good book on algorithms and very in depth, they made everything easy to understand and read. Used for my algorithms and advanced algorithms courses. Exercises are good as well.
June 9, 2017
Good textbook for graduate class in Algorithms. Focuses on intuitive explanations instead of rigorous esoteric formal language.
March 10, 2020
So far so good.
September 12, 2022
A very profound book for algorithm engineering students
January 24, 2024
Cleanest, most intuitive breakdown of algorithmic thinking I've encountered.
Should be mandatory reading for any mathematician or computer scientist
Should be mandatory reading for any mathematician or computer scientist
March 18, 2024
Classical textbook about algorithms, detailed explanations.
March 20, 2022
I'm adding this to my goodreads because I read it like 4 times for my Algorithms class in university lmao
April 10, 2018
I'm halfway through the book. It's fantastic, to say the least. Rarely does one get to see such clear exposition of nuances in 'Greedy Algorithms', 'Network Flow'. I say this because I'm currently reading other Algorithms and DS books too. It's hard not to draw a comparison, especially when the authors make reading enjoyable.
January 9, 2016
It explains the techniques really well and also does a really good job at showing how these techniques are actually used in practice. However, definitely not as comprehensive as CLRS, so buy that one as well because you'll need a reference sooner or later.
Verdict: 10/10, made me understand how to approach DP problems, finally.
Verdict: 10/10, made me understand how to approach DP problems, finally.
September 10, 2009
I had a great time with this book and it's associated class. Seemed like a great way to learn algorithms-type things. If I remember correctly, it even had a pretty good overview of the Fast Fourier Transform.
December 9, 2013
it's fun to solve the exercises
December 27, 2013
It's hard to understand. I don't like it.
April 14, 2016
Its a more specialized version of Introduction to Algorithm. If you are really into algorithms it makes sense to get this. But most of the time its better to get Introduction to Algorithms.
January 23, 2017
I guess it's fair to include the textbooks I read as books I read.
TODO: add review
TODO: add review
Read
October 21, 2010Rewarding.
April 20, 2017
Other books tell what is algorithms, while this one tells why we use them and how we come up with those solutions.
Displaying 1 - 26 of 26 reviews