this post was submitted on 25 Dec 2023
27 points (96.6% liked)

Programming

16207 readers
568 users here now

Welcome to the main community in programming.dev! Feel free to post anything relating to programming here!

Cross posting is strongly encouraged in the instance. If you feel your post or another person's post makes sense in another community cross post into it.

Hope you enjoy the instance!

Rules

Rules

  • Follow the programming.dev instance rules
  • Keep content related to programming in some way
  • If you're posting long videos try to add in some form of tldr for those who don't want to watch videos

Wormhole

Follow the wormhole through a path of communities [email protected]



founded 1 year ago
MODERATORS
 

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.

When a computer program explores a large space of possibilities, it needs good data structures that are able to undo every tentative decision that has been made, thereby allowing new decisions to take their place.

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!

no comments (yet)
sorted by: hot top controversial new old
there doesn't seem to be anything here