Recent News
[click here to zip down to the
schedule of public events]
Happy $1^6 3^4 5^2 7^0$
a curious progression of factors that can also be premultiplied by $(-1)^8$
and written $\prod_{k=0}^4 (2k-1)^{8-2k}$.
(Others write $\bigl(\sum_{k=0}^9 k\bigr)^2$, or $\sum_{k=0}^9 k^3$.)
Some Generative AI
Oliver Manger sent me a delightful image of “dancing lynx”
for my `\W-th birthday!
The first third of Volume 4C
I recently sent to my publisher (Addison–Wesley) the camera-ready copy for
Volume 4, Fascicle 7 of
The Art of Computer Programming,
entitled “Constraint Satisfaction”. The official date scheduled for
publication of this 304-page paperback
is February 19. But copies can be ordered now, and you can get the best deal at
informIT.com. That website also has the publisher's
traditional hype about the great stuff inside.
(Or, you can see a free preview of the whole thing in compressed PostScript form:
Prefascicle f7a. The contents of that prefascicle agrees
fairly well
with the contents of the first paperback printing of Volume 4, Fascicle 7,
except for parts of the index. As usual, the prefascicle is
“frozen” and will not be maintained, while the paperback will gradually
improve with time.)
TAOCP update
The fourth volume of
The Art of Computer Programming
deals with Combinatorial Algorithms, the area of computer science
where nonobvious 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
Part 1 (Volume 4A, 883 pages, now in its twenty-fourth printing)
was published in 2011; Part 2 (Volume 4B, 714 pages, now in its
second printing) was published at the close of 2022. The
first 275 or so pages of Volume 4C will be published soon,
as announced above, together with an index.
While preparing many of the new exercises in Volumes 4B and 4C, I spent
a lot of time
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 on 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
the finer points out carefully as yet.
I still cling to a belief that such details are extremely instructive.
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 exercise numbers:
- MPR-28-29: Prove basic inequalities for sums of independent binary random variables
- MPR-50: Prove that Ross's conditional expectation inequality is sharper than the second moment inequality
- MPR-59: Derive the four functions theorem
- MPR-61: Show that independent binary random variables satisfy the FKG inequality
- MPR-99: Generalize the Karp–Upfal–Wigderson bound on expected loop iterations
- MPR-103-104: Study ternary “coupling from the past”
- MPR-121-122: Study the Kullback–Leibler divergence of one random variable from another
- MPR-127: Analyze the XOR of independent sparse binary vectors
- MPR-130 and 131: Derive paradoxical facts about the Cauchy distribution (which has “heavy tails”)
- 7.2.2-79: Analyze the sounds that are playable on the pipe organ in my home
- 7.2.2.1-29 and 30: Characterize all search trees that can arise with Algorithm X
- 7.2.2.1-55: Determine the fewest clues needed to force highly symmetric sudoku solutions
- 7.2.2.1-104: Construct infinitely many “perfect” n-tone rows
- 7.2.2.1-121: 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.1-129: Enumerate all the symmetrical solutions to MacMahon's triangle-tiling problem
- 7.2.2.1-147: Construct all of the “bricks” that can be made with MacMahon's 30 six-colored cubes
- 7.2.2.1-151 and 152: Arrange all of the path dominoes into a single loop
- 7.2.2.1-196: Analyze the running time of Algorithm X on bounded permutation problems
- 7.2.2.1-262: Study the ZDDs for domino and diamond tilings that tend to have large “frozen” regions
- 7.2.2.1-305 and 306: Find optimum arrangements of the windmill dominoes
- 7.2.2.1-320: Find all ways to make a convex shape from the fourteen tetraboloes
- 7.2.2.1-323: Find all ways to make a skewed rectangle from the ten tetraskews
- 7.2.2.1-334: Build fake solutions for Soma-cube shapes
- 7.2.2.1-337: Design a puzzle that makes several kinds of “dice” from the same bent tricubes
- 7.2.2.1-346: Pack space optimally with small tripods
- 7.2.2.1-375: Determine the smallest incomparable dissections of rectangles into rectangles
- 7.2.2.1-387: Classify the types of symmetry that a polycube might have
- 7.2.2.1-432: Find the most interesting 3×3 kakuro puzzles
- 7.2.2.1-442: Enumerate all hitori covers of small grids
- 7.2.2.2-6: Verify a certain (previously unpublished) lower bound on van der Waerden numbers
W(3,k)
- 7.2.2.2-57: Find a 6-gate way to match a certain 20-variable Boolean function at 32 given points
- 7.2.2.2-165: Devise an algorithm to compute the largest positive autarky of given clauses
- 7.2.2.2-212: Prove that partial latin square construction is NP-complete
- 7.2.2.2-282: Find a linear certificate of unsatisfiability for the flower snark clauses
- 7.2.2.2-306 thru 308: Study the reluctant doubling strategy of Luby, Sinclair, and Zuckerman
- 7.2.2.2-318: Find the best possible Local Lemma for d-regular dependency graphs with equal weights
- 7.2.2.2-322: Show that random-walk methods cannot always find solutions of locally feasible problems using independent random variables
- 7.2.2.2-335: Express the Möbius series of a cocomparability graph as a determinant
- 7.2.2.2-339: Relate generating functions for traces to generating functions for pyramids
- 7.2.2.2-347: Find the best possible Local Lemma for a given chordal graph with arbitrary weights
- 7.2.2.2-356: Prove the Clique Local Lemma
- 7.2.2.2-363: Study the stable partial assignments of a satisfiability problem
- 7.2.2.2-442 thru 444: Study the UC and PC hierarchy of progressively harder sets of clauses
- 7.2.2.2-518: Reduce 3SAT to testing the permanent of a {-1,0,1,2} matrix for zero
- 7.2.2.3-12: Analyze the energy of one-dimensional Ising configurations
- 7.2.2.3-25: Count the extreme (p/q)-strings of length qm
- 7.2.2.3-33: Enumerate up-up-or-down-down permutations
- 7.2.2.3-50 and 55: Analyze boundary cycles of Huffman–Clowes networks
- 7.2.2.3-104: Show that free trees have superexponentially many graceful labelings
- 7.2.2.3-117: Use palindromials to count α-graceful labelings of complete bipartite graphs
- 7.2.2.3-137: Characterize graceful tournaments
- 7.2.2.3-159: Study vertex labels that make all shortest distances easy to compute
- 7.2.2.3-213: Explore Matula's algorithm for subtree isomorphism
- 7.2.2.3-306: Analyze Gaschnig and Dechter's backmarking algorithm
- 7.2.2.3-480: Design Constraint Satisfaction Automata for various global constraints
- 7.2.2.3-483 and 484: Study canonical solutions to the n queens problem
(If you're depressed by current world news, you might find some solace by immersing
yourself in a bit of research into eternally beautiful patterns.)
Please don't be alarmed by the highly technical nature of these examples;
more than 750 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.
Preliminary sketches of material that will be in later parts of Volume 4C
have also been drafted, and 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, those PostScript files are now searchable!
Oral histories
I seem to get older every day, and people keep asking me to
reminisce about the glorious days of yore. If you're interested
in checking out some of those videos and other archives, take a
look at my
news page for 2020, which I've updated
with a few items captured after that year.
Public lectures in 2025
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.
-
Sometime in December
- The 29th annual
Christmas Lecture
Click here for the “recent news”
that was current at the end of 2024,
if you're interested in old news as well as new news.