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.
More InformationRelated ArticlesYoda'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 The Art Of Computer Programming - A Great Present. Donald Knuth's Christmas Tree Lecture Donald Knuth and the Art of Programming To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.
Comments
or email your comment to: comments@i-programmer.info <ASIN: 0321751043> <ASIN:0134397606> |
Last Updated ( Friday, 22 December 2023 ) |