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.”
of this story at Slashdot.
Source:: Slashdot