I read it a long time ago, around 1990. I remember people talking about it a lot in the early 80s
It's a seminal early text, but CS is a fast-changing field so I couldn't recommend it as a primary text for somebody who wants to learn CS today, however, it's definitely fun to flip through.
His stuff on "Searching and Sorting", for instance, just isn't relevant in a day when your language has a sort() function built in and hashtables. Also, in some of the areas I know about in depth, such as random number generation, Knuth's book is dangerously behind the times.
even in the 1990s there were much better random number generators than anything that Knuth or the Numerical Recipes people talked about (and I'm saying that as somebody who was lucky enough to take a class in Numerical Methods from Saul Teukolsky.)
Frankly it irks me that "computer science" is called a "science" rather than a kind of engineering. There's kind of a suggestion here that "engineering" is lower class and that "science" is something more dignified.
Today if you want to write efficient sorting and searching code you need to either think about very advanced algorithms or you need to think about how to get the best performance out of the memory hierarchy and that is all about having a predictable pattern of branching and memory access. If you are not doing that it is much smarter to use the sort() that came with your language.
A little knowledge really is dangerous. If you write your own half-baked algorithms you're going to waste a lot of time adding bugs and slowing down your code. For instance, if you know a little about cryptography you might invent some cypher which is easy to crack, when really you should focus on using established codes such as A.E.S., 3DES, and Twofish and use them correctly rather than inventing something which the NSA can crack in 10 seconds and a high schooler can do in 10 hours.
On the other hand, there are a lot of algorithms that really are interesting today, particularly those that function over partial orderings such as B.S.P. and transitive closure, dynamic programming (it's really amazing you can compute the Levenstein distance as fast as you can), suffix trees (it's counterintuitive that these can be constructed as fast as they can) or the block sorting that underpins bzip2 (it's amazing you can reconstruct the data from it at all.)
Knuth's books cover ground that has been done to death where you really ought to lean on the standard library.
But there is a difference between using the stdlib in practice, and having a good knowledge of how (say sorting) works and the different approaches even if you never need to implement one in practice. There remains value in the understanding
Quicksort is the algorithm that introductory CS will point you to.
If you want to build code that is life safety critical, say for automotive or aviation, you should not use recursion. You want to have bounded stack consumption. Lower teaching methods that you get in introductory CS can kill people.
Yes. You are mistaking computer science with computer programming.
Computer science is rarely concerned with a particular implementation in a particular language. It surveys procedures and algorithmic techniques which don't fall into the specificity of any one language, unless you are studying the very nature of programming languages of course.
Computer Science perhaps is a misnomer, but it for sure isn't an engineering study. It's a subcategory of mathematics, such as pure mathematics or combinatorics etc.
I've been reading a little bit of it every day. The quality of the writing is top notch, so I can actually ready it just for fun. I'm still on the first volume, and plan to be for a while. I definitely get lost on the mathier parts of it, but for the most part I can follow along, and I'd consider myself on the advanced side of intermediate.
I have read sections, more in the super-reference mode. For example, there was a period i was interested in random number generation, so that section was one. Another time, we had to implement floating point (in the pre-80x87 days), and that section was absolutely essential.
Incidentally, I have two copies, one set is the original edition. That set has something that has been deleted from later references--the fold-out page for Tape Merging. It is illustrating such tings as Read-backward polyphase merge, Read-backward oscillating sort, and Read-forward polyphase merge. I guess we don't sort on tape much anymore.
I've read portions of volumes 1, 3 and 4A so I haven't finished the books.
The thing about these books is that while you can _Read_ them like any other book, reference or otherwise, what sets them apart are the questions at the end that have always been very thought provoking.
4A to me was the most useful - combinatorial algorithms, talking about generating trees, permutations. Reading it really cleared out some concepts that relate to sorting and searching. It's almost like someone condensed all known information about those algorithms (till the last 2-3 years) into one dense manual for dummies. Oh wait..
And, they don't look half bad on your bookshelf with that leather cover (although I don't own the boxed set). I've always been tempted to buy.
There's no better time to read them than right now. And I don't think the right way to read them is volume wise. What I've done is to go through the table of contents and pick something that looks interesting, and chew on it.
I've read portions of volumes 1, 3 and 4A so I haven't finished the books.
The thing about these books is that while you can _Read_ them like any other book, reference or otherwise, what sets them apart are the questions at the end that have always been very thought provoking.
4A to me was the most useful - combinatorial algorithms, talking about generating trees, permutations et al. Reading it really cleared out some concepts that relate to sorting and searching. It's almost like someone condensed all known information about those algorithms (till the last 2-3 years) into one dense manual. (oh wait..)
There's no better time to read them than right now IMHO. And I don't think the right way to read them is volume wise. What I've done is to go through the table of contents and pick something that looks interesting, and chew on it for a bit. But to each their own.
I've "read" most of the first three volumes if it counts to read the text and skip most of the math. I always figured it was enough to "get" the algorithm, and go back to the math if I ever needed it. So far, years later, I've never needed to go back to the math, so I'm glad I didn't spend much time on it.
No doubt the math is useful in a theoretical way, and I'm pretty sure I could follow through most of it if I really needed to, but as far as proving algorithms and asymptotic run times, I've yet to need more than a general understanding of big O notation in my real work.
How long it takes is entirely up to you. If you try to understand every detail of every proof and theorem it will probably take a very long time.
I'm not sure it's worth reading all the way through, to be honest. I guess I'd suggest the first volume for a solid, math heavy intro to algorithm analysis and design. But after that, there's not much point unless you're going to read it for fun, and in that case, why ask about it on HN? The reality is that few people will ever need to know that much detail about any of the algorithms covered because almost all of them are library functions now.
I've spent some time implementing my own multi-precision integer library, and I've used TAoCP as a reference for that, but not otherwise.
From this (admittedly limited) data point, I'd say it's a useful reference if you're working on implementing some of the tricky algorithms contained therein, but you'll need to work hard for it. The code is all assembler (a dialect Knuth invented for the book; I think it predates structured programming), so you'll need the proofs to even understand what's going on. I'm not sure how much benefit you'll derive from just reading it through without digging into the problems, but I haven't done it.
I haven't read TAoCP. I am reading them. I have been for years. Every time I open one up, I learn something. I am also always confused. That's what I love about the work. It reminds me that this stuff is hard - so hard that Knuth hasn't finished learning the subject even after 50 years spent writing a 12 chapter book about compilers.
What makes them great books is Knuth's ability to tackle writing at multiple levels of sophistication. As I learn more maths new portions of each section become accessible. As I learn more about data structures and algorithms a similar thing tends to happen.
I haven't been in a rush to 'finish' them. Neither has Knuth. I read them because I enjoy reading them.
I've read very carefully some parts of it, mostly combinatorial algorithms, because I had a program to write or an algorithm to study. I've also done exercises here and there when they caught my interest (obBrag: and once got a $2.56 check out of it). I'm also using TAOCP as a bedside table book, because Knuth is fun and relaxing to read.
22 comments
[ 4.4 ms ] story [ 55.5 ms ] threadIt's a seminal early text, but CS is a fast-changing field so I couldn't recommend it as a primary text for somebody who wants to learn CS today, however, it's definitely fun to flip through.
His stuff on "Searching and Sorting", for instance, just isn't relevant in a day when your language has a sort() function built in and hashtables. Also, in some of the areas I know about in depth, such as random number generation, Knuth's book is dangerously behind the times.
Can you be specific about how it is behind the times?
http://www.honeylocust.com/RngPack/
even in the 1990s there were much better random number generators than anything that Knuth or the Numerical Recipes people talked about (and I'm saying that as somebody who was lucky enough to take a class in Numerical Methods from Saul Teukolsky.)
You're conflating Computer Science with Computer Programming.
Frankly it irks me that "computer science" is called a "science" rather than a kind of engineering. There's kind of a suggestion here that "engineering" is lower class and that "science" is something more dignified.
Today if you want to write efficient sorting and searching code you need to either think about very advanced algorithms or you need to think about how to get the best performance out of the memory hierarchy and that is all about having a predictable pattern of branching and memory access. If you are not doing that it is much smarter to use the sort() that came with your language.
A little knowledge really is dangerous. If you write your own half-baked algorithms you're going to waste a lot of time adding bugs and slowing down your code. For instance, if you know a little about cryptography you might invent some cypher which is easy to crack, when really you should focus on using established codes such as A.E.S., 3DES, and Twofish and use them correctly rather than inventing something which the NSA can crack in 10 seconds and a high schooler can do in 10 hours.
On the other hand, there are a lot of algorithms that really are interesting today, particularly those that function over partial orderings such as B.S.P. and transitive closure, dynamic programming (it's really amazing you can compute the Levenstein distance as fast as you can), suffix trees (it's counterintuitive that these can be constructed as fast as they can) or the block sorting that underpins bzip2 (it's amazing you can reconstruct the data from it at all.)
Knuth's books cover ground that has been done to death where you really ought to lean on the standard library.
Kinda.
Quicksort is the algorithm that introductory CS will point you to.
If you want to build code that is life safety critical, say for automotive or aviation, you should not use recursion. You want to have bounded stack consumption. Lower teaching methods that you get in introductory CS can kill people.
Computer science is rarely concerned with a particular implementation in a particular language. It surveys procedures and algorithmic techniques which don't fall into the specificity of any one language, unless you are studying the very nature of programming languages of course.
Computer Science perhaps is a misnomer, but it for sure isn't an engineering study. It's a subcategory of mathematics, such as pure mathematics or combinatorics etc.
"You're full of shit," (Don Knuth) [1]
I think that no one in the world, except Knuth, has read the entire TAOCP (joke.)
[1] http://www.folklore.org/StoryView.py?story=Close_Encounters_...
https://www.youtube.com/watch?v=DmbGs290qeM
In Coders at Work, Bernie Cosell notes that he (and apparently colleagues) read TaoCP cover to cover.
Incidentally, I have two copies, one set is the original edition. That set has something that has been deleted from later references--the fold-out page for Tape Merging. It is illustrating such tings as Read-backward polyphase merge, Read-backward oscillating sort, and Read-forward polyphase merge. I guess we don't sort on tape much anymore.
The thing about these books is that while you can _Read_ them like any other book, reference or otherwise, what sets them apart are the questions at the end that have always been very thought provoking.
4A to me was the most useful - combinatorial algorithms, talking about generating trees, permutations. Reading it really cleared out some concepts that relate to sorting and searching. It's almost like someone condensed all known information about those algorithms (till the last 2-3 years) into one dense manual for dummies. Oh wait..
And, they don't look half bad on your bookshelf with that leather cover (although I don't own the boxed set). I've always been tempted to buy.
There's no better time to read them than right now. And I don't think the right way to read them is volume wise. What I've done is to go through the table of contents and pick something that looks interesting, and chew on it.
4A to me was the most useful - combinatorial algorithms, talking about generating trees, permutations et al. Reading it really cleared out some concepts that relate to sorting and searching. It's almost like someone condensed all known information about those algorithms (till the last 2-3 years) into one dense manual. (oh wait..)
There's no better time to read them than right now IMHO. And I don't think the right way to read them is volume wise. What I've done is to go through the table of contents and pick something that looks interesting, and chew on it for a bit. But to each their own.
No doubt the math is useful in a theoretical way, and I'm pretty sure I could follow through most of it if I really needed to, but as far as proving algorithms and asymptotic run times, I've yet to need more than a general understanding of big O notation in my real work.
How long it takes is entirely up to you. If you try to understand every detail of every proof and theorem it will probably take a very long time.
I'm not sure it's worth reading all the way through, to be honest. I guess I'd suggest the first volume for a solid, math heavy intro to algorithm analysis and design. But after that, there's not much point unless you're going to read it for fun, and in that case, why ask about it on HN? The reality is that few people will ever need to know that much detail about any of the algorithms covered because almost all of them are library functions now.
From this (admittedly limited) data point, I'd say it's a useful reference if you're working on implementing some of the tricky algorithms contained therein, but you'll need to work hard for it. The code is all assembler (a dialect Knuth invented for the book; I think it predates structured programming), so you'll need the proofs to even understand what's going on. I'm not sure how much benefit you'll derive from just reading it through without digging into the problems, but I haven't done it.
What makes them great books is Knuth's ability to tackle writing at multiple levels of sophistication. As I learn more maths new portions of each section become accessible. As I learn more about data structures and algorithms a similar thing tends to happen.
I haven't been in a rush to 'finish' them. Neither has Knuth. I read them because I enjoy reading them.