Recent News

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

News flash (January 1): Happy New Year to all! One of my correspondents wrote that the new `millenium' began on January 1, 2000, but the new `millennium' begins today. Soon I will be 3f years old, hexwise.

The Millennium Edition of Computers & Typesetting

My publishers at Addison-Wesley have risen to the occasion by putting together a splendid boxed set of the five volumes on Computers & Typesetting that summarize the results of my work on TeX and METAFONT. This is the first update of Volume D for many years, and it also includes many recent changes to The TeXbook and The METAFONTbook and to Computer Modern Typefaces, thanks to improvements suggested by thousands of volunteers all over the world. Nearly every page of these books has been changed since the first editions of 1986. So I urge everybody whose library has only the 1986 printings to ask their friendly librarian to obtain the new definitive set, and I also think everyone with more than a casual interest in digital typography will benefit from this upgraded set of books. The publishers and I have taken great care to dot all the i's and cross all the t's so that the books reach the highest standards of quality.

Welcome, Kadin

News flash (January 9): Grandson #4 born at 11:37am!

name = "Kadin Morris Tucker"
type = "melodious"
weight = "4.2 kg"
height = "1 cubit"
eyes = "grey"
hair = "brown"
mother = "Jennifer Knuth"
father = "Greg Tucker"
remark = "born on Tuesday full moon, just like his brother Rees"
everybody = "happy"

Adieu to a cherished relative

My wife's mother, Wilda Ernestine Bates Carter, died peacefully in her sleep on March 4. She was one of the finest people that I've been privileged to know. Here is a sample of her creative needlework,

which hangs in my office at home. (She signed it with her initials, an anagram of CWEB.)

Major New Version of CWEB

Hip, hip, hooray, a long-cherished dream is now a reality: CWEB version 3.6 introduced new features for clickable hypertext links by which you can read programs with Acrobat. It also contained extensive revisions that greatly improve its support for C++. And version 3.63 (January 1, 2001) is even better! See my CWEB page for full details.

I strongly urge all CWEB users to upgrade to version 3.63 as soon as possible. Version 3.6 represented the first nontrivial change to that system in many years --- although I decided not to call it version 4 --- and version 3.61 extended it to hypertext. Version 3.63 corrects and improves several aspects of those early releases. My present intention is that version 3.63 will in fact be the very last upgrade (except of course for fixes to catastrophic bugs). The CWEB book has just been reprinted, with complete documentation of Version 3.63.

Current projects

As I work on Volume 4, I can't resist writing programs to test the algorithms I discuss. The most interesting ones at the moment involve counting the total number of fixed polyominoes, using slight refinements of a new algorithm by Iwan Jensen. Just as the millennium ended, my programs POLYNUM and POLYSLAVE completed a long run on two different computers, confirming previous results and establishing a new world record for polyomino enumeration: Now it can be told that the number of 47-ominoes is exactly t(47)=272,680,844,424,943,840,614,538,634!

