Recent News

[click here to zip down to the schedule of public lectures]

Happy MMXX to all!

I celebrated my 82nd birthday this year by watching a marvelous video of the Czech première of my multimedia composition Fantasia Apocalyptica.

A happy π birthday

Johan de Ruiter sent me a great puzzle for my birthday this year!

However, a sad word ladder

VIRUS - VIRES - FIRES - FIRER - FIVER - FEVER
(fortunately my family and I are still healthy)

Oral histories

Since that was my 10001st birthday (in base three), I'm still operating a little bit in history mode. People have periodically asked me to record some memories of past events --- I guess because I've been fortunate enough to live at some pretty exciting times, computersciencewise. These after-the-fact recollections aren't really as reliable as contemporary records; but they do at least show what I think I remember. And the stories are interesting, because they involve lots of other people.

So, before these instances of oral history themselves begin to fade from my memory, I've decided to record some links to several that I still know about:

Interview by Philip L Frana at the Charles Babbage Institute, November 2001
transcript of OH 332
audio file (2:00:33)
Interviews commissioned by Peoples Archive, taped in March 2006
playlist for 97 videos (about 2--8 minutes each)
Interview by Ed Feigenbaum at the Computer History Museum, March 2007
Part 1 (3:07:25) Part 2 (4:02:46)
(transcript)
Interview by Marc Pachter, filmed by Peter Badge, commissioned by the Heidelberg Laureate Forum, November 2016
video (57:02)
Interview by Susan Schofield for the Stanford Historical Society, May 2018
(audio files, 2:20:30 and 2:14:25; transcript)
Interview by David Brock and Hansen Hsu about the computer programs that I wrote during the 1950s, July 2018
video (1:30:0)
(texts of the actual programs)
Wide-ranging interview filmed in my office at home by Lex Fridman, March 2019
video (1:45:55); audio podcast
And a podcast in ACM's new "ByteCast" series (interviewed by Rashmi Mohan on 12 March 2020)
audio podcast (28 min) and transcript
Most recently, Susan D'Agostino prepared a profile that features story telling:
Quanta magazine (16 April 2020)

Some extended interviews, not available online, have also been published in books, notably in Chapters 7--17 of Companion to the Papers of Donald Knuth (conversations with Dikran Karagueuzian in the summer of 1996), and in two books by Edgar G. Daylight, The Essential Knuth (2013), Algorithmic Barriers Falling (2014). Also, if you want to see older stuff, a good list of “historic” interviews has been compiled by volunteers at the TUG website.

Progress on Volume 4B

The fourth volume of The Art of Computer Programming deals with Combinatorial Algorithms, the area of computer science where good techniques have the most dramatic effects. (I love it the most, because one good idea can often make a program run a million times faster.) It's a huge, fascinating subject, and I published Part 1 (Volume 4A, 883 pages, now in its fourteenth printing) in 2011.

Two-thirds of Part 2 (Volume 4B) are now available in preliminary paperback form as Volume 4, Fascicle 5 (v4f5): “Mathematical Preliminaries Redux; Introduction to Backtracking; Dancing Links”; and Volume 4, Fascicle 6 (v4f6): “Satisfiability”. Here are excerpts from the hype on the back cover of v4f5 (382 pages):

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 firstfruits 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.

The utility of this approach is illustrated by showing how it resolves and extends a wide variety of fascinating puzzles, old and new. Puzzles provide a great vehicle for understanding basic combinatorial methods and fundamental notions of symmetry. The emphasis here is on how to create new puzzles, rather than how to solve them. A significant number of leading computer scientists and mathematicians have chosen their careers after being inspired by such intellectual challenges. More than 650 exercises are provided, arranged carefully for self-instruction, together with detailed answers---in fact, sometimes also with answers to the answers.

And here is the corresponding hype on the back cover of v4f6 (310 pages, to appear soon in its third printing):

This fascicle, brimming with lively examples, introduces and surveys “Satisfiability,” one of the most fundamental problems in all of computer science: Given a Boolean function, can its variables be set to at least one pattern of 0s and 1 that will make the function true?

Satisfiability is far from an abstract exercise in understanding formal systems. Revolutionary methods for solving such problems emerged at the beginning of the twenty-first century, and they've led to game-changing applications in industry. These so-called “SAT solvers” can now routinely find solutions to practical problems that involve millions of variables and were thought until very recently to be hopelessly difficult.

Fascicle 6 presents full details of seven different SAT solvers, ranging from simple algorithms suitable for small problems to state-of-the-art algorithms of industrial strength. Many other significant topics also arise in the course of the discussion, such as 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 many of the new 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,” where N is one of the following exercises in Volume 4 Fascicle 5:

Furthermore, I fondly hope that diligent readers will write and say “Dear Don, I have read exercise N and its answer very carefully, and I believe that it is 100% correct,” where N is one of the following exercises in Volume 4 Fascicle 6:

Please don't be alarmed by the highly technical nature of these examples; more than 250 of the other exercises are completely non-scary, indeed quite elementary. But 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.

Remember that you don't have to work the exercise first. You're allowed to peek at the answer; in fact, you're even encouraged to do so. Please send success reports to the usual address for bug reports (taocp@cs.stanford.edu). Thanks in advance!

By the way, if you want to receive a reward check for discovering an error in TAOCP, your best strategy may well be to scrutinize the answers to the exercises that are listed above.

Meanwhile I continue to work on the final third of Volume 4B, which already has many exciting topics of its own. Those sections are still in very preliminary form, but courageous readers who have nothing better to do might dare to take a peek at the comparatively raw copy in these “prefascicles.” One can look, for instance, at Pre-Fascicle 8a (Hamiltonian Paths and Cycles); Pre-Fascicle 9b (A Potpourri of Puzzles). Thanks to Tom Rokicki, these PostScript files are now searchable!

Something for music fans

Check out these videos, just posted by Jan Overduin: Playlist

Public lectures in 2020

Although I must stay home most of the time and work on yet more books that I've promised to complete, I do occasionally get into speaking mode. Here's a current schedule of events that have been planned for this year so far:

Friday, January 31 at 10:25am in the Clarke Center Auditorium
“Stratified importance sampling” (a talk for Persi Diaconis's 75th birthday conference, open to the public) (view slides) (view current state of fasc9c) (view a related PDF)
Tuesday, September 22 (online, part of the Virtual Heidelberg Laureate Forum)
Dialogue: Robert Endre Tarjan/Donald Ervin Knuth (watch video, 58 minutes)
Friday, October 9 (online, Virtual Homecoming sponsored by the Alumni Association of Case Western Reserve University)
accepting an award at 60th class reunion, reminiscing about college days (watch video) (my part starts at time 38:00)
sometime in October? (no, this has been postponed)
Participating in a performance or two of Fantasia Apocalyptica at First Lutheran Church, Palo Alto, as part of their centennial celebration
sometime in early December? (no, there will be no Christmas lecture this year, sorry)
A Computer Musing (the 26th annual Christmas lecture)

Click here for the “recent news” that was current at the end of 2019, if you're interested in old news as well as new news.

Don Knuth's home page

Valid HTML 4.01 Transitional