Donald Knuth’s Christmas Tree Lecture on Dancing Links — and Organ Music – InApps Technology 2022

For the last 24 years, computer science legend Donald Knuth has been delivering an annual Christmas lecture at Stanford University, where he’s a professor emeritus. Over the last few years, videos have begun quietly appearing on the web, letting the rest of the world watch, which is almost like visiting an old friend for the holidays.

“God I love this man,” posted one commenter on YouTube, adding “Keep cranking it out, Don!”

The New York Times profiled the revered 80-year-old mathematician last week as the “Yoda of Silicon Valley” and “the spirit-guide of the algorithmic realm.” It would be fair to say that Knuth literally wrote the book on algorithms — specifically, his masterwork, “The Art of Computer Programming,” which he has released in installments for the last 56 years. Knuth retired in 1993 — at age 55 — to focus on finally finishing it. He says it will take him another 25 years to finish the book — although the Times points out he’s been saying that for almost 40 years.

On Tuesday, Dec. 4, the 80-year-old mathematician again stepped into the Nvidia Auditorium at Stanford’s Huang Engineering Center — wearing his traditional Christmas sweater. “Tonight I’m going to talk about a few things that are technical,” he tells his audience, “but mostly its Show and Tell.” (Meaning he’ll quickly demonstrate things to tempt his audience to look them up later.)

The lecture feels festive — like an eagerly-awaited event. He’s speaking on the Christmas-y theme of “dancing” links, an idea first invented in 1979, but later popularized by Knuth in a paper published in 2000 — and in that year’s annual Christmas lecture, “Before this particular room was built.” He describes it as “an idea so simple, you might say, ‘How could anybody talk for more than five minutes about this idea?’”

It expands on the basic computing concept of a linked list — a sequence of data structures containing not only values, but also the locations for the next and previous value in the sequence. If you picture a grid of data in rows and columns, each row (or column) could be represented by a linked list. The classic problem is to select a subset of rows which would leave you with a value in each column — but with no duplicates. Knuth draws out a grid, then presents a surprisingly simple technique for finding the solution. “When you look at it, it just seems that these numbers in the computer are following an elegantly-choreographed dance, and so that’s why I call it dancing links.”

It’s evident he takes real joy in algorithms, and Knuth admits that he’s like a kid with a new toy at Christmas. “Because I have this technology of dancing links that I can use to solve problems that I never thought I would solve in my lifetime.” And then he drew a laugh and applause by warning the audience that unfortunately, “It’s completely orthogonal to deep learning.”

Knuth has already written 350 pages about it for the next installment of his book. He also mentions his other book — “Selected Papers on Fun and Games” —”Which is a really great book to give for Christmas.”

But he’s quickly moved on to similar algorithms which solve other problems. He shows a photo illustrating the problème des ménages puzzle, which has 13 solutions. He bounces to P.A. MacMahon’s triangles puzzle from 1892. Then he tells the story of Stanford’s AI lab back in 1964, when one of its first large computations ever was performed — documenting the MacMahon Squares problems. (After running for 40 hours, Stanford researchers calculated that there were 12,261 solutions.) It was a fact re-published “in lots of publications throughout the 1960s,” Knuth tells his audience — adding “It turned out that it was wrong.”

It all leaves you thinking that it must be fun to be Donald Knuth. By the end of his talk he’s talking about the Partridge problem — so named because mathematician Bob Wainwright was thinking of the numerical pattern in the “Twelve Days of Christmas” song. Even word search puzzles make an appearance, as Knuth wonders out loud if he should save something for next Christmas’s lecture. He touches on music, dominos, coloring problems, trees of letters — and even Sudoku-like games like KenKen and Kakuro. About an hour in he starts playing with a Christmas gift that I remembered from my own childhood — a Soma cube — said to have been the first non-square object ever rendered.

Other Interests

Beyond algorithms, Knuth has taken an interest in a wide range of ephemera. In 2012, Knuth and his wife took leisurely drives through Ohio photographing every diamond-shaped highway sign that they saw on the highway. They’re now part of a 1,150-photo collection — some contributed from fans online — each with their GPS coordinates.

The Times looked back even further, including touching photographs of young Donald Knuth, holding a black cat — or the copy of Mad magazine that published the nonsensical “Potrzebie System of Weights and Measures” that he wrote when he was 19. 61 years later, we’re living in a world where Google has implemented conversions from the Potrzebie system as part of their search engine (It’s a feature they apparently launched 10 years ago to celebrate Knuth’s 70th birthday).

The Times recalled that after high school, Milwaukee-born Knuth studied at Case Western Reserve University, where “He became a computer scientist before the discipline existed.” He even managed the basketball team, running statistics he gathered through one of IBM’s very mass-produced computers, the IBM 650 — a feat celebrated by a short IBM newsreel applauding “Donald Knuth, student mathematician” helping his “electronic coach”.

He was already earning more than his professors by writing compilers, according to the Times. But maybe his roots go even further back. Knuth’s father had been a teacher — teaching bookkeeping at the local high school — and also owned a printing business, foreshadowing some of the future interests of his son, including pioneering work in the 1970s in digital typesetting.

According to one biography, Knuth’s father had also played the organ — on Sunday’s Knuth would see his father playing the organ at their church. The biographer writes that “Donald inherited his father’s appreciation of music and education, particularly patterns in language.” Another biography quotes Knuth as saying “Mathematics is the science of patterns. Music is patterns.”

As a teenager in the 1950s Knuth had even thought about a career in music, but after World War II, “The system channeled anybody with an aptitude for science into physics.” He got a full scholarship to Case Western, where his interests began to change. “He soon realized that he loved math more than physics, specifically the area of discrete mathematics.” Eventually, he’d earned a Ph.D. from CalTech, where he then began working as an associate professor and exploring the new field of computer science. “A lot of the papers coming out were quite simply wrong … So one of my motivations was to put straight a story that had been very badly told.”

But he never stopped loving music. His house even has a music room with a custom-made, 812-pipe pipe organ. And in January he turned 80, an event marked by a three-day symposium titled “Knuth80: Algorithms, Combinatorics, and Information,” in the Swedish city of Piteå. “It’s impossible for me to thank adequately all of the wonderful people who contributed their time to making this event such a stunning success,” Knuth wrote on his website, calling the event “certainly one of the greatest highlights of my life.” Probably because the event culminated with the world premiere of his new multimedia work for pipe organ, “Fantasia Apocalyptica“, which Knuth describes as 50 years in the making.

Jan Overduin, organist emeritus at the First United Church in Ontario, explains in a video that the piece is filled with playful intellectual twists, calling it “a somewhat literal translation of the ancient book of Revelation.” For example, at one point there’s an excerpt from a Bach oratorio — but the melody is played in reverse. “The vision foretells the future — future events — so time is being turned around. Upside-down, topsy-turvy.” There’s even special music for the Four Horsemen of the Apocalypse. “If it’s a white horse, it will be played on the white keys,” Overduin explains. “If it’s a black horse, it’ll be played on the black keys…

“A red horse, or pale horse — well, that’s a little more tricky. I’ll give you a hint, though. For the red horse?” He plays a cheery stanza, then turns to the camera seriously and says: “Santa Claus.”

Knuth will be releasing his masterwork to the world under Creative Commons license (CC0) — “no rights reserved.”