Recent News

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

Happy MMXIX to all!

A little puzzle

Explain this pattern. (The answer appears below.)

Fantasia Apocalyptica is now on YouTube

Patrick Brunet of the University of Waterloo has masterfully combined four video tracks and two audio tracks of recordings from the North American première of my multimedia composition Fantasia Apocalyptica, as it was brilliantly performed last November by organist Jan Overduin. You can watch it here.

You can also now see videos of the world première performance (Sweden, January 2018), streamed either in 3D or 2D, thanks to Michael Angeletti of Stanford's Media Preservation Lab.

Oral histories

Having just celebrated my 10000th birthday (in base three), I'm operating a little bit in history mode. Every once in awhile, people have asked me to record some of my 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 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)

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

The Stanford GraphBase becomes an eBook

Addison-Wesley has just released my book The Stanford GraphBase in electronic form! This is a one-of-a-kind book, very difficult to present properly in PDF format, because it features about three dozen examples of literate programming; thus it's loaded with hundreds and hundreds of cross-references between pages, linking variables and code with the stories of the algorithms themselves. And I'm happy to say that the publishers have done a really good job.

Indeed, here's what I wrote to them when I got my proof copy:

I tried hard to find something wrong, and came up emptyhanded.
The navigation aspects --- I mean, clicking on cross-references, and searching --- are outstanding. Even while searching for "anna" I found "Savannah" as part of a map --- which Acrobat reader nicely rotated to landscape view because that page is intended to be read sideways.
Mona Lisa looks good even when greatly magnified. The tricky overlaid illustrations on page 29 turned out perfect.
So --- hearty congratulations to the team who made this successful eBook!

Most of the programs are at most a dozen or so pages long. They include expositions of many of my favorite algorithms, including: the Hungarian method for the assignment problem; Pang Chen's algorithm for stratified greed; Dijkstra's algorithm for shortest paths; an exact algorithm for Delaunay triangulation; an ultra-fast random number generator; the Kruskal and Prim and Cheriton-Karp-Tarjan algorithms for minimum spanning trees; Tarjan's algorithm for strong components; etc. All of them can now be viewed conveniently in hypertext form, on your phone, when you've run out of email to answer.

(click here for further information)

A coffee-table book

I'm also pleased to announce the publication of Fantasia Apocalyptica Illustrated, which features the 128 illustrations that Duane Bibby created to accompany the music of Fantasia Apocalyptica.

Many readers have been entranced by Duane's artwork in The TeXbook, The METAFONTbook, and numerous other texts. Now you can see how he has magnificently risen to the challenge of continuing the centuries-old tradition of telling the powerful stories in the Book of Revelation visually, as carried out by great artists such as van Eyck, Dürer, El Greco, Rubens, Blake, etc.

Each image appears together with an excerpt from the Greek text of Revelation, an English translation, and a musical translation, as presented in the world première of Fantasia Apocalyptica in January 2018.

Let's celebrate everybody's full names

One of the delights of Wikipedia is that its biographies generally reveal a person's full and complete name, including the correct way to spell it in different alphabets and scripts.

When I prepared the index to Volume 1 of The Art of Computer Programming, I wanted to make it as useful as possible, so I spent six weeks compiling all of the entries. In order to relieve the tedium of index preparation, and to underscore the fact that my index was trying to be complete, I decided to include the full name of every author who was cited, whenever possible.

None of my textbooks had done this. But in Caltech's library I learned that the Catalan numbers had not only been investigated by Lamé, Catalan, Rodrigues, and Binet, they had been studied by Gabriel Lamé, Eugène Charles Catalan, Benjamin Olinde Rodrigues, and Jacques Philippe Marie Binet. I also had become personally acquainted with Nicolaas Govert de Bruijn, Edsger Wybe Dijkstra, Charles Antony Richard Hoare, etc., so I had lots of good data. My index presented Russian names like Andreĭ Nikolaevich Kolmogorov in a westernized transcription.

Later, when I typeset the index to the second edition of Volume 2, using an early prototype of TeX in 1980, I had the ability to include Chinese and Japanese names in their native form. And by the time the third editions came out in the 1990s, I was also able use Greek, Hebrew, and Cyrillic alphabets, and to present Arabic and Indian names in appropriate native scripts. At last I did not have to rely entirely on transliteration when listing the name of the father of algorithms, Abu Ja‘far Mohammed ibn Mūsā al-Khowārizmī. I even hand-crafted an ancient Sumerian name by using METAFONT to draw the necessary characters of a cuneiform alphabet.

Over the years, many people have told me how they've greatly appreciated this feature of my books. It has turned out to be a beautiful way to relish the fact that computer science is the result of thousands of individual contributions from people with a huge variety of cultural backgrounds.

And at last, thanks to Unicode, the world's alphabets and scripts are present on almost everybody's computers and cellphones. So it's easy now for people who use different writing systems to share their names with each other.

The American Mathematical Society has recently launched a great initiative by which all authors can now fully identify themselves, without becoming egocentric and immodest. It's an extension to the Author Profile feature that was introduced some years ago: You can now characterize your name, not only in the customary western alphabets used in traditional AMS publications, but also in any native script.

It's really easy to update your profile: Ed Dunne has given nice step-by-step instructions together with several well-chosen examples. (See the related story by Allyn Jackson in Notices of the American Mathematical Society, January 2018, pages 59–60.)

