If this is art then I'll have to admit - after 20 years of learning and practicing programming, I'm still a mechanic (or craftsman), not an artist.
I will not be able to read and understand this book fully and I probably won't even try, unless I'm locked in a cell with it.
Although I've helped build software used by millions, what I did was stitch together things that are too brilliant (or insane) for me to fully understand. And I assume that most of my colleagues did the same.
There are pylons of brilliance on the shoulders of which everyone builds, and Knuth must be one of the strongest.
Thank you Mr Knuth for holding so much weight on your shoulders.
Everyone with a good computer science education should be able to digest his books. I know that around here college education is often derided as outdated, impractical, too costly (which is a USA-ian problem), or outright irrelevant, but what Knuth writes about ain't rocket science yet important for many a programmer to understand. He writes in a quite readable style about the fundamentals of programming and computer science theory that's relevant to that programming. I know most programmers mostly glue together prefab components into working systems that successfully serve millions, but if one wants to go beyond the surface, to ask why it all works the way it does, a good computer science education is an advantage.
I like your sentiment, but your "good computer science education" sounds a lot like a "true scotsman". A lot of the people I work with have BS's in CS and a lot don't. I haven't seen any correlation between a real in depth understanding of computer science and a CS degree.
I agree programmers should be able to read and understand Knuth's books, but I don't think a CS degree is preparation. Would you think someone needs a CS degree if they already have a good understanding of the books?
My complaint with college is that it seems to be mostly fluff. If you show up and pay the bills then you'll get your degree.
Define 'need'. In college I learned, besides all the normal CS stuff:
* writing
* accounting
* organizational psychology
* small amounts of business stuff
* lots of EE, digital and analog
* how to read and write research papers
* how to research
* how to prove theorems (important if you are inventing your own)
* linear algebra, calculus, stats and probability, discrete algebra
* physics I-III, plus 1 semester of experimental physics
* chemistry (I,II, no organic)
* a bit of philosophy
* circuit design
* numerical computation
It would be a Herculean task to take all that up in your spare time to the level I did at school (I still learn on my own time, so you have to catch up not just with what I did at school, but everything afterwards). It's 4+ years of opportunity to bump against really good minds. I went to professors and said "I want to learn x". (think of the course catalog as a suggestion!) That got me, among other things a co-authorship with a professor on an academic book. All of that has been relevant to my career except for the chemistry. Even with that, my first job could have used it if I had stuck around more, and it is useful to know if you want to be scientifically literate.
Or, you know, you can punch your time cards, do the bare minimum, and graduate with a pretty useless certificate.
College as voc tech to learn to manipulate the LAMP stack is probably a poor choice of time. If you want to be able to take a job to compute cancer statistics, program robots, build digital interface cards, perform computer vision, simulate the ocean, write aircraft wing simulations, model and research traffic flow, work on medical devices, you almost certainly need more then votech and/or self learning, IMO. I've done most in that list professionally, and friends of mine have done the rest (no rockets in that list, but I was offered a job to do that, turned it down).
There are multiple paths to life, but the chance to just think and learn for awhile is pretty incredible if you can afford it.
This. You realise the value of the time you pissed away only when it's too late. Unfortunately, college coincides with the most callow years of your life, when you scarcely know the value of time, or the opportunity you are about to squander. Sigh...
One of my friends has loaned some books to my other friend's brother at the beginning of the year.
The year being over, I asked my friend if his brother is done with the books. He got back to me saying that his brother asked if I was in 1st year, and that he was surprised when he learned that I graduated and still studying.
I had a chance to talk with him yesterday (well, this morning at 4 AM), we were seven people at my friend's.
I said that not working harder than I did back in college is a mistake I am paying the price for today. I urged him to work harder than he is for he will later regret it with hot tears. I said that right now, he's in a cocoon where nothing is expected of him except to study, which he should do vigorously, relentlessly, and constantly. He has no other obligations or pressure other than to learn and become excellent. I said if I was asked to kill ten people to be able to go back a decade, I would kill an additional two to show how thankful I am for the bargain.
I tried to convey the message because he didn't fully grasp that time wasted is never, ever coming back. That once it's gone, it is forever. That it is the only thing we own only for its very duration, not a second more.
I hope he understood. There was a fleeting expression of realization after the chuckles that I hope will grow.
“I see it all perfectly; there are two possible situations — one can either do this or that. My honest opinion and my friendly advice is this: do it or do not do it — you will regret both.”
― Søren Kierkegaard, Either/Or: A Fragment of Life
Thus, follow your heart- dwell not on what you did, nor on what you do, but listen to what you need. Long after, look back, and see, more clearly, what you need now.
I won't say you're wrong, but I still think I'd rather regret having gone to school than, as I do now, regret having not gone; not that I haven't done rather well for myself, so much as that I'd have liked to do more -- I've learned from experience that the ancestor comment, about how much you have to make up, to be absolutely true; however autodidactic you happen to be, there's a lot of value in the distilled knowledge university courses can provide, and only so many hours in a day -- and days in a lifetime -- besides.
I don't know about other schools but my CS degree took a little more than showing up. Granted many of my classmates, even some of those who managed to graduate, never quite "got it." It's easy to say you don't need something you don't have. The lack of CS knowledge in our field is shameful and is a large contributor to all the crap code being pumped out at huge expense. That said, if you really love what you do you will probably learn how to do it well, eventually. A CS degree is a huge advantage, regardless.
Certainly, if all you're after is a degree (the certificate), not much effort is needed. On the other hand, if you want to, you can get more out of college. Which brings me back to my "good computer science education": it depends a lot on the aims of the student and how she approached her learning. That is not to say that there are no computer science programs that is basically vocational training, nor that there are programs that are very theoretical in nature, of course, but if you want, you can get more value for your money than a degree.
> Would you think someone needs a CS degree if they already have a good understanding of the books?
To be a programmer? No. But, at least to me, programming related matters is but a small part of computer science. Which makes Knuth's books such a great resource: it goes into detail in that small, yet quite large, field of programming.
You can say the it's up to the student to put in the effort but that really just sounds like confirmation that it's not part of a college education. If you want more out of an education you have to do it yourself, don't expect much from college.
I guess what I'm saying is that an undergraduate CS degree is just a vocational degree. College does not prepare you to read TAoCP. If you want a solid CS foundation you have to self study.
> I guess what I'm saying is that an undergraduate CS degree is just a vocational degree.
I think my undergraduate CS degree contained exactly four courses that I would classify as pure vocational in nature: the first class everyone had to take was to learn to program in Delphi; a class on functional programming; a class on GUI programming; and a class on object oriented programming. After that, all classes were either:
- mathematics, from analysis, statistics, writing/reading proofs, to loads of discrete mathematics
- formal methods, from proving correctness of programs, modeling, to different methods to analyze complex systems
- theory, from automata theory, language theory, compiler theory, database theory, relational algebra, to complexity and computability
- odds and ends, such as ethics, philosophy, history
Then, each trimester, we also had an engineering project where we would have to apply theory. There were no vocational classes associated. If we had to, or wanted to, use a tool, language, system, we had to learn it by ourselves first. Nevertheless, these engineering projects can be seen as vocational in nature too, of course. Still, that makes for about one vocational class a year (of about 15), and three engineering projects a year.
So, when people talk about undergraduate computer science degrees, I always assume their experiences are not dissimilar to mine.
I would argue that anyone who can read and understand TAOCS in its entirety is extremely privileged. Even if the entire CS curriculum was just "Read TAOCS", only the most motivated and hard-working students would make it through. TAOCS is enormous and a lot of the content is dense; even if it is possible for anyone with a (good) CS degree to digest, finding the time to do so would constitute a significant life commitment/accomplishment. Probably above/beyond that of getting a degree.
Even this single section within a single chapter could be used as the basis of an entire course.
I agree with you. It might make for an interesting course: the teacher develops instructional materials fitted for the class she's teaching, using Knuth's chapter as a reference and foundation, guiding and challenging students to dig deep on this topic. I'd like such a class, both as a teacher and a student, I think.
The primary benefit of TAOCS is that it's self-contained and all written in the same voice/style. It's much higher quality than a lot of other texts on the subjects it covers, but a given chapter is not necessarily that best text for the given topic.
It would be really cool if there were a "TAOCS" elective offered every single semester, just for the sake of fun. I would love to teach a course like that. I think it would work really well for e.g., an honors program ("to get honors in the major, one option is to enroll in this course for 4 consecutive semesters")
More generally, I think the policy that courses should use TAOCS where a chaper exists for the topic at hand would certainly increase the quality of courses at non-top CS programs (certainly, it would have at mine).
But in general, there are often texts that do a better job at covering a topic. E.g., this is a really interesting chapter, but I think there are probably better introductory texts on SAT (entirely subjective, of course).
Which is to say, if I know the area well then I will probably not use TAOCS. But if I don't then TAOCS is a safe choice.
Maybe I've exaggerated and downplayed my ability a bit for more drama. Of course I could digest the books if I absolutely wanted or needed to.
But probably I won't need to, because others have done it already and have implemented those ideas efficiently enough that I can just use their work.
There are a lot more problems that need to be solved at higher levels these days and many of them aren't even in computer science. That's were I spend most of my research time - the coding/cs stuff is easy now.
The point I was trying to make was that Knuth is one of the granddaddies of this whole reality that we populate and that was my attempt to express my gratitude.
I'm infinitely curious about everything, but at some point in life you realise that you can't go too deep in all directions, because it's a fractal of knowledge out there, so some things you just have to trust to be true and move towards new grounds.
You might be amused about one of the questions asked of each interviewee in http://www.codersatwork.com/ about whether or not they read TAoCP. Most, including Knuth, claim that they did not read it.
I have one of the first printings of the three first volumes but have not read all parts. I did do a deep dive in the floating point, as we at one point had to write that at MWC for an early compiler for the non-8087 class of computers. (Good work, Tim M.!)
Wasn't the question about whether or not they read other people's code. Doesn't make much sense to ask if Knuth reads his own book. Nor would the answer of no make any sense. Just this last year he discovered a new fact that he shared from Concrete Mathematics in the Christmas Tree Lecture. He clearly goes through them a lot.
Just saw I double posted in reply to you. Apologies.
Not sure what book I have in mind, then. I know there was one where they focus for many interviewees was whether or not they read other people's code.
And, I should add that I don't see it as a failing that people don't read some literature. I do think it is more approachable than it often gets credit for. To the point that I wish I had tried to read it years ago. That said, people that are being obviously productive should remain so using whatever strategy they have used to this point. :)
You should try it, at the least. It is surprisingly approachable and a lot of fun. I make no claims to be proficient in even a majority of the exercises.
I will add that learning algorithms in the way he presents them has been hugely successful in really understanding working with abstractions. Not just inventing the cheap abstractions of giving names to things; but really understanding how you can abstract some problems onto others and use common tools in solving them.
I know, I've tried it, maybe one evening read a thing, another evening another. And I would probably be able to understand it if I wanted to.
But I can't possibly allocate so much time reading these (long and complicated) books, because, well, all these problems are solved and implemented by people smarter than myself.
They're in the libraries, codecs, standards or embedded in the programming languages.
Problems I'm trying to solve are further and further away from that deep abstract level - and more in the realms of social psychology, perception, etc.
Thanks to Knuth and others, I can move away from the abstract to the concrete, from the computer to the human mind, even if I couldn't possibly explain the fundamentals in such detail as he does.
Chapter 7 will eventually fill at least four volumes . . . assuming that I'm able to remain healthy.
Apparently TAOCP has a lot in common with the Wheel of Time.
I have a ton of respect for these huge, decades-long, life-defining projects and the people who undertake them (Robert Caro's LBJ biography is another example.) So the end of this project always receding further into the distance makes me wistful, even if the quality of what gets put out is still excellent.
My intuition based on what I've seen and read is that a lot of the later chapters of the "12 chapter book about compilers" are in draft form, having accumulated over the 50 years since Knuth started writing. As Knuth notes in the fascicle, SAT has proven to be the core of the book (and thus Combinitorial Algorithms). In the beginning, it looked like the hard problems be limited to things relative to memory. It turns out that the hard problems involve pruning spaces larger than the universe.
I just picked up my father's old copy of vol. 1, Fundamental Algorithms. It's amazing that a book published in 1973 (second edition) can still be worth studying. I'd like to work from the copy I have, largely for sentimental reasons. My father passed away a few years ago, and it feels really good to work from the same book he studied decades ago.
Is it reasonable to study the second edition, or should I buy a copy of the third edition? I've been a hobbyist programmer for 20+ years, and I'd like to strengthen my understanding of basic data structures.
Knuth is a mathematician, and these are, mainly, books discussing mathematical results. Math is eternal - only the notation changes. You can, and, until recently, many did, learn geometry directly from Euclid.
Indeed he would need to change the books if there is a breakthrough in some of the algorithm areas described, but TAO is an excellent way to "quicky" move to the state of art in many areas.
I think getting a copy of the third edition is much better.
It is really worth studying even though sometimes you will be discouraged when answering some of the problems in the book and that would be normal. In fact, reading Donald Knuth's book is difficult but you should not feel bad about it.
Here is a quote from Peter Seibel's book, Coders at Work:
"I try to give the key ideas and I try to simplify them the best I can, but then what happens is every five pages of my book is somebody's career.
In other words, there's still so much more beyond any five pages of my book that you can make a lifetime's worth of study, because there's just that much in computer science."
The core algorithms Knuth discusses are unchanged in all those years. The practicality concerns are wildly different. Study the algorithms from the book, because it doesn't have a huge amount of opinion on when to use them anyway.
For anyone curious, this section is on SAT solving. It's section 7.2.2.2 of TAOCP, and is over 300 pages long. Pretty thorough for a section of backtrack, within a section on generating all possibilities, within a full chapter on combinatorial searching.
For what it's worth, I went to a presentation by Knuth on this exact section with a SAT expert who frequently commented how (for the presentation at least), significant amounts of relevant material had not been mentioned, and some techniques introduced were not particularly close to the state of the art, or good for educational purposes.
What I'm saying is that there's plenty of literature on SAT Solving already, and some of it is probably better.
I was reading the proceedings of the 2013 SAT competition and was pleasantly surprised to find Knuth listed as a contestant! It also included a few paragraphs he wrote about his submission.
I'm wondering if someone should be starting a new generation of TAOCP as wiki. As wonderful as TAOCP is, frankly, first volumes are bit outdated. Many problems that were mentioned opened have had huge progress and many new fields have opened up since their publications. Several Level 50 problems are now being taught in CS Masters or some even Bachelor levels. Besides I really find MIX too arcane and getting in the way. In a way, it's kind of disturbing that we still fall back on ~40 years old material for the field as fast moving as Computer Science. Sure, much of the CS is timeless but we are ignoring so much progress and growth in fields such as Computational Geometry, Number Theory, Cryptography, Semi-Numeral algos and so on. Also, even if Knuth manages to complete all of his planned volumes, it would still have scratched only tip of the tip of a iceberg. Of course, some of material will start becoming stale pretty much as soon as it was created. Currently Wikipedia is not a great option to create such writing because it doesn't allow content in "teaching style" or things like creating exercise. If we can distribute this effort out with editor that can approximate Knuth's meticulousness, it could be great boon for our field. Knuth as an original flame bearer could be a great person himself to start such an effort.
There is Wikibooks for this kind of content, but I suspect that compiling and editing a book like this (hundreds of pages of content, extensive exercises, references to the literature, proofs and equations, etc.) would be very difficult on a wiki.
You need contributors who can dedicate enormous amounts of time, a good wiki system (most can't cope with automatic cross-references to equations or sections, and don't provide special formatting or indexing for exercises, proofs, etc.), and editors who can combine the efforts of the contributors and produce something coherent.
I'd like to see software that can handle this kind of text. ScholarlyMarkdown[0] is trying to do it, and something programmable like Pollen[1] would be easily extended to support TeX-like features.
The software won't solve the time sink problem, though. Knuth is like a monk, sitting in his room pushing out manuscript pages. Who else is willing to dedicate the time?
This is a big enough project to justify a bespoke wiki-style system. Perhaps a thesis project for someone, along with tooling to convert existing content from TAOCP. Get some kind of grant to cover employing CS-literate undergrads on a UROP project to do the more difficult data entry and QA.
Heh, nothing's stopping you from starting that wiki. If you can get through any of those volumes, as 'outdated' as some of the information may be, you will be far ahead in algorithm analysis skills than 99.9999999% of the programmers out there. The key is focusing on any volume instead of being distracted by the new findings in the field. I tell this to myself too many times but don't listen. Sigh.
The lone genius working for years on a book is as far from a wiki as can possibly be.
Creating a quality computer science wiki with quality editing seems like a fine thing to do but "TAOCP as wiki" is just a contradiction in terms. You will invite certain comparisons that make you look foolish from the beginning.
If you want to work on solving the problems you're describing, one of the surest paths would be to translate the existing MIX code from the older books to MMIX versions.
I would love to contribute to a new, more open TAOCP that strives to cover a wider range. But I think it will be difficult to organize this.
If you want nicer fonts you can download your preferred latex distribution (miktex is easy to install but big) and your preferred perl distribution (ActivePerl maybe). Then you can run pkfix (which you may need to install) on the ps file like this:
There's some speculation about where the next breakthroughs will come from at the end of the chapter; it will be interesting to look back in 10-20 years and see if Knuth was correct.
I also liked the Fermatesque "exercise 223 is also currently unsolved, although I've rated it only '40' because I once thought of an answer (which I have since forgotten!)".
I too saw this footnote near the beginning (page 9):
“At the present time very few people believe that P=NP. In other words, almost everybody who has studied the subject thinks that satisfiability cannot be decided in polynomial time. The author of this book, however, suspects that N^O(1)-step algorithms do exist, yet that they’re unknowable. Almost all polynomial time algorithms are so complicated that they lie beyond human comprehension, and could never be programmed for an actual computer in the real world. Existence is different from embodiment.”
But would the existence of such "step algorithms" be fully equivalent to P=NP or a limited case applicable to only a subset of NP problems (i.e. one's thought previously to be NP)?
I read that not as 'step algorithms' but as 'algorithms requiring N^(O(1)) steps'; in other words - polynomial time algorithms.
One way to think of this is in terms of galactic algorithms, which are algorithms that incrementally improve the exponent in a polynomial time algorithm, but have constant terms so huge that they're effectively useless, practically. He's suggesting that there could exist a polynomial time algorithm for an NP problem which is similarly useless - but with the additional caveat that we won't even be able to prove theorems about it!
>>These so-called "SAT solvers" are able to handle industrial-strength problems, involving millions of variables, with relative ease, andthey've had a profound impact on many areas of research such as computer-aided verification.
I would be very interested in hearing of industrial/practical applications of those. Anyone with some experience?
One neat example that comes to my mind is how some package managers use SAT solvers to resolve package conversioning conflicts.
I would say that SAT solvers (or SMT solvers, depending on the problem domain) are applicable to almost any kind of problem where the first thing that comes to your mind is implementing a brute-force search using backtracking. SAT solvers implement lots of tricks that are likely to leave naive backtracking algorithms in the dirt (knuth's chapter covers lots of them)
One silly example I like is the time I used a SAT solver to find the solutions for a little Flash puzzle game.
My favorite part is how I could add some symmetry-breaking predicates to greatly speed up the solver on highly symmetrical problem instances. Those instances are very hard for hand-written algorithms and a SAT solver let me work around the symmetry problems in a highly declarative manner.
p2 (https://www.eclipse.org/equinox/p2/), the provisioning platform used in Eclipse, uses a SAT solver (specifically, http://sat4j.org/) to resolve complex plug-in dependencies (with version range constraints and other OSGi-specific niceties) when you install or update plug-ins in Eclipse.
I'm not 100% sure about this, but IIRC it'll be quite a while before they plan to rework Volumes 1-3 for MMIX (the new assembly language). Instead two smaller updates have been published, "TAOCP Volume 1, Fascicle 1: MMIX" and "The MMIX Supplement" by Martin Ruckert.
Regarding if it's justified, you might want to look at Knuth's forword to The MMIX Supplement. In short, he says that it's important to have some understanding of all the layers in the computer, and thus learning assembly is time well spent even if you never use it as such.
Nope, except for the fun, the assembly part does not add much to the matter. The essence is how to design, describe and analyze algorithms, so it is largely orthogonal to the language you use.
It is actually a little humbling to see just how well written and understood some assembly can be. In particular, the section simulating elevators is clearer than many high level examples I have seen of similar complexity.
I'm reluctant to post a PDF because of the copyright, but I'd recommend running the ps file through "pkfix" before converting to PDF. (This will replace the bitmap fonts with outline fonts.)
You could also boot on a Ubuntu live environment - bare-metal or through a virtual machine.
You can preview the .gz directly from the file manager - it's transparent.
When you design and write your own typesetting system in order to publish seven volumes on "The Art of Computer Programming", you get to choose whatever format you want.
I am not sure how it is related to 2015. I actually prefer a ps file that I can render to a PDF easily instead a Javascript heavy messy website where everything is distracting you from the content. On the top of that Knuth invented Tex to be able to write scientific documentations with ease[1].
Well, he has accepted electronic versions of his book. It's unfortunate that all but the pdf versions don't meet his standards:
"Note: However, I have personally approved ONLY the PDF versions of these books. Beware of glitches in the ePUB and Kindle versions, etc., which cannot be faithful to my intentions because of serious deficiencies in those alternative formats."
I prefer electronic books simply because they take zero physical space in my apartment. I do wish we could fix the issues.
To be fair, books on PDF are electronic books. Kindles don't handle them well, but tablets do.
Also, I agree with him! ePUB and Kindle markup/typesetting just don't look as good yet, and they certainly can't handle complex mathematics with any amount of grace.
> books on PDF are electronic books. Kindles don't handle them well, but tablets do.
Pdfs on current generation kindles (300dpi) look great, actually, as long as they are computer-generated. Scanned documents can be hit-or-miss, though.
Really? Last I tried, it'd display a page at a time, leaving you to scroll around. Particularly terrible with 2 column layouts like those loved for papers.
Yes, and yes. The viewer automatically crops whitespace in the margins to make best use of display space. Most documents will be smaller compared to the printed version, but still very readable. Anything with the "article" style looks great. Nearly every document with more than one column needs to be reformatted though.
I suspect someone like Knuth might attract quite a bit of mail from "math cranks" [0]; this tiny little hurdle might actually discourage a few of them.
Knuth uses vanilla TeX (which he wrote, btw). Also, the typesetting on the linked text is absolutely gorgeous. It looks much nicer than most LaTeX documents that I have seen. Wouldn't mind checking out the source.
Not sure why the parent is getting downvoted -- the ps.gz file lacks searchable text, which is a reasonable thing to expect in 2015. But, of course, the file is freely made available by Don Knuth, so all is forgiven :)
Side note: I've always thought Knuth looks delightfully like a resident of Whoville. https://s-media-cache-ak0.pinimg.com/236x/45/16/e3/4516e3256...