Milestone for MIT Press’s bestseller, "Introduction to Algorithms"

http://web.mit.edu/newsoffice/2011/introduction-to-algorithms-500k-0810.html

by ilamont • 15 years ago

81 48 15 years ago

web.mit.edu

sandGorgon• 15 years ago

Nope - the book sold far more: They are not taking into account Eastern Economy Editions. The book is quite popular in Indian colleges.

johnpmayer• 15 years ago

I've got mine sitting at my desk right now

marshray3• 15 years ago

It'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• 15 years ago

I 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• 15 years ago

Which bookstores? Most don't sell textbooks, except for university bookstores.

marshray3• 15 years ago

Every 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• 15 years ago

Its 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• 15 years ago

I agree with gary4gar, this is such an excellent book.

CLR is sitting by my desk now. Seeing this book inspires me to code.

endtime• 15 years ago

I 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• 15 years ago

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

utefan001• 15 years ago

I 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• 15 years ago

I 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• 15 years ago

I 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• 15 years ago

The Monzy quote made by Cliff Stein caused me spit up my diet coke with laughter :) http://www.monzy.com/intro/killdashnine_lyrics.html

Monzy was my TA for CS147 (intro to HCI). Small world.

ChuckMcM• 15 years ago

I 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_Entrepreneur15• 15 years ago

I'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.

coliveira• 15 years ago

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

Well said. I've taken courses both in CS and Math. CS people think they know math, but most of the time they have very poor math skills, and this is true even in Theoretical CS. Most proofs in CS are way too complicated and badly written. I think this book is one of the reasons for this -- most of the time the proofs are extremely complicated and verbose, it is a bad example for students that want to learn algorithms. Sedgewick's book is much better, in my opinion.

NY_Entrepreneur15• 15 years ago

Learning 'math' as a good ugrad or grad student is NOT easy and involves a special step often called 'mathematical maturity' where the student learns to be good at reading and writing definitions, theorems, and proofs in math. This step is NOT easy to learn and in practice is nearly impossible to learn without some careful teaching. The usual place to learn the step is in a very precise course, with a lot of very well graded homework, in abstract algebra and then to strengthen the learning via very precise courses in advanced calculus and, maybe, point set topology or measure theory. Without that step, nearly no one knows how to do well writing definitions, theorems, and proofs in math.

Mostly fields outside math try hard to teach math within their fields. Examples of such fields include physics, chemistry, economics, psychology, sociology, electronic engineering, and, yes, computer science, In all cases, the results are at best poor. Of course, those fields are helped by the fact that the math departments don't want to do well teaching service courses, say, in second order stationary stochastic processes for signal processing in electronic engineering with the fast Fourier transform!

But you noticed the problem: The CS profs make a mess out of math.

For the book of this thread from MIT, that fact is a bit surprising: For one, among the authors, at least Rivest has done some good math. For another, for each math topic in that book, MIT has some high expertise. E.g., in optimization, Bertsekas is there and long there have been others.

Once the basic ugrad lessons in math are learned, one still has to learn how to communicate in less severe forms. So, the book failed there, too: Their algebra for the core steps of the simplex algorithm was too long. And, their intuitive explanation, as I objected to here, really was not correct. Sadly they just wrote their chapter on the simplex algorithm too quickly from too little study. This is especially sad since there are many highly polished presentations of the simplex algorithm.

They got pushed into attention to linear programming, and the simplex algorithm, because of some important connections with some problems, e.g., flows on networks that they want to regard as part of computer science, where linear programming is a very important tool.

So, really, it's a strain to call 'flows on networks' computer science. Instead, it's a topic in applied math, back to Ford and Fulkerson, yes, with some by Dantzig, but more from Cunningham and Bertsekas, in particular, part of operations research. So, CS wants to hijack flows on networks. Not really good.

I omitted a more serious objection to the book: It makes a mess, a really bad mess, out of probability. Yes, in the study of the performance of algorithms, probability is important. So, once again, CS wants to borrow and use or just hijack some applied math and makes a mess. That at MIT they make such a big mess out of probability is something of a surprise. Still, in the US, the good courses in probability require both measure theory and functional analysis and are rare, even in math departments. Sad situation.

In using probability for performance of algorithms, in TACP Knuth did better: He stayed with a more elementary approach to probability and made it powerful enough.

E.g., in the book, I saw where they mentioned that the need for probability was that the data had a 'distribution'. Mostly that's not what have to pay attention to: E.g., don't much care about Gaussian, uniform, exponential, etc. Instead, what care about most of all is independence and, then, sometimes, lack of ties. Sad situation.

For both teaching and research, CS needs to clean up its act in math.

Still better, math should just open up, welcome, take in, and take over all the more important fields that are heavily math -- physics, economics, social science, electronic engineering, computing, operations research, etc. Instead of being one of the smallest departments on campus, teaching a few service courses, and otherwise struggling, math could be one of the biggest departments on campus, awash in both funding and students, and one of the most important pillars of growth in our economy.