I strongly encourage everybody to document their full names at the AMS site, as soon as possible. Just go to http://www.ams.org/mathscinet/MRAuthorID/search and identify yourself. That database already contains more than 860,000 authors, so you'll be in good company. Even if you weren't born in a country with exotic characters, I urge you to complete your author profile by including any middle name(s) that you have. I don't think those names should appear only in a few legal papers and on your dissertation. Even if you never actually use them in publications, they are an important part of life. The rest of us shouldn't have to wait to learn your full name until Wikipedia has a page for you.

Of course, if you have only two names, that's fine too.

The middle third of Volume 4B

One of the most important sections of The Art of Computer Programming has been published in preliminary paperback form as Volume 4, Fascicle 6: “Satisfiability”. Here are excerpts from the hype on its back cover:

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 some of those 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 6:

Please don't be alarmed by the highly technical nature of these examples; more than 100 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), if you have time to provide this extra help. Thanks in advance!

The first third of Volume 4B

Volume 4B will begin with a special section called ‘Mathematical Preliminaries Redux’, which extends the ‘Mathematical Preliminaries’ of Section 1.2 in Volume 1 to things that I didn't know about in the 1960s. Most of this new material deals with probabilities and expectations of random events. There's also an introduction to the theory of martingales.

You can have a sneak preview by looking at the current draft of pre-fascicle 5a (55 pages), last updated 11 September 2019. As usual, rewards will be given to whoever is first to find and report errors or to make valuable suggestions. I'm particularly interested in receiving feedback about the exercises (of which there are 131) and their answers (of which there are 131).

There's stuff in here that isn't in Wikipedia yet!

After these preliminaries, Volume 4B will resume the story of Combinatorial Algorithms that was begun in Volume 4A. Sneak previews of this material are available too, in near-final form: Please take a peek at the current draft of pre-fascicle 5b (“Introduction to Backtracking”), and the current draft of pre-fascicle 5c (“Dancing Links”).

Thanks to Tom Rokicki, these PostScript files are now searchable!

Volume 4 Fascicle 5, which combines the pre-fascicles 5a, 5b, and 5c mentioned above, will be published in paperback this fall. It will feature more than 650 exercises and their answers, designed for self-study.

Of course those exercises, like those in Fascicle 6, include many cutting-edge topics that weren't easy for me to boil down into their essentials. So again I'm hoping to receive “Dear Don” letters, as explained above—either confirming that at least somebody besides me believes that I did my job properly, or pointing out what I should really have said. The exercises I'm most anxious about in pre-fascicle 5a are the following:

And in pre-fascicle 5b, I seek help and reassurance for the exercises in the following list:

Finally, the following exercises in pre-fascicle 5c are also on my wish list:

Let me reiterate that you don't have to work the exericse first. You're allowed to peek at the answer; indeed, you're encouraged to do so, in order to verify that the answer is 100% correct. Furthermore, 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.

Hey, check out this brand new paperback! I received my first copy on December 5, and you can get yours by searching for "fascicle 5" in books. Here are excerpts from the hype on its back cover:

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.

Public lectures in 2019

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 is a current schedule of events that have been planned for this year so far:

Sunday March 31, 9:15am at First Lutheran Church, Palo Alto
leading an informal discussion of Joshua 3:16
Sunday April 7, 9:15am at First Lutheran Church, Palo Alto
leading an informal discussion of Philippians 3:16
Sunday May 5, 9:15am at First Lutheran Church, Palo Alto
leading an informal discussion of Psalm 3:16 (aka Psalm 4:8)
Friday August 9 to Sunday August 11
TUG 2019, the 40th Annual Meeting of the TeX Users Group, will be held near Stanford this year, and I plan to visit some of the sessions (and perhaps even say a few words)
Tuesday September 3, 4:00pm at the Simons Institute for the Theory of Computing
Participating in a panel discussion to inaugurate the Richard M. Karp Lecture Series (view slides)
Tuesday, October 8, 2:00pm in lecture hall D1 of the Faculty of Informatics at Masaryk University in Brno
“All Questions Answered (except about music)”, celebrating the 25th Anniversary of their Faculty of Informatics (watch video or view transcript)
Wednesday, October 9, 12:15pm in lecture hall D3+D1 of the Faculty of Informatics at Masaryk University in Brno
“All Questions Answered (about music or anything else)” (watch video or view questions)
Friday October 11, 7pm
Participating in a performance of Fantasia Apocalyptica at Jesuit Church of the Assumption of the Virgin Mary in Brno
Sunday October 20, 9:15am at First Lutheran Church, Palo Alto
leading an informal discussion of Job 3:16
Sunday October 27, 9:15am at First Lutheran Church, Palo Alto
leading an informal discussion of Ecclesiastes 3:16
Sunday November 10, 9:15am at First Lutheran Church, Palo Alto
leading an informal discussion of Song of Solomon 3:16 (aka 4:5)
Thursday December 5, 6:30pm in NVIDIA Auditorium
A Computer Musing entitled “Pi and The Art of Computer Programming” (the 25th annual Christmas lecture)

Puzzle solution (a reverse-engineered diagram)


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

Don Knuth's home page

Valid HTML 4.01 Transitional