I'm starting the first volume.
Right at the start, Knuth introduces Induction Mathematical Proof, and more specifically tries to show that we can describe it as an `algorithm mathematical proof`.
I showed it to a friend who is quite good at math, and he told me the book may be trying too hard especially in the examples variety, and how it might not be needed for comprehension's sake.
Would you still recommend this book, and if yes, in what circumstances?
In 1956, Knuth graduated high school and entered college, where he encountered a computer for the first time (the IBM 650, to which the series of books is dedicated). He took to programming like a fish to water, and by the time he finished college in 1960, he was a legendary programmer, single-handedly writing several compilers on par with or better than professionals (and making good money too). In 1962 when he was a graduate student (and also, on the side, a consultant to Burroughs Corporation), the publisher Addison Wesley approached him with a proposal to write a book about writing compilers (given his reputation), as these techniques were not well-known. He thought about it and decided that the scope ought to be broader: programming techniques were themselves not well-known, so he would write about everything: “the art of computer programming”.
This was a time when programming a computer meant writing in that computer's machine code (or in an assembly language for that machine) — and some of those computers were little more than simple calculators with branches and load/store instructions. The techniques he would have to explain were things like functions/subroutines (a reusable block of assembly code, with some calling conventions), data structures like lists and tries, how to do arithmetic (multiplying integers and floating-point numbers and polynomials), etc. He wrote up a 12-chapter outline (culminating in "compiler techniques" in the final chapter), and wrote a draft against it. When it was realized the draft was too long, the plan became to publish it in 7 volumes.
He had started the work with the idea that he would just be a “journalist” documenting the tricks and techniques of other programmers without any special angle of his own, but unavoidably he came up with his own angle (the analysis of algorithms) — he suggested to the publishers to rename the book to “the analysis of algorithms”, but they said it wouldn't sell so ACP (now abbreviated TAOCP) it remained.
He polished up and published the first three volumes in 1968, 1969, and 1973, and his work was so exhaustive and thorough that he basically created the (sub)field. For example, he won a Turing Award in 1974 (for writing a textbook, in his free time, separate from his research job!). He has been continually polishing these books (e.g. Vols 1 and 2 are in their third edition that came out in 1997, and already nearly the 50th different printing of each), offering rewards for errors and suggestions, and Volume 4A came out in 2011 and Volume 4B in 2023 (late 2022 actually).
Now: what is in these books? You can look at the chapter outlines here: https://en.wikipedia.org/w/index.php?title=The_Art_of_Comput... — the topics are low-level (he is interested in practical algorithms that one could conceivably want to write in machine code and actually run, to get answers) but covered in amazing detail. For example, you may think that there's nothing more to say about the idea of “sequential search” than “look through an array till you find the element”, but he has 10 pages of careful study of it, followed by 6 pages of exercises and solutions in small print. Then follow even more pages devoted to binary search. And so on.
(The new volumes on combinatorial algorithms are also like that: I thought I'd written lots of backtracking programs for programming contests and whatnot, and “knew” backtracking, but Knuth exhausted everything I knew in under a page, and followed it with dozens and dozens of pages.)
If you are a certain sort of person, you will enjoy this a lot. Every page is full of lots of clever and deep ideas: Knuth has basically taken the entire published literature in computer science on each topic he covers, digested it thoroughly, passed it through his personal interestingness filter, added some of his own ideas, and published it in carefully written pages of charming, playful, prose. It does require some mathematical maturity (say at the level of decent college student, or strong high school student) to read the mathematical sections, or you can skim through them and just get the ideas.
But you won't learn about, say, writing a React frontend, or a CRUD app, or how to work with Git, or API design for software-engineering in large teams, or any number of things relevant to computer programmers today.
Some ways you could answer for yourself whether it's worth the time and effort:
• Would you read it even if it wasn't called “The Art of Computer Programming”, but was called “The Analysis of Algorithms” or “Don Knuth's big book of super-deep study of some ideas in computer programming”?
• Take a look at some of the recent “pre-fascicles” online, and see if you enjoy them. (E.g. https://cs.stanford.edu/~knuth/fasc5b.ps.gz is the one about backtracking, and an early draft of part of Volume 4B. https://cs.stanford.edu/~knuth/fasc1a.ps.gz is “Bitwise tricks and techniques” — think “Hacker's Delight” — published as part of Volume 4A. Etc.)
• See what other people got out of the books, e.g. these posts: https://commandlinefanatic.com/cgi-bin/showarticle.cgi?artic... https://commandlinefanatic.com/cgi-bin/showarticle.cgi?artic... https://commandlinefanatic.com/cgi-bin/showarticle.cgi?artic... are by someone who read the first three volumes in 3 years. For a while I attended a reading group (some recordings at https://www.youtube.com/channel/UCHOHy9Rjl3MlEfZ2HI0AD3g but I doubt they'll be useful to anyone who didn't attend), and we read about 0.5–2 pages an hour on average IIRC. And so on.
I find reading these books (even if dipping into only a few pages here and there) a more rewarding use of time than social media or HN, for instance, and wish I could make more time for them. But everyone's tastes will differ.
https://silezukuk.tumblr.com/image/616657913
Any recommendations/suggestions?
In 2015, I decided I was no longer poor and should buy the box-set as a treat. I set aside time to read a chapter in the first week after it arrived, but realised that it would take years to read and actually understand the material in that one book, let alone the other two. I decided I'd just dig in from time to time, but found that I never actually did, because in all honestly I'm less interested in abstract algorithms now, and prefer to spend free time doing other things in life that don't involve computers.
So, my copy is still essentially untouched after almost a decade.
Deleted Comment
I don't get what you find strange about comparing reading TAOCP vs reading social media. Your time is limited, and each activity that you choose bears an opportunity cost. Of course it is an interesting question to ask whether you should read another book instead, but I bet that most people waste a lot more time on social media than reading a book that is not TAOCP, so svat's comparison does make a lot of sense in my opinion.
There is also a contrast between the two: they lie on opposite ends of a spectrum from shallow to deep, of things that make you really think / put in honest effort, and also give a deeper enjoyment.
As for reading other (good) books: like anything else, it's ultimately a question of what gives you most joy, I guess. Learning (say) real analysis from Rudin would also be deep and make you work, but Knuth has more jokes.
But then again, as a result of all this work from him, pulling together and categorizing and cataloguing and analyzing all the disparate ad-hoc “tricks” that programmers had come up with, Knuth basically put (this area of) computer science on good foundations and made it a respectable academic discipline. So in that sense he successfully executed a Principia-like project.
To put it another way, the computer programming/algorithms world is generally divided into hackers who derive satisfaction from elegant ways of bending computers to their will, and theorists who are happy to talk asymptotics, treat their problems abstractly as a branch of mathematics, and often never write a single program. What sets Knuth apart is that he straddles both words: is firmly a hacker at heart, but is able to bring prodigious theoretical skill to bear on the area.
---
PS- not to be "that guy" but I do think that a future edition should port the MMIX to RISC-V because it'll be actually runnable and I'd bet money that RISC-V is the educational standard going forward for the next 50 years.
Dead Comment
I think you can read at various levels though.
When I say I've read most of Volumes 1-3, I mean literally that, I read the text through. At that level it isn't too difficult to read, and you'll learn a lot like that.
However some bits I've studied in much greater detail, like for instance the multi-precision arithmetic algorithms which I had to implement. For that I read it multiple times, implemented the algorithms, did some of the exercises. That takes much much longer than just reading it through.
It is rather like reading a research paper which you do roughly like this, stopping after any step where you think it is no longer providing value to you.
To get the most out of it, you'll need to go to level 5, but you can get a great deal out of it at the earlier levels.So I've read most of TAOCP at level 3, half a volume at level 4 and only 50 pages at level 5.
If nothing else I've loaded the index in my head!
PS the examples are notorious in TAOCP. The easy ones will take a few minutes and the hard ones are unsolved research problems!
I haven't read the book, so he poses research questions as exercises to the reader...?
"Develop computer programs for simplifying sums that involve binomial coefficients"
Which was solved in the book titled "A = B":
https://www2.math.upenn.edu/~wilf/AeqB.html
or
https://www.amazon.com/B-Marko-Petkovsek/dp/1568810636
> "Nobody ever taught me about a B-tree. I had heard of it. When I went to write my own B-tree, on the bookshelf behind me, I’ve got Don Knuth’s The Art of Computer Programming, so I just pulled that down, I flipped to the chapter on searching and looked up B-trees and he described the algorithm. That’s what I did. Funny thing, Don gives us details on the algorithm for searching a B-tree and for inserting into a B-tree. He does not provide an algorithm for deleting from the B-tree. That’s an exercise at the end of the chapter, so before I wrote my own B-tree I had to solve the exercise at the end. Thanks, Don. I really appreciate it."
https://corecursive.com/066-sqlite-with-richard-hipp/#b-tree...
My favorite episode is https://corecursive.com/remote-developer/
I read through volume 1 several times. I then skimmed through the arithmetics part of volume 2 and read only the section about random numbers, which is very fascinating but you will be able to live without unless you are doing simulations or cryptography/cryptoanalysis.
Whether you will need volumes 4a, b, c depends on whether your work has much to do with combinatorics. I'm a professor and I did not need most of it, but had a good laugh about the hidden gems and jokes like the exercise about Knuths personal pipe organ.
As a software engineer, you may occasionally consult volumes 3 and 1 (searching, sorting, data structures).
[Side node: If I was Knuth, I don't think I would have created three subvolumes instead of the planned single volume 4. While it is true that the material exploded, that will always be the case, and is also true for the other chapters. In his shoes, I would have worked on succession planning and trying to map out the remaining volumes so that the book can be completed one day. Under Knuths approach (esp. going back to update the existing volumes repeatedly on the way) TAOCP will unlikely ever be completed, which would be a shame.]
One day I was working on a problem and I realized that I was storing a lot of 0's in my matrix and I remembered that I read about sparse matrices in TAOCP (this was before you could just go to numpy and make a sparse matrix). So I went back to that chapter and used that to solve my problem.
That's happened to me many times in my career now, I remember that I read the general idea in TAOCP and then when I realize I need it, I go back and learn it for real.
If you want to be someone who understands computation (using computers to solve real problem), then it's probably good to have "read" TAOCP just to see what kinds of problems other people have encountered and know that there is at least one good solution to them. Then if you ever need to solve that problem, you know where to look for a start.
A little more philosophical: a culture needs a common core set of ideas that everyone can reference. When working together as a group, having a set of common ideas is a great shortcut in communicating. I'm not religious, but I see the bible as a historical way that this worked for the western cultures - there was a set of "givens" that everyone could hang their ideas off of. Every field of knowledge needs this common understanding. I view TAOCP as this for the field of computing. There are better ways to solve many of the problems now, or common libraries that provide the solutions, but having the problems named and discussed gives everyone a good starting place to talk.
tl;dr - yes, TAOCP is good, read it to learn the concepts and ideas that people smarter than you solved years ago.
It does feel that sometimes he goes deeper than what you'd expect from a 7 volume book.
As with any complicated topic, you need to give yourself some sleep to be able to truly intuit it.
That's probably true, in the sense that it deals largely with the kind of functionality modern programmer should be calling from a library, not implementing by hand. But I think it's hugely enriching to read these books. I read 1-3 back in the 70s, and was particularly inspired by Sorting and Searching, and especially the chapter on random numbers. RNGs have intrigued me ever since.
I find Knuth's writing style very pleasant. He's funny. So is it worth the time and effort? Not if "worth it" means "makes you a better Javascript programmer". But it's worth it in the sense that reading books about the history and geography of a country is "worth it" before visiting; your appreciation of the place is deepened, possibly transformatively. It could even be that you would never have visited had you not read those books.
I found TAOCP easy to read, much more so than most textbooks. I don't think I tackled many of the exercises; certainly none of the challenging ones. So for me, the "effort" aspect of "is it worth the time and effort" was quite low, so the ROI was quite high. If you find the books hard to read, then don't bother (and perhaps you aren't really interested in low-level algorithms).
TAOCP is extremely rigorous and detailed, the discussion of any topic there will cover every detail. For practical software engineering, it's not useful, you don't deal need that level of theoretical understanding as a software engineer (if you're one of the few who need it, you'd know you are). And you need a very solid mathematical background to actually understand it.
If you want to understand the theory of CS algorithms, I think the CLRS "Introduction to Algorithms" is an excellent textbook. It covers about everything most people are likely to encounter, has comprehensive mathematical analysis but is much easier to follow than TAOCP. For an understanding of the mathematics involved, Concrete Mathematics is a good book, it teaches the mathematical concepts and tools that are the foundation of other, more rigorous books.
For instance, I just opened randomly to the binary tree traversal material in Vol. I. It's very mathematic or formal, e.g. "T2. [P = Λ?] If P = Λ, go to step T4." and so on. To fish out some of the more interesting details, you have to look through the questions and then flip to the answers.
Meanwhile, https://en.wikipedia.org/wiki/Tree_traversal has the same information but somehow more clearly presented.
If I flip to other random pages and scan for 30 seconds, I can't find much that is actually interesting---particularly in the early volumes.
-----
The Art of Electronics is more my speed, as it's a collection of real-world applications, deep dives into each component type, quick comparison tables, and clear overview of a specific design's pros and cons. It's as much interesting to read through as it is useful as a reference.
I can flip to basically any random page of The Art of Electronics and find something eliciting, "Oh cool." I can't say the same for TAOCP.