|Donald Knuth At 80 Still Improving TAOCP|
|Written by Kay Ewbank|
|Wednesday, 24 January 2018|
Donald Knuth, author of the classic The Art of Computer Programming, has celebrated his 80th birthday and is still working on improving his monumental work. He's also still hoping people will check out the hard exercises of TAOCP to make sure they're correct.
One of the all time greats of computer science, Donald Knuth, has turned 80 The event was marked by a celebration called Knuth80, held in the city of Piteå in northern Sweden. The event highlighted Knuth's work in both computer science and music, with a scientific symposium titled ”Knuth80: Algorithms, Combinatorics, and Information”. The symposium included contributions from some big names in computer science.
Bob Sedgewick, William O. Baker Professor of Computer Science at Princeton University, gave a talk on Cardinality Estimation; Tim Roughgarden Professor in the Computer Science at Stanford University spoke on ”Don, Stable Matchings, and Matroids. Wojtek Szpankowski, Saul Rosen Professor of Computer Science and Electrical and Computer Engineering at Purdue University gave a session on ”Analytic Information Theory: From Shannon to Knuth and Back”.
The computer science sessions were followed by the world premiere of Fantasia Apocalyptica, a multimedia work for pipe organ and video written by Knuth.
Knuth is still hard at work at Stanford, and continues to work on The Art of Computer Programming. He's going back through the book adding or refining areas where, as he says on his website, he adds things he didn't know about in the 1960s.
One section of TAOCP has recently been published in preliminary paperback form as Volume 4, Fascicle 6: “Satisfiability”. The volume includes details of seven different SAT solvers, ranging from simple algorithms suitable for small problems to state-of-the-art algorithms of industrial strength. Other topics include bounded model checking, the theory of traces, Las Vegas algorithms, phase changes in random processes, the efficient encoding of problems into conjunctive normal form, and the exploitation of global and local symmetries. More than 500 exercises are provided, arranged carefully for self-instruction, together with detailed answers.
"I worked particularly hard while preparing some of those exercises, attempting to improve on expositions that I found in the literature; and in several noteworthy cases, nobody has yet pointed out any errors. It would be nice to believe that I actually got the details right in my first attempt. But that seems unlikely, because I had hundreds of chances to make mistakes. So I fear that the most probable hypothesis is that nobody has been sufficiently motivated to check these things out carefully as yet.
I still cling to a belief that these details are extremely instructive, and I'm uncomfortable with the prospect of printing a hardcopy edition with so many exercises unvetted. Thus I would like to enter here a plea for some readers to tell me explicitly, ``Dear Don, I have read exercise N and its answer very carefully, and I believe that it is 100% correct.''
He then gives a list of exercises in Volume 4 Fascicle 6, and says that while many of the other exercises in the book are "completely non-scary", indeed quite elementary,
"of course I do want to go into high-level details also, for the benefit of advanced readers; and those darker corners of my books are naturally the most difficult to get right. Hence this plea for help."
So there you go. You could earn the gratitude of a computing legend.
or email your comment to: firstname.lastname@example.org
|Last Updated ( Wednesday, 24 January 2018 )|