Dynamic Programming
Dr. Rashid Amin
Dynamic programming is essentially
recursion without repetition.
Developing a dynamic programming
algorithm generally involves two separate
steps:
◦ Formulate problem recursively. Write down a
formula for the whole problem as a simple
combination of answers to smaller subproblems.
◦ Build solution to recurrence from bottom up. Write
an algorithm that starts with base cases and works
its way up to the final solution.
The words “computer” and “commuter” are
very similar, and a change of just one letter,
p->m
The word “sport” can be changed into “sort”
by the deletion of the ‘p’
The edit distance of two strings, s1 and s2, is
defined as the minimum number of point
mutations required to change s1 into s2,
where a point mutation is one of:
◦ change a letter,
◦ insert a letter or delete a letter
For example, the edit distance between FOOD
and MONEY is at most four:
There are numerous applications of the Edit
Distance algorithm.
Spelling Correction
◦ If a text contains a word that is not in the dictionary, a
‘close’ word, i.e. one with a small edit distance, may be
suggested as a correction.
◦ such as Microsoft Word, have spelling checking and
correction facility.
Plagiarism Detection
◦ If someone copies, say, a C program and makes a few
changes here and there, for example, change variable
names, add a comment of two, the edit distance between
the source and copy may be small.
Computational Molecular Biology
◦ DNA is a polymer. The major units of DNA are nucleotides.
There are four different types of nucleotides found in DNA,
those are given one letter abbreviations as shorthand for
the four bases.
A-adenine G-guanine
C-cytosine T-thymine
Speech Recognition
◦ Algorithms similar to those for the edit-distance problem
are used in some speech recognition systems.
◦ Find a close match between a new utterance and one in a
library of classified utterances.
A better way to display this editing process is
to place the words above the other:
The first word has a gap for every insertion (I)
and the second word has a gap for every
deletion (D).
Columns with two different characters
correspond to substitutions (S). Matches (M)
do not count.
The Edit transcript is defined as a string over
the alphabet M, S, I, D that describes a
transformation of one string into another. For
example
S D I M D M
1+ 1+ 1+ 0+ 1+ 0+ = 4
In general, it is not easy to determine the
optimal edit distance.
For example, the distance between
ALGORITHM and ALTRUISTIC is at most 6.
Suppose we have an m-character string A and
an n-character string B.
Define E(i, j) to be the edit distance between
the first i characters of A and the first j
characters of B. For example,
The edit distance between entire strings A
and B is E(m, n).
The gap representation for the edit sequences
has a crucial “optimal substructure” property.
If we remove the last column, the remaining
columns must represent the shortest edit
sequence for the remaining substrings.
The edit distance is 6 for the following two
words.
If we remove the last column, the edit distance
reduces to 5.
We can use the optimal substructure property
to devise a recursive formulation of the edit
distance problem.
There are a couple of obvious base cases:
◦ The only way to convert an empty string into a
string of j characters is by doing j insertions. Thus
E(0, j) = j
◦ The only way to convert a string of i characters into
the empty string is with i deletions:
E(i, 0) = i
There are four possibilities for the last
column in the shortest possible edit
sequence:
Deletion: Last entry in bottom row is empty.
In this case E(i, j) = E(i-1, j) + 1
Insertion: The last entry in the top row is
empty.
In this case E(i, j) = E(i, j - 1) + 1
Substitution: Both rows have characters in the
last column.
If the characters are different, then
E(i, j) = E(i - 1, j - 1) + 1
If characters are same, no substitution is
needed: E(i, j) = E(i - 1, j - 1)
Thus the edit distance E(i, j) is the smallest of
the four possibilities:
Consider the example of edit between the
words “ARTS” and “MATHS”:
The edit distance would be in E(4, 5). If we
recursion to compute, we will have
Recursion clearly leads to the same repetitive
call pattern that we saw in Fibonnaci
sequence.
To avoid this, we will use the DP approach.
We will use the base case E(0, j) to fill first
row and the base case E(i, 0) to fill first
column.
We will fill the remaining E matrix row by row.
Possible edit scripts. The red arrows from E[0,
0] to E[4, 5] show the paths that can be
followed to extract edit scripts.
There are Q(n2) entries in the matrix. Each
entry E(i, j) takes Q (1) time to compute. The
total running time is Q(n2).