6 ms·

Introduction to Algorithms, Fourth Edition – The MIT Press

75 points by philonoist 5y ago

jrussino 5y ago
Is there any published information available yet about what the major differences are from the third edition? I couldn't find much so I posed the question on quora: https://www.quora.com/unanswered/What-are-the-major-differences-between-the-CLRS-third-edition-and-the-fourth-edition https://www.quora.com/unanswered/What-are-the-major-differen...
- jrussino 5y ago
  Already received a reply from Dr. Cormen: "I’ve been tweeting out differences between 3e and 4e here: https://twitter.com/clrs4e https://twitter.com/clrs4e" Also, from the description on purchase pages (Amazon, etc.): " New for the fourth edition • New chapters on matchings in bipartite graphs, online algorithms, and machine learning • New material on topics including solving recurrence equations, hash tables, potential functions, and suffix arrays • 140 new exercises and 22 new problems • Reader feedback–informed improvements to old problems • Clearer, more personal, and gender-neutral writing style • Color added to improve visual presentation • Notes, bibliography, and index updated to reflect developments in the field • Website with new supplementary material "
  - fastasucan 5y ago
    The added color is almost enough to want me buy the new editon imo, I can only get so much out of the b&w graphics.
iamcreasy 5y ago
In one of Cormans' answer to question "Is CLRS really an "introduction"? If so, what's next?"[1] he replied, "Yes, Introduction to Algorithms really is an introductory text—on algorithms". But then he recommended the next book people should read is Don Knuth’s The Art of Computer Programming. Here is the quote "What’s next? Don Knuth’s The Art of Computer Programming, which I consider the greatest books (it is a multi-volume set) computer science has ever had or ever will have." I suppose the target groups of people studying his introductory book is not any random junior student at a random CS department if he is expecting them to pick up Knuth's Art of Computer Programming right after Introduction to Algorithms. [1] https://www.quora.com/Is-CLRS-really-an-introduction-If-so-whats-next https://www.quora.com/Is-CLRS-really-an-introduction-If-so-w...
- dragontamer 5y ago
  > I suppose the target groups of people studying his introductory book is not any random junior student at a random CS department if he is expecting them to pick up Knuth's Art of Computer Programming right after Introduction to Algorithms. I believe high-school students _can_ start that book at page1 chapter1. Just because it is rigorous and difficult doesn't mean that the high school student is ill-equipped to read it. TAOCP is one of the clearest written math-heavy books I've ever read, which makes it ideal for beginners. Yes, its rigorous. Yes, it will take you days, even weeks, to make progress beyond a few pages at times. But that's not a bad thing. Knuth hits the hardest subjects in the earliest sections and very precisely describes a lot of problems. Instead of relying upon "Dog isa Animal" and other crude, counter-productive "training wheels language" unsuitable for advanced understanding... Knuth just lays out the math as it is, in all of its complexity and glory. Rigor is good. And the sooner people practice with rigor, the better their minds will be. If anything, mathematical rigor needs to be introduced at younger ages when the mind is more pliable to learning different languages. ------- TAOCP is somewhere between an algorithms book and a math book. The 1st chapter is 100% math. It can be pursued independently and the 1st chapter is an _excellent_ introduction to rigorous mathematics.
