Computer Musings
I occasionally give lectures at Stanford during the academic year.
These lectures are
open to the public as well as to
students and faculty. No tuition is charged, no attendance is taken,
no credit is given.
Each talk
is independent of the others, and pitched at an audience of nonspecialists.
Sometimes I talk about difficult technical issues, but I try to minimize
the jargon and complications by stressing the motivation
and the paradigms and the highlevel picture, without sweeping the
details entirely under the rug.
Dancing Cells (the 27th annual Christmas Lecture; Wednesday, December 6, 2023)
This talk is sort of a sequel to “Dancing Links”, the
Christmas Lecture of 2018, because there have been surprising new
developments since then—stimulated by the work of Christine Solnon
at INSA de Lyon.
When a computer program explores a large space of possibilities, it needs good
data structures that are able to undo every tentative decision that has
been made, thereby allowing new decisions to take their place.
The dancing links idea is a simple modification of a 60yearold method
(doubly linked lists), which is particularly suited to undoing.
As a result, algorithms based on dancing links have become the
method of choice for exploring the set of solutions to a huge variety of
combinatorial problems.
The dancing cells idea, similarly, is a simple modification of a
30yearold method (sparseset representation), and it provides efficient
support for that same wide class of applications. Indeed, programs
based on dancing cells often turn out to be significantly faster than
the analogous programs based on dancing links.
And again, there is exquisite choreography!
Another fun talk that I hope to give before long will be entitled
Strong Components and Weak Components
and here's a brief summary:
A directed graph can often be best understood and used if we
partition its vertices into separate components of various kinds.
Most important are the strongly connected components,
called “strong components” for short;
and strong components are in turn partitioned into “weak components.”
Two definitions of weak components have appeared in the literature of
graph theory. One of them is rather weak and uninteresting, while the
other is becoming more and more relevant and appreciated
(see the discussion here).
Basically, the strong components are the smallest clusters of vertices that
you can shrink to a point and obtain a dag, a digraph with no oriented
cycles. The weak components, correctly defined, are the smallest clusters that
you can shrink to a point and obtain an oriented path.
I'll discuss Tarjan's beautiful algorithms for computing the strong and
weak components of a given directed graph. (This will be fun because
my personal favorite, among all of the algorithms of all kinds that I've
ever encountered so far in my life, is his method for discovering
the strong components as it explores the graph.)
Furthermore, if time permits, I'll disclose the answer to the following riddle:
In what major world city are shirts of size XL smaller than shirts of size L?
Musings Online
Great news! Videotapes were made of many past lectures in this
series, and the
Stanford Center for Professional
Development has for a long time made them freely available as part
of the "stanfordonline" channel on YouTube. Captions
are now available too. You can
find them on their website;
or you can use the following convenient playlists that they've prepared,
showing all of the videos in the collection:
 The Christmas Lectures

(twentythree videos)
 Other Computer Musings

