Module 4: Dynamic

Programming
● General Method,
● Multistage graphs,
● Single source shortest path:Bellman Ford Algorithm
● All pair shortest path: Floyd Warshall Algorithm,
● Assembly-line scheduling Problem
● 0/1 knapsack Problem,
● Travelling Salesperson problem,
● Longest common subsequence
Multistage Graphs
• Similar to divide-and-conquer algorithm
• Differs in the fact that sub problems are not
independent
• Solves each subproblem and saves answer to
avoid repetition
• Typically applied to optimization problems
 Algorithm 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 in a
bottomup fashion.
4. Construct an optimal solution from computed
information.
 Examples(wiki)
• In 1940s by Richard Bellman to describe the process of solving problems where one needs to
find the best decisions one after another.
• Tower of Hanoi puzzle
• Graph theory; game theory; AI and machine learning; economics and finance
problems; bioinformatics; as well as calculating the shortest path, which is used in
GPS.
• The Bellman–Ford algorithm for finding the shortest distance in a graph.
• The Viterbi algorithm (used for hidden Markov models, and particularly in part of
speech tagging)
• The Earley algorithm (a type of chart parser)
• Many string algorithms including longest common subsequence, longest increasing
subsequence, longest common substring, Levenshtein distance (edit distance)
• The Selnninger (a.k.a. System R) algorithm for relational database query
optimization
 Fibo/ Tower of Hanoi example
• https://www.cs.usfca.edu/~galles/visualization/DPFib.html...
Simulation of fibo
• https://haubergs.com/hanoi

Technique of memoization or memoisation is an optimization technique used primarily to speed

up computer programs by storing the results of expensive function calls and returning the cached
result when the same inputs occur again
Multistage Graph
Multistage Graph
Multistage Graph
ALGORITHM MULTISTAGE (G, K, n, P)
cost[n] ← 0
for j ← n-1 to 1 do
cost[j] ← c[j,r]+cost[r]
π[j] ← r
end
p[1] ← 1
p[k] ← n
for j ← 2 to k-1 do
p[j] ← π[p[j-1]]
end
Complexity Analysis
If graph G has |E| edges, then cost computation time would be O(n+ |
E|).

The complexity of tracing the minimum cost path would be O(k), k<n.
Thus total time complexity of multistage graph using dynamic
programming would be O(n+ |E|).
Solve the below problem by forward approach
d(S,A) =1 S-A
d(S,B) =2 S-B
d(S,C) =7 S-C
d(S,D) = min{d(S,A)+c(A,D) , d(S,B)+c(B,D)}
= min{1+3 , 2+4} = 4 S-A-D
d(S,E) = min{d(S,A)+c(A,E) , d(S,B)+c(B,E) , d(S,C)+c(C,E)}
= min{1+6 , 2+10, 7+3} =7
S-A-E
d(S,T) = min{d(S,D)+c(D,T) , d(S,E)+c(E,T) , d(S,C)+c(C,T)}
= min{4+8, 7+2, 7+10} =9
S-A-E-T
Solve the below problem by backward
approach
 V 1 2 3 4 5 6 7 8 9 10 11 12

Cost 16 7 9 18 15 7 5 7 4 2 5 0

d 2/3 7 6 8 8 10 10 10 12 12 12 12

d(1,1) = 2 d(1,1) = 3
d(2,2) = 7 d(2,3) = 6
d(3,7) = 10 d(3,6) = 10
d(4,10) = 12 d(4,10) = 12

Final Path : 1-2-7-10-12 // 1-3-6-10-12

Minimum Cost : 16
Bellman Ford
(Single source shortest path)
Complexity of Bellman ford Algorithm
In general graph, the complexity can be considered as O(|E||V|)
where |E| is the no of edges & |V| is the number of vertices i.e
(n-1). Therefore, the complexity is O(n2).

In complete graph the no of edges is (n(n-1))/2

