________________________________________________________________________________
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-w...
> 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.
>I suppose the target groups of people studying his introductory book is not any random junior student at a random CS department
I have never understood this take on CLRS because I was basically this archetype - I went back to school for a MS in CS, at a mediocre state school, after a BS in math during which _I never took a single programming class_ and my first algos class was out of CLRS. So I literally taught myself how to program the summer before by going through the Django tutorial and jumped straight into algos. I wasn't some kind of math genius either (or else I wouldn't have jumped ship after the BS). But there's not a single proof in the back that spans more than a page or two so I cannot fathom what people find difficult about digesting it. And the exercises are basically Leetcode problems, well known to everyone by now.
After many years of referring to the book over and over (during prep seasons for interviews) and helping other people through parts of it I think the reality is most CS students just don't understand that there's more to CS than JavaScript and Django and CLRS is a real shock more so than challenge.
I think the problem is CLRS is extremely dry and can easily put you to sleep so people do just enough to pass or get a good grade and forget about it. As a math grad, I think you had the advantage of having a lot more theory. Ideally more algo classes would combine with practical stuff like the youtube channel Coding Train or thr book Nature of Code by Schiffman to make things interesting for people who like to see things happen immediately.
>As a math grad, I think you had the advantage of having a lot more theory.
The funny thing is that I didn't. I sucked exactly at the kind of combinatorics (figured that out in the first few weeks of stats where you have to count things cleverly), graph theory type stuff during my math BS and so I avoided all of it. I excelled at analysis but CLRS has very little of that (maybe a couple of sections on convergence of numerical algos?).
What I did have was "mathematical maturity" enough to read proofs, but like I said there are so few that it doesn't matter IMHO.
> people who like to see things happen immediately
Our modern culture and lifestyle cultivates a desire for instant gratification in ways that make rigorous study of math and theory incredibly hard for most people who don't have the guiding structure of a math degree programme to counter-balance these forces.
> 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).
> 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).
I know that Knuth has some introduction in the beginning, but he goes over it pretty quickly, which is why I was saying that _some_ primer material is helpful just to get a headstart and not feel confused (plus Knuth himself says that you should just skim over the beginning material if you want to get to the "exciting" stuff).
> Spend days or weeks per section, or even on a single page if you get stuck.
This is asking a lot for people who don't have much time to spare. That being said, it's also why many people struggle to start Knuth's books. Most people have forgotten high school math at this point, and it's hard to learn and re-learn when you get older. I think some introductory coursework like the book posted by OP might be more fast-paced for people looking to start learning about algorithms.
Of the 672 pages of Book 1, at least 200 of the pages are about introductory Math subjects (if we include the dozens of pages of exercises in the back of the book associated with the math sections, and probably a good chunk of the Index/Bibliography too).
And as I stated earlier: this is elementary stuff. Like "What is a number", and "Summations". Yes, its difficult to _truly understand_ summations, and you may have to spend days or weeks relearning the material.
But that's just what math is. If you want to understand all the ins-and-outs of how numbers add together, you just gotta study it for longer than a day or two.
But Knuth provides something like 80+ exercises (and all of them worked out completely in the back of the book) to get you started on this subject.
-------
Summations are really useful for understanding for-loops and inductive reasoning anyway. A deep study into summations / loops / in general probably benefits the typical programmer, despite being a theoretical math subject.
> This is asking a lot for people who don't have much time to spare.
It takes far less time to read through a Knuth section than technical documentation for CPUs or GPUs, or spec-sheets on protocols, or any of the other stuff our field has to regularly deal with.
Reading and learning takes time. You have to be patient with yourself. You aren't going to be an expert on HTML, CSS, OpenCL, CUDA, x86 processors, ARM processors, or anything unless you spend days, weeks, or months reading, studying, and exercising (aka: writing simple programs or even advanced programs) on the subject.
That's the nature of our field. In the case of Knuth's approach on Algorithms, its Math heavy because you must understand the inductive reasoning that underlies it all.
Its one thing to say "Quicksort is fast". But what Knuth says is "This implementation of Quicksort executes in 3n * log(n) + X time" (or something like that, I forget exactly. But Knuth calculates it out exactly).
And furthermore, Knuth offers a mathematical proof, showing the student how to evaluate unknown algorithms.
--------
Knuth's book isn't about "Quicksort", even though it discusses it. Its about how to use Math to calculate how fast some algorithms are vs others. That's a lot of math to learn, go over, and become an expert in. Permutations, Random variables, summations (over the loop), induction and proofs.
This is all stuff a high-school student can learn, but whether you're 15 or 55, it will take weeks to learn and go through.
When you say he discusses how sums are similar to calculus, does that mean he relates sums to integrals (e.g Riemann sums)? Asking because I'm wondering if there's other connections I haven't been exposed to.
For Christmas, I (an adult) asked my mom to get me a few volumes instead of clothes this year. I'm looking forward to giving them a go like you described.
Oh, its just a throw-away sentence about infinite sequences / sums, and the usage of lim x->infinity to solve that kind of problem.
The bulk of that section is about distributive property of summations, sum_A(foo) + sum_B(foo) == sum_AorB(foo) + sum_AandB(foo), and other such properties.
Its a primer on the mathematics of programming, which is almost entirely discrete mathematics. There's no integral or derivative in that section!
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-differen...
Already received a reply from Dr. Cormen:
"I’ve been tweeting out differences between 3e and 4e here:
"
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
"
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.