Prof. Dr. Robert Giegerich

"Dynamic Programming: More Fun with Product Algebras"

Dynamic programming is widely used programming method in combinatorial optimization.
It is indispensable in biosequence analysis, for string comparison, RNA structure prediction, gene prediction, and many other tasks. But it is not an easy technique to employ.
The simplicity of textbook applications (such as string edit distance or optimal matrix chain multiplication) is deceiving. In real life, the development of a dynamic programming algorithm is tedious. Algorithmic ideas are obscured by the low abstraction level of the typical matrix recurrences.
Testing the code is cumbersome, as it is difficult to recognize when a wrong (sub-optimal) result is returned.
The ADP discipline: This situation has been alleviated somewhat by the discipline of ALGEBRAIC dynamic programming (ADP). In ADP, a dynamic programming application is specified by a tree grammar and a family of evaluation algebras. From these declarative modules, correct and efficient code is obtained via the ADP compiler. Dynamic Programming becomes fun when PRODUCTS of algebras are introduced. Using products, simple building blocks give rise to a surprising variety of applications.
The Presentation will shortly review the formal theory behind ADP, and then proceed to demonstrate the variety of questions that can be answered using product algebras -- ending with some questions where this seems impossible.