17 ms·
Current draft of The Art of Computer Programming pre-fascicle 6a [ps]
- nmrm 11y agoThere'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.
- taosat 11y agoA surprising tidbit: Knuth believes that P=NP is true, but the algorithm to solve NP is unknowable - footnote on page 1 (pdf page 9). Proponents of RSA, DHE crypto - take note.
- rasz_pl 11y agoThere is a movie about it: Travelling Salesman (2012) http://www.imdb.com/title/tt1801123/reference http://www.imdb.com/title/tt1801123/reference
- michaelsbradley 11y agoI 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 don't know the answer and am genuinely curious.
- sdenton4 11y agoI 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!
- deleted 11y ago[deleted]
- schoen 11y agoI 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!)".
- deleted 11y ago[deleted]
- lallysingh 11y agops.gz? It's 2015!
- informatimago 11y agoSo what?
- piqufoh 11y agoWhen 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.
- deleted 11y ago[deleted]
- bokmann1969 11y agoYou don't know much about Knuth, do you?
- readme 11y agoPaper is even older and people still use that. The problem is...?
- istvan__ 11y agoI 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]. 1. https://en.wikipedia.org/wiki/TeX https://en.wikipedia.org/wiki/TeX
- runn1ng 11y agoI vastly prefer HTML with searchable text, easy copy-pasting capability, easy indexability, etc. to PDF with its outdated printed-page metaphor. On the other hand, it's Knuth and TAOCP, so I can't really complain much.
- spewbot 11y ago524 exercises
- a3n 11y agoIf you don't want to DL the .gz just yet, and just want to read about it, see here: http://www-cs-faculty.stanford.edu/~uno/news.html http://www-cs-faculty.stanford.edu/~uno/news.html 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/4516e3256d744ca4cff19402da907d75.jpg https://s-media-cache-ak0.pinimg.com/236x/45/16/e3/4516e3256...
- deleted 11y ago[deleted]
- bkcooper 11y agoChapter 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.
- thret 11y ago"You can have a sneak preview... As usual, rewards will be given to whoever is first to find and report errors or to make valuable suggestions." If you want to frame one of those cheques, get in fast.
- Tomte 11y agoYou don't get cheques, anymore. Only certificates from his fantasy bank.
- brudgers 11y agoMy 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.
- lambda 11y agoFor 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.
- Danltn 11y agoFor 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.
- taosat 11y agoCould you convince this SAT expert to review Knuth's fascicle and send his comments to Knuth? or blog about it for everyone's benefit?
- hoilogoi 11y agoI 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.
- kzhahou 11y agoDoes Knuth have a protege, helping him today, and to carry on the task should it take decades still? Also, is there a condensed version of his work that preserves the spirit and rigor?
- liotier 11y ago> Also, is there a condensed version of his work > that preserves the spirit and rigor ? "Don Knuth finally sells out" - http://i.imgur.com/hxmHdVZ.jpg http://i.imgur.com/hxmHdVZ.jpg
- xentronium 11y ago> Also, is there a condensed version of his work that preserves the spirit and rigor? I am not sure if this is useful for you, but Sedgewick's and Cormen's books are among more digestible alternatives.
- kzhahou 11y agoThanks! I've read Cormen, but not Sedgewick.
- couchand 11y agoThanks dang et al for fixing the title so quickly!
- japhyr 11y agoI 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.
- GauntletWizard 11y agoThe 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.
- JustSomeNobody 11y agoVery little has changed in the fundamental ways we write software in the past decades.
- leephillips 11y agoKnuth 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.
- wslh 11y agoIndeed 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.
- e19293001 11y agoI 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."
- codeshaman 11y agoIf 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.
- taeric 11y agoYou 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.
- codeshaman 11y agoI 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.
- ht_th 11y agoEveryone 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.
- bluecalm 11y ago>>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?
- pcdavid 11y agop2 (https://www.eclipse.org/equinox/p2/ https://www.eclipse.org/equinox/p2/), the provisioning platform used in Eclipse, uses a SAT solver (specifically, http://sat4j.org/ 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.
- ufo 11y agoOne 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. https://github.com/hugomg/hexiom https://github.com/hugomg/hexiom 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.
- clw8 11y agoI've been holding off on reading TAOCP because of the modernized assembly language promised for the next version -- is this at all justified?
- mpu 11y agoNope, 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.
- taeric 11y agoIt 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.
- znfi 11y agoI'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.
- deleted 11y ago[deleted]
- deleted 11y ago[deleted]
- zatatto 11y agoGot a link to PDF?
- sytelus 11y agoI'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.
- jcoffland 11y agoTechnology is fast moving. Computer Science, the real kind, moves slowly. TAOCP is still extremely relevant and MIX is cool, IMHO.
- deleted 11y ago[deleted]
- deleted 11y ago[deleted]
- msie 11y agoHeh, 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.
- zatatto 11y agoAnyone's got PDF? I can't open this .gz.ps file.
- msie 11y agoAsk anyone with a Mac. It generates PDFs automatically from it.
- dunham 11y agoI'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.)
- zatatto 11y agoi wish i knew how to do that
- crb002 11y agoMuch SAT. Such generating function. Algorithm W on page 79 (WalkSAT) is the workhorse. Lemma L and Algorithm M page 82 were my favorites.
- ElliotH 11y agoFor Windows users the incantation to get a version with fonts that aren't great but readable is this: gswin64 -sDEVICE=pdfwrite -o fasc6a.pdf fasc6a.ps You can get ghostscript here: http://www.ghostscript.com/download/gsdnld.html http://www.ghostscript.com/download/gsdnld.html and you will need it on your path. 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: pkfix fasc6a.ps fasc6a-pkfix.ps Finally you can run gswin64 -sDEVICE=pdfwrite -o fasc6a-pkfix.pdf fasc6a-pkfix.ps Which will give you a pretty nice pdf.