Fans of ``dancing links'' might want to try a new program called HAMDANCE that I wrote on May 13; it finds Hamiltonian circuits faster than my previous program HAM. [Caution: I haven't tested it thoroughly as yet.] These programs, together with a few other refinements of the original DANCE program called GDANCE and XGDANCE, can be found here.

Also, fans of algorithms for combinatorial generation and/or the ``science of programming'' will, I think, enjoy reading two programs KODA-RUSKEY and LI-RUSKEY that I recently put online. Bug reports are welcome (although I'm not offering cash rewards in this case, sorry).

News flash (June 24): Jill and I are thankful for 40 years of wedded bliss!

A resource for puzzle fans

I'm planning to include lots of combinatorial puzzles in Volume 4 of The Art of Computer Programming, so I've been spending quite a bit of time studying the origins of the grand old classics. My recent trip to England allowed me to finish a long-standing project, to compile lists of several hundred columns that Henry E. Dudeney wrote for a newspaper called The Weekly Dispatch, together with hundreds more that he contributed monthly to The Strand Magazine during the last twenty years of his life. I've made brief descriptions of each problem that particularly interested me from a computer programmer's standpoint, and I've prepared cross-indexes linking each of the problems to Dudeney's books in cases where he republished them later. I've also done similar things with Sam Loyd material, especially with respect to a fascinating newspaper column that Loyd and Dudeney wrote jointly in 1896--1898.

Here is where one can find the origin of many now-famous puzzles, like pentominoes, the no-three-in-line problem, Golomb rulers, the Chinese Postman problem, and multipeg Tower of Hanoi, not to mention numerous dissection problems and word games. All these indexes are in simple ASCII text format. Extensions and corrections are welcome (but in this case I'm not offering any monetary rewards for errata:-).

Dudeney's columns in The Weekly Dispatch, April 1896--April 1904
Dudeney and Loyd's columns in Tit Bits, September 1896--April 1898
Dudeney's columns in The Strand Magazine, May 1910--June 1930
Key to the original problem numbers in Dudeney's books, versus the new numbers assigned by Martin Gardner in his Scribner's edition
An index to Sam Loyd's Cyclopedia of Puzzles (1914)
Key to the original page numbers of Loyd's Cyclopedia, versus the new numbers assigned by Martin Gardner in his Dover editions
An index to Hoffmann's Puzzles Old and New (1893)

Beam Me Up, Scotty


A First Glimpse of Volume 4

Are you bursting with curiosity about what will appear some day in Volume 4? I've just made a few pages available to experts in the field, so that they can help me get the bugs out. And if you are courageous and have nothing better to do, you might also enjoying helping me debug this stuff. (Yes, I'm paying the usual rewards to anybody who discovers a previously unreported error. So you might able to finance a new car or at least a new book, if you dig deeply enough into this.) Here it is: Pre-Fascicle 2a: A Draft of Section Generating all $n$-tuples [version of 17 September].

Note: If you have already downloaded an earlier version, please replace it with the new one, because I've made substantial improvements to the material on de Bruijn sequences that used to occupy pages 24 and 25. I think you'll agree that the new material, which also replaces exercises 93--98 [or so] with some great new ideas I just learned about, justifies the fact that the fascicle is now a few pages longer than before.

By the way, I'm extremely grateful to more than 100 people who have sent comments about errata in the previous versions of this draft. But I must admit that I'm worried about one thing: Nobody has yet said a word about the answers to some of the exercises that I worked hardest on---especially exercises 20, 30, 31, 61, 64, 73, and 107. The reason might perhaps be that the answers to all those exercises are 100% correct. But I suspect the real reason is that nobody had time to study the somewhat hairy technical details. Hey, I wouldn't have put those problems in the book if I didn't think they were full of instructive ideas! And now the draft of 17 September has several new exercises [93--97] that really cry out to be checked carefully. Can somebody please write to say "I have studied the answers to exercises so-and-so, and I believe you actually got them right the first time"?

My MIT Lectures in Book Form

News flash, 19 August: I just received my personal copy of a new book that I hope at least a few people will like. The title is Things a Computer Scientist Rarely Talks About, and it might be subtitled Interactions Between Faith and Computer Science.

Computer problems

Crackers (I mean, bad-guy hackers) have disrupted Stanford's computers lately. If you emailed a bug-report to taocp or knuth-bug or sgb before October and I haven't answered it yet, chances are good that I never received it. So please re-send the message, thanks. (On the other hand, if you sent any unsolicited mail to one of those addresses, tough luck --- you shouldn't do that!)

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:

Tuesday, 16 January at 4:30pm
delivering a Strachey Lecture about "Structured Programming and Literate Programming" at the Oxford University Computing Laboratory, in the Clarendon Laboratory's Martin Wood Lecture Theatre
Thursday, 18 January at 1:30pm in Room 1.04 of the (new) Computer Science Building
speaking about "47-ominoes" at The University of Warwick's Department of Computer Science
Friday evening, 20 April
speaking about writing at the annual Author's Dinner sponsored by the Associates of the Stanford University Libraries
Thursday afternoon, 10 May at 4:15pm in Terman Auditorium
A Computer Musing lecture entitled ``Twisted toruses: or, tori, tori, tori''
Thursday, September 20, 11:30am
giving a plenary talk, "The Joys of Asymptotics," at HERCMA 2001, the 5th Hellenic European Conference on Computer Mathematics & its Applications
Monday, 24 September, 6:30pm
speaking and receiving a doctor's degree at the Great Hall of the Athens University of Economics and Business
Tuesday, 2 October, 5:15pm, in N5 Hörsaalzentrum Morgenstelle
speaking informally about MMIX at University of Tübingen
Tuesday, 2 October, 6:30pm in Fürstenzimmer Schloß Hohentübingen
playing a small organ, speaking briefly, and receiving a doctor's degree from the University of Tübingen
Friday, 5 October, 10:30am
All Questions Answered, at the Technical University of Munich
Saturday, 6 October, 3:00pm
speaking as part of the Oktober MMIXfest at the Munich University of Applied Sciences
Sunday, 28 October, 4:00pm
Playing the continuo organ at First Lutheran Church of Palo Alto, in a performance of Bach's Cantata No. 9 and Pachelbel's Magnificat
Thursday evening, 8 November, 6:30--8:00pm at the Pake Auditorium, XEROX PARC, 3333 Coyote Hill Road, Palo Alto
All Questions Answered, sponsored by the Computer Museum History Center
Tuesday evening, November 13, 7:00pm
speaking at the Stanford Bookstore as we launch the book Things a Computer Scientist Rarely Talks About
Thursday, December 6, 4:15pm in Gates room B01
A Computer Musing lecture entitled ``Totally Acyclic Digraphs (Spiders) and how to squish them''
Tuesday, 24 December 24, 10:00pm
Playing the continuo organ at First Lutheran Church of Palo Alto, in a performance of Bach's Christmas Oratorio [part 2] and Prætorius's Christmas Mass

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

Don Knuth's home page

(Netscape-HTML checked)