O(|E||V|) = O((n(n-1)/2) (n-1)
= O(n3)
 -1
2
5

6 3
-2
1

5
1 3 7

-2
5 3

6
4
-1
List of edges - (1,2), (1,3), (1,4), (3,2), (4,3), (2,5), (3,5), (4,6), (5,7), (6,7)
v 1 2 3 4 5 6 7
d[v] 0 ∞ ∞ ∞ ∞ ∞ ∞
PN - - - - - - -

After 1st iterations

v 1 2 3 4 5 6 7
d[v] 0 3 3 5 5 4 7
PN - 3 4 1 2 4 6
After 2nd iterations
v 1 2 3 4 5 6 7
d[v] 0 1 3 5 2 4 5
PN - 3 4 1 2 4 5

After 3rd iterations

v 1 2 3 4 5 6 7
d[v] 0 1 3 5 0 4 3
PN - 3 4 1 2 4 5
 After 4th iterations
v 1 2 3 4 5 6
7
d[v] 0 1 3 5 0 4
3
PN - 3 4 1 2 4
5 2
5

1 3 7

6
4
 1
7 10

8 5
3 5 2

2
3 8
4
 1
2 4
8
2 5

1 -3 4 6

-4
4 6
3 5
-2
All pair shortest path (Floyd-Warshall Algorithm)
All pair shortest path (Floyd-Warshall Algorithm)
 7
1 2

10 4
3

3
 2
1 2

3
6 7

4 3
1
Assembly Line Scheduling
Assembly Line Scheduling
Assembly Line Scheduling
 Assembly Line Scheduling
f1[j] 9 18 20 24 32 35
f2[j] 12 16 22 25 30 37 fopt=38
j 1 2 3 4 5 6

l1[j] 1 2 1 1 2
l2[j] 1 2 1 2 2 lopt=1
j 2 3 4 5 6
Assembly Line Scheduling
 0/1 Knapsack
ALGORITHM Dynamic-0-1-knapsack (v, w, n, W)
for w = 0 to W do
c[0, w] = 0
for i = 1 to n do
c[i, 0] = 0
for w = 1 to W do
if wi ≤ w then
if vi + c[i-1, w-wi] then
c[i, w] = vi + c[i-1, w-wi]
else
c[i, w] = c[i-1, w]
end
else
c[i, w] = c[i-1, w]
end
end
end
Travelling Salesman problem

Given a set of n cities , find the minimum length path such that it
covers each city exactly once and terminates the tour at starting city”
Travelling Salesman Problem
Longest Common Subsequence (LCS)
ALGORITHM LCS(X,Y)
for i ← 1 to m do
LCS[i,0] ← 0
end
for j ← 1 to n do
LCS[0,j] ← 0
end
for i ← 1 to m do
for j ← 1 to n do
if Xi == Yj then
LCS[i,j] ← LCS[i-1, j-1] +1
elseif LCS[i-1, j] ≥ LCS[i, j-1] then
LCS[i,j] ← LCS[i-1, j]
else
LCS[i,j] ← LCS[i, j-1]
end
end
end
return LCS
Complexity Analysis of Longest
Common Subsequence

If we have a string P of length m then 2m subsequences are possible & the

time required for the worst case would be O(n2m).

In dynamic programming, the only table of size n x m is filled up using 2

nested for loop. So running time of dynamic programming approach
would take O(nm) same as the space complexity.
Q1). Find LCS for following string X=ACBAED & Y=ABCABE

0 A C B A E D

0 0 0 0 0 0 0 0

A 0 1 1 1 1 1 1

B 0 1 1 2 2 2 2

C 0 1 2 2 2 2 2

A 0 1 2 2 3 3 3

B 0 1 2 3 3 3 3

E 0 1 2 3 3 4 4

Soln : ACBE // ACAE // ABAE

Q2). Using algorithm determine an longest common sequence of
(A,B,C,D,B,A,C,D,F) & (C,B,A,F).
Soln : CBAF
Q3). P=(MLNOM) Q=(MNOM)
Soln : MNOM
Q4). S1 = abdacc S2 = babcc
Soln : bacc / abcc
Q5). S1 = stone S2 = longest
Soln : one