I have an example: Some years ago I took a problem in practical computing and derived some new probabilistic math for a solution. Right, I used measure theory. I wrote prototype software, ran it on some real data, etc., and wrote a paper. So that I could get the paper in front of people in computing, where the applications are, I looked for journals in computer science. From one editor in chief of one of the best journals, a chaired prof of computer science at one of the best research universities, I got back "Neither I nor anyone on my board of editors has the prerequisites to review your paper.". Later I got almost the same statement from a second such person. For a third such person, at MIT, I wrote custom tutorials for two weeks before they gave up. But in the end the editor in chief of a good Elsevier journal seems to have walked the paper around campus and gotten feedback enough to get the paper reviewed -- the editor couldn't review it!

The paper was a nice contribution to computer science. Generally nice contributions will want some math. For all concerned, CS needs to learn some math.

Here's what they need to do: After calculus, get a good book on abstract algebra, pay full attention to the proofs, and learn some 'mathematical maturity'. Then get a good, first book on linear algebra and learn some important material, still paying attention to the proofs, and get more maturity. Then get Halmos, 'Finite Dimensional Vector Spaces' and learn from one of the best writers of math ever and get an introduction to Hilbert space theory. Then go carefully through Rudin's 'Principles'. Then do some more in ordinary differential equations where get to use both Rudin and Halmos. Then do some optimization -- e.g., pick from linear programming and some of Bertsekas. Then learn some measure theory, functional analysis, and probability based on measure theory. Cover basic stochastic processes, e.g., Markov, Gaussian, and martingales. Then learn some mathematical statistics. THEN return to computer science.

yid2• 15 years ago

I find it hard to believe that you wrote such a long, pedantic rant about an "extras" chapter in an introductory algorithms book. Are you aware that most introductory algorithms courses (i.e., the ones this book is targeted at) don't end up touching linear programming? Why? Because there are tens of other algorithms that are more useful for a typical CS person at that level. For those skimming the book, or perhaps more commonly, keeping it as a reference, it's a great compendium of algorithms references, much like a slightly more rigorous, paper version of Wikipedia.

NY_Entrepreneur15• 15 years ago

For your "I find it hard to believe that you wrote", you might read my:

"I'm sure that there is a lot of good material in that book, especially on core computer science topics."

If you look carefully, then you will find that as my first sentence.

I'm "aware" is about me, which is not appropriate, instead of about the book, which is appropriate, but, as explained early in the book, nearly no course covers the whole book.

But I was kind to the book: It made an even worse mess out of probability, and that material was farther from the back cover. Also see another post on this thread saying that generally in the book the proofs are poorly written.

"For those skimming the book, or perhaps more commonly, keeping it as a reference, it's a great compendium of algorithms references, much like a slightly more rigorous, paper version of Wikipedia." I can believe that, but it doesn't conflict with what I wrote. Indeed, I found and downloaded a PDF of the book for just the purpose you mentioned and that I mentioned in my first sentence: The book likely has some core computer science stuff, that is, not just poorly done, hijacked applied math that apparently I know much better than the authors, that I may be able to use as I finish the software for my server farm.

Gads, it looks like they want to use the approximation approach of starting with a minimum spanning tree to solve the traveling salesman problem in the plane. The idea also works in any Euclidean R^n. It's a CUTE idea. I first saw it in a paper of Karp who easily has some nice proofs of some astounding properties. Sadly in the book I saw some references for the idea but not from Karp, and I didn't see mention of some of the really nice properties. There's a chance of a biggie point there: For all the teeth grinding over NP-complete, that problem is NP-complete but surprisingly easy to solve with surprisingly good accuracy; so, the suggestion is that there is a crack in the armor of the NP-complete difficulty. That suggestion is actually more important than the problem itself which in practice people are not struggling with. Yes, the traveling salesman problem remains important, say, for production scheduling, but there the problem is not on a Euclidean R^n.

Some computer science is nice and useful. Hopefully there has been some such since I put down Knuth's TACP! So, maybe in some issues of handling deadlocks, transactions, race conditions, reliability via parallelism, and more, there will be something useful in the book it would take me more than 90 seconds to reinvent!

Still I'm correct: They should clean up their act in their math. We should get better from MIT.

scott_s4• 15 years ago

But the book is only an 'introduction'

"Introduction" is the first word in the title. Its intentions should be quite clear.

NY_Entrepreneur15• 15 years ago

I was trying to be clear! The book is ballpark 1000 pages, and early parts of the book claim that it is trying to be unusually comprehensive. So, 'introduction' in the title conflicts with the breadth but is appropriate for the depth.

Maybe if I wrote twice as much as I did, then people would just find other objections, e.g., with length!

ianl• 15 years ago

I 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• 15 years ago

I 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• 15 years ago

I'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• 15 years ago

For 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-comput...

danielharan• 15 years ago

Is there a legal ebook version?

Milestone for MIT Press’s bestseller, "Introduction to Algorithms"

Related Stories