As Donald Knuth has just published Volume 4, Fascicle 7 of The Art of Computer Programming (TAOCP), on constraint satisfaction, I would like to provide more information about the errors I discovered in 2019 in other volumes, for which I received two Knuth reward checks. To date, my account balance on his “bank”, the Bank of San Serriffe, is still 0x2.40 (hexadecimal dollars). 0x2.00 for two errors, and 0x0.40 for two “valuable suggestions.”

His response to my errors reports was faster than I expected: I emailed him four times to report different errors from December 18, 2019, to January 1, 2020 (although Knuth does not typically use email, there is an email address reserved for reporting TAOCP errors, which his assistant prints). He updated the errata on January 1 and responded with a postal mail on January 9, 2020.

The envelope contained my printed emails with his handwritten notes in pencil and two checks (dated December 24, 2019, and January 1, 2020).

Some reward recipients have shared their letters online, here and there; however, I will paraphrase Knuth’s responses instead of reproducing them verbatim, as they are part of private correspondence (this can change in the future—per express authorization, for instance—; in that case, I will update this article to share a full scan of the letters). A notable exception is an excerpt of a letter containing generic information and a good anecdote: Knuth wished me a “Joyeux Noël” (French for “Happy Christmas”) because, probably without realizing it, I sent him an email on December 25.

---

Errors Related to Algorithm X

I was familiar with Algorithm X before reviewing Volume 4 Pre-Fascicule 5c (published as Volume 4, Fascicule 5)—because exact cover problems are fantastic! I did not expect to find fundamental errors, as Algorithm X has probably been one of the sections most thoroughly reviewed by its creator.

At that time, I kept track of Algorithm X’s states manually (I was on a flight without a computer). I maintained a record of the memory state with pen and paper, an experience that allowed me to focus on the essential details and discover small errors and imprecisions that led to minor corrections.

Reported Errors

Local Variables Not Declared

While the local variables of the first algorithmic step, cover(i), are identified as such, the variables of the subsequent steps are not.

Though this is not particularly problematic (this is trivially inferable from the context), Knuth recognized that it would have been beneficial to state this characteristic for each step explicitly. However, he decided against breaking up Algorithm X between different pages due to space constraints and, therefore, could not add clarifications for each step; he then appropriately quoted Voltaire: “The secret of being a bore is to tell everything.” Nevertheless, Knuth ultimately found an elegant solution (see below).

Reward: 32¢ (0x20¢)

Unused Memory Fields

When it was time to simulate the impact of the algorithm on the memory state, I was confused by this:

My interpretation was that a program attempting to access one of these unused fields would fail, as I assimilated them as being in an uninitialized state. And indeed, my pen-and-paper program failed when reaching the hide step for the last spacer. Using the memory dump table as an example, covering one of the last nodes after some iterations leads to set q to 30 and, therefore, to d ← DLINK(30). If an unused field means an uninitialized memory location, then the algorithm's execution should prematurely stop as, in this example, DLINK(30) = —. However, Knuth clarified that he did not explicitly state the variable was uninitialized; instead, it must be assumed to be initialized, but its value has no impact on the algorithm.

Reward: 32¢ (0x20¢)

Unused Variables

Finally, N and Z were set during the algorithm initialization step, but I did not need to utilize them when manually tracking the memory state.

According to Knuth, they were, in fact, used in the exercises, notably exercise 83.

To ensure this was the case, he reviewed it and noticed an error: N should be N₁.

He graciously rewarded me for helping him discover this error. (I transitively found this error, so to say.)

Reward: $2.56 (0x$1.00)

Corrections

Corrections arising from my emails, all dated back to January 1, 2020, can be found in the Errata for Volume 4 Fascicle 5, long-form (available here). Specifically, they are listed on pages 5 and 13 of the downloadable compressed PostScript file.

It appears that:

• Knuth clarified what “unused” field means by implicitly stating that they are implicitly but necessarily initialized but "can contain anything".

• Instead of listing all local variables, he refers to p, l, r as being part of a non-exhaustive list of local variables (“Undeclared variables like p, l, r are local”).

• Last, in his answer 83, he replaced N with N₁.

Small Aside: Using a “HeartBeat-Arrow” as Delimiter

Notice how Knuth uses a bespoke symbol (a “heartbeat-arrow”) to indicate the transition from the error to its correction:

This is because he, as his corrections are inline/embedded (no table), he needed a symbol that is necessarily not already present in his books; otherwise, it could have been confused with a corrected symbol (typically, a simple right-pointing arrow, →, would have most probably been confused with a corrected material implication, and so forth). I believe this is an illustration of a delimiter, a special marker that cannot use the same symbols or structure as the regular text (in my previous blog post, I develop this general idea).

---

Erroneous Reference to an Obscure Article

Reported Error

When reading the section on Hamiltonian paths in antiquity from Volume 4, pre-fascicule 8a, I stumbled upon the reference to a French article about icosahedral objects inscribed with Greek letters: P. Perdrizet, in Bulletin de l’Institut français du Caire 30 (1930), 1-16. I did not find this article in the journal, but instead located it in Bulletin de l’Institut français d’archéologie orientale.

Acknowledging the error, Knuth took the time to review some articles in this journal and strongly recommended a volume about Egyptian poetry: https://ignca.gov.in/Asi_data/31424.pdf. Although he did not specify an article, I believe he referred to Vikentiev, V. (n.d.). The metrical scheme of the « Shipwrecked Sailor ». Bulletin de l’Institut français d’archéologie orientale, 35(1), 1–40. It is indeed remarkable for that time (see notably Planche 1, page 18 of the PDF).

Reward: $2.56 (0x$1.00)

Correction

There is no erratum, as it is a pre-fascicule that is directly edited.

Here is, as a substitute, a comparison of a version from November 2019, retrieved with Wayback machine, and the current one (March 2025):

Conclusion

This event has left me with an immense sense of respect for Donald Knuth’s dedication to accuracy and attention to detail. It was an honor to contribute to the improvement of his work, even if it was just a small (to be honest: minuscule) part. I look forward to continuing my exploration of the latest published TAOCP volume, and discovering more errors to correct.