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

I'm happy to announce the imminent appearance of a new journal, ACM Transactions on Algorithms, to be edited by the entire former editorial staff of the Journal of Algorithms. An official announcement has appeared in the March 2004 issue of SIGACT News, and the web site for prospective readers and authors has just been launched. The editor-in-chief is Hal Gabow of the University of Colorado, and he promises that the inaugural issue will be ``gangbusters.''

I've been making some headway on actually writing Volume 4 of The Art of Computer Programming instead of merely preparing to write it, and some first drafts are now 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 2a: Generating all $n$-tuples (version of 10 December 2004)
- Pre-Fascicle 2b: Generating all permutations (version of 10 December 2004)
- Pre-Fascicle 3a: Generating all combinations (version of 10 December 2004)
- Pre-Fascicle 3b: Generating all partitions (version of 10 December 2004)
- Pre-Fascicle 4a: Generating all trees (version of 11 December 2004)
- Pre-Fascicle 4b: History of combinatorial generation (version of 28 December 2004)

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

**If you have previously downloaded a pre-fascicle dated prior to
29 August 2003, I recommend that you upgrade to the current version.**
The main reason is that I've decided to change the terminology used
for ``Gray codes'', which I had formerly restricted to cases where the
sequence is cyclic (with the last element adjacent to the first).
Such things are now called ``Gray cycles'', and the term ``Gray code'' is
used to mean either a Gray cycle or a Gray path. This change brings my
terminology into line with common usage.

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.2.1.1--96 (analysis of a coroutine-based algorithm)
- 7.2.1.1--98 (decoding a recursively generated de Bruijn cycle)
- 7.2.1.2--43 (a Sims table with only short cycles)
- 7.2.1.2--75 (enumeration of northeasterly knight's tours)
- 7.2.1.3--25 (proof of van Zanten's theorem)
- 7.2.1.3--33 (enumeration of near-perfect 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--92 (synchronized standard sets in toruses)
- 7.2.1.3--93 (counterexample when hypotheses are violated)
- 7.2.1.3--100 (the heaviest multicomplexes)
- 7.2.1.4--18 (two versions of Yee's one-to-one correspondence)
- 7.2.1.4--19 (Heine's famous identity)
- 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--49 and 50 (analysis of the smallest parts of a partition)
- 7.2.1.4--55 (basic properties of the majorization lattice)
- 7.2.1.4--56 (my algorithm for partitions in an interval of the majorization lattice)
- 7.2.1.5--27 and 28 (theory of generalized rook polynomials)
- 7.2.1.5--62 (elementary way to locate the largest Stirling numbers via Darroch's theorem)
- 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)
- 7.2.1.6--105 (counting spanning trees when graphs are built up from smaller ones)
- 7.2.1.6--108 (counting spanning arborescences when digraphs are built up from smaller ones)
- 7.2.1.7--2 (the genetic code and the I Ching)
- 7.2.1.7--10 (a coupon-collecting problem relating to dice)
- 7.2.1.7--28 (partitions that are
*almost*noncrossing)

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 last year, 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.

The 15th printing of my ``mathematical novelette'' Surreal Numbers has just appeared in print. For the first time, its contents have been typeset with TeX, using also a special ``rock'' font designed with METAFONT; and all known errors have been corrected.

The glorious 3rd printing of Selected Papers on Computer Science is now available, with all known errors corrected and with several pages of new material.

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.

After the depressing outcome of recent elections, I've decided to post my letter to Condoleezza Rice written in September 2002.

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:

- Sunday 22 February, 9am, at First Lutheran Church of Palo Alto,
- informal discussion of the Bible verse 2 Corinthians 3:16
- Tuesday afternoon, 8 June, at the Université de Montréal
- Lecture about "Notation"
- Tuesday, 15 June, 9am
- Giving a keynote lecture in Berkeley as part of a weeklong MSRI workshop, the 10th Seminar on Analysis of Algorithms
- Sunday, 17 October, 9am, at First Lutheran Church of Palo Alto,
- informal discussion of the Bible verse 2 Timothy 3:16
- Friday afternoon, 29 October, 4:30pm at Terman Auditorium (Stanford)
- A Computer Musing lecture entitled ``Hooray for probability theory''
- Sunday evening, 5 December
- Playing the continuo organ at First Lutheran Church of Palo Alto, in a performance of Bach's Cantata 140 ("Wachet auf...")
- Monday, 13 December, 4:30pm, in Skilling Auditorium
- A Computer Musing lecture entitled ``Sand piles and spanning trees'' (the eleventh annual Christmas Tree Lecture)

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