Transcript Dynamic programming

Dynamic
Programming
Nithya
Tarek
Dynamic Programming


Dynamic programming solves problems by
combining the solutions to sub problems.
Paradigms:



Divide and conquer
Greedy Algorithm
Dynamic programming
String Matching


Longest common subsequence
Knuth-Morris-Pratt pattern matching
Example – Fibonacci Numbers
using recursion
Function f(n)
if n = 0
output 0
else
if n = 1
output 1
else
output f(n-1) + f(n-2)
Example – Fibonacci Numbers
using recursion




Run time: T(n) = T(n-1) + T(n-2)
This function grows as n grows
The run time doubles as n grows and is order
O(2n).
This is a bad algorithm as there are
numerous repetitive calculations.
Example – Fibonacci Numbers
using Dynamic programming
f(5)
f(4)
f(3)
f(2)
f(3)
f(2)
f(1)
f(2)
f(1)
Example – Fibonacci Numbers
using Dynamic programming



Dynamic programming calculates from
bottom to top.
Values are stored for later use.
This reduces repetitive calculation.
Longest Common
Subsequence


The input to this problem is two sequences
S1=abcdace and S2=badcabe. The problem
is to find the longest sequence that is a
subsequence of both S1 and S2 where S1 ≠
S2.
Distance between S1 and S2 is defined as
the number of characters we have to remove
from one string and add to that string to make
S1 and S2 equal.
Longest Common
Subsequence
S1: a
b
c
d
a
c
e
S2:
a
d
c
a
b
e


b
Length LCSS = 4
Edit Distance = 3(remove) +3(add) = 6
Longest Common
Subsequence

Theorem:
|S1| = m, |S2|=n
LCSS = L
Edit distance = m + n – 2L
Longest Common Subsequence
S1i
S1
i
S2j
S2
j
Longest Common
Subsequence
To find LCSS(S1i, S2j)
S1
S2
i
j
If S1[i] = S2[j]
Then return LCSS[S1i-1, S2j-1] + 1
Else return max{LCSS[S1i-1, S2j ],
LCSS[S1i, S2j-1 ] }
 This algorithm is very slow
Solving LCSS using Dynamic
programming


LCSS Matrix:
The last entry in the
matrix shows the LCSS
a b c d a c
e
b
0
1
1
1
1
1
1
a
1
1
1
1
2
2
2
d
0
1
1
2
2
2
2
c
1
1
2
2
2
3
3
a
1
1
2
2
3
3
3
b
0
2
2
2
3
3
3
e
0
2
2
2
3
3
4
Solving LCSS using Dynamic
programming




Runtime for this matrix using Dynamic
programming is order of O(m,n)
O(1) times to fill up each entry
There are mn entries.
Space required: O(mn)
Advantages of Dynamic
programming


A recursive procedure does not have memory
Dynamic programming stores previous
values to avoid multiple calculations
Space and Time




The space can be reduced to order of
O(min{m,n})
It is enough to keep only two rows j and j-1
After calculating the entries for row j move
that row up to row j-1 and delete row j-1 and
get the new entries for row j.
The time cannot be reduced
Space reduction
To compare for a smaller area w, where w is
the window size, the matrix size will reduce.
S1: a
b
c
d
a
c
e

S2:
b
a
d
3
w
c
3
w
a
b
e
Space reduction
Specifying the window size reduces the
number of calculation
 The runtime of this algorithm is:
O(2w * min{m,n})
It is a linear time algorithm and the space
required: O(w)