- gh0std3v 5y ago
  > I suppose the target groups of people studying his introductory book is not any random junior student at a random CS department if he is expecting them to pick up Knuth's Art of Computer Programming right after Introduction to Algorithms. I don't think he's expecting a student to do that. He recommends the book in response to the question "What’s next?", implying that if a student would like to learn more, they should go to Knuth's books. Also, judging from the Quora link, he assumes the student has had a course in discrete mathematics, so they should be familiar with mathematical proofs and be comfortable with some level of rigor. I don't think Knuth's books are impossible to read, but a primer to some of the material can help (and understanding mathematical proof is a prerequisite).
  - dragontamer 5y ago
    > I don't think Knuth's books are impossible to read, but a primer to some of the material can help (and understanding mathematical proof is a prerequisite). Its like no one has read "The Art of Computer Programming". Page 10 is an introduction to mathematical proofs !! Knuth covers this very early, because its so fundamental to the rest of the book. The book assumes the reader doesn't know rigorous math or proofs, and has an extremely solid section full of exercises for mathematical induction and proofs. The following sections are on the absolute barebones of math. Page 21 starts the section on numbers (really starting at the basics here). It covers integers, rationals, reals, complex numbers, logarithms and exponents. Honestly, this is like sophomore high-school level stuff, maybe even middle school to an advanced student ("Talented and Gifted" middle-school should cover this stuff actually ). I kid you not, I think an advanced 13 year old can handle this section. Page 27 explains sums and products ("sigma" notation). This should have been covered in high-school level pre-calculus, but we're finally approaching later high-school level math. There are discussions about how sigma is similar to calculus, but it doesn't seem necessary to understand the section. Page 39 is floor, ceiling, modulus arithmetic. While fundamental to discrete mathematics (arguably college level), its so elementary I'm not sure if it really counts as college level yet. Page 45 remains in high-school level: Permutations, Combinations, and Factorials, but also includes the Gamma function (which I'd argue is college-level). But given how Gamma is so similar to Factorial, I'd argue that the high-school level reader would still have an easy time with the concept. Page 53 are binomial coefficients / combinations, including pascal's triangle, and a huge number of identities. I'd say this is the first, college-level section. But by this point, the reader should be very much used to the idea of rigorous math. ---------- Seriously, if you've never given it a read... its pretty simple. Start at page 1, and work forward. Eventually you'll come across some exercises. At this point, test your knowledge to see if you truly understood the previous section. Do a few "level 10" or "level 20" problems (2 minute problems to 30 minute problems). Maybe think about level 30 or level 40 problems (1 day to 1 month problems), but don't feel like you actually have to solve them. Just read them over and "see why they're difficult" and make sure you understand the concepts. Then, start the next section. -------- Spend days or weeks per section, or even on a single page if you get stuck. Skip over * sections ("advanced"), unless you're confident in your abilities to read some of the most difficult comp. sci concepts. If you think you're bad at math, skip over "M" or "HM" exercises and sections (Math and High Math respectively).

75 points by philonoist 5y ago

Is there any published information available yet about what the major differences are from the third edition? I couldn't find much so I posed the question on quora: https://www.quora.com/unanswered/What-are-the-major-differences-between-the-CLRS-third-edition-and-the-fourth-edition https://www.quora.com/unanswered/What-are-the-major-differen...

jrussino 5y ago
Already received a reply from Dr. Cormen: "I’ve been tweeting out differences between 3e and 4e here: https://twitter.com/clrs4e https://twitter.com/clrs4e" Also, from the description on purchase pages (Amazon, etc.): " New for the fourth edition • New chapters on matchings in bipartite graphs, online algorithms, and machine learning • New material on topics including solving recurrence equations, hash tables, potential functions, and suffix arrays • 140 new exercises and 22 new problems • Reader feedback–informed improvements to old problems • Clearer, more personal, and gender-neutral writing style • Color added to improve visual presentation • Notes, bibliography, and index updated to reflect developments in the field • Website with new supplementary material "
- fastasucan 5y ago
  The added color is almost enough to want me buy the new editon imo, I can only get so much out of the b&w graphics.

iamcreasy 5y ago

In one of Cormans' answer to question "Is CLRS really an "introduction"? If so, what's next?"[1] he replied, "Yes, Introduction to Algorithms really is an introductory text—on algorithms". But then he recommended the next book people should read is Don Knuth’s The Art of Computer Programming. Here is the quote "What’s next? Don Knuth’s The Art of Computer Programming, which I consider the greatest books (it is a multi-volume set) computer science has ever had or ever will have." I suppose the target groups of people studying his introductory book is not any random junior student at a random CS department if he is expecting them to pick up Knuth's Art of Computer Programming right after Introduction to Algorithms. [1] https://www.quora.com/Is-CLRS-really-an-introduction-If-so-whats-next https://www.quora.com/Is-CLRS-really-an-introduction-If-so-w...

dragontamer 5y ago
> I suppose the target groups of people studying his introductory book is not any random junior student at a random CS department if he is expecting them to pick up Knuth's Art of Computer Programming right after Introduction to Algorithms. I believe high-school students _can_ start that book at page1 chapter1. Just because it is rigorous and difficult doesn't mean that the high school student is ill-equipped to read it. TAOCP is one of the clearest written math-heavy books I've ever read, which makes it ideal for beginners. Yes, its rigorous. Yes, it will take you days, even weeks, to make progress beyond a few pages at times. But that's not a bad thing. Knuth hits the hardest subjects in the earliest sections and very precisely describes a lot of problems. Instead of relying upon "Dog isa Animal" and other crude, counter-productive "training wheels language" unsuitable for advanced understanding... Knuth just lays out the math as it is, in all of its complexity and glory. Rigor is good. And the sooner people practice with rigor, the better their minds will be. If anything, mathematical rigor needs to be introduced at younger ages when the mind is more pliable to learning different languages. ------- TAOCP is somewhere between an algorithms book and a math book. The 1st chapter is 100% math. It can be pursued independently and the 1st chapter is an _excellent_ introduction to rigorous mathematics.
gh0std3v 5y ago
> I suppose the target groups of people studying his introductory book is not any random junior student at a random CS department if he is expecting them to pick up Knuth's Art of Computer Programming right after Introduction to Algorithms. I don't think he's expecting a student to do that. He recommends the book in response to the question "What’s next?", implying that if a student would like to learn more, they should go to Knuth's books. Also, judging from the Quora link, he assumes the student has had a course in discrete mathematics, so they should be familiar with mathematical proofs and be comfortable with some level of rigor. I don't think Knuth's books are impossible to read, but a primer to some of the material can help (and understanding mathematical proof is a prerequisite).
- dragontamer 5y ago
  > I don't think Knuth's books are impossible to read, but a primer to some of the material can help (and understanding mathematical proof is a prerequisite). Its like no one has read "The Art of Computer Programming". Page 10 is an introduction to mathematical proofs !! Knuth covers this very early, because its so fundamental to the rest of the book. The book assumes the reader doesn't know rigorous math or proofs, and has an extremely solid section full of exercises for mathematical induction and proofs. The following sections are on the absolute barebones of math. Page 21 starts the section on numbers (really starting at the basics here). It covers integers, rationals, reals, complex numbers, logarithms and exponents. Honestly, this is like sophomore high-school level stuff, maybe even middle school to an advanced student ("Talented and Gifted" middle-school should cover this stuff actually ). I kid you not, I think an advanced 13 year old can handle this section. Page 27 explains sums and products ("sigma" notation). This should have been covered in high-school level pre-calculus, but we're finally approaching later high-school level math. There are discussions about how sigma is similar to calculus, but it doesn't seem necessary to understand the section. Page 39 is floor, ceiling, modulus arithmetic. While fundamental to discrete mathematics (arguably college level), its so elementary I'm not sure if it really counts as college level yet. Page 45 remains in high-school level: Permutations, Combinations, and Factorials, but also includes the Gamma function (which I'd argue is college-level). But given how Gamma is so similar to Factorial, I'd argue that the high-school level reader would still have an easy time with the concept. Page 53 are binomial coefficients / combinations, including pascal's triangle, and a huge number of identities. I'd say this is the first, college-level section. But by this point, the reader should be very much used to the idea of rigorous math. ---------- Seriously, if you've never given it a read... its pretty simple. Start at page 1, and work forward. Eventually you'll come across some exercises. At this point, test your knowledge to see if you truly understood the previous section. Do a few "level 10" or "level 20" problems (2 minute problems to 30 minute problems). Maybe think about level 30 or level 40 problems (1 day to 1 month problems), but don't feel like you actually have to solve them. Just read them over and "see why they're difficult" and make sure you understand the concepts. Then, start the next section. -------- Spend days or weeks per section, or even on a single page if you get stuck. Skip over * sections ("advanced"), unless you're confident in your abilities to read some of the most difficult comp. sci concepts. If you think you're bad at math, skip over "M" or "HM" exercises and sections (Math and High Math respectively).