LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Dancing Cells
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Dancing Cells

93 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
STANFORD

Donald Knuth delivers his 27th Annual Christmas Tree Lecture at Stanford, presenting a sequel to his 2018 talk on Dancing Links. He introduces dancing cells, a modification of the thirty-year-old sparse-set representation technique, built to solve the same problem dancing links addresses: how a computer program exploring a huge space of possibilities can efficiently undo tentative decisions and backtrack to try new ones. Knuth credits the recent developments to Christine Solnon's work at INSA de Lyon and walks through why programs built on dancing cells often run significantly faster than their dancing-links counterparts when searching for solutions to combinatorial problems. The talk runs ninety-three minutes and assumes some comfort with data structures and algorithmic search, rewarding anyone who wants to see a veteran computer scientist work through a concrete technical improvement step by step, with his characteristic attention to the elegance of the underlying choreography.

At a glance

Lecture facts

Runtime compared with the other 734 Mathematics lectures
Runtime1 h 33 m
Compared with MathematicsLonger than 92%
Source channelStanford Online (YouTube)