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 non-specialists.
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 high-level picture, without sweeping the
details entirely under the rug.
The next talk in the series will be entitled
Hamiltonian Paths in Antiquity (The 22nd Annual Christmas Lecture)
and the date will be
Thursday, December 8, 2016
and the time will be 6:00pm.
Please note that this lecture will
be held in Huang Engineering Center's NVIDIA Auditorium, not
in the CS building.
The talk will also be streamed live as a webinar from
Stanford's Center for
Professional Development.
About 1850, William Rowan Hamilton invented the Icosian Game, which
involved finding a path that encounters all points of a network
without retracing its steps. Variants of his game have turned out
to be important in many modern computer applications.
The speaker will give evidence that people have been interested
in such questions since at least Graeco-Roman times. Furthermore,
ingenious Sanskrit and Arabic documents from the ninth
century, and continuing through medieval times, also
reveal that this is perhaps the oldest nontrivial
combinatorial problem in the history of civilization.
Musings Online
Great news! Videotapes were made of many past lectures in this
series, and the
Stanford Center for Professional
Development has offered to host a permanent archive of digitized
versions, freely
viewable from their website.
This work is still in progress, but dozens of webcasts are already
ready for streaming. Many of these are in fact also available via
iTunes!
Here is a reverse-chronological 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 03 2015
- ***Universal Commafree Codes (see the
COMMAFREE-EASTMAN 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
SKEW-TERNARY-CALC 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.6--105 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.5--27 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.6--103 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.5--62 and 7.2.1.5--55(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 7--137 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 (black-and-white version);
Compressed PostScript (color version);
Wassermann's beautiful solutions to the Aztec Diamond challenge
- Mar 3 1999
- ***The MMIX architecture simulator: A testbed for
buzzword-compliant 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 Garsia-Wachs algorithm]
CWEB program for experiments
- Oct 27 1998
- ***Constructing bubblesort at random: one-dimensional particle physics [see
Sorting and Searching, 2nd edition,
exercise 5.3.4--40]
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.2--28]
- Oct 8 1996
- Sorting genomes, a simple problem about DNA
[see errata to Volume 3, new exercises
5.1.4--41,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.3-23]
- Nov 7 1995
- a randomized adversary for computing the median
[see errata to Volume 3, new exercise 5.3.3-26]
- 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
[videotape available (cheap!) from
University Video Communications]
- Nov 16 1993
- two-way 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 Gosper-Zeilberger 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 high-level 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 360-year-old 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
Don Knuth's online publications
Don Knuth's home page