Study notebook

Press N to jot a timestamped note or B to pin a moment while watching.

Dancing Links: A Data Structure for Exact Covering Problems

Donald Knuth Stanford University

Professor Emeritus

1:30:25·2018·graduate level·Standalone Lecture

Donald Knuth's 24th annual Christmas lecture, detailing the elegant 'Dancing Links' algorithm and its surprising effectiveness for solving exact covering problems across diverse applications.

Systems & CS Theory & Algos Algorithms & Data Structures Probability & Information Theory combinatorics exact cover

Donald Knuth's 24th Annual Christmas Lecture: Dancing Links

Donald Knuth, Professor Emeritus

2018

Referenced inHacker News

Seminar notes & discussion

Sign in to comment

No public seminar notes on this lecture yet.

More from Donald Knuth

Faith and Science: Interactions

Stanford University

Related lectures

In Context (Clojure/Conj 2026)

Rich Hickey · Clojure/Conj

Shared subfield · Algorithms & Data Structures & Probability & Information Theory

Lecture 3b: Factorial Asymptotics, Stirling's Formula (15-750)

Ryan O'Donnell · Carnegie Mellon University

Shared subfield · Probability & Information Theory & combinatorics

Dual Averaging Method for Regularized Stochastic Learning and Online Optimization

Lin Xiao · Google

Shared subfield · Probability & Information Theory & Algorithms & Data Structures

Latent Variable models and Subset Smoothing (SIMONS-TCS-ML)

Ravi Kannan · UC Berkeley / Simons Institute

Shared subfield · Probability & Information Theory & Algorithms & Data Structures

Extremal Combinatorics Meets Algorithms and Data Structures

Parinya Chalermsook · University of Oxford

Shared subfield · Algorithms & Data Structures & Probability & Information Theory

Dynamic Programming III (MIT 6.8210, Lecture 6)

Russ Tedrake · MIT

Shared subfield · Algorithms & Data Structures & Probability & Information Theory