[click here to zip down to the schedule of public lectures]
The church in Ontario that will be sponsoring the Canadian premiere of my organ composition Fantasia Apocalyptica next year has just posted an excellent “trailer”, which illustrates and explains quite beautifully what I was trying to achieve while writing this music.
Time marches on, and guess what: Next January, God willing, I'm due to become an octogenarian!
To my great surprise, several of my cherished friends have decided to mark the occasion by organizing an international symposium
Knuth80: Algorithms, Combinatorics, and Information
to be held in the delightful city of Piteå (PEET-ay-oh) in northern Sweden, during the period 7 January – 11 January 2018.
This symposium will feature about 30 invited talks, followed by the world premiere of Fantasia Apocalyptica, a major musical work for pipe organ accompanied by video projections. The talks will run the gamut of the topics that I've pursued during my career as an educator, from the analysis of algorithms and combinatorial mathematics to typography and literate programming.
(By the way, many people tell me that they think northern Sweden is cold in January. It isn't warm; but Chicago is colder!)
For me this will be the fulfillment of a lifelong dream, not only because of the presence of my distinguished colleagues and mentors, but because I began to make plans for Fantasia Apocalyptica more than 50 years ago. Now that the piece has taken shape and I've been giving it the final spit-and-polish, I'm extraordinarily happy that a leading organist, Jan Overduin, has agreed to give the inaugural performances. Jan thoroughly understands the unusual principles on which this composition is based, and indeed he has already enhanced it in numerous ways.
An 80th birthday is obviously a once-in-a-lifetime experience for me. But many of my friends have also expressed a desire to help me celebrate, by enjoying their own once-in-a-lifetime winter excursion to northern Scandinavia. Piteå is not only the site of one of the world's finest new pipe organs, it shares many outstanding attractions with nearby Luleå. Facebook now has a ‘public group’ called Knuth80, which features timely postings and facilitates communication between people who are seriously thinking of joining the party. Please sign up for the Knuth80 group if you're interested. Among other things, we plan to arrange group rates for international travelers, if there is sufficient interest, and to provide shuttle buses and other aids to local travel within Sweden. Please follow Knuth80 in Facebook if you want uptodate information about this unique event.
Another good reason for following Knuth80 in Facebook is to watch the growing collection of Jan Overduin's entertaining videos, which informally present snippets of the Fantasia. I think advance familiarity with the music will significantly enhance everyone's experience when they eventually have an opportunity to hear the whole piece.
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 just 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.
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 740,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. Those names shouldn't 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.
For fifty years, a little muse has been whispering in my ear, urging me to compose a special kind of organ music. Now that dream is actually coming to fruition, and you can read about it here if you're interested.
One of the most important sections of The Art of Computer Programming has now 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 (firstname.lastname@example.org), if you have time to provide this extra help. Thanks in advance!
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!
I've been told that my Christmas lecture in December 2016 may have been the first university lecture ever screened live in 3D. Whether or not that's true, you might like to take a look at the archived video, which you can view with an ordinary browser as well as with a virtual-reality headset: click here to try it in low-res, or here to try it in hi-res!
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: