Stanford Lecture: Don Knuth—"Hamiltonian Paths in Antiquity" (2016)

Computer Musings 2016
Donald Knuth's 23rd Annual Christmas Tree Lecture: "Hamiltonian Paths in Antiquity"
Speaker: Donald Knuth

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.

About the Speaker:
Donald Ervin Knuth is an American computer scientist, mathematician, and Professor Emeritus at Stanford University.

He is the author of the multi-volume work The Art of Computer Programming and has been called the "father" of the analysis of algorithms. He contributed to the development of the rigorous analysis of the computational complexity of algorithms and systematized formal mathematical techniques for it. In the process he also popularized the asymptotic notation. In addition to fundamental contributions in several branches of theoretical computer science, Knuth is the creator of the TeX computer typesetting system, the related METAFONT font definition language and rendering system, and the Computer Modern family of typefaces.