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.
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 afterthefact 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 28 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 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)

Wideranging interview filmed in my office at home by Lex Fridman, March 2019
 video (1:45:55);
audio podcast
Some extended interviews, not available online, have also been published
in books, notably in Chapters 717 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).
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 thirteenth printing)
in 2011.
Twothirds 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 27page 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 decadesold
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 selfinstruction, together with
detailed answersin 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 twentyfirst century, and they've led to gamechanging
applications in industry. These socalled “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 stateoftheart 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
selfinstruction, 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:
 MPR24: Find the median number of heads when a biased coin is tossed
 MPR2829: Prove basic inequalities for sums of independent binary random variables
 MPR50: Prove that Ross's conditional expectation inequality is sharper than the second moment inequality
 MPR59: Derive the four functions theorem
 MPR61: Show that independent binary random variables satisfy the FKG inequality
 MPR88: Find the exact probability that at most 2/3 of the balls in Polya's urn are red
 MPR99: Generalize the Karp–Upfal–Wigderson bound on expected loop iterations
 MPR103104: Study ternary “coupling from the past”
 MPR114: Prove Alon's “combinatorial nullstellensatz”
 MPR121122: Study the Kullback–Leibler divergence of one random variable from another
 MPR127: Analyze the XOR of independent sparse binary vectors
 MPR130131: Derive paradoxical facts about the Cauchy distribution (which has “heavy tails”)
 7.2.213: Construct an explicit solution to the n queens problem, for all n>3
 7.2.23738: Implement and analyze Eastman's algorithm for commafree codes
 7.2.27172: Investigate Don Woods's famous selfreferential list of Twenty Questions
 7.2.273: Solve a clueless anacrostic puzzle
 7.2.27576: Devise an algorithm that lists every nelement connected subset of a given graph
 7.2.279: Analyze the sounds that are playable on the pipe organ in my home
 7.2.2.12: Show that the dancing links mechanism is correct when firstinfirstout as well as lastinfirstout
 7.2.2.12930: Characterize all search trees that can arise with Algorithm X
 7.2.2.153: Find every 4clue instance of shidoku (4×4 sudoku)
 7.2.2.155: Determine the fewest clues needed to force highly symmetric sudoku solutions
 7.2.2.166: Construct sudoku puzzles by placing nine given cards in a 3×3 array
 7.2.2.169: Investigate gerrymandering in Bitland
 7.2.2.191: Find the longest right word stairs in WORDS(1000) and the longest left word stairs in WORDS(500)
 7.2.2.1103: List all of the 12tone rows with the allinterval property, and study their symmetries
 7.2.2.1104: Construct infinitely many “perfect” ntone rows
 7.2.2.1109: Encode any given “wordcross puzzle” as an XCC problem
 7.2.2.1115: Find all hypersudoku solutions that are symmetric under transposition or under 90° rotation
 7.2.2.1121: Determine which of the 92 Wang tiles in exercise 2.3.4.3–5 can actually be used when tiling the whole plane
 7.2.2.1129: Enumerate all the symmetrical solutions to MacMahon's triangletiling problem
 7.2.2.1136: Completely solve Conway's “quintominal dodecahedron” problem
 7.2.2.1147: Construct all of the “bricks” that can be made with MacMahon's 30 sixcolored cubes
 7.2.2.1151152: Arrange all of the path dominoes into a single loop
 7.2.2.1172: Find the longest snakeinthebox paths and cycles that can be made by kings, queens, rooks, bishops, or knights on a chessboard
 7.2.2.1189: Determine the asymptotic behavior of the Gould numbers
 7.2.2.1196: Analyze the running time of Algorithm X on bounded permutation problems
 7.2.2.1215: Show that exclusion of noncanonical bipairs can yield a dramatic speedup
 7.2.2.1262: Study the ZDDs for domino and diamond tilings that tend to have large “frozen” regions
 7.2.2.1303: Enumerate and pack the parallominoes (staircase polygons)
 7.2.2.1305306: Find optimum arrangements of the windmill dominoes
 7.2.2.1309: Find all ways to make a convex shape from the twelve hexiamonds
 7.2.2.1320: Find all ways to make a convex shape from the fourteen tetraboloes
 7.2.2.1323: Find all ways to make a skewed rectangle from the ten tetraskews
 7.2.2.1327: Analyze the Somap graphs
 7.2.2.1334: Build fake solutions for Somacube shapes
 7.2.2.1337: Design a puzzle that makes several kinds of “dice” from the same bent tricubes
 7.2.2.1346: Pack space optimally with small tripods
 7.2.2.1375: Determine the smallest incomparable dissections of rectangles into rectangles
 7.2.2.1386387: Classify the types of symmetry that a polyiamond, polyhex, or polycube might have
 7.2.2.1394: Prove that every futoshiki puzzle needs at least six clues
 7.2.2.1415: Make an exhaustive study of homogenous 5×5 slitherlink
 7.2.2.1424: Make an exhaustive study of 6×6 masyu
 7.2.2.1426: Design a masyu puzzle whose clues are the pixels of ‘π.’
 7.2.2.1432: Find the most interesting 3×3 kakuro puzzles
 7.2.2.1442: Enumerate all hitori covers of small grids
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:
 7.2.2.26: Verify a certain (previously unpublished) lower bound on van der Waerden numbers
