B.
Tech 4th SEMESTER – CSE
DESIGN & ANALYSIS OF ALGORITHMS
CHAPTER – 08
Dynamic programming
1
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.
• 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.
• 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
2
LONGEST COMMON SUBSEQUENCE (LCS)
As the name suggests:
LONGEST means it should be the longest string.
COMMON means you will be given with 2 strings. You have to find out the common strings in them.
SUBSEQUENCE: It’s a sequence of strings / sequence of characters from a string, and this sequence of
characters would be in increasing order with respect to their position.
Eg:
W= a b c d
The possible subsequences are : ab, bd, ac, ad, acd, bcd, abcd, ……………..
The subsequences not possible are : ca, db, ……..
The of subsequences possible are : 2n
n= no. of elements in the given string W
Here, n= 4
24 = 16
3
Suppose Given:
W1= a b c d
W2= b c d
Possible Subsequences for W1 are: ab, bd, ac, ad, acd, bcd, abcd, …………….. Till 16 subsequences
Possible Subsequences for W2 are: b, bc, cd, bd, bcd, …………….. Till 08 subsequences
Practically, it is not possible always to find out the LCS using the above technique if the given string is a
longer ones. Hence, we apply the dynamic programming approach to find out the LCS.
4
Longest common subsequence (LCS)
Length of the LCS is 4
The required LCS is: B C B A
5
6
Lcs algorithm
The procedure takes time O(m+n), since
it decrements at least one of i and j in
each recursive call.
The running time of the procedure is
Ɵ(mn), since each table entry takes Ɵ (1)
time to compute.
7
Matrix chain multiplication
▪ The number of column of 1st matrix must be equal to the number of row of 2nd matrix.
▪ The dimension of the resultant matrix = row of 1st matrix X column of 2nd matrix
▪ Total number of multiplications= 2x3x2 = 12
8
9
• Both (A1 * A2)* A3 and A1* (A2 * A3) would give the same product because they are associative in property.
• But we are actually not interested in the product , rather we are trying to find out the effort required to
multiply the both possibilities.
• This is known as parenthesizing.
• In the above case there are only two parenthesization possible and the cost each produces is 40 and 36
respectively.
• But if lets say there were 10 matrices A1*A2*………..*A10 finding out which matrix should be multiplied first
would be a big problem. Hence finding out an easier method to multiply them is better.
• So, given any matrices, first find out how to multiply them and then multiply the matrices.
• If you have a chain of matrices for multiplication, then first of all find out which multiplication should be
performed (how the parenthesization should be done) such that the total efforts put in for multiplying them
should be minimized.
• The above example shows that the parenthesization that gives 36 is better.
10
• Hence dynamic programming approach says that you should try all possible parenthesization and pick up the
best one.
• Let us generate the formula:
11
• Let just apply the formula for finding out the parenthesization for multiplying 4 matrices:
12
13
14
15
16
k= 2
k= 1
The value of k= 2
17
k= 3
k= 2
The value of k= 2
18
k= 4
k= 3
The value of k= 4
19
20
k= 3
k= 2
k= 1
The value of k= 2
21
k= 4
k= 3
k= 2
The value of k= 2
22
23
k= 4
k= 3
k= 2
k= 1
24
The value of k= 2
25
To Print the optimal parenthesization, we use the PRINT-OPTIMAL-PARENS procedure.
26
Matrix chain multiplication algorithm
27
THANK YOU
28