Dynamic programming at ease - with Grammars, Algebras, Products
summary
Claim: dynamic programming for sequences becomes index-free and modular by describing candidates as tree grammars, scoring/choice as evaluation algebras, and composing objectives with products of algebras. The compiler Bellman's GAP generates efficient code that handles tabulation and backtracking, turning exponential search into polynomial table fills. Examples include coin-change, Boggle, string alignment and RNA folding; products let the system compute best score and simultaneously print candidates or count co‑optimal solutions, and the approach is already implemented and used on molecular structure prediction.
AI-written summary · about
chapters (24)
- 0:00Combinatorial Optimization Problems
- 1:54Classic Dynamic Programming
- 6:21Overview
- 6:56Reverse engineering of DP algorithms
- 11:24Reverse Engineering Summary
- 12:27Reverse engineering - reversed :D :D
- 14:38The Signature
- 16:00Evaluation algebras
- 16:28Choice Functions
- 17:44Scoring schemes
- 18:40Scoring alingments
- 19:36Problem variants: Affine gaps and local alignment
- 20:39Building blocks of RNA
- 22:40Counting solutions: RNA structures
- 24:35Programs are grammars
- 26:03Problem specification
- 26:38Bellman's Principle of Optimality
- 27:45Phase amagalmation
- 28:58Where do we stand? (revisited)
- 30:00Products of algebras
- 30:38Semantics of
- 31:30Fun things to do with products
- 34:01Tools developed with ADP
- 34:42What's cool about Algebraic Dynamic Programming?
related talks
17mGuiding Dynamic Programing via Structural Probability for Accelerating Programming by Example
40mDynamic programming - 101
32mCompilation of Dynamic Sparse Tensor Algebra
57mSolutions That Evolve: Building Self-Improving Systems with Genetic Algorithms
40mGenetic Programming in Clojure
01h 07mParallel-by-construction Tree Manipulation with APL (Part 2)
55mParallel-by-construction Tree Manipulation with APL (Part 1)
18mJavaScript and Artificial Intelligence