W(3,k)
 7.2.2.257: Find a 6gate way to match a certain 20variable Boolean function at 32 given points
 7.2.2.2165: Devise an algorithm to compute the largest positive autarky of given clauses
 7.2.2.2177: Enumerate independent sets of flower snark edges
 7.2.2.2212: Prove that partial latin square construction is NPcomplete
 7.2.2.2237: Establish the pigeonhole principle efficiently using extended resolution
 7.2.2.2245: Prove that Tseytin's unsatisfiable graphparity clauses make CDCL solvers take exponential time
 7.2.2.2246: But those clauses can be refuted efficiently with (clairvoyant) extended resolution
 7.2.2.2282: Find a linear certificate of unsatisfiability for the flower snark clauses
 7.2.2.2306308: Study the reluctant doubling strategy of Luby, Sinclair, and Zuckerman
 7.2.2.2318: Find the best possible Local Lemma for dregular dependency graphs with equal weights
 7.2.2.2322: Show that randomwalk methods cannot always find solutions of locally feasible problems using independent random variables
 7.2.2.2335: Express the Möbius series of a cocomparability graph as a determinant
 7.2.2.2339: Relate generating functions for traces to generating functions for pyramids
 7.2.2.2347: Find the best possible Local Lemma for a given chordal graph with arbitrary weights
 7.2.2.2356: Prove the Clique Local Lemma
 7.2.2.2363: Study the stable partial assignments of a satisfiability problem
 7.2.2.2374: Design efficient data structures for the preprocessing of SAT clauses
 7.2.2.2386: Prove that certain CDCL solvers will efficiently refute any clauses that have a short certificate of unsatisfiability
 7.2.2.2428: Show that Boolean functions don't always have forcing representations of polynomial size
 7.2.2.2442444: Study the UC and PC hierarchy of progressively harder sets of clauses
 7.2.2.2518: Reduce 3SAT to testing the permanent of a {1,0,1,2} matrix for zero
Please don't be alarmed by the highly technical nature of these examples;
more than 250 of the other exercises are completely nonscary,
indeed quite elementary. But of course I do want to go into highlevel 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
PreFascicle 8a (Hamiltonian Paths and Cycles);
PreFascicle 9b (A Potpourri of Puzzles).
Thanks to Tom Rokicki, these PostScript files are now searchable!
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:

Saturday, February 1 at 10:25am in Geology Corner Room105

“Stratified importance sampling” (a talk for
Persi Diaconis's 75th birthday conference, open to the public)

sometime in October(?)

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