(thirtyseven videos)
 The "Aha" Sessions (Stanford's "classic" problem solving course CS204, as it was captured in 1985)

(twentytwo videos)
 TeX for Beginners (a oneweek intro, from February 1981 when TeX was brand new)

(five videos)
 Advanced TeXarcana (a oneweek course from March 1981 when TeX was brand new)

(five videos)
 TeX82 (an intensive course about the internal details, 2830 July 1982)

(twelve videos)
 Complete playlist incorporating all of the above

(more than 100 videos)
Here is a reversechronological list of all previous lectures in the series.
If I subsequently wrote a related paper on the topic, the number of that paper
in my
list of publications
is given in brackets. Links to downloadable source files are also
shown when the sources are available.
Lectures available online are
marked with "***".
 Dec 07 2022
 ***Twintrees, Baxter Permutations, and Floorplans
(see exercises MPR135 and 7.2.2.1372 in
The Art of Computer Programming)
 Dec 05 2019
 ***Pi and The Art of Computer Programming
 Dec 04 2018
 ***Dancing Links (see the
preliminary draft manuscript)
(also look for "DLX" in my collection of
downloadable programs)
 Dec 07 2017
 ***A Conjecture That Had To Be True
(American Mathematical Monthly problem 12005 was published in 2017; its solution was published in August 2019)
 Dec 08 2016
 ***Hamiltonian Paths in Antiquity (see the
preliminary draft manuscript)
 Dec 03 2015
 ***Universal Commafree Codes (see the
COMMAFREEEASTMAN program)
 Dec 02 2014
 ***(3/2)ary trees (see the
Mathematica source file christmas20.m
and the
sample run shown during the talk)
 Dec 09 2013
 ***Planar Graphs and Ternary Trees (see the
SKEWTERNARYCALC program)
 Dec 14 2012
 ***Trees and Chordal Graphs
 Dec 08 2011
 ***Bayesian Trees and BDDs (see the
TREEPROBS program)
 Dec 06 2010
 ***Why Pi?
 Dec 08 2009
 ***Spanning Trees and Aspects;
based on exercise 7.2.1.6105 of
The Art of Computer Programming
 Dec 09 2008
 ***Fun With ZDDs;
based on material to appear in Section 7.1.4 of
The Art of Computer Programming;
see also the downloadable program
BDD15
 Jun 05 2008
 ***Fun With Binary Decision Diagrams (BDDs);
based on material to appear in Section 7.1.4 of
The Art of Computer Programming;
see also the downloadable program
BDD14
 Dec 03 2007
 ***Sideways Heaps;
based on material to appear in Section 7.1.3 of
The Art of Computer Programming
 Jun 06 2007
 ***Cool graphs [based on Section 7 of
The Art of Computer Programming]
 Dec 06 2006
 ***Trees, Rivers, and RNA (an exposition of the remarkable constructions
in the downloadable programs
ZEILBERGER, FRANÇON, VIENNOT)
 Oct 24 2006
 ***Platologic Computation [subsequently renamed "Broadword Computation";
based on material to appear in Section 7.1.3 of
The Art of Computer Programming]
 May 06 2005
 ***Integer Partitions and Set Partitions: A Marvelous Connection
[to appear in exercise 7.2.1.527 of
The Art of Computer Programming; see also the CWEB
program VACILLATE]
 Dec 13 2004
 ***Sand Piles and Spanning Trees [to appear in exercise 7.2.1.6103 of
The Art of Computer Programming; see also the CWEB
program SAND]
 Oct 29 2004
 ***Hooray for Probability Theory (an exposition of the forthcoming
exercises 7.2.1.562 and 7.2.1.555(b) of
The Art of Computer Programming)
 Dec 16 2003
 ***Finding All Spanning Trees [to appear in Section 7.2.1.6 of
The Art of Computer Programming; relevant CWEB programs
are GRAYSPAN,
SPSPAN,
GRAYSPSPAN,
SPGRAPH,
and a MetaPost source file for the
documentation]
 Oct 17 2003
 ***Notation [see the reprint of P137 in
Selected Papers on Discrete Mathematics,
Chapter 2]
 Feb 14 2003
 Ramanujan's cool proof of Bertrand's postulate
 Dec 3 2002
 ***Chains of Subsets [to be discussed in Section 7.2.1.6 of
The Art of Computer Programming]
 Apr 23 2002
 Topological Sorting Revisited [see Algorithm 7.2.1.2V in
The Art of Computer Programming]
[If you are the person who borrowed the master tape, please
please return it so that Stanford can put this lecture online!]
 Dec 06 2001
 Totally Acyclic Digraphs (Spiders) and how to squish them
[see the reprint of P160 in
Selected Papers on Computer Languages,
Chapter 25, and the program
SPIDERS]
[If you are the person who borrowed the master tape, please
please return it so that Stanford can put this lecture online!]
 May 10 2001
 Twisted Toruses: or, Tori! Tori! Tori! [will eventually be
discussed in exercise 7137 of
The Art of Computer Programming]
[If you are the person who borrowed the master tape, please
please return it so that Stanford can put this lecture online!]
 Dec 5 2000
 ***Trees, Forests, and Polyominoes [see the
POLYENUM and
DAGENUM programs]
 May 30 2000
 ***The joy of asymptotics [see the Addendum to Chapter 21 in
Selected Papers on Analysis of Algorithms]
 Feb 22 2000
 ***Dancing links [P159]
TeX file of the paper;
MetaPost illustrations (B&W);
MetaPost illustrations (color);
Compressed PostScript (blackandwhite version);
Compressed PostScript (color version);
Wassermann's beautiful solutions to the Aztec Diamond challenge
 Mar 3 1999
 ***The MMIX architecture simulator: A testbed for
buzzwordcompliant pipelines
 Feb 9 1999
 ***MMIX: A RISC Computer for the New Millennium
 Dec 3 1998
 ***Trees and alphabetic codes [see
Sorting and Searching, 2nd edition,
Section 6.2.2, the GarsiaWachs algorithm]
CWEB program for experiments
 Oct 27 1998
 ***Constructing bubblesort at random: onedimensional particle physics [see
Sorting and Searching, 2nd edition,
exercise 5.3.440]
program for experiments,
and another one
 Jan 20 1998
 ***Fast I/O with many disks, using a magic trick [see
Sorting and Searching, 2nd edition,
Section 5.4.9]
 Dec 3 1997
 ***Lattices of Trees, part I
 Oct 29 1997
 ***35 years of (linear) probing [P158]
TeX file;
video archive of lecture
 Dec 10 1996
 J. J. Sylvester and the matrix tree theorem
[see errata to Volume 1, new exercise
2.3.4.228]
 Oct 8 1996
 Sorting genomes, a simple problem about DNA
[see errata to Volume 3, new exercises
5.1.441,42,43]
 May 3 1996
 Shellsort with three increments: an instructive analysis [P157]
TeX file
 Dec 5 1995
 frieze patterns and trees
[see errata to Volume 1, new exercise 2.323]
 Nov 7 1995
 a randomized adversary for computing the median
[see errata to Volume 3, new exercise 5.3.326]
 Oct 17 1995
 random number generators with quantitative guarantees of quality
[see errata to Volume 2, new material in Section 3.5]
 Apr 25 1995
 sorting by shorting: Knowlton and Graham's method for
identifying wires in cables [P154]
TeX file
 Feb 28 1995
 generalized determinants and their relation to perfect matchings [P156]
TeX file
 Jan 24 1995
 stable allocation and its relation to uniform hashing [P149]
TeX file
 Dec 6 1994
 more fun with binary trees: recursive arithmetic on gigantic numbers
CWEB file
 Nov 8 1994
 independent intervals: an unusual minimax algorithm [P151]
CWEB file;
change file
 Oct 11 1994
 how to count spanning trees [P150]
TeX file
 Apr 5 1994
 leaper graphs: generalized knights of the rectangular table [P147]
TeX file
 Nov 30 1993
 ***the associative law, or the anatomy of rotations in binary trees
 Nov 16 1993
 twoway rounding and its surprising connection to network flows [P145]
TeX file
 Oct 26 1993
 the birth of the giant component (the seeds of chaos) [P140]
TeX file
streaming video of similar talk given in 1999
 Oct 12 1993
 the GosperZeilberger algorithm: a breakthrough in summation technology
 May 4 1993
 some EMACS hacks to make your fingers more powerful
 Apr 6 1993
 technical illustrations with
MetaPost:
a highlevel language for PostScript graphics
[examples]
 Feb 16 1993
 knight's tours revisited
 Jun 2 1992
 $1^m+2^m+\cdots+n^m$ and all that: fascinating facts about power sums,
and the solution of a 360yearold riddle [P142]
TeX file
 May 12 1992
 convolution polynomials: their amazing properties and numerous applications
[P141]
TeX file
 Mar 10 1992

The Stanford GraphBase:
A platform for combinatorial computing
 Feb 11 1992
 why
CWEB
might become your favorite programming language
 Jan 28 1992

MMIX 2009:
a RISC computer for the third millennium
``It was a musing.''  Peter Gordon