Recent News
Recent News
[click here to zip down to the schedule of public lectures]
I got a bit older at the beginning of this year ... and, wow, what a wonderful surprise celebration we had! I can't sufficiently thank all my friends who traveled to Stanford and treated me to some of the absolutely most thrilling days of my life, as we celebrated the joys of Computer Science in general and Analysis of Algorithms in particular. Great talks by Persi Diaconis, Scott Kim, Bob Sedgewick, Philippe Flajolet, Svante Janson, Jeff Vitter, Andrei Broder, Andrew Odlyzko, Herb Wilf, Bob Tarjan, Leo Guibas, and Vaughan Pratt --- plus a great organ concert by Gwen Adams and Joseph Hansen --- and a chance to greet more than a hundred people that I rarely get to see, including more than twenty of the students whose dissertations I've had the good fortune to sign in years past. Thank you all enormously for a festive event that will live forever in my memory. It could not have been more perfect!
Everyone who came to my birthday party was able to meet my indefatigable mother, Lou, who was still continuing to work with real estate in downtown Milwaukee long after I myself had retired. Alas, her age finally caught up with her, and she passed away at the end of June. (When she died she was exactly 32,758 days old, just ten short of $2^{15}$.) She was, thankfully, able to put her life in order and to have many upbeat moments with family and friends during the final months. Here is a memorial booklet that celebrates her life and work.
The third edition of Seminumerical Algorithms introduced a nice, portable random number generator called ran_array --- or, in FORTRAN, RNARRY. To use this generator, people call "ran_start(seed)" --- or RNSTRT(SEED), a la FORTRAN.
Late last year I received a message from a researcher in Spain, Pedro Gimeno, who noticed a new type of deficiency in this generator. He was using ran_array to generate only a few random numbers, but he was initializing it with many different seed values. This mode of usage had never been considered before in the literature, as far as either of us knew, and he found that essentially every generator he tried was giving him problems when used in such a way.
Indeed, I had never tried testing a random number generator by looking only at the first few numbers that correspond to seeds 1, 2, ..., 1000000 (say). So I tested ran_array/ran_start in Gimeno's manner; lo and behold, several tests for randomness failed.
I couldn't figure out why such a problem could occur, because both ran_array and ran_start have fairly substantial theoretical underpinnings; so I asked Richard Brent for help. Working with Gimeno, he carried out elaborate tests and found two cures for the problem: (1) Discard the first 2000 numbers produced by ran_array after it has been started. (2) Improve the algorithm used by ran_start to prime the pump. With either (1) or (2), no statistical bias is detected in the resulting numbers by Marsaglia's famous "Die Hard" battery of tests.
Brent and Gimeno recommended using BOTH fixes (1) and (2), to be doubly confident that residual nonrandomness isn't lurking.
So I've done that. The new method appears in the ninth printing of Seminumerical Algorithms (January 2002), and sources in both C and FORTRAN are freely available. Fortunately the new version is shorter and easier to understand than the original.
Please note, however, that the new version is NOT compatible with the old. The procedure ran_array has not changed, but the seed-value initialization by ran_start is quite different, so you get different results.
As before, the programs have been carefully written so that identical results are obtained with both C and FORTRAN routines, in both the integer version and the double-precision floating point version. The method can also be ported readily to other languages.
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.64 (March 2, 2002) is even better! See my CWEB page for full details.
I strongly urge all CWEB users to upgrade to version 3.64 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.64 corrects and improves several aspects of those early releases. My present intention is that version 3.64 will in fact be the very last upgrade (except of course for fixes to catastrophic bugs).
A glorious new printing of The Stanford GraphBase is now available from the publishers, with corrections to all known errors. More than half of the pages of the previous printing have been improved; and I've added a few new jokes too.
I've been making some headway at last 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.)
(Truly hardy adventurers may also wish to hunt for a sneak preview of the next few pages.)
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). 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:
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 a recent visit to Norway I was able to complete tracing my ``academic genealogy,'' namely to learn the names of my thesis advisor's advisor's advisor's ... advisor, as far back as I'll ever be able to go:
My dear friend Ole-Johan Dahl passed away this year --- during the same week as my mother, in fact --- and while I was in Norway I received from Knut Holmqvist a wonderful memento: excerpts from the time Dahl and I played a four-hands-piano arrangement of Gershwin's Rhapsody in Blue, on the day when the University of Oslo's new Institute for Informatics building was dedicated (19 September 1988). Here are those clips, as a QuickTime movie (5MB gzipped).
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:
Don Knuth's home page
