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

Save the date! The long-awaited inaugural performances of the multimedia composition Fantasia Apocalyptica in my home church will take place on Friday, October 20, and Saturday, October 21, at 7:30pm. (These concerts had been planned to be the climax of the church's centennial celebrations in 2020, but they had to be postponed because of you-know-what.)

The organist will be Jin Kyung Lim, who played the Fantasia at its California premiere in San Francisco in 2021. Years ago, as I was writing the music, she also gave the first-ever public performance of a “beta test” version, as part of a recital on the Murray Harris organ at Stanford's Memorial Church (04 November 2015).

The October concerts will be the culmination of a project that's been part of my life for 60 years! They will take place at First Lutheran Church in Palo Alto, and further details can be found on that website.

(On the five Sunday mornings preceding the concerts, I'll be giving informal impromptu introductions to the piece. See the schedule below.)

This 10×10 reentrant knight's tour,
found with the help of Peter Weigel,
has the amazing property that
a queen at position 85 attacks all of the prime numbers (shown in green).
Furthermore, all of the odd numbers attacked by that queen are
prime—except the ‘1’, which some people think is prime.
Furthermore, the exact date of my birth just happens to be present, along with 2023.

I'm gettin' kinda old: now nearly one-third of a byte (256÷3). My age is a beautiful binary palindrome, also the product of two Fermat primes!

Germán González-Morris sent me a delicious Pi Day treat, which you can find in the amendment to page 411 on page 5 of the Errata for Volume 4B of The Art of Computer Programming.

My dear friend Jan Overduin, organist and teacher extraordinaire, passed away early in May. I've prepared a webpage in his memory, highlighting experiences that we shared.

The January issue of an excellent mathematics magazine, Bhāvanā, begins with an interview in which two of its editors asked me 40 wide-ranging questions. I decided to answer each of them by using exactly 280 ASCII characters; so, if want to check this, you can look here. (These are the answers without the questions.)

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 twenty-second printing) in 2011.

Ta da: My publishers told me at the end of September 2022 that Part 2 (732 pages) had just arrived at their warehouse. Shipments began in October and the book was already in its second printing as of November 2022.

Full details, including a dozen reviews from people who have looked closely at previews of the content, appear on the publisher's website.

Preliminary versions of most of this material were published in 2015 and 2019 as Volume 4, Fascicle 6 and Volume 4, Fascicle 5. Errata to those paperbacks, as well as to all the hardcover volumes, can be found on the TAOCP home page.

I've spent considerable time, 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 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 exercises:

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

Please don't be alarmed by the highly technical nature of these examples;
more than 500 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 Part 3 (Volume 4C), 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, those PostScript files are now searchable!

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.

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.

- Wednesday, March 1, 1pm Central Time (GMT 6:00)
- All Questions Answered (via Zoom), as part of the “Seminar with IT Pioneers and Leaders” program hosted by the Department of Computer Science at Tecnológico de Monterrey; the lecture will be livestreamed, and you can register at their website!
- Sunday, September 17, 9am to 9:45am, at First Lutheran Church in Palo Alto
- An informal introduction to Fantasia Apocalyptica, part 1
- Sunday, September 24 9am to 9:45am, at First Lutheran Church in Palo Alto
- An informal introduction to Fantasia Apocalyptica, part 2; independent of part 1
- Sunday, October 1, 9am to 9:45am, at First Lutheran Church in Palo Alto
- An informal introduction to Fantasia Apocalyptica, part 3; independent of parts 1 and 2
- Sunday, October 8, 9am to 9:45am, at First Lutheran Church in Palo Alto
- An informal introduction to Fantasia Apocalyptica, part 4; independent of parts 1, 2, and 3
- Sunday, October 15, 9am to 9:45am, at First Lutheran Church in Palo Alto
- An informal introduction to Fantasia Apocalyptica, part 5; independent of parts 1, 2, 3, and 4
- Friday, October 20, and Saturday, October 21, 7:30pm, at First Lutheran Church in Palo Alto (600 Homer Avenue at Webster Street, Palo Alto)
- Fantasia Apocalyptica will be performed by organist Jin Kyung Lim, with video accompaniment by Heather Paisar, Donald Knuth, and Sharmon Hilfinger (click here for the program)
- Wednesday, December 6 at 5:30pm PST, in the NVIDIA Auditorium (lower level, Huang Engineering Center)
- A Computer Musing entitled “Dancing Cells” (the 27th annual Christmas lecture, not counting pandemic years) (watch the video)
- Saturday, January 6, 2024, 4pm to 5pm, in San Francisco (Moscone Center Room 024)
- An invited talk, “Recreational Computer Science,” at the Joint Mathematics Meetings [JMM 2024]

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