Explore dynamic programming techniques for solving combinatorial optimization problems in this conference talk from Strange Loop. Learn how to tame exponentially complex problems using tabulation and Bellman's principle of optimality. Discover a formal framework for specifying dynamic programming algorithms on sequences using tree grammars and evaluation algebras. Gain insights into Bellman's GAP, a programming language derived from this formalism, which allows for abstract problem description while generating efficient programs. Examine real-world applications in molecular structure prediction and learn how to apply these concepts to various dynamic programming challenges. Delve into topics such as reverse engineering DP algorithms, evaluation algebras, scoring schemes, problem variants, and the semantics of algebraic dynamic programming. Understand how to leverage these techniques to solve complex problems in text search, pattern matching, route finding, and biological sequence analysis more efficiently.
Overview
Syllabus
Combinatorial Optimization Problems
Classic Dynamic Programming
Overview
Reverse engineering of DP algorithms
Reverse Engineering Summary
Reverse engineering - reversed :D :D
The Signature
Evaluation algebras
Choice Functions
Scoring schemes
Scoring alingments
Problem variants: Affine gaps and local alignment
Building blocks of RNA
Counting solutions: RNA structures
Programs are grammars
Problem specification
Bellman's Principle of Optimality
Phase amagalmation
Where do we stand? (revisited)
Products of algebras
Semantics of
Fun things to do with products
Tools developed with ADP
What's cool about Algebraic Dynamic Programming?
Taught by
Strange Loop Conference
