This talk presents the ALGEBRAIC approach to dynamic programming (ADP), which guarantees 100 percent more fun in the life of a dynamic programmer.

Motivation:
Dynamic programming is indispensible in bioinformatics, but not an easy technique to employ. The simplicity of textbook examples (such as the Needleman-Wunsch, Smith-Waterman, Nussinov algorithms) is deceiving. In real life, the development of a dynamic programming algorithm is tedious. Our algorithmic ideas are obscured by the low abstraction level of matrix recurrences. Testing the code is cumbersome, as it is difficult to recognize when a wrong (sub-optimal) result is returned.

The new framework:
The logic of a dynamic programming algorithm can be cleanly separated into the aspects of problem decomposition and candidate scoring. The former is described by a special form of grammar, the latter by a family of functions called an evaluation algebra. These specifications given, an implementation can be generated automatically, and translated into correct and efficient code using the ADP compiler recently completed by Peter Steffen.
Liberated from tedious coding and debugging issues, we may embark on more sophisticated analyses. For a problem at hand, we may want to know not only the optimal score, but also an optimal solution itself, information about its uniqueness, eventually all co-optimal solutions, the solutions under multiple criteria (the most beautiful among the best), the best solution satisfying some nontrivial extra requirement, and so on.

Benefits and applications:
It turns out that all such concerns can also be described as evaluation algebras, and a powerful product operation on these algebras allows to create new and combined analyses from them, without re-programming effort.
The presentation will introduce the ADP technique in an informal way, point to some bioinformatics tools recently built with this approach, and -- hopefully -- stimulate discussion on its potential further applications.