It always feels like visiting an old friend for the holidays…
As Donald Knuth approached his 87th birthday, the computer science guru honored what’s become a long-standing tradition. He gave a December “Christmas lecture” that’s also streamed online for his fans.
But besides offering the comfort of a familiar face — a December sighting of our favorite algorithm expert demonstrating his infectious glee for math theory — this year, Knuth also included some precious and personal looks back.
So beyond playing with numbers — and yes, trees — Knuth delivered his own version of Christmas cheer: some fond memories of computer science pioneer Edsger Dijkstra and mathematician Theodore Motzkin, plus stories about a new collaboration with long-time algorithm craftsman Robert Tarjan.
Along the way, Knuth was also honoring a Christmas tradition that he’s kept for nearly three decades. And he even shared a special peek ahead at what’s coming up to his almost-finished series of textbooks, The Art of Computer Programming.
Perhaps doing it all with an extra-merry twinkle in his eye…
Knuth’s Favorite Algorithm
“I doubt if I can give a perfect lecture,” Knuth began modestly, “but I do have a lot of good stories to tell…” And the lecture was delivered just one day after he’d finally sent his publisher Volume 4’s fascicle #7 of his life’s masterwork, The Art of Computer Programming, Knuth said — before promising the audience a glimpse at what he hopes to publish in fascicle 12a.
“Who knows how long the Force will be with me,” he added with a smile, “but anyway, I’m going to keep telling these stories as well as I can.”
And then Knuth zoomed in on a footnote in that upcoming fascicle where he confides the news that he does have a favorite algorithm: Tarjan’s algorithm.
Knuth began by casually showing his audience a simple “directed” graph — where the vertices have one-way connections (indicated with an arrow). Groups of vertices can form a kind of network, with each one reachable by all its fellow network members (when traveling along those one-way connections).
But then Knuth said that he’d been there where the related concept of “weak components” was defined, showing a 1970 letter he wrote to mathematician Ronald Graham after receiving a letter from mathematician Theodore Motzkin. Knuth resolved to include Motzkin as a third joint author on their upcoming paper on the topic — only to learn days later that Motzkin had died of a heart attack at age 62 (adding him posthumously).
Answering questions from the audience later, Knuth looked back on that moment in history. “The funny thing is… You’d think this must be something that people discovered ages ago… At the time we were doing this, we thought, ‘Well, we must be rediscovering the wheel.’”
But there was still more to be discovered. It was in January of 1973 that he’d first read that beloved algorithm Robert Tarjan had created for identifying all the strong components in a directed graph.
And Knuth also shared an early review of that algorithm, which complained that its first half was “not very surprising.”
“There’s no accounting for taste,” Knuth joked to his audience
Later, Knuth showed an old copy of Edsger Dijkstra’s book A Discipline of a Programmer. “Turns out that in 1973, the same year that I learned Tarjan’s algorithm in January, Dijkstra sent me a draft of something he’d been working on, on finding the strong components of a directed graph!”
Knuth flips to Chapter 25 before revealing the punchline. Dijkstra’s solution ultimately included four additional arrays, because “It turned out that Dijkstra didn’t figure out Tarjan’s simplification…”
“He thought he had solved the problem the best possible way. But Tarjan figured out a very clever way…”
Playing a Game
Soon, Knuth was making the complicated feel as simple as a newly unwrapped Christmas present. It’s not unusual to see data linked together into a “tree” hierarchy. Soon, Knuth created what he called a depth-first forest, explaining that “a forest is a bunch of trees.”
“Most years, my Christmas lecture has something to do with trees,” he said with a smile…
After giving a letter to each vertex in his graph, Knuth created a simple list for each letter showing the other vertices it’s connecting to. While it’s complex graph theory, Knuth shared a clever way to envision it. “I think it’s a good idea to imagine that you’re playing an Adventure game. ‘You’re in a cave…’ And this cave has different rooms — A, B, C… up to O. From each room, you have different rooms you can move to…” And soon he’s helpfully demonstrating the concept of a depth-first search. (Described by Wikipedia as exploring “as far as possible along each branch before backtracking”)
As dead ends are reached, Knuth points out this can also neatly signify the terminus for our “strong component” network of vertices. And that means we can immediately remove them from further checking altogether — until, as the algorithm churns away, “we’ve removed everything.”
Or, as Knuth says later, “The beauty of it is that it’s so darn fast.”
Of course, he’s already calculated exactly how many calls to memory it takes to run this algorithm, and can deliver that number for a graph of any size. But he summarizes the beauty of this algorithm with just three words.
“It goes lickety-split.”
What comes through is his earnest goodwill for algorithms — and for the humans who have created them. When solving these problems, “It turns out to be not-so-simple to keep everything so that it’s guaranteed to be linear time, in the worst case,” Knuth says. “But the algorithm — it’s one of those, after you look at it, you say ‘Yeah, that’s deep’…
“I mean, you can get it in a day or two. But it’s not like something that I would expect ChatGPT to ever figure out.”
Knuth’s New Caveat for Premature Optimization
Knuth wrote about Tarjan’s original algorithm in a 1993 book called The Stanford Graphbase — using for his example a thousand-vertex graph representing categories in Roget’s Thesaurus. But that wasn’t the end of Knuth’s involvement with Tarjan.
It was when answering questions from the audience that there was a minor revelation: that two years ago, Knuth had reached out to 74-year-old Robert Tarjan, “and we found a better way than his original algorithm…
“It’s all explained now in my fascicle 12a.”
Nearly a half-century after Tarjan’s original algorithm, Tarjan and Knuth had teamed up. (“Tarjan noticed in 2021 that we can save time and space by encoding PRE and LOW in the existing LINK and REP fields…” Knuth writes in the pre-fascicle.) That led to a 2022 paper by Robert Tarjan and mathematician Uri Zwick, where the two authors announced they’d developed “a streamlined version of Tarjan’s strong components algorithm, from scratch.”
Previous Donald Christmas Lectures
Donald Knuth’s Christmas Lectures are an annual tradition at Stanford University. Each year in early December, the renowned computer scientist and author of “The Art of Computer Programming” delivers a lecture on a variety of topics related to computer science and mathematics, to the delight of students and greybeards alike. These talks are capture on YouTube.
Donald Knuth’s 2023 Christmas Lecture: Making the Cells Dance
Donald Knuth’s 2022 ‘Christmas Tree’ Lecture Is about Trees
Donald Knuth on Machine Learning and the Meaning of Life (2021)
Donald Knuth’s 2019 ‘Christmas Tree Lecture’ Explores Pi in ‘The Art of Computer Programming’
Donald Knuth’s 2018 Christmas Tree Lecture on Dancing Links — and Organ Music
Donald Knuth’s 2017 Christmas Tree Lecture Tackles a ‘Curious Problem’ in Combinatorial Geometry
Knuth tells his audience, “We went further, Tarjan and I… We realized that if you look at it, there was actually a little bit of fat left, and we could combine two of the fields in one. And so here we change the definition of the simpler algorithm and make it more complicated yet faster.”
After all, Knuth points out, a computer doesn’t forfeit any speed gains if the code is harder for humans to understand.
Later, Knuth provides details. “One other thing we added to this algorithm is a recognition that in many cases… you don’t have to look at all the edges of the graph because if you get to a point where you’ve already seen every vertex and you know that all of the vertices in the tree you have are in the same strong component — then you don’t have to look any further.”
“I think it’s interesting that Dijkstra thought about this hard and didn’t see the secret sauce…”
Would this lead to a historical revision of one of Knuth’s most famous observations (“I’ve been quoted as saying that premature optimization is the root of all evil in programming?”)?
Not quite.
“This was not premature optimization — this was post-mature optimization!”
Memories of Dijkstra
With five minutes left to go, a young student asks “Did you know Dijkstra personally?”
“Oh yeah…” Knuth says, prompting the student to ask what Dijkstra was like.
“His strength was his inability to compromise. And it was the kind of thing where — people wanted to have his advice, but they were afraid to have him as a colleague because — he was very much perfection.” Knuth remembers when visiting Dijkstra’s home and playing a four-handed piano piece, “I would always let him lead…”
“He was kind of like an encyclopedia. Whatever we were talking about, he would know more about it than I did.”
“But the last years of his life, he stopped writing computer programs. I thought that was really dumb. He thought it was better just to do everything with pencil and paper.”
Although as 2024’s annual Christmas lecture rollicked along, Knuth himself also made his own allowances for the noble fallibility of all of us humble humans. At one point, Knuth had realized he’d forgotten to write down a connection between two of his vertices — and quickly corrected the error while acknowledging its timeless inevitability.
“Because I’m not a computer. I’m a human being.”
Enjoy the whole talk here:
The post Donald Knuth’s 2024 Christmas Lecture: ‘Strong’ Memories appeared first on The New Stack.