Monday, March 22, 2021 4:09 PM
Chapter 4 Dynamic Programming
▪ The principle should be satisfied by the problem, when it is to be solved using
dynamic programming method is principle of optimality.
▪ Dynamic programming is another algorithm design strategy used in the problems
where optimization (maximization/minimization) of result is expected.
▪ It gives the optimal solution.
▪ It has optimal sub structure and uses recurrence relation to find optimal solution.
▪ In dynamic programming all feasible solutions of the problem are found and
among them optimal solution is considered.
▪ This design strategy is popular in the problems where solution to the problem
can be viewed as a result of sequence of decisions.
▪ Dynamic programming is mostly suitable for the problems where recursive
algorithm is required.
▪ In this technique the smallest subproblems are solved first, then there results
are combined to solve larger subproblems and so on till we get the solution
for the given problem.
▪ It is not faster than greedy strategy.
▪ We can use dynamic programming method when solution has optimal
structure.
▪ It divides the larger problem into subproblems. optimal substructure is problem
is divisible.
▪ Finding optimal solution to these subproblems and store the result.
Dynamic programming uses Memoization.
▪ If the problem can be broken into subproblems which are reused several times,
the problem possesses overlapping subproblems property.
❖ Properties of Dynamic Programming:
1. Optimal structure
2. Overlapping subproblems
Ch 4 Dynamic Programming Page 1
When we apply Top-Down approach of dynamic programming then it decreases
time complexity but increases space complexity.
Ch 4 Dynamic Programming Page 2
❖ Matrix Chain Multiplication:
Let M=M1×M2× …….Mn
be the product of n matrices. Each matrix Mi consists of ri columns. The
orders in which the matrices are multiplied together have a significant effect
on the total number of scalar multiplication required to evaluate M.
For example Let M1,M2,M3, and M4 be four matrices.
To find out the product M=M1×M2×M3×M4 we can parenthesize in one of the
following distinct ways.
1. (M1 (M2 (M3 M4)))
2. (M1 ((M2 M3) M4))
3. ((M1 M2) (M3 M4))
4. ((M1 (M2 M3)) M4)
5. (((M1 M2) M3) M4)
If A is a matrix of order p × q and B is another matrix of order q × r .
Then, to find the product AB the number of scalar multiplication done
p×q×r
Given a chain M1,M2 …Mn of n matrices, where for i=1,2,……n matrix Mi has
ri-1 rows and ri columns.
▪ M=M1M2M3……Mn in a such way that minimizes the number of scalar
multiplications.
▪ However dynamic programming provides an algorithm with time complexity
O(n3).
Let mij be the minimum cost of computing the product.
mij= 0 if i=j
min (mik+mk+1,j + ri-1rkrj) j>i
mik is the minimum cost of evaluating the product.
Ch 4 Matrix Chain Multiplication Page 1
mik is the minimum cost of evaluating the product.
Recurrence Relation:
dp[i, j] = 0 if i=j
dp[i, j] = min{dp[i, k] + dp[k+1, j]} + mat[i-1]*mat[k]*mat[j]
Suppose A is of order 2×3 and B is of order 3 × 4 then the total number of
scalar multiplication are 2×3×4=24
Let M1, M2, M3, M4 are four matrices with dimensions 2X3, 3X4,4X2, 2X5.
Find the number of minimum scalar multiplications required to multiply
matrices M1M2M3M4
1. (M1 (M2 (M3 M4)))
2. (M1 ((M2 M3) M4))
3. ((M1 M2) (M3 M4))
4. ((M1 (M2 M3)) M4)
5. (((M1 M2) M3) M4)
(M1 (M2 (M3 M4)))
Ch 4 Matrix Chain Multiplication Page 2
Ch 4 Matrix Chain Multiplication Page 3
Friday, April 2, 2021 10:03 AM
Let M1, M2, M3, M4 are four matrices with dimensions 2X3, 3X4,4X2, 2X5.
Find the number of minimum scalar multiplications required to multiply matrices
M1M2M3M4
Matrix_Multiplication Page 1
Friday, March 26, 2021 10:41 AM
❖ 0/1 Knapsack Merge and Purge Method:
▪ This is another method for finding the optimal solution of 0/1 knapsack
problem using dynamic programming strategy.
▪ In the previous method (0/1 knapsack function method ) the optimal solution
is the value of fn(m) whereas in 0/1 knapsack merge and purge method the
optimal solution is the value of Sn.
▪ Every (Pj,Wj) is a state where wi is the total weight of objects included in the
Knapsack and Pj is corresponding profit.
❖ The Dominance Rule: (Purging Rule)
▪ Two pairs (pj ,wj) and (pk, wk) with property that pj<=pk and wj>=wk then
the pair (pj, wj) is discarded. The pair (pk, wk) dominates (pj, wj).
The dominated pair gets purged.
▪ While generating Si's all the pairs (p, w) with w > m are also purged.
Since the knapsack capacity is m. In this way continuing the generation of sets
Si, Si 1 and Hence Si+1 obtain the set Sn. This is the last set generated.
The optimum solution is given by the P value of the last pair in Sn.
Example: Find an optimal solution for 0/1 knapsack problem by using merge
and purge method. n=3 m=6 P=(1,2,5) and W=(2,3,4)
Ch 4 0 1 Knapsack Merge and Purge Method Page 1
Ch 4 0 1 Knapsack Merge and Purge Method Page 2
Ch 4 0 1 Knapsack Merge and Purge Method Page 3
Friday, March 26, 2021 10:16 AM
❖ 0/1 Knapsack:
▪ 0/1 Knapsack is based on the dynamic programming method.
▪ 0/1 knapsack problem is solved using function method and merge and purge
method.
A thief robbing a store finds n items, the ith item is worth Vi Rs. and weights
Wi are integers. He wants to take a valuable as load possible but he can carry at
most m kgs in his knapsack( a bag) for some integer m. what items should take?
Here thief can select or leave behind an item. He cannot take fractional amount
of an item or cannot take item more than once.
This is 0/1 knapsack problem.
We have already defined the greedy knapsack.
▪ The only variation is that xi=0 or xi=1 and not a fraction.
▪ It is a maximization problem.
▪ An optimal solution is a feasible solution for which
n
∑ pixi is maximum
i=1
❖ 0/1 knapsack with function method:
▪ In 0/1 knapsack problem items are indivisible and in fractional knapsack items
are divisible.
fn(m)= max {fn-1(m), fn-1(m-wn) + pn}
f0(m)=0;
f1(m)= P1; w1<=m
= 0; w1>m
fn(-m)=-∞;
❖ Solve the following 0/1 knapsack problem. n=3, m=14, W=(8,6,4)
P=(10,11,9). Find Maximum Profit (Use Function Method)
Ch 4 0 1 Knapsack_Function Method Page 1
f1(m)= P1; w1<=m
= 0; w1>m
0/1 knapsack problem using with n=3, m=7, W=(2,3,4) P=(11,12,15).
Find Solution Vector (Use Function Method)
Ch 4 0 1 Knapsack_Function Method Page 2
Monday, March 29, 2021 2:33 AM
❖ All pairs Shortest Path (Floyd- Warshall Algorithm)
▪ Dynamic programming approach is being followed in Floyd Warshall
Algorithm to solve all pair shortest path problem.
▪ Suppose we wish to compute the shortest path distance between every pair of
vertices in directed graph G with n vertices and m edges.
Let G=(V,E) be a directed graph with n vertices. Let cost be a cost adjacency
matrix for G such that Cost (i, i)=0 length of shortest path from i to j.
If k is intermediate vertex on this shortest path, then sub must be shortest paths
from i to k and k to j respectively.
The all pair shortest path is to determine a matrix A such that A< i, j> is the
shortest path.
Once this decision has been made we need to find two shortest path, one from i to
k and other from k to j.
Using Ak (i , j) to represent the length of shortest path from i to j going though
no vertex of index greater than k we obtain.
▪ Floyd-Warshall Algorithm is used to find all pair shortest distances using
Dynamic Programming method.
▪ Floyd Warshall’s Algorithm is used for solving all pair shortest path
problems. It means the algorithm is used for finding the shortest paths between
all pairs of vertices in a graph.
▪ Floyd Warshall’s Algorithm can be applied on directed graph.
1. Which algorithm is used to find all pair shortest distances using Dynamic
Programming ?
2. Floyd Warshall’s Algorithm is used for solving all pair shortest distances
problem.
Ch 4 All Pair Shortest Path_Floyd_Warshall Page 1
Ch 4 All Pair Shortest Path_Floyd_Warshall Page 2
Monday, March 29, 2021 3:07 AM
❖ Bellman Ford Algorithm:
▪ Bellman ford algorithm provides solution for Single source shortest path
problems.
▪ Which algorithm is used to find single source shortest path when the graph
contains negative weighted edges?
▪ Bellman ford algorithm is used to indicate whether the graph has negative
weight cycles or not.
▪ Bellman Ford Algorithm can be applied for directed and weighted graphs.
Ch 4 Bellman Ford Algorithm Page 1
Ch 4 Bellman Ford Algorithm Page 2
Friday, April 2, 2021 12:08 PM
Ch 4 Function Method Page 1
Ch 4 Function Method Page 2
Friday, April 2, 2021 12:08 PM
Ch 4 Function Method_Example Page 1
Ch 4 Function Method_Example Page 2
Tuesday, March 23, 2021 6:54 PM
❖ Longest Common Subsequence:
▪ Longest Common Subsequence (LCS) is a good example of the technique of
dynamic programming.
▪ It is one of the string matching problem.
▪ This technique is also used in file comparison. We can compare two different
versions of the same file to determine what changes have been made to the
file. This comparison is made by line by line.
Application : For DNA matching LCS with dynamic programming is used.
Definition:
Given a sequence x=<x1,x2….xm> y= <y1,y2….yn> and a sequence
z=<z1,z2…..zk>
Given two sequences X and Y, a sequence Z is a common subsequence of X
and Y if Z is a subsequence of both sequences X and Y.
a. If xi = yj then
C[i, j] = C[i-1, j-1] + 1
i.e. Upper Diagonal element + 1 and arrow " Cross Arrow"
b. If Xi Yj then
check the upper and left side of the element to be computed.
If upper element is greater than or equal to left element then new element is
upper element with arrow "↑" otherwise new element is left element is left
element and arrow is "←"
Ch 4 Longest Common Subsequence Page 1
element and arrow is "←"
Find LCS of the sequences X and Y where
X= <A,B,C,B,D,A,B>
Y= <B,D,C,A,B,A>
j 0 1 2 3 4 5 6
i Yi B D C A B A
0 Xi 0 0 0 0 0 0 0
1 A 0
2 B 0
3 C 0
4 B 0
5 D 0
6 A 0
7 B 0
Algorithm LCS_length (X, Y, m, n)
// m is the length of sequence X.
//n is the length of sequence Y.
{
m=length(X);
n=length(Y);
for i=0 to m do
Ci,0 =0;
for j=0 to n do
C0,j =0;
for i=1 to m do
for j=1 to n do
if xi=yj then
{
Cij =Ci-1,j-1 +1;
bij= " Cross arrow";
}
else
if Ci-1,j >= Ci,j-1 then
//upper element is greater than or equal to left
write upper element as it is and "↑"
Ch 4 Longest Common Subsequence Page 2
write upper element as it is and "↑"
{
cij=Ci-1,j;
bij="↑";
else
{
Cij=Ci,j-1; //else write left element as it is & "←"
bij= "←";
}
return c and b;
}
Algorithm printLCS
Algorithm printLCS (b, x, i, j)
{
if i=0 or j=0 then
return;
if bij= "cross arrow" then
{
printLCS (b,x,i-1,j-1);
Print xi;
}
else
{
if bij="↑" then
printLCS(b, x, i-1, j);
else
printLCS(b, x, i, j-1);
}
printLCS
Find length of LCS of two sequences X=<0,1,0,1,0> and Y = <1,0,1,1,0>
j 0 1 2 3 4 5
i Yj 1 0 1 1 1
0 Xi
1 0
Ch 4 Longest Common Subsequence Page 3
0 Xi
1 0
2 1
3 0
4 1
5 0
Length of common subsequence is:
Given two sequences X and Y , a maximum length common subsequence of X
and Y is called Longest Common Subsequence of X and Y.
Ch 4 Longest Common Subsequence Page 4
Thursday, March 25, 2021 10:47 AM
❖ String Editing:
▪ We are given two strings X= x1,x2,……xn and Y= y1,y2….ym where xi,
1<=i<=n and yj, 1<=j<=m are members of a finite set of symbols known as the
alphabet.
▪ We want to transform X into Y using a sequence of edit operations on X.
▪ The permissible edit operations are insert, delete and change and there is cost
associated with performing each.
The cost of sequence of operations is the sum of the costs of the individual
operations in the sequence.
▪ The problem of string editing is to identify minimum cost sequence of edit
operations that will transform X into Y.
▪ Let D (xi) be the cost of deleting the symbol xi from X,
▪ I (Yj) be the cost of inserting the symbol Yj into X,
▪ C (xi, yj) be the cost of changing the symbol Xi of X into Yj
Example: X be the sequence of x1,x2,x3,x4,x5=a, a, b, a, b and Y be the
sequence of y1,y2,y3,y4= b, a, b, b
The cost of each insertion and deletion operation is 1 and cost of changing any
symbol to any other symbol is 2. Find number of edit operations for
transforming string X into Y.
If i ≠ j
C D
I
Add C=+2 D=+1 I=+1
i=j Write diagonal element as it is.
j b a b b
i yj 0 1 2 3 4
xi 0
a 1
a 2
b 3
a 4
b 5
▪ The minimum cost of edit sequence is:
Ch 4 String Editing Page 1
b 5
▪ The minimum cost of edit sequence is:
x1 x2 x3 x4 x5
a a b a b
y1,y2,y3,y4= b, a, b, b
▪ String Editing is used to identify minimum cost sequence of edit operations that
will transform X into Y.
▪ Find number of edit operations for transforming string SSAB to AAB. The cost
of each insertion and deletion operation is 1 and cost of changing any symbol to
any other symbol is 2.
X= SSAB
Y= AAB
j A A B
i yj 0 1 2 3
xi 0
S 1
S 2
A 3
B 4
X = abc
Y = abc
j A B C
i yj 0 1 2 3
xi 0
A 1
B 2
C 3
The edit distance between two strings be zero when two strings are equal.
When the lengths of the two strings are equal edit distance is not zero.
Ch 4 String Editing Page 2
When the lengths of the two strings are equal edit distance is not zero.
Both dynamic programming and recursion is can be used to solve the edit
distance problem.
Ch 4 String Editing Page 3
Saturday, March 27, 2021 8:42 AM
❖ Travelling Salesman problem:
▪ Travelling Salesman Problem is solved by using dynamic programming method.
▪ It consists of Salesman and set of cities. The salesman travels along all the cities
and cost of travelling should be minimum.
▪ The salesman has to visit each city starting from one city and returning to same
city. The main challenge to this is minimize the total distance in this trip.
We have find out we should have minimum cost/distance in this trip.
Let G=(V,E) be a directed graph on n vertices. The cost of tour is sum of cost of
the edges on the tour.
Look at the figure:
A,B,C,D are four cities. These are connected by different roads. The distance of
the road are written (in kms) in the figure. A salesman starts his tour at A and
travels along the roads in such way that he visits every other city only once and
comes back to A. The distance travelled during his tour is minimum.
We observe different tours like
A->C->D->B->A , A->B->C->D->A
out of which in the first tour distance travelled is 16 km and in that of second is 11
km minimum.
Naturally the salesperson prefers the tour with minimum distance travelled.
▪ This is minimization problem. It is the problem of finding minimum distance.
g(i, s )=min {cij + g(j, s-{j})}
Ch 4 TSP Page 1
▪ It gives shortest path traversed by salesperson and path includes every vertex.
Shortest path is always cycle.
▪ The traveling salesman problem involves visiting each city only once.
Ch 4 TSP Page 2