# Recent News

## An Awesome Year

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

## The Stanford GraphBase is now out in paperback!

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

## Volume 4, Fascicle 1, is here

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.

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

## Interview by Richard Morris

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

## Did you borrow a video from me?

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;

## A blast from the past

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

### Message to Hannah Terret (née Terrett)

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

## Public lectures

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