The ADP Exposition
Algebraic Dynamic Programming (ADP) is a new method to design and
implement, tune, test and teach Dynamic Programming
algorithms. Compared to the traditional style, ADP provides a much
higher level of abstraction, helping to solve more sophisticated
problems with better chances of success.
This WWW site constitutes an exposition of what has been achieved with
ADP, and at the same a work plan. Feel free to join in on using or
further developing ADP.
ADP-Literature: An annotated bibliography
of articles on ADP, which have appeared or have been accepted for
publication.
ADP-Applications: A showcase of ADP
algorithms, classic and new ones, from computer science and
bioinformatics, including the oldest Dynamic Programming problem of
the world.
ADP-Education: A collection of hints on
using ADP in computer science and bioinformatics education, using the
material in ADP-Applications.
ADP-Advanced: Advanced Techniques in ADP
are these that extend the ADP core concepts of evaluation algebra and
yield parsers in some direction. All these techniques are used in ADP-Applications, but here they are explained
from a methodical point of view.
ADP-Compiler: The ADP compiler
translates ADP programs to (optimized) ADP, to C, and into traditional
DP recurrences typeset in LaTeX.
ADP-HMM: There is much correspondence
between HMMs (hidden markov models) and Dynamic Programming. However,
the terminologies used in these two areas are quite distinct. Here we
present the use of ADP with probabilistic algebras and their relation
to HMMs and stochastic context-free grammars.