[click here to zip down to the
schedule of public lectures]
Fascicles for The Art of Computer Programming
Hurray, hurray: After many years of preparation, at last I can report
the publication of new material for my books on
The Art of
Computer Programming, first released in paperback on Valentine's Day
of last year. ``Volume 1 Fascicle 1,'' a programmer's introduction to the
MMIX computer, is an update to
Sections 1.3 and 1.4 of Volume 1, Fundamental Algorithms,
planned for inclusion in the eventual fourth edition of that volume.
``Volume 4 Fascicle 2'' contains sections 220.127.116.11 and 18.104.22.168 of
Volume 4, Combinatorial Algorithms, a work in progress.
``Volume 4 Fascicle 3,'' published last August,
contains sections 22.214.171.124--126.96.36.199 of Volume 4.
And early in February I received my copy of ``Volume 4 Fascicle 4,''
containing sections 188.8.131.52--184.108.40.206.
If all goes well, Volume 4 Fascicle 0 will be ready in early 2007.
More sneak previews of Volume 4
Early drafts of some of the forthcoming fascicles are also
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.)
(If you have trouble downloading these files, your browser is probably
screwing up; please see
my FAQ page
for a workaround.)
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.1.1--83 (an online algorithm for optimum server locations)
- 7.1.1--116 (functions with conjectured maximum number of prime implicants)
- 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--36 and 37 (efficient prefix computation with small depth)
- 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--10 and 12 (multiplication and division in Conway's field)
- 7.1.3--14 and 16 (branching functions and animating functions)
- 7.1.3--19 (Paley's amazing rearrangement inequalities)
- 7.1.3--58 (characterization of Omega-routable permutations)
- 7.1.3--75 (improvement of Ofman's mapping netword)
- 7.1.3--83 (shifting a scattered accumulator to the right)
- 7.1.3--91 (alpha channels without multiplication)
- 7.1.3--110 (powers of two in O(lg lg n) bitwise steps)
- 7.1.3--124 (lower bounds on a basic RAM)
- 7.1.3--158 and 159 (Fibonacci and negaFibonacci codeword manipulation)
- 7.1.3--173 (cleaning up thresholded raster images)
- 7.1.3--179 (online algorithm for components of a bitmap)
- 7.1.3--186 (fast three-register algorithm for quadratic B\'ezier splines)
- 220.127.116.11--97 (analysis of a coroutine-based algorithm)
- 18.104.22.168--99 (decoding a recursively generated de Bruijn cycle)
- 22.214.171.124--25 (proof of van Zanten's theorem)
- 126.96.36.199--33 (enumeration of genlex listings for index lists)
- 188.8.131.52--42 (analysis of an algorithm for near-perfect combination generation)
- 184.108.40.206--63 (minimal-change algorithm for contingency tables)
- 220.127.116.11--100 (the heaviest multicomplexes)
- 18.104.22.168--18 (two versions of Zeilberger's one-to-one correspondence for joint partitions)
- 22.214.171.124--28 (Lehmer's fabulous formulas, to be checked empirically)
- 126.96.36.199--47 (Nijenhuis and Wilf's algorithm for random partitions)
- 188.8.131.52--56 (my algorithm for partitions in an interval of the majorization lattice)
- 184.108.40.206--28 and 29 (theory of generalized rook polynomials)
- 220.127.116.11--19 (proof that Skarbek's algorithm is dual to lexicographic generation)
- 18.104.22.168--25 (my new prune-and-graft method of generating all linked binary trees)
- 22.214.171.124--26, 27, 28 (basic facts about three important lattices of trees)
- 126.96.36.199--33 (representing binary tree links with a single permutation)
- 188.8.131.52--37 (analysis of the Zaks--Richards algorithm for trees by degrees)
- 184.108.40.206--60 (an algorithm to invert the Chung--Feller mapping)
- 220.127.116.11--99 (quick Gray code to list spanning trees of a series-parallel graph)
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
if you have time to provide this extra help. Thanks in advance!
A Recent Bio/Profile from Stanford Magazine
at First Byte by Kara Platoni
Farewell, Old Friend
My father-in-law, Dr. James W. Carter, passed away peacefully in
November at the age of 93. Here is a brief
about his life and work.
During our summer vacation in 2003, 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.
Did you borrow a video from me?
Videotapes of most of my
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.
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
- Tuesday 10 January, 6pm, at
Café Scientifique Palo Alto
- ``All Questions Answered''
- Tuesday 21 March, 8:45am
- Participating in a panel discussion to reminisce about the past
forty years, as part of the
40th anniversary celebration
of Stanford's Computer Science department
- Monday 12 June, 5pm, in the large auditorium
- Public lecture ``The Joy of Technical Illustration'' at the
American University of
- Tuesday 13 June, 5pm, in the large auditorium
- Public lecture ``Literate Programming'' at the
American University of
- Friday 30 June, 10:00am in room CS 1.04
- informal lecture ``Boolean footprints'' at the
The University of Warwick's
Department of Computer Science
- Monday 3 July, 4:00pm at the
Oxford University Comlab
- ``Boolean footprints''
- Tuesday 24 October, 5:30pm, in Skilling Auditorium
Computer Musing lecture entitled
``Platologic computing'' [subsequently renamed ``Broadword computing'']
- Wednesday 6 December, 4:30pm, in Skilling Auditorium
Computer Musing lecture entitled
``Trees, Rivers, and RNA,'' the twelfth annual Christmas tree lecture
Click here for the ``recent news'' that was current at the end of 2005, if you're interested in old news as well as new news.