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

I'm happy to announce Volume 1, Number 1 of a new journal, ACM Transactions on Algorithms (July 2005), edited by the entire former editorial staff of the Journal of Algorithms. It's available now at ACM's Digital Library. Last year the editor-in-chief (Hal Gabow of the University of Colorado) promised that the inaugural issue would be ``gangbusters''; his promise was, if anything, an understatement. Congratulations to all the authors and editors!

David Kestenbaum came to Stanford in July 2004 and spent an entire day following me around; we even went swimming together! He taped a lot of noises that I made, and eventually boiled everything down to an 8-minute interview that aired on Morning Edition on 14 March 2005. (Great job, David, making sense out of my nerdy life. Of course you meant to say ``100 million'' instead of ``10 million'' at one point:-)

Hurray, hurray: After many years of preparation, at last I can report
the publication of new material for my books on
The Art of
Computer Programming, first released in paperback on Valentine's Day
of this year. ``Volume 1 Fascicle 1,'' a programmer's introduction to the
`MMIX` computer, is an update to
Sections 1.3 and 1.4 of Volume 1, Fundamental Algorithms,
planned for inclusion in the eventual fourth edition of that volume.
``Volume 4 Fascicle 2'' contains sections 7.2.1.1 and 7.2.1.2 of
Volume 4, Combinatorial Algorithms, a work in progress.
``Volume 4 Fascicle 3,'' published in August, contains sections 7.2.1.3--7.2.1.5 of
Volume 4.
The publishers
plan to release Volume 4 Fascicle 4 next winter, Volume 4 Fascicle 1
next summer, and approximately two fascicles per year henceforth.

First drafts of some of the forthcoming fascicles are also ready for beta-testing. I've put them online primarily so that experts in the field can help me check the results; but brave souls who aren't afraid to look at relatively raw copy are welcome to look too. (Yes, the usual rewards apply if you find any mistakes.)

- Pre-Fascicle 0b: Boolean Basics (version of 05 December 2005)
- Pre-Fascicle 4a: Generating All Trees (version of 28 October 2005)
- Pre-Fascicle 4b: History of Combinatorial Generation (version of 28 October 2005)

(If you have trouble downloading these files, your browser is probably screwing up; please see my FAQ page for a workaround.)

Note to Internet friends: I'm extremely grateful that hundreds of you have taken time to read these drafts, and to detect and report errors that you've found. Your comments have improved the material enormously. But I must confess that I'm also disappointed to have had absolutely no feedback so far on several of the exercises on which I worked hardest when I was preparing this material. Could it be that (1) you've said nothing about them because I somehow managed to get the details perfect? Or is it that (2) you shy away from the more difficult stuff, being unable to spend more than a few minutes on any particular topic? Although I do not like to think that readers are lazy, I fear that hypothesis (1) is far less likely than hypothesis (2). I may have to remove material that nobody cares about. But I still cling to a belief that this stuff is 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:

