7 ms·

In his recent Dancing Links talk (a couple of weeks ago), he mentioned a generalization of exact cover that also covers constraint programming. You may want to

by svat 8y ago

In his recent Dancing Links talk (a couple of weeks ago), he mentioned a generalization of exact cover that also covers constraint programming. You may want to look into that (XCC) in the meantime, in Knuth's fascicle on Dancing Links (https://cs.stanford.edu/~knuth/fasc5c.ps.gz https://cs.stanford.edu/~knuth/fasc5c.ps.gz). I know the feeling of waiting for new chapters of TAOCP; I'm waiting for Chapter 8 on recursion because his idea of it is so different from everyone else's.

taeric 8y ago
What makes his idea different from everyone else's? I know he covers coroutines, being something not really available in most languages. That said, I thought it was an accepted term and I didn't think that was his invention.
- dragontamer 8y ago
  > What makes his idea different from everyone else's Depth and coverage. Case in point: Knuth's coverage of Quicksort doesn't calculate the Big-O. It calculates the precise average running time. He literally counts the assembly-language statements. You might say "But arrays might be randomly sorted", and yeah, Knuth averages the runtime across all possible ways that an array can be sorted. Its a beautiful work of math. There's almost no room for questions once Knuth finishes a subject. Its so exhaustively covered that I can't even imagine questions I have on any subject after he's done writing about it. The few questions I do have are the "Difficulty 40+" questions that Knuth puts at the end of each section, which would serve as excellent questions for Masters Thesis or a PH.D Thesis. IE: There's no answer to those questions yet. Anyway, while most textbooks hand-wave the idea of "Quicksort is faster than Mergesort, even both are O(n*log(n))". Knuth is pretty simple, he says: Look at these two precise numbers I've calculated (and proved). Quicksort is faster (or at least, the Assembly-language version of Quicksort he wrote on his imaginary computer is faster) Basically, Knuth got "to the bottom of it", there's no hand-waving involved in the explanation. He just tackles the hard questions head on and solves it more precisely than everyone else. ---------- Some of the older chapters are going out of date, which is natural for a work so complete. There is so much material out there that Knuth has to make a decision on whether to revise older stuff (which he does occasionally) or to write about subjects which don't have a major unifying work yet (ie: Constraint Programming has some textbooks here and there, but most of its ideas are only in academic journals, and haven't really been unified into a singular work yet IMO. Even the textbooks on the subjects are mostly introductions + references to papers) And sometimes, Knuth gets lucky. Knuth's Book3 "Searching and Sorting" includes a HUGE table of sorting methods applied to tape drives. But today's RAM is now faster sequentially rather than random-access. So Knuth's calculations on Tape-Drive sorts actually applies to modern DDR4 RAM better than any other treatment on the subject. No one else calculated the cost of "internal movements" (aka: cache on modern systems, but it was RAM on older computers) + "external movements" (which was Tape Drives in Knuth TAOCP / Book 3, but is really DDR4 RAM on today's machines). So yeah, Book 3 is out of date and focuses a huge amount of time on external sorting methods. But... it just so happens that if you know a bit about the sequential nature of modern DDR4 RAM, it is actually super-relevant to today's computers.
  - taeric 8y ago
    That doesn't sound like it is different, so much as just more complete. His analysis of permutations in order to analyze runtimes is, as you say, truly a wonder. This doesn't feel different from everyone else's idea, though. Unless you just mean in the general complexity analysis, where most of us are basically taught to stop at the highest order terms. It is interesting, because Knuth seems credited with pushing Big-O analysis, but he never stopped at the highest term when analyzing an algorithm. Far as I can tell, he never has. He has done this to compare some algorithms, but even then he has always been empirical for actually comparing things. Treating the Big-O as a hypothesis to test, if anything.
- svat 8y ago
  Oh sorry, to be clear, by "his idea of it" I meant "the way he thinks about it [recursion]". What's different is that when most people learn programming, they pick up the idea that iterative structures (loops etc) are simple, and recursion is something more "advanced", harder to understand. Knuth thinks that recursion is the simpler thing (what comes to humans/children naturally), and the mark of a better programmer is being able to translate recursion into iterative structures. This seems to tie in with his attitude towards programming in general: while in the zeitgeist the idea is that a good program builds better abstractions until the structure of the program reflects human thought, Knuth seems to think that a good programmer is one who starts with a human-level description of the solution and carefully refines it until it translates into a good set of instructions (in machine code). (There's no contradiction, but the point of view seems different from the usual.) He briefly mentions something related in his Structured Programming with Go To Statements (1974) https://pic.plover.com/knuth-GOTO.pdf#page=21 https://pic.plover.com/knuth-GOTO.pdf#page=21 > I have always felt that the transformation from recursion to iteration is one of the most fundamental concepts of computer science, and that a student should learn it at about the time he is studying data structures. This topic is the subject of Chapter 8 in my multivolume work; but it's only by accident that recursion wasn't Chapter 3, since it conceptually belongs very early in the table of contents.
  - taeric 8y ago
    I think some of this is likely to be a product of the times. The vast majority of early programming languages were not friendly to recursion. It wasn't at all uncommon for functions not to be reentrant, and to rely on self manipulation to set the return stack, if I recall. Even today, for many "systems level" programs, you have to take extreme care around recursion, since you are likely to blow the stack limits. (That is, you can't just use recursion freely, but instead have to prove the maximum depth that you will trigger it.) That is to say, I don't see what makes this different than how most others view recursion. If you can afford to do it, then you should do so. If you can't, then you should be ready for a lot of his other tricks. (Threaded trees being my personal favorite, at the moment. DFS with no stacks? Crazy talk! :) )
    - 8y ago

