TNS
VOXPOP
Where are you using WebAssembly?
Wasm promises to let developers build once and run anywhere. Are you using it yet?
At work, for production apps
0%
At work, but not for production apps
0%
I don’t use WebAssembly but expect to when the technology matures
0%
I have no plans to use WebAssembly
0%
No plans and I get mad whenever I see the buzzword
0%
Tech Culture

Donald Knuth’s 2023 Christmas Lecture: Making the Cells Dance

How a "memorable homework" problem from a 1974 computer science book inspired a much more efficient way to sort sets.
Dec 24th, 2023 6:00am by
Featued image for: Donald Knuth’s 2023 Christmas Lecture: Making the Cells Dance
Stanford University livestream

It’s like visiting an old friend for the holidays…

Approaching his 86th birthday, Donald Knuth — Stanford’s beloved computer science guru — honored what’s become a long-standing tradition. He gave a December “Christmas lecture” that’s also streamed online for all of his fans.

“Old-timers like me, in our hubris, we used to think that all the important data structures were well-understood by 1970 or 1980,” Knuth joked to his audience. “So, no need to learn anything more.

“But what I’m talking about today is something that I learned three years ago…”

The Curious Mind of Donald Knuth

It’s all proof that there’s always more fun mathematical surprises to explore. More than 60 years ago, back in 1962, a 24-year-old Donald Knuth first started writing The Art of Computer Programming — a comprehensive analysis of algorithms which, here in 2023, he’s still trying to finish.

And 30 years ago Knuth also began making rare live appearances each December in front of audiences of Stanford students. Five years ago the New York Times dubbed Knuth “the spirit-guide of the algorithmic realm,” and there’s something special about seeing him live, sharing his own personal brand of thoughtful analysis.

As the decades rolled along, Knuth continued offering his smiling, gentle inquisitiveness.

Recently Stanford uploaded several decades of Knuth’s past Christmas lectures, along with a series of 22 videos of Knuth from 1985 titled “the ‘Aha’ Sessions'” (courses in mathematical problem-solving). There are also two different sets of five videos from 1981 showing Knuth introducing his newly-created typesetting system TeX. There are even 12 videos from 1982 of what Knuth calls “an intensive course about the internal details.”

And on Dec. 6, wearing his traditional brown holiday sweater, Knuth gave yet another live demonstration of the beautifully clear precision that’s made him famous…

Beyond ‘Dancing Links

So what’s the topic for this year?

Beginning programmers are taught about linked lists — where every element in the list contains not only a value, but also the location for the next and previous elements. Knuth helped popularize a way of moving through those elements where “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.” Knuth discussed them in 2018, and this year’s lecture was described as a kind of sequel.

“We’ve improved dancing links now to something that has the jazzy name dancing cells.”

And then, like the Ghost of Christmas Past, Knuth looked back nearly half a century. “The whole story starts with one of the first really great books on computer science,” he told the audience, putting up his own dog-eared copy of The Design and Analysis of Computer Algorithms, by Alfred Aho, Jeffrey Ullman, and John Hopcroft.

That 1974 book included an exercise challenging readers to find a way to always initialize a matrix’s values to zero when they’re first accessed. And the solution turned out to be both clever and unexpectedly useful. It involves keeping a much smaller list of only those values which are known.

Nearly 20 years later, a 1993 paper revisited the idea. It had proved to be especially helpful in a real-world application: handling values in memory when implementing a compiler. The paper even references that 1974 textbook, noting their solution was “inspired by a memorable homework problem…”

“In other words,” Knuth observes wryly to his audience, “homework problems actually do get noticed somehow.”

The 1993 researchers had also added a clever operation for deleting values — and Knuth included a discussion of it in the latest update to his Art of Computer Programming, volume 4B (just released in 2022). “It makes a wonderful Christmas present,” Knuth joked to his audience — drawing some appreciative laughter.

But it was also a chance for Knuth to demonstrate some remarkably efficient data handling…

 Donald Knuth demonstrates dancing cells in 2023 Christmas Lecture (screenshot from Stanford Online video)

It turns out there’s an incredibly easy way to delete a value in a list of numbers: just swap it with whatever number appears in your list’s last position — and then, shorten the length of your list by one. All numbers with a position beyond the length of your list are now known to have been deleted — and they form a handy cluster of all the deleted values. Because of a naturally occurring pattern, they even appear in order — with the most recently deleted numbers appearing first.

This has yet another added benefit. Knuth then created a second list, holding the number for each digit’s position in that first list. Then you can tell if a number’s been deleted or not from that first list — just by whether or not its position number is higher than the length of the list!

“So as the algorithm proceeds, these numbers in here do a little dance.” It’s like the “dancing links” algorithm that charted paths through a doubly-linked list, but now it’s tracking “deleted” or “undeleted” status. So for this phenomenon, computer science professor Christine Solnon came up with a better name: “dancing cells.”

Then Knuth jumped through time, to a 2013 paper that recognized this idea’s importance…

The Grand Finale

Knuth launched into an explanation of the concept of constraint satisfaction problems — whether all requirements can be met for the values of various variables, or whether all Boolean variables can be true. Knuth drew a warm laugh by telling his audience that once created, some of these models can be applied to an infinite set of values. “But that’s way beyond me. I’m a finite guy.”

There’s a third subset of problems that involves covering a map with colors, which Knuth jokes is a topic so obscure that “As of today, it still doesn’t have a Wikipedia page… Which is a shame,” he adds — because it’s the subject of half of 4th volume of The Art of Computer Programming. “I’m waiting for people to realize what a great thing this is”.

The lecture culminates by showing how such problems can be solved using “dancing cells” algorithms — which in many cases are more efficient and speedier than the old “dancing links” algorithm, sometimes by a factor of 20.

Knuth says he might give a future lecture to popularize the idea — just to help the world catch up. But beyond that, “I don’t have time to wait.

I have to write more books.”


Previous Donald Knuth Christmas Lectures

Group Created with Sketch.
THE NEW STACK UPDATE A newsletter digest of the week’s most important stories & analyses.