- 7.1.1--27 (the Fredman--Khachiyan algorithm for CNF versus DNF)
- 7.1.1--34 (the aymptotic average number of implicants and prime implicants)
- 7.1.1--35, 36, 37 (key properties of shellable Boolean functions)
- 7.1.1--51 (optimum strategies for four Boolean games)
- 7.1.1--65 and 67 (Schensted's theory of the Y function)
- 7.1.1--73 (Sholander's construction of a median algebra from betweenness postulates)
- 7.1.1--81 (an online algorithm for optimum server locations)
- 7.1.1--107 (key properties of the binary majorization lattice)
- 7.1.1--110 (Håstad's threshold function requiring huge weights)
- 7.1.1--114 (functions with conjectured maximum number of prime implicants)
- 7.1.1--119 (simple examples of regular functions that aren't threshold functions)
- 7.1.1--129 (properties of ``bent functions'')
- 7.2.1.1--97 (analysis of a coroutine-based algorithm)
- 7.2.1.1--99 (decoding a recursively generated de Bruijn cycle)
- 7.2.1.3--25 (proof of van Zanten's theorem)
- 7.2.1.3--33 (enumeration of genlex listings for index lists)
- 7.2.1.3--42 (analysis of an algorithm for near-perfect combination generation)
- 7.2.1.3--63 (minimal-change algorithm for contingency tables)
- 7.2.1.3--100 (the heaviest multicomplexes)
- 7.2.1.4--18 (two versions of Zeilberger's one-to-one correspondence for joint partitions)
- 7.2.1.4--28 (Lehmer's fabulous formulas, to be checked empirically)
- 7.2.1.4--47 (Nijenhuis and Wilf's algorithm for random partitions)
- 7.2.1.4--56 (my algorithm for partitions in an interval of the majorization lattice)
- 7.2.1.5--28 and 29 (theory of generalized rook polynomials)
- 7.2.1.6--19 (proof that Skarbek's algorithm is dual to lexicographic generation)
- 7.2.1.6--25 (my new prune-and-graft method of generating all linked binary trees)
- 7.2.1.6--26, 27, 28 (basic facts about three important lattices of trees)
- 7.2.1.6--33 (representing binary tree links with a single permutation)
- 7.2.1.6--37 (analysis of the Zaks--Richards algorithm for trees by degrees)
- 7.2.1.6--60 (an algorithm to invert the Chung--Feller mapping)
- 7.2.1.6--99 (quick Gray code to list spanning trees of a series-parallel graph)

Note that you don't have to work the exercise first; you're allowed and
even encouraged to peek at the answer.
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!

During our summer vacation in 2003, my wife and I amused ourselves
by taking leisurely drives in Ohio and photographing every diamond-shaped
highway sign that we saw along the roadsides. (Well, not *every* sign;
only the distinct ones.) For provenance, I also stood at the base of each sign
and measured its GPS coordinates.

This turned out to be even more fun than a scavenger hunt, so we filled in some gaps when we returned to California. And we intend to keep adding to this collection as we drive further, although we realize that we may have to venture to New England in order to see `FROST HEAVES'.

Here are the images of our collection so far.

Videotapes of most of my Computer Musings have been made since 1998, and I have often loaned copies to people who were unable to attend in person.

Now there is good news and bad news. The good news is that more than a dozen of these videos have been digitized, and they are available for viewing. The bad news is that three people have not returned the tapes they borrowed, and there is no backup copy; I learned recently that my copy was unique, because all the master tapes were erased. If you are the person who currently has any of the following tapes:

- Twisted toruses (or: tori, tori, tori), from 10 May 2001;
- Totally acyclic digraphs (spiders) and how to squish them, from 06 Dec 2001;
- Topological sorting revisited, from 23 Apr 2002;

please PLEASE return it/them immediately.

Although I must stay home most of the time and work on 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:

- Tuesday 11 January, 4:30pm
- Oxford Comlab Seminar, ``Sand piles and spanning trees''
- Wednesday 2 February, 4:00pm
- Mathematics Colloquium at Royal Institute of Technology, Stockholm, ``Sand piles and spanning trees''
- Tuesday 8 February, 2:00pm
- Seminar talk at Institut Mittag-Leffler, Djursholm, Sweden, ``Hooray for probability theory''
- Friday 4 March, 4:00pm
- Colloquium talk at CAMS/EHESS (i.e., le Centre d'Analyse et de Mathématique Sociales à l'Ecole des Hautes Etudes en Sciences Sociales), Paris, ``Lattices of trees''
- Tuesday 8 March, 5:00pm
- With Hermann Zapf in an informal panel discussion at EuroTeX 2005, Abbaye des Prémontrés (Pont-à-Mousson, France)
- Sunday 24 April, 9am, at First Lutheran Church of Palo Alto,
- informal discussion of the Bible verse 1 Peter 3:16
- Friday 6 May, 4:30pm, in Skilling Auditorium
- A Computer Musing lecture entitled ``Integer partitions and set partitions: A marvelous connection''
- Tuesday 15 November, 4:30pm
- Oxford Comlab Seminar, ``Shellability of monotone Boolean functions''
- Tuesday 22 November, 17h15 in auditorium G 30 in the University of Zurich -- Irchel
- Public lecture "The Joy of Technical Illustration", organized by the departments of computer science aka informatics at ETH (Zürich) and University of Zürich, as part of ETH's gala 150th anniversary celebration
- Tuesday 10 January 2006, 6pm, at Café Scientifique Palo Alto
- ``All Questions Answered''

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