Introductory examples
These examples are some of the simplest cases of dynamic programming. If all DP problems were as simple as these, then a systematic method like ADP would not be necessary at all.
El Mamun's Caravan
El Mamun is probably the most intuitive example. It involves minimizing or maximizing the value of an expression by inserting parentheses in arbitrary ways. It also comes with a fun story.
Matrix Chain Multiplication
Optimal matrix chain multiplication is a favourite problem in computer science textbooks. Given is a sequence of matrices of varying dimensions, which are to be multiplied:
A * B * C * D
Associativity of matrix multiplication allows us to group the matrices in arbitrary way:
A * (B * (C * D)) or (A * B) * (C * D) or ((A * B) * C) * D
This grouping determines the overall effort, measured in the number of scalar oerations. The goal is to minimize scalar multiplications.
String Comparison
Several problems in string comparison are treated here, all based on the model of editing one string into another. We show distance and similarity problems, including local similarity and additive as well as affine gap scores.
(The same problems are addressed in the Section "Bioinformatics Classics" under the names by which they are known in the bioinformatics community.)
background image
university bielefeld AG PI BiBiServ
ambient picture