by svat 8y ago

taeric 8y ago

What makes his idea different from everyone else's? I know he covers coroutines, being something not really available in most languages. That said, I thought it was an accepted term and I didn't think that was his invention.

dragontamer 8y ago
> What makes his idea different from everyone else's Depth and coverage. Case in point: Knuth's coverage of Quicksort doesn't calculate the Big-O. It calculates the precise average running time. He literally counts the assembly-language statements. You might say "But arrays might be randomly sorted", and yeah, Knuth averages the runtime across all possible ways that an array can be sorted. Its a beautiful work of math. There's almost no room for questions once Knuth finishes a subject. Its so exhaustively covered that I can't even imagine questions I have on any subject after he's done writing about it. The few questions I do have are the "Difficulty 40+" questions that Knuth puts at the end of each section, which would serve as excellent questions for Masters Thesis or a PH.D Thesis. IE: There's no answer to those questions yet. Anyway, while most textbooks hand-wave the idea of "Quicksort is faster than Mergesort, even both are O(n*log(n))". Knuth is pretty simple, he says: Look at these two precise numbers I've calculated (and proved). Quicksort is faster (or at least, the Assembly-language version of Quicksort he wrote on his imaginary computer is faster) Basically, Knuth got "to the bottom of it", there's no hand-waving involved in the explanation. He just tackles the hard questions head on and solves it more precisely than everyone else. ---------- Some of the older chapters are going out of date, which is natural for a work so complete. There is so much material out there that Knuth has to make a decision on whether to revise older stuff (which he does occasionally) or to write about subjects which don't have a major unifying work yet (ie: Constraint Programming has some textbooks here and there, but most of its ideas are only in academic journals, and haven't really been unified into a singular work yet IMO. Even the textbooks on the subjects are mostly introductions + references to papers) And sometimes, Knuth gets lucky. Knuth's Book3 "Searching and Sorting" includes a HUGE table of sorting methods applied to tape drives. But today's RAM is now faster sequentially rather than random-access. So Knuth's calculations on Tape-Drive sorts actually applies to modern DDR4 RAM better than any other treatment on the subject. No one else calculated the cost of "internal movements" (aka: cache on modern systems, but it was RAM on older computers) + "external movements" (which was Tape Drives in Knuth TAOCP / Book 3, but is really DDR4 RAM on today's machines). So yeah, Book 3 is out of date and focuses a huge amount of time on external sorting methods. But... it just so happens that if you know a bit about the sequential nature of modern DDR4 RAM, it is actually super-relevant to today's computers.
- taeric 8y ago
  That doesn't sound like it is different, so much as just more complete. His analysis of permutations in order to analyze runtimes is, as you say, truly a wonder. This doesn't feel different from everyone else's idea, though. Unless you just mean in the general complexity analysis, where most of us are basically taught to stop at the highest order terms. It is interesting, because Knuth seems credited with pushing Big-O analysis, but he never stopped at the highest term when analyzing an algorithm. Far as I can tell, he never has. He has done this to compare some algorithms, but even then he has always been empirical for actually comparing things. Treating the Big-O as a hypothesis to test, if anything.
svat 8y ago
Oh sorry, to be clear, by "his idea of it" I meant "the way he thinks about it [recursion]". What's different is that when most people learn programming, they pick up the idea that iterative structures (loops etc) are simple, and recursion is something more "advanced", harder to understand. Knuth thinks that recursion is the simpler thing (what comes to humans/children naturally), and the mark of a better programmer is being able to translate recursion into iterative structures. This seems to tie in with his attitude towards programming in general: while in the zeitgeist the idea is that a good program builds better abstractions until the structure of the program reflects human thought, Knuth seems to think that a good programmer is one who starts with a human-level description of the solution and carefully refines it until it translates into a good set of instructions (in machine code). (There's no contradiction, but the point of view seems different from the usual.) He briefly mentions something related in his Structured Programming with Go To Statements (1974) https://pic.plover.com/knuth-GOTO.pdf#page=21 https://pic.plover.com/knuth-GOTO.pdf#page=21 > I have always felt that the transformation from recursion to iteration is one of the most fundamental concepts of computer science, and that a student should learn it at about the time he is studying data structures. This topic is the subject of Chapter 8 in my multivolume work; but it's only by accident that recursion wasn't Chapter 3, since it conceptually belongs very early in the table of contents.
- taeric 8y ago
  I think some of this is likely to be a product of the times. The vast majority of early programming languages were not friendly to recursion. It wasn't at all uncommon for functions not to be reentrant, and to rely on self manipulation to set the return stack, if I recall. Even today, for many "systems level" programs, you have to take extreme care around recursion, since you are likely to blow the stack limits. (That is, you can't just use recursion freely, but instead have to prove the maximum depth that you will trigger it.) That is to say, I don't see what makes this different than how most others view recursion. If you can afford to do it, then you should do so. If you can't, then you should be ready for a lot of his other tricks. (Threaded trees being my personal favorite, at the moment. DFS with no stacks? Crazy talk! :) )
  - 8y ago