Readings on Dynamic Programming

Readings on Dynamic Programming

Reading for the dynamic programming part of the Algorithm Design lecture:

• String Alignment using Dynamic Programmingby Gina M. Cannarozzi. This does a nice job of describing how matrix D[i,j] of substring alignment scores is computed. Note that Cannarozzi uses the term "gap score" to refer to the points allowed for matching a string character with "no character". What she calls "global alignment" is what we assume to be the standard version of the problem of aligning two strings.
• Another example, with a slightly different presentation style is given here
• An example of a form of sequence alignment called the longest common subsequence problem is given in this web page at IBM: Dynamic programming an sequence alignment.
• Our text gives a general description of dynamic programming and gives applications to Fibonacci number calculation, orderings for matrix multiplications, computing optimal binary search trees, and the all-pairs shortest paths in a graph problem. It does not cover the string alignment problem.