Donald Knuth's Christmas Lecture 2023
Written by Mike James
Friday, 22 December 2023

It's getting to feel a lot like Xmas. Well it;s that time of year again and we have the 2023 Knuth Christmas Lecture. Can you remember when it was the Christmas Tree lecture? Well this year it's dancing cells a close relative of dancing links.

"This talk is sort of a sequel to “Dancing Links”, the Christmas Lecture of 2018, because there have been surprising new developments since then—stimulated by the work of Christine Solnon at INSA de Lyon."

I have to admit that I feel slightly unhappy about dancing links because it's a sort of "use after free". In this case the idea is not to free a node just in case you need to backtrack and undo the changes you have made.

"The dancing links idea is a simple modification of a 60-year-old method (doubly linked lists), which is particularly suited to undoing. As a result, algorithms based on dancing links have become the method of choice for exploring the set of solutions to a huge variety of combinatorial problems. The dancing cells idea, similarly, is a simple modification of a 30-year-old method (sparse-set representation), and it provides efficient support for that same wide class of applications. Indeed, programs based on dancing cells often turn out to be significantly faster than the analogous programs based on dancing links. And again, there is exquisite choreography!"

The idea is to subject a sparse-set to the same use after free trick. A sparse-set is an array which stores not the integers in the set but indicators of where the set element is stored in a dense array arrangement.  What is remarkable is that it doesn't matter what is stored in the elements of the sparse-set that do not reference elements actually in the set.This means that it doesn't matter how you initalize the sparse set and you never have to process the entire list of elements to say clear the set.  Lookup sparse sets because they are very interesting and potentially useful data structures. The dancing cell idea builds on the fact that cells that are not referencing elements of the set can have anything stored in them so why not the make use of this by not initializing them when you need to modify the set. This makes backtracking easy again.

Happy holidays.

Computer Musings

#### Related Articles

Yoda's (Donald Knuth) Xmas Lecture 2018

Knuth's 25th Christmas Lecture - Pi And The Art Of Computer Programming (2019)

No Donald Knuth Christmas Lecture This Year (2020)

Donald Knuth's Xmas Lecture Is Back (2022)

Donald Knuth's Christmas Tree Lecture 2017

Knuth's 22nd 360 Degree Not Christmas Tree Lecture

Knuth's 21st Not Christmas Tree Lecture

Donald Knuth's Christmas Tree Lecture

Donald Knuth's Christmas Tree Lecture

Donald Knuth and the Art of Programming

 Amazon Ending Alexa Skills Payments12/04/2024Amazon has told developers who are signed up to the Alexa Developer Rewards Program that their monthly payments will end at the end of June. The announcement follows a decision to end the program unde [ ... ] + Full Story Azure AI And Pgvector Run Generative AI Directly On Postgres26/03/2024It's a match made in heaven. The Azure AI extension enables the database to call into various Azure AI services like Azure OpenAI. Combined with pgvector you can go far beyond full text search. Let's  [ ... ] + Full Story More News