9 ms·
Milestone for MIT Press’s bestseller, "Introduction to Algorithms"
- sandGorgon 15y agoNope - the book sold far more: They are not taking into account Eastern Economy Editions. The book is quite popular in Indian colleges.
- johnpmayer 15y agoI've got mine sitting at my desk right now
- marshray 15y agoIt's strange - the article talks about it being this 20-year favorite, but I didn't see it show up in US bookstores until the last few years.
- psykotic 15y agoI read the first edition when I was in high school eleven years ago. Even back then it was considered the standard go-to book for learning the basics of algorithms and data structures. If your bookstores weren't carrying it, they must have not have been well stocked. My opinion of the book nowadays is actually somewhat low. The content and style is competent but generic and uninspiring. It does a poor job of teaching algorithm design, but admittedly that is a flaw with most of these books. Udi Manber's lesser-known textbook is just a lot better in that regard. It does mean sacrificing some breadth of coverage compared to CLR. For me it's the right trade-off because so much of CLR's coverage comes across as perfunctory, as if they're just checking boxes off an endless curriculum list that's intended to please everyone, much like the big calculus books. The grab bag of advanced chapters in the book's last half are the exception to that rule. They're usually in the authors' own research areas, and it shows.
- lurker19 15y agoWhich bookstores? Most don't sell textbooks, except for university bookstores.
- marshray 15y agoEvery Borders and Barnes & Nobles that I lived near. They do carry a few hard-core algorithms books and eventually it did show up there. It's true that I don't get to university bookstores as often as I'd like.
- gary4gar 15y agoIts an excellent book. I am proud to own a copy. Authors have done a good job! Anyone who want to learn algorithms & data stuctures should get this & read it cover-to-cover. PERIOD
- rreeves 15y agoI agree with gary4gar, this is such an excellent book. CLR is sitting by my desk now. Seeing this book inspires me to code.
- endtime 15y agoI powered through nearly the whole book in a pretty short period of time, preparing for my Google interviews. It was a great review (and a great intro to a few classes of algorithms (e.g. max flow) I hadn't seen before). Congrats to the authors.
- scarmig 15y agoOne of the most exciting things that has happened to me recently was finding a brand new copy of this in a used bookstore (real version, not EE) for $8. No marks, no anything. (And my life is full of excitement, trust me!) Great book, one of the must-reads. Though I'll admit I've only gotten like a third of the way through it...
- deleted 15y ago[deleted]
- utefan001 15y agoI had a little bit more excitement than that when I found Intro to Algorithms for 10 cents at the local library. Hidden within many pages were $20 and $50 bills. Over $500. There was no name in the book and the library said they had no way to figure out who the book belonged to. I assume the owner did not trust banks or his room mate. I now have a habit of looking for money inside whenever I see a used book for sale.
- idle_processor 15y agoI occasionally "hide" bills in selected sections of textbooks I've been meaning to read. It serves as a perk or secondary means of positive reinforcement (the primary being learning interesting/useful stuff). It also indirectly brings the material near where I've stuffed the bill to the forefront of my mind, even if I'm not incentivizing myself with cash. "Where was that $20? Oh, near Djikstra's algorithm. I'd been meaning to look that over."
- MaysonL 15y agoI once found about $200 in a book I owned, that I had no memory of putting there. I had previously read that copy of that book, without the money.
- andrewparker 15y agoThe Monzy quote made by Cliff Stein caused me spit up my diet coke with laughter :) http://www.monzy.com/intro/killdashnine_lyrics.html http://www.monzy.com/intro/killdashnine_lyrics.html Monzy was my TA for CS147 (intro to HCI). Small world.
- ChuckMcM 15y agoI consider this book and Sedgwick's "Algorithm's in C" to be the two algorithm books to have if you don't own any. Mine is signed by Dr. Rivest but I never managed to get Verterbi's autograph for it.
- NY_Entrepreneur 15y agoI'm sure that there is a lot of good material in that book, especially on core computer science topics. But the book is only an 'introduction' since for many of the topics for serious interest in practice it will be important to go deeper than the book. In places the authors of the book have bitten off more than they can chew well. E.g., in linear programming they have: "Gaussian elimination begins with a system of linear equalities whose solution is unknown. In each iteration, we rewrite this system in a equivalent form that has some additional structure. After some number of iterations, we have rewritten the system so that the solution is simple to obtain. The simplex algorithm proceeds in a similar manner, and we can view it as Gaussian elimination for inequalities." NO! They blew it! That just ain't the point! They failed to 'get it'! They don't understand! With liberal grading, they get a gentleman C- for effort! They get a grade of B until they get to: "we can view it as Gaussian elimination for inequalities." where they get a big red mark through their effort! They emphasized the role of inequalities, but that is really trivial. With no difficulty at all, we convert a linear programming problem with inequality constraints (<= or >= but not < or >) to one with (a) equality constraints and (b) all the variables greater than or equal to zero. Fine. But notice the part (b) where we still have some inequalities although some simpler ones. That conversion was easy. But it didn't do us any good at all for the main point of linear programming or the simplex algorithm for finding solutions since the main point is optimization, that is, doing good things for the objective function. So, with the equality constraints, in the simplex algorithm, we proceed with elementary row operations. Yes, each "iteration" is in terms of elementary row operations on a system of linear equations. It is MUCH better to mention "elementary row operations" than "iterations"(s) because the 'iterations' can't be easily justified but the elementary row operations can. That is, there's no doubt that elementary row operations yield an equivalent system of linear equations; either we learned this well enough in high school or we can easily establish it ourselves in a few minutes. Yes, so does Gauss elimination use elementary row operations. But, for the simplex algorithm itself, directly, that's the end of the connection with Gauss elimination! Why? Gauss elimination, for numerical stability, should emphasize careful selection of the 'pivot' elements, e.g., as in George E. Forsythe and Cleve B. Moler, 'Computer Solution of Linear Algebraic Systems', Prentice-Hall, Englewood Cliffs. and the simplex algorithm of linear programming does not have that freedom or luxury. So, each 'iteration' in the simplex algorithm is just an application of elementary row operations on a system of linear equations. Nice to know this. Next, and the main point of the simplex algorithm, which elementary row operations are selected? That is, there is enormous freedom, and all the freedom would result in an equivalent system, so how to exploit the freedom? Well, the authors omitted a step! Once we have converted the given linear program with, possibly, some <= or >= constraints, to all equality constraints and all variables >= 0 (and all the right sides >= 0), we want an 'initial basic feasible solution'. How do we get one? We in effect just 'glue it on'! So, if for some positive integer n we have n constraints, then we glue on, that is, append, n more variables, that is, n more columns, where the n x n matrix in the constraints is just the identity matrix. These variables are called 'artificial'. We (temporarily) modify the objective function: We set each of the old cost coefficients to, say, 0 and the cost coefficients of each of the artificial variables to, say, 1. What's going on with the artificial variables? Sure: The first question about a linear program is, does it have a feasible solution or not? We say that a solution, that is, values for the variables, is 'feasible' if it satisfies the constraints. It may be that there is no feasible solution; we want to know. So, this work with artificial variables answers the question about feasible or not. How? The problem with the artificial variables is obviously feasible (before we appended the artificial variables, we multiplied some of the equality constraints by -1 so that all the constants on the right side were >= 0). So, if we just assign the right side variable values to the artificial variables (the only way we can given that n x n identity matrix), then we will have a basic feasible solution to the problem with the artificial variables. Then we apply the simplex algorithm to minimize. We look at the resulting optimal value of the objective function. If that value is positive, then the initial problem is infeasible. If the value is 0, then the initial problem is feasible and we have a feasible solution for it. With some inspection, we also have a basic feasible solution for the initial problem after dropping some redundant rows. Also, easily we can put the original cost coefficients back where they belong in place of the 0s we inserted. So, due to the artificial variables, we have a basic feasible solution and, if you will, an identity matrix that is the goal of Gauss elimination. So, Gauss elimination can't really help us. But some elementary row operations can help us, and they do, that's what we use, and that's the core of the simplex algorithm. Now we address a crucial issue: Looking at what are called 'reduced costs', it may be that they tell us that our present basic feasible solution is optimal. If so, then we stop. Else, we pick a variable not in the basis and ask what would happen to the objective function value if we (a) increased this non-basic variable and (b) adjusted the basic variables to maintain equality in the constraints. Now we address another major point: Looking at increasing the value of this non-basic variable, it may be that we can increase it all we want, without bound. In this case we have just discovered that our problem is unbounded. That is, assuming we are minimizing, we can save all we want. Else, there is a maximum value to which we can increase this non-basic variable without driving one of the old basic variables negative and, thus, giving us an infeasible solution. That is, increasing this non-basic value to its maximum value drives one or more old basic variables to zero. So, we say that this non-basic variable 'enters' the basis and some old basic variable at zero 'leaves' the basis. This calculation needs only elementary row operations. So, each iteration of the simplex algorithm, actually including finding the reduced costs, needs only elementary row operations on a system of linear equations. Then, the big point, the HUGE point, the main point about the simplex algorithm is WHAT elementary row operations are used. The answer is, we use elementary row operations that, one non-basic variable at a time, improve the value of the objective function. THAT'S what's special in the simplex algorithm and NOT that it's 'Gauss elimination on systems of inequalities'. For more, geometrically, the feasible region is an intersection of finitely many half spaces and, thus, is a closed, convex set with extreme points, edges connecting pairs of extreme points, and flat sides. Each basic feasible solution corresponds to an extreme point. One simplex iteration, when it improves the value of the objective function, leaves its extreme point and moves along an edge from that extreme point. It is possible to move from one basis to another with no change in the value of the objective function; in this case it is possible for the simplex algorithm to 'cycle', that is, return to a given basis infinitely often. By being more selective about entering variables, we can avoid cycling. If there is an optimal solution, then there is an optimal basic feasible solution; there is an optimal basic feasible solution where the reduced costs will show that the solution is optimal; and the simplex algorithm that does not cycle will find such a solution in finitely many iterations. Once again, don't go to computer science people, not even the ones at MIT, to learn some applied math, not even applied math as simple, elementary, old, and beautifully polished as the simplex algorithm of linear programming.
- ianl 15y agoI own two copies of this book, the best algorithms book you can own. One sits at home and another in my office at school.
- milhous 15y agoI didn't study CS, but have found this on almost every developer's bookshelf, impressive run. Since my friend has it, I wanted to get something different and picked up Skiena's Algorithm Design Manual. Anyone have thoughts between the two?
- m0nastic 15y agoI'm still going through Skiena's book (we used CLRS in school, so I figured I'd use Skiena's as a counterpoint), but so far I've been impressed with Skiena. It's a lot more terse (as evidenced from the size differences between the two), and so far I seem to be grokking it better (although it's been over a decade since I even cracked CLRS open).
- chewbranca 15y agoFor those of you just getting into this book, there is also a great course with video lectures up on MIT's OCW site: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/index.htm http://ocw.mit.edu/courses/electrical-engineering-and-comput...
- danielharan 15y agoIs there a legal ebook version?