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

(3/2)-ary Trees (The 20th Annual Christmas Tree Lecture)

and the date will be

Tuesday, December 2, 2014

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.

In previous lectures I've discussed binary trees, ternary trees, quaternary trees, etc., which are enumerated by the coefficients of important functions called generalized binomial series of order 2, 3, 4, etc. What happens when we consider generalized binomial series of order 3/2, or of other fractional orders? The answer is pretty amazing.

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 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

Valid HTML 4.01 Transitional