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 will be posted later this year.)

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)
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 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 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 03 May 2017. 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!

Adventurous people might also dare to take a peek at the current draft of pre-fascicle 5b (“Introduction to Backtracking”), and the current draft of pre-fascicle 5c (“Dancing Links”). I hope to have Volume 4 Fascicle 5 complete and available in paperbook early this year.

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

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