Design & Analysis of Algorithms
(KCS 503)
UNIT-3
Dynamic Programming
From:
Asif Khan
Department of CSE
GNIOT, Greater Noida
Reference:
Thomas H. Corman et al.
The MIT Press
Dynamic Programming
Dynamic programming, like the divide-and-conquer
method, solves problems by combining the solutions
to subproblems.
Divide-and-conquer algorithms partition the problem
into disjoint subproblems, solve the subproblems
recursively, and then combine their solutions to solve
the original problem.
Dynamic Programming
In contrast, dynamic programming applies when the
subproblems overlap: that is, when subproblems share
subsubproblems.
In this context, a divide-and-conquer algorithm does
more work than necessary, repeatedly solving the
common subsubproblems.
Dynamic Programming
A dynamic-programming algorithm solves each
subsubproblem just once and then saves its answer in
a table, thereby avoiding the work of recomputing the
answer every time it solves each subsubproblem.
We typically apply dynamic programming to
optimization problems. Such problems can have many
possible solutions. Each solution has a value, and we
wish to find a solution with the optimal (minimum or
maximum) value. We call such a solution an optimal
solution to the problem, as opposed to the optimal
solution, since there may be several solutions that
achieve the optimal value.
Dynamic Programming
When developing a dynamic-programming algorithm,
we follow a sequence of four steps:
1. Characterize the structure of an optimal solution.
2. Recursively define the value of an optimal solution.
3. Compute the value of an optimal solution, typically
in a bottom-up fashion.
4. Construct an optimal solution from computed
information.
Matrix-chain multiplication
An Example of Dynamic Programming
In matrix-chain multiplication problem, we are given
a sequence (chain) A1, A2,……,An of n matrices to be
multiplied, and we wish to compute the product
A1A2 …..An
We can evaluate this product by using the standard
algorithm for multiplying pairs of matrices as a
subroutine, once we have parenthesized it to resolve
all ambiguities in how the matrices are multiplied
together.
Matrix multiplication is associative, and so all
parenthesizations yield the same product.
Matrix-chain multiplication
A product of matrices is fully parenthesized if it is
either a single matrix or the product of two fully
parenthesized matrix products, surrounded by
parentheses. For example, if the chain of matrices is
A1, A2, A3, A4, then we can fully parenthesize the
product A1A2A3A4 in five distinct ways:
Matrix-chain multiplication
Let us see the algorithm to multiply two matrices A
and B and store the result in third matrix C
Matrix-chain multiplication
We can multiply two matrices A and B only if they are
compatible: the number of columns of A must equal
the number of rows of B. If A is a p x q matrix and B
is a q x r matrix, the resulting matrix C is a p x r
matrix.
The time to compute C is dominated by the number of
scalar multiplications in line 8, which is pqr. So we
shall express costs in terms of the number of scalar
multiplications.
Matrix-chain multiplication
To illustrate the different costs incurred by different
parenthesizations of a matrix product, consider the
problem of a chain A1, A2, A3 of three matrices.
Suppose that the dimensions of the matrices are
10x100, 100 x 5, and 5 x 50, respectively.
If we multiply according to the parenthesization
((A1A2)A3), then
10x100x5=5000 scalar multiplications to compute the
10 x 5 matrix product A1A2, plus another
10x5x50=2500 scalar multiplications to multiply this
matrix by A3,
So a total of 7500 scalar multiplications.
Matrix-chain multiplication
If instead we multiply according to the
parenthesization (A1(A2A3)), then
100x5x50 = 25,000 scalar multiplications to compute
the 100 x 50 matrix product A2A3, plus another
10x100x50 = 50,000 scalar multiplications to multiply
A1 by this matrix,
So a total of 75,000 scalar multiplications. Thus,
computing the product according to the first
parenthesization is 10 times faster.
Matrix-chain multiplication
Now we can state the matrix-chain multiplication
problem as follows: given a chain A1, A2,……,An of n
matrices, where for i = 1,2,…..,n, matrix Ai has
dimension pi-1 x pi , fully parenthesize the product
A1A2 …..An in a way that minimizes the number of
scalar multiplications.
So Dimensions of A1 is p0 x p1, Dimensions of A2 is
p1 x p2, ……, Dimensions of An is pn-1 x pn.
Note that in the matrix-chain multiplication problem,
we are not actually multiplying matrices. Our goal is
only to determine an order for multiplying matrices
that has the lowest cost.
Matrix-chain multiplication
Applying dynamic programming:
Step 1: The structure of an optimal parenthesization
For convenience, let us adopt the notation Ai ..j, where
i ≤ j , for the matrix that results from evaluating the
product AiAi+1….Aj.
If i < j, then to parenthesize the product AiAi+1….Aj,
we must split the product between Ak and Ak+1 for
some integer k in the range i ≤ k < j. That is, for some
value of k, we first compute the matrices Ai..k and
Ak+1..j and then multiply them together to produce the
final product Ai..j.
Matrix-chain multiplication
The cost of parenthesizing this way is the cost of
computing the matrix Ai..k plus the cost of computing
Ak+1..j, plus the cost of multiplying them together.
The optimal substructure of this problem is as follows.
To optimally parenthesize AiAi+1….Aj, if we are
splitting the product between Ak and Ak+1, then the
way we parenthesize the “prefix” subchain
AiAi+1….Ak must be an optimal parenthesization.
Similarly the parenthesization of the subchain
Ak+1Ak+2….Aj must be an optimal parenthesization.
Matrix-chain multiplication
Step 2: A recursive solution
We will define the recursive solution to determine the
minimum cost of parenthesizing AiAi+1….Aj for 1 ≤ i
≤ j ≤ n.
Let m[i,j] be the minimum number of scalar
multiplications needed to compute the matrix Ai..j.
For the full problem, the lowest cost to compute A1..n
would thus be m[1,n]. We can define m[i,j]
recursively as follows.
Matrix-chain multiplication
Step 3: Computing the optimal costs
By using the formula define in step 2, we can now
compute the optimal (minimal) cost.
Example: Find out optimal Perenthesization of the
following chain of matrices:
A1(3x5), A2(5x1), A3(1x2), A4(2x6), A5(6x5)
Dimension Array p 3 5 1 2 6 5
0 1 2 3 4 5
Matrix-chain multiplication
i
j j i
1 2 3 4
15 10 12 60
- - - - -
0 0 0 0 0
s
m
p 3 5 1 2 6 5
m[1,2]=m[1,1]+m[2,2]+p0p1p2 = 3x5x1= 15
m[2,3]=m[2,2]+m[3,3]+p1p2p3 = 5x1x2= 10
m[3,4]=m[3,3]+m[4,4]+p2p3p4 = 1x2x6= 12
Matrix-chain multiplication
i j i
j
1 2 3 4
15 10 12 60
- - - - -
0 0 0 0 0
s
m
m[1,3]=min{m[1,1]+m[2,3]+p0p1p3,=min{0+10+ 3x5x2
m[1,2]+m[3,3]+p0p2p3} 15+ 0+3x1x2}
=21
Matrix-chain multiplication
p 3 5 1 2 6 5
m[2,4]= min{0+12+5x1x6 0 1 2 3 4 5
10+0 +5x2x6} =42
m[3,5]= min{0+60+1x2x5
12+0 +1x6x5} =42
m[1,4]= min{0+42+ 90
15+12+ 18
21+ 0 + 36} = 45
m[2,5]= min{0+42+ 25
10+60+ 50
42+ 0 + 150} = 67
Matrix-chain multiplication
p 3 5 1 2 6 5
0 1 2 3 4 5
m[1,5]= min{0+67+ 75
15+42+ 15
21+60+ 30
45+ 0 + 90} = 72
Matrix-chain multiplication
72 2
i j i
j
45 67 2 2
21 42 42 2 2 4
1 2 3 4
15 10 12 60
- - - - -
0 0 0 0 0
s
m
Matrix-chain multiplication
Step 4: Constructing an optimal solution
2 i
(A1 A2 A3 A4 A5) j
2 2
((A1 A2 ) (A3 A4 A5 )) 2 2 4
1 2 3 4
((A1 A2 ) ((A3 A4 )A5 )) - - - - -
s
Longest Common Subsequence (LCS)
A subsequence of a given sequence is just the given
sequence with zero or more elements left out.
For example, Z ={B, C, D, B} is a subsequence of
X={A, B, C, B, D, A, B} with corresponding index
sequence {2, 3, 5, 7}.
Given two sequences X and Y, we say that a sequence
Z is a common subsequence of X and Y if Z is a
subsequence of both X and Y . For example, if
X={A,B,C,B,D,A,B} and Y={B,D,C,A,B,A}, the
sequence {B,C,A} is a common subsequence of both
X and Y .
Longest Common Subsequence (LCS)
The sequence {B,C,A} is not a longest common
subsequence (LCS) of X and Y , however, since it has
length 3 and the sequence {B,C,B,A}, which is also
common to both X and Y , has length 4. The sequence
{B,C,B,A} is an LCS of X and Y , as is the sequence
{B,D,A,B}, since X and Y have no common
subsequence of length 5 or greater.
In the longest-common-subsequence problem, we are
given two sequences X={x1,x2,…..,xm} and
Y={y1,y2,….,yn} and wish to find a maximum length
common subsequence of X and Y .
Longest Common Subsequence (LCS)
Step 1: Characterizing a longest common subsequence
Let X={x1,x2,…..,xm} and Y={y1,y2,….,yn} be
sequences, and let Z ={z1,z2,….,zk} be any LCS of X
and Y .
1. If xm = yn, then zk = xm = yn and Zk-1 is an LCS of
Xm-1 and Yn-1.
2. If xm ≠ yn, then zk ≠ xm implies that Z is an LCS of
Xm-1 and Y .
3. If xm ≠ yn, then zk ≠ yn implies that Z is an LCS of
X and Yn-1.
Longest Common Subsequence (LCS)
1. Let X= ABCADA and Y=BDCDBA then Z=BCDA
be an LCS of X and Y .
If xm = yn, then zk = xm = yn and Zk-1 i.e. BCD is an
LCS of ABCAD and BDCDB
2. Now let X=BDCDB and Y= ABCAD then Z=BCD
If xm ≠ yn, then zk ≠ xm implies that Z is an LCS of
Xm-1 and Y i.e. BDCD and ABCAD
3. Now let X=BDC and Y= ABCA then Z=BC
If xm ≠ yn, then zk ≠ yn implies that Z is an LCS of X
and Yn-1 i. e. BDC and ABC
Longest Common Subsequence (LCS)
Step 2: A recursive solution
Let us define c[i, j] to be the length of an LCS of the
sequences Xi and Yj. If either i = 0 or j = 0, one of the
sequences has length 0, and so the LCS has length 0.
The optimal substructure of the LCS problem gives
the recursive formula:
Step 3: Computing the length of an LCS
j 0 1 2 3 4 5 6
i yj B D C D B A
0 xi 0 0 0 0 0 0 0
1 A 0
2 B 0
3 C 0
4 A 0
5 D 0
6 A 0
Step 3: Computing the length of an LCS
j 0 1 2 3 4 5 6
i yj B D C D B A
0 xi 0 0 0 0 0 0 0
1 A 0 0 0 0 0 0 1
2 B 0
3 C 0
4 A 0
5 D 0
6 A 0
Step 3: Computing the length of an LCS
j 0 1 2 3 4 5 6
i yj B D C D B A
0 xi 0 0 0 0 0 0 0
1 A 0 0 0 0 0 0 1
2 B 0 1 1 1 1 1 1
3 C 0
4 A 0
5 D 0
6 A 0
Step 3: Computing the length of an LCS
j 0 1 2 3 4 5 6
i yj B D C D B A
0 xi 0 0 0 0 0 0 0
1 A 0 0 0 0 0 0 1
2 B 0 1 1 1 1 1 1
3 C 0 1 1 2 2 2 2
4 A 0
5 D 0
6 A 0
Step 3: Computing the length of an LCS
j 0 1 2 3 4 5 6
i yj B D C D B A
0 xi 0 0 0 0 0 0 0
1 A 0 0 0 0 0 0 1
2 B 0 1 1 1 1 1 1
3 C 0 1 1 2 2 2 2
4 A 0 1 1 2 2 2 3
5 D 0
6 A 0
Step 3: Computing the length of an LCS
j 0 1 2 3 4 5 6
i yj B D C D B A
0 xi 0 0 0 0 0 0 0
1 A 0 0 0 0 0 0 1
2 B 0 1 1 1 1 1 1
3 C 0 1 1 2 2 2 2
4 A 0 1 1 2 2 2 3
5 D 0 1 2 2 3 3 3
6 A 0
Step 3: Computing the length of an LCS
j 0 1 2 3 4 5 6
i yj B D C D B A
0 xi 0 0 0 0 0 0 0
1 A 0 0 0 0 0 0 1
2 B 0 1 1 1 1 1 1
3 C 0 1 1 2 2 2 2
4 A 0 1 1 2 2 2 3
5 D 0 1 2 2 3 3 3
6 A 0 1 2 2 3 3 4
Step 3: Computing the length of an LCS
j 0 1 2 3 4 5 6
i yj B D C D B A
0 xi 0 0 0 0 0 0 0
1 A 0 0 0 0 0 0 1
2 B 0 1 1 1 1 1 1
3 C 0 1 1 2 2 2 2
4 A 0 1 1 2 2 2 3
5 D 0 1 2 2 3 3 3
6 A 0 1 2 2 3 3 4
Step 4: Constructing an LCS
j 0 1 2 3 4 5 6
i yj B D C D B A
0 xi 0 0 0 0 0 0 0
1 A 0 0 0 0 0 0 1
2 B 0 1 1 1 1 1 1
3 C 0 1 1 2 2 2 2
4 A 0 1 1 2 2 2 3
5 D 0 1 2 2 3 3 3
6 A 0 1 2 2 3 3 4
THANK YOU