| 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.
|
BASIC Turns 60 02/05/2024 On May 1,1964 the first BASIC program ran and the world was about to change. Now when we look back it is easy to be critical, but these were different times. |
Open Platform For Enterprise AI Launched 18/04/2024 A new platform aimed at building and supporting an open artificial intelligence (AI) and data community has been launched. The Open Platform for Enterprise AI (OPEA) was announced by The Linux F [ ... ] |
More News
|
Comments
or email your comment to: comments@i-programmer.info
<ASIN: 0321751043>
<ASIN:0134397606>