| 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.
|
| Last Updated ( Friday, 22 December 2023 ) |
