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

Best wishes to everyone for a happy 2009, aka MMIX!

Did you know that 2009 is (1/2+3)`*`(4+5`*`(6`*`7+8`*`9))?

Addison--Wesley has just published The Stanford GraphBase in a spiffy new paperback edition. I've completely rewritten Chapter 3, and made dozens of other refinements throughout. This is a book that I use almost daily while writing The Art of Computer Programming, so I'm really happy to see the new printing. (Hint, hint: It should make a terrific graduation present for a Comp Sci major...)

Paperback previews of new material for The Art of Computer Programming, called ``fascicles,'' have been published occasionally since 2005. I'm pleased to announce the arrival of the latest installment, which plugs the gap between Fascicle 0 and Fascicle 2. It deals with

- Bitwise tricks and techniques
- Boolean decision diagrams

and is cram-packed with lots of new stuff among nearly 500 exercises and answers to exercises.

Together with Fascicles 0, 2, 3, and 4, it makes a total of 818 pages (not counting front matter and indexes), which will eventually form the content of Volume 4A (planned for late 2010 or early 2011), once the material has been thoroughly checked.

*Note to Computer Science professors:* I've heard that some college
courses for grad students and advanced undergrads are being based
on one or more of these fascicles. Please let me know about your
experiences, if you try such an experiment.

*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 these details are 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--97 (properties of graph sums and graph products)
- 7--105 (characterization of graphical degree sequences---using the revised answer in the current errata)
- 7--137 and 138 (generalized toruses)
- 7.1.1--83 (an online algorithm for optimum server locations)
- 7.1.1--122 (simple examples of regular functions that aren't threshold functions)
- 7.1.1--132 (properties of ``bent functions'')
- 7.1.2--16 (minimum-memory computation of 7-variable functions)
- 7.1.2--43 (efficient finite state transduction with small depth)
- 7.1.2--63 (upper bound for functions with lots of don't-cares)
- 7.1.2--67 (design of a tic-tac-toe chip)
- 7.1.2--68 (analysis of a functional decomposition algorithm)
- 7.1.2--76 (Uhlig's cloning algorithm, computes twice as fast as expected)
- 7.1.2--85 and 86 (introduction to Razborov's monotone lower bounds)
- 7.1.3--124 (lower bounds on a basic RAM)
- 7.1.3--158 and 159 (Fibonacci and negaFibonacci codeword manipulation)
- 7.1.3--179 (online algorithm for components of a bitmap)
- 7.1.4--107 (testing whether a BDD defines a 2SAT instance)
- 7.1.4--110 (explicit functions of $n$ variables whose BDD is largest)
- 7.1.4--124 (computing the BDD size for the hidden weighted bit function, given any permutation of the variables)
- 7.1.4--191 (counting all ZDDs that have no 0-sink)
- 7.1.4--226 (a new way to generate all simple cycles of a graph)
- 7.1.4--259 (generating all set partitions with ZDDs)
- 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.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--27, 28 (basic facts about 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--99 (quick Gray code to list spanning trees of a series-parallel graph)

Remember 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!

On March 16 I spoke in the Authors@Google series, about interactions between religion and science. They've posted it here!

See Geek of the Week, 26 November 2009, which focuses on aspects of technical writing.

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

I learned recently that my 33-year-old paper on the early history of programming languages unfortunately omitted an important development because I had failed to look carefully for sources in Canada. Future printings of my book Selected Papers on Computer Languages will rectify this oversight. Furthermore, thanks to archivist Marnee Gamble, I'm able to post three interesting documents from the Patterson Hume Fonds at the University of Toronto Archives, which show how the system was described by its authors at the time of its introduction:

- the user manual
- TRANSCODE: A system of coding for the Ferranti MARK I Computer by J. N. P. Hume and B. H. Worsley (Computing Centre, University of Toronto, 1 October 1954), 17 pages
- appendix to the user manual
- A continuation of the preceding document, pages i--viii
- supplement to the user manual
- TRANSCODE library functions (Computing Centre, University of Toronto, April 1957), 14 pages

The Palin-drome I was trying to recall is: ``All I saw: Wasilla.''

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:

- Monday, 9 March, 4:15pm in room 200-002 (History Corner basement)
- lecturing about "Priority sampling" to Stanford class CS345A (guests are welcome)
- Thursday, 21 May, 4pm at Oxford Comlab
- lecturing about "Sheep, goats, and Gilbreath"
- Tuesday, 26 May, 4:15pm at Oxford Comlab
- lecturing about "Priority sampling"
- Saturday, 30 May, 4:00pm at Rewley House, Oxford
- speaking about Surreal Numbers as part of a workshop on Mathematics and Fiction sponsored by the British Society for the History of Mathematics
- Tuesday, 02 June, 2:00pm at Old Royal Naval College, Greenwich
- speaking on "history of computer science versus history of mathematics"
- Friday, 25 September, 3:30pm at Stanford Memorial Church
- playing the organ for Rajeev Motwani's memorial celebration
- Tuesday, 08 December, 5:30pm at Skilling Auditorium
- A Computer Musing entitled ``Spanning trees and aspects'' [the fifteenth annual Christmas Tree Lecture]

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