81-Year-Old Donald Knuth Releases New TAOCP Book, Ready to Write Hexadecimal Reward Checks (stanford.edu) 39
In 1962, 24-year-old Donald Knuth began writing The Art of Computer Programming -- and 57 years later, he's still working on it.
But he's finally released The Art of Computer Programming, Volume 4, Fascicle 5: Mathematical Preliminaries Redux; Introduction to Backtracking; Dancing Links.
An anonymous reader writes: On his personal site at Stanford, 81-year-old Donald Knuth promised this newly-released section "will feature more than 650 exercises and their answers, designed for self-study," and he shared an excerpt from "the hype on its back cover":
This fascicle, brimming with lively examples, forms the first third of what will eventually become hardcover Volume 4B. It begins with a 27-page tutorial on the major advances in probabilistic methods that have been made during the past 50 years, since those theories are the key to so many modern algorithms. Then it introduces the fundamental principles of efficient backtrack programming, a family of techniques that have been a mainstay of combinatorial computing since the beginning.
This introductory material is followed by an extensive exploration of important data structures whose links perform delightful dances. That section unifies a vast number of combinatorial algorithms by showing that they are special cases of the general XCC problem --- "exact covering with colors." The first fruits of the author's decades-old experiments with XCC solving are presented here for the first time, with dozens of applications to a dazzling array of questions that arise in amazingly diverse contexts...
Knuth is still offering his famous hexadecimal reward checks (now referred to as "reward certificates," since they're drawn on the imaginary Bank of San Serriffe) to any reader who finds a technical (or typographical) error. "Of course those exercises, like those in Fascicle 6, include many cutting-edge topics that weren't easy for me to boil down into their essentials. So again I'm hoping to receive 'Dear Don' letters...either confirming that at least somebody besides me believes that I did my job properly, or pointing out what I should really have said...."
And to make it easier he's even shared a list of the exercises where he's still "seeking help and reassurance" about the correctness of his answers. "Let me reiterate that you don't have to work the exericse first. You're allowed to peek at the answer; indeed, you're encouraged to do so, in order to verify that the answer is 100% correct."
An anonymous reader writes: On his personal site at Stanford, 81-year-old Donald Knuth promised this newly-released section "will feature more than 650 exercises and their answers, designed for self-study," and he shared an excerpt from "the hype on its back cover":
This fascicle, brimming with lively examples, forms the first third of what will eventually become hardcover Volume 4B. It begins with a 27-page tutorial on the major advances in probabilistic methods that have been made during the past 50 years, since those theories are the key to so many modern algorithms. Then it introduces the fundamental principles of efficient backtrack programming, a family of techniques that have been a mainstay of combinatorial computing since the beginning.
This introductory material is followed by an extensive exploration of important data structures whose links perform delightful dances. That section unifies a vast number of combinatorial algorithms by showing that they are special cases of the general XCC problem --- "exact covering with colors." The first fruits of the author's decades-old experiments with XCC solving are presented here for the first time, with dozens of applications to a dazzling array of questions that arise in amazingly diverse contexts...
Knuth is still offering his famous hexadecimal reward checks (now referred to as "reward certificates," since they're drawn on the imaginary Bank of San Serriffe) to any reader who finds a technical (or typographical) error. "Of course those exercises, like those in Fascicle 6, include many cutting-edge topics that weren't easy for me to boil down into their essentials. So again I'm hoping to receive 'Dear Don' letters...either confirming that at least somebody besides me believes that I did my job properly, or pointing out what I should really have said...."
And to make it easier he's even shared a list of the exercises where he's still "seeking help and reassurance" about the correctness of his answers. "Let me reiterate that you don't have to work the exericse first. You're allowed to peek at the answer; indeed, you're encouraged to do so, in order to verify that the answer is 100% correct."
Guiseppe Peano would like to have a word with you. (Score:1)
He's got some axioms to show you. :)
Re: (Score:2)
Alright, it took me 30 damn years ... (Score:5, Funny)
...from the first fortune seen on a command line, to now... to realize that "TAO" stands for "the art of".
My life is finally complete. ;)
Re:Alright, it took me 30 damn years ... (Score:4, Funny)
My life won't be complete until he publishes volume 7!
Re:Alright, it took me 30 damn years ... (Score:4, Funny)
Rumor is he and George R. R. Martin are collaborating on that 7th book.
Re: (Score:2)
Crap! So it does! I'm going to crawl back into my cave in shame.
Just remember... (Score:5, Funny)
Obligatory Dr.Fun cartoon (Score:5, Funny)
Re: (Score:1, Troll)
Having watched my dad degrade from a normal human being to a 95 year old frail wreck of a person that is hallucinating pigeons in the living room and thinks they're real, I tend to agree.
Set some age after which anyone can have elective euthanasia. I certainly don't want to live to 95 with the cognitive decline and physical decay.
There's nothing "golden" about the golden years, they fucking suck, and after a life of having all your vitality sucked out of you by your boss, your work, your life, the never-end
LEARN GAME (Score:3, Insightful)
PS: Look to your Dad's example: He's 95 years old, whereas you're not even 50, ergo he was still swinging the D in his late 40s [and that was well before Viagra or Cialis].
Use your Dad as your inspiration: Learn Game & go forth with your mighty sword & slay teh p00ntang.
Re: (Score:1)
You sir nailed the description of life. And was labeled Troll for it. I guess truth is not popular.
Re: (Score:2)
Re: (Score:2)
Re: (Score:1)
I'm sorry for your father's condition and the stress it puts on you.
On the other hand, there's the 102 year old karate master mentioned in this article, still teaching. https://www.cnbc.com/2019/05/2... [cnbc.com]
Aging is a tremendously individual thing.
I hit 50 next month. I'm ju
I for one appreciate it (Score:3, Informative)
Back in the 60s I relied on his books in many situations. There were no abundant repositories to download things of value and this was the next best thing.
Actually it was the better thing in that you had to have some understanding of his work to use it. Most modules today get downloaded with 50+ dependencies and the user generally has no clue.
Now having said all that, could someone teach Mr. Knuth the Art of Web Page Design? I mean that page ...
I like his page (Score:5, Informative)
Re: (Score:3)
And remember that he's written a book on Digital Typography [acm.org], and after being disappointed with the typesetting of the second volume of TAOCP, wrote TeX [wikipedia.org].
Re: (Score:2)
Yeah I'm aware of that but geez ... time to move on.
HTML/CSS has come a long way in 30 years and the present versions (supported by all major browsers) can arguably be used to produce results at least as good as TeX. If he was that concerned about the hardcopy quality you would think he would have the same level of interest in his digital copy. I am sure he has grad students in reach that would do it for him for $50.
Re: I like his page (Score:4, Insightful)
Re: (Score:1)
What is his page missing
A margin.
Re: (Score:2)
No, a margin is not missing. This page uses the browser's default margin, which is 8px on Firefox and Chrom(ium). The text also wraps and unwraps to fit my browser window. Thankfully, he is not among the many misguided web developers who waste my screen space with their infernally wide margins and sidebars. Some of us actually use our multitasking operating systems for multiple tasks, and do not run our browsers full-screen.
Re: I like his page (Score:1)
Precisely why Don's web page is perfect.
Use Firefox "reader" mode (the 'page' icon next to the URL on mobile) if you don't want to pan and zoom.
Simple html allows itself to be easily restyled by the client, as originally intended.
Re: (Score:3)
What annoys me about the web, an annoyance now over 25 years old, is that there is no good way to present mathematical formulas. This is particularly bizarre since HTML and the web came out of a physics lab. The thing is there was already the perfect "mark-up" for formulas available, in use, with an open source rendering engine - TeX. If Berners-Lee had only specified a "TeX" tag as a requirement for valid HTML implementations, we would not have had 25 years of "pictures of formulas" or hacks like MathJax.
Re: (Score:2)
Re: (Score:1)
Re: (Score:2)
It's been around since 1996. The downside is you have to use a browser that supports it, like Firefox.
Apparently it's one of the most requested features in Chromium [igalia.com].
The imaginary Bank of San Serriffe (Score:3)
San Serriffe [theguardian.com] was a 1977 April Fools' day spoof special report in the UK Guardian newspaper. Everything connected with San Serriffe was named after printing and typesetting terms.
At this point (Score:4, Insightful)
These are seminal works but there is no way he will finish TAOCP in the time he has left. I hope he releases a detailed bullet point outline of what he was planning to cover (and I do not mean the mere two-three bullet points we have seen mentioned publicly) so there could be a dedicated group or maybe many groups who could try to finish the work when he is gone. Who knows, they may be fast enough and good enough to get his blessing for some chapters while he is still alive. Sigh.
Re: (Score:2)
Re: (Score:3)
He is almost done with volume 4B with 4C and 4D still to go before volume 4 is complete. Volume 4 in general seems pretty mapped out even if still substantially unfinished.
Knuth has stated plans for 7 volumes total. And he is way above 80. And the last three volumes are not mapped out in as much detail. And the tentative release date for volume 5 is 2025. And these tentative deadlines have already slipped more times than Elon Musk's promises. I respect everything about the man but it really does not look li
Re: (Score:2)
Decades of experience + decades of interaction with colleagues and students = hundreds or thousands of years of learning and experience to draw from. But we could probably off shore it and get it done cheaper.... /s
dancing links digressimento (Score:5, Interesting)
I'm sure I've posted this before. Some years ago I downloaded a dancing link implementation for Sudoku, made a very minor tweak to the heuristic used to order the available choices, fired it up on what the Internet promised me was the hardest Sudoku of all time, and then watching in horror and amazement as it solved the entire problem without backtracking once. Not a single time. At one point there was a three-way guess, where it got lucky. At another point there was a two-way guess, and it got lucky again. Everything else was forced.
Perhaps my clever heuristic helped it make the "lucky" guesses. I don't know. I didn't poke around with it much longer.
The world's hardest Sudoku is hard in this dimension: none of the "logical" inferences that we normally apply to chose a necessarily correct move could be applied without regressing into a rat's nest of associated inferences, until there's more working parts involved than a normal human brain can handle (excepting any Sudoku rainmen out there).
Note that a "move" for the purposes of this discussion is the elimination of a possible solution pattern. A primitive move is to eliminate a single digit for a single cell. There are 9x9*9=729 primitive moves available on an empty Sudoku board. When you place an actual digit into an an actual cell, you are eliminating that digit elsewhere in what amounts to 4*3+8=20 primitive moves (many of which will already be known).
You can also obtain partial primitive moves: if this cell is a 3, then that cell can't be a 5. These get hairy to maintain in your mind extremely rapidly.
Crucially, with the "hardest" Sudoku, the three-way guess happened first thing, right at the outset. Immediately a puzzle designed to force nothing (to keep the inference depth high), became a force everything. In loading up all of the inferential uncertainty into the very first move, it seemed to have the side effect of eliminating almost all subsequent uncertainty once you got past this initial hurdle.
It's not unusual that "extreme" exemplars in one chosen dimension are Opposite George in a nearby dimension. Like the world's "most secure" network, based on the world's strongest firewall, but with no internal host security whatsoever. Hard white crust on the outside. Yummy yolk on the inside. (If every website in the world was programmed to fall back to static HTML when JavaScript is refused down to the last byte, you might even be able to make this security model work, up to a point.)
———
I used to do the 5-star Sudokus in coffee shops sometimes. I had a set time limit of about 20 minutes. What made these puzzles 5-star is that you could proceed with the standard logical inferences up to a point, but then you had to combine two of the standard inferences into a hybrid inference to crack the puzzle open. So the strategy was to speedily cross off all the low-hanging fruit, bring the puzzle to the choke point, find the hybrid inference, then speedily play out the implications of the the main break into a full solution.
It turn out that the essential challenge is a housekeeping challenge: while speedily crossing off all the low-hanging fruit, one must not miss a single primitive move. If you missed just one trick in the speedy prologue, you could wander around in circles for 10 minutes looking for a break that doesn't exist.
When my housekeeping was fast and accurate, I usually found the break in about a minute, and I usually made my time limit. If I muffed my housekeeping, I could struggle to finish the puzzle in twice as much time. Worst of all: erroneous housekeeping, where you actively cross something off by mistake, rendering the puzzle unsolvable under your deduced constraints.
Generally I tried to work within the logical system, rather than running down forcing loops. It was often possible to see that a certain assumption would force six cells in rapid succession, either leading to a quick contradiction, or giving you high confidence that your guess ha
Re: (Score:2)