module4_dynamic programming_2022.pdf

Dynamic Programming
Principle of Optimality
Multistage Graph
Single Source shortest path
All pair shortest path
0/1 knapsack
TSP
LCS

1. Dynamic Programming
Module 4
Shiwani Gupta 1

2. Dynamic Programming
Dynamic Programming is applied to optimization problems.
Solves problems with overlapping subproblems.
Each subproblem solved only once and result recorded in a table.
Shiwani Gupta 2

3. Divide n Conquer vs Dynamic
Programming
Subproblems are independent
Recomputations performed
Less Efficient due to rework
Recursive Method (Top Down
Approach of problem Solving)
Splits its input at specific
deterministic points usually in
middle
Subproblems are overlapping
No need to recompute
More Efficient
Iterative Method (Bottom Up
Approach of problem Solving)
Splits its input at every possible
split point
Shiwani Gupta 3

4. Greedy vs Dynamic Programming
Used to obtain optimum solution
Picks optimum solution from a set
of feasible solutions
Optimum selection is without
revising previously generated
selections
Only one decision sequence is
ever generated
No guarantee of getting optimum
solution
Also obtains optimum solution
No special set of feasible
solutions
Considers all possible
sequences to obtain possible
solution
Many decision sequences may
be generated
Guarantees optimal solution
using Principle of optimality
In an optimal sequence of decisions or choices, each subsequence must
also be optimal.
Shiwani Gupta 4

5. Principle of optimality
Principle of optimality:Suppose that in solving a problem, we have to
make a sequence of decisions D
1
, D
2
, …, D
n
. If this sequence is
optimal, then the last k decisions, 1 k n must be optimal.
e.g. the shortest path problem
If i, i
1
, i
2
, …, j is a shortest path from i to j, then i
1
, i
2
, …, j must be a
shortest path from i
1
to j
Shiwani Gupta 5

6. Applications of Dynamic Programming
Multistage Graphs
Single Source Shortest Path
All Pair Shortest Path
Optimal Binary Search Tree
0/1 Knapsack Problem
Traveling Salesman Problem
Longest Common Subsequence
Flow Shop Scheduling
Shiwani Gupta 6

7. Multistage Graph
Multistage Graph G=(V,E) is a directed graph whose vertices are
partitioned into k stages, k ≥ 2
To find a shortest path from source to sink
Apply the greedy method :
the shortest path from S to T : 1 + 2 + 5 = 8 S A B T
3
4
5
2 7
1
5 6
Shiwani Gupta 7

8. The shortest path in Multistage Graphs
The greedy method can not be applied to this case:
(S, A, D, T) 1+4+18 = 23.
The real shortest path is: (S, C, F, T) 5+2+2 = 9.
We obtain min. path at each current stage by considering path length
of each vertex obtained in earlier stage. S T
132
B E
9
A D
4
C F
2
1
5
11
5
16
18
2
Shiwani Gupta 8

9. Dynamic programming approach (forward approach):
d(S, T) = min{1+d(A, T), 2+d(B, T), 5+d(C, T)} S T
2
B
A
C
1
5
d(C, T)
d(B, T)
d(A, T) A
T
4
E
D
11
d(E, T)
d(D, T)
d(A,T) = min{4+d(D,T), 11+d(E,T)} = min{4+18, 11+13} = 22.
Forward approach
(backward reasoning)
Shiwani Gupta 9

10. d(B, T) = min{9+d(D, T), 5+d(E, T), 16+d(F, T)}
= min{9+18, 5+13, 16+2} = 18.
d(C, T) = min{ 2+d(F, T) } = 2+2 = 4
d(S, T) = min{1+d(A, T), 2+d(B, T), 5+d(C, T)}
= min{1+22, 2+18, 5+4} = 9.
The above way of reasoning is called backward reasoning.B T
5
E
D
F
9
16
d(F, T)
d(E, T)
d(D, T)
Dynamic programming approach
Shiwani Gupta 10

11. Backward approach
(forward reasoning)
d(S,T) = min{d(S, D)+d(D, T),d(S,E)+d(E,T), d(S, F)+d(F, T)}
= min{d(S, D)+18,d(S,E)+13, d(S, F)+2}
d(S,D)=min{d(S,A)+d(A,D),d(S,B)+d(B,D)}
=min{d(S,A)+4,d(S,B)+9}
Shiwani Gupta 11S T
132
B E
9
A D
4
C F
2
1
5
11
5
16
18
2

12. Backward approach
(forward reasoning)
d(S,E)=min{d(S,A)+d(A,E),d(S,B)+d(B,E)}
=min{d(S,A)+11,d(S,B)+5}
d(S,F)=min{d(S,B)+d(B,F),d(S,C)+d(C,F)}
=min{d(S,B)+16,d(S,C)+2}
d(S,A) = 1;d(S, B) = 2;d(S, C) = 5
d(S,D)= min{ 1+4, 2+9 } = 5d(S,E)= min{ 1+11, 2+5 } = 7
d(S,F)= min{ 2+16, 5+2 } = 7 d(S,T) = min{ 5+18, 7+13, 7+2 } = 9
Shiwani Gupta 12S T
132
B E
9
A D
4
C F
2
1
5
11
5
16
18
2

13. Shiwani Gupta 13

14. Shortest Path Problems
Single-source (single-destination). Find a shortest path
from a given source (vertex s) to each of the vertices.
Dijkstra’s Algorithm -Greedy
Bellman-Ford Algorithm –Dynamic Programming
Single-pair. Given two vertices, find a shortest path
between them. Solution to single-source problem solves
this problem efficiently, too.
All-pairs. Find shortest-paths for every pair of vertices.
Dynamic programming algorithm.
Floyd Warshall’s Algorithm –Dynamic Programming
Applications
static/dynamic network routing
robot motion planning
map/route generation in traffic
Shiwani Gupta 14

15. Bellman-Ford Algorithm
Dijkstra’s doesn’t work when there are negative edges
Bellman-Ford algorithm detects negative cycles (returns false) or
returns the shortest path-tree
AlgorithmBellmanFord (vertices, edges, source)
for(each vertex v) //loop to initialize graph
if (v is source) then
v.distance← 0
else
v.distance← infinity
v.pred← null
for (i← 1 to tot_vertices-1) //O(n)
for (each edge uv) //O(nm)
u ← uv.source
v ← uv.destinationShiwani Gupta 15

16. Bellman-Ford Algorithm
//newly obtained min dist
if( v.distance > u.distance + uv.weight ) then
v.distance = u.distance + uv.weight//relax edge
v.pred← u
for (each edge uv)
u ← uv.source
v ← uv.destination
if( v.distance > u.distance + uv.weight ) then
write(“Graph has negative weights”)
return false
Time Complexity: O (nm)
Shiwani Gupta 16

17. Bellman-Ford Example
5
¥ ¥
¥ ¥
0s
zy
6
7
8
-3
7
2
9
-2
xt
-4
6 ¥
7 ¥
0s
zy
6
7
8
-3
7
2
9
-2
xt
-4
5
6 4
7 2
0s
zy
6
7
8
-3
7
2
9
-2
xt
-4
5
2 4
7 2
0s
zy
6
7
8
-3
7
2
9
-2
xt
-4
5
2 4
7 -2
0s
zy
6
7
8
-3
7
2
9
-2
xt
-4
5
Shiwani Gupta 17

18. Shiwani Gupta 18

19. All Pair Shortest Path
Find the distance between every pair of vertices in a
weighted directed graph G.
We can make n calls to Dijkstra’s algorithm (if no negative
edges), which takes O(n(nlog n+m))time or O(n
3
) time.
Likewise, n calls to Bellman-Ford would take O(n
2
m) time.
We can achieve O(n
3
) time using dynamic programming
Floyd Warshall’s Algorithm (Generalization of Dijkstra’s)
Shiwani Gupta 19

20. Floyd Warshall’s Algorithm
Representation of the Input
We assume that the input is represented by a weight matrix
W= (w
ij); i,j in Ethat is defined by
w
ij= 0 if i=j
w
ij= w(i,j) if ijand (i,j) in E
w
ij=  if ijand (i,j) not in E
Representation of the Output
If the graph has n vertices, we return a distance matrix (d
ij), where d
ijthe
length of the path from ito j.
Intermediate Vertices
Without loss of generality, we will assume that V={1,2,…,n}, i.e., that
the vertices of the graph are numbered from 1 to n.
Given a path p=(v
1, v
2,…, v
m) in the graph, we will call the vertices v
k
with index k in {2,…,m-1} the intermediate vertices of p.
Shiwani Gupta 20

21. The key to the Floyd-Warshallalgorithm is the following definition:
Let d
ij
(k)
denote the length of the shortest path from ito j such that all
intermediate vertices are contained in the set {1,…,k}.
Consider a shortest path p from ito j such that the intermediate vertices
are from the set {1,…,k}.
If the vertex k is not an intermediate vertex on p, then d
ij
(k)
= d
ij
(k-1)
If the vertex k is an intermediate vertex on p, then d
ij
(k)
= d
ik
(k-1)
+ d
kj
(k-
1)
Interestingly, in either case, the subpathscontain merely nodes from
{1,…,k-1}.
Floyd Warshall’s Algorithm
Shiwani Gupta 21

22. Recursive Formulation
Therefore, we can conclude thatd
ij
(k)
= min{d
ij
(k-1)
, d
ik
(k-1)
+ d
kj
(k-1)
}
If we do not use intermediate nodes, i.e.,
when k=0, then d
ij
(0)
= w
ij
If k>0, then d
ij
(k)
= min{d
ij
(k-1)
, d
ik
(k-1)
+ d
kj
(k-1)
}
Shiwani Gupta 22

23. Floyd Warshall algorithm
AlgorithmAllPair(G) //assumes vertices 1,…,n
for all vertex pairs (i,j)
if i = j
D
0[i,i] 0
else if (i,j) is an edge in G
D
0[i,j] weight of edge (i,j)
else
D
0[i,j] + 
for k 1 to n do
for i 1 to n do
for j 1 to n do
D
k[i,j] min{D
k-1[i,j], D
k-1[i,k]+D
k-1[k,j]}
return D
n
Can reduce compexity to O (n
2
) by using single array
Shiwani Gupta 23

24. Shiwani Gupta 24

25. Shiwani Gupta 25

26. Shiwani Gupta 26

27. Shiwani Gupta 27

28. Example of Floyd-Warshall
Shiwani Gupta 28

29. Shiwani Gupta 29

30. The 0/1 Knapsack Problem
Given: A set S of n items, with each item i having
w
i-a positive weight
b
i-a positive benefit
Goal: Choose items with maximum total benefit but with
weight at most W.
If we are notallowed to take fractional amounts, then this is
the 0/1 knapsack problem.
In this case, we let Tdenote the set of items we take
Objective: maximize
Constraint:
Ti
ib 


Ti
iWw
Shiwani Gupta 30

31. Given: A set S of n items, with each item i having
b
i-a positive “benefit”
w
i-a positive “weight”
Goal: Choose items with maximum total benefit but with weight at
most W.
Example
Weight:
Benefit:
1 2 3 4 5
4 in2 in2 in6 in2 in
$20 $3 $6$25$80
Items:
box of width 9 in
Solution:
•item 5 ($80, 2 in)
•item 1 ($20, 4in)
•item 3 ($6, 2in)
“knapsack”
Shiwani Gupta 31

32. 0/1 Knapsack Algorithm, First Attempt
S
k: Set of items numbered 1 to k.
Define B[k] = best selection from S
k.
Problem:does not have subproblem optimality:
Consider set S={(3,2),(5,4),(8,5),(4,3),(10,9)} of
(benefit, weight) pairs and total weight W = 20
Best for S
4:
Best for S
5:
Shiwani Gupta 32

33. 0/1 Knapsack Algorithm, Second Attempt
S
k: Set of items numbered 1 to k.
Define B[k,w] to be the best selection from S
kwith weight at most w
Good news: this does have subproblem optimality.
i.e., the best subset of S
kwith weight at most w is either
the best subset of S
k-1with weight at most w or
the best subset of S
k-1with weight at most w-w
kplus item k





else}],1[],,1[max{
if],1[
],[
kk
k
bwwkBwkB
wwwkB
wkB
Shiwani Gupta 33
https://youtu.be/nLmhmB6NzcM19:21

34. 0/1 Knapsack Algorithm
Consider set S={(1,1),(2,2),(4,3),(2,2),(5,5)} of (benefit, weight)
pairs and total weight W = 10
Shiwani Gupta 34

35. 0/1 Knapsack Algorithm
Trace back to find the items picked
Shiwani Gupta 35

36. 0/1 Knapsack Algorithm
Each diagonal arrow corresponds to adding one item into the bag
Pick items 2,3,5
{(2,2),(4,3),(5,5)} are what you will take away
Shiwani Gupta 36

37. 0/1 Knapsack Algorithm
Algorithm 01Knapsack(B,w,n,W):
Input:set S of n items with benefit B
iand weight w
i; maximum weight W
Output:benefit of best subset of S with weight at most W
forw 0 to W do
B[0,w] 0
fori 1 to n do
forw 0to Wdo
ifw
i≤ w then
B[i,w]max{B[i-1,w],B[i]+B[i-1,w-w
i]}
keep[i,w]=1 //if keeping i
th
file in knapsack
else
B[i,w]B[i-1,w]
keep[i,w]=0
returnB[n,W] //max computing time of files that can fit into storage
K=W
for i = n downto 1
if keep[i,k]==1
output i
k=k-w[i]
Running time: O(nW).
Shiwani Gupta 37

38. Shiwani Gupta 38
Weights:{3,4,6,5}
Profits:{2,3,1,4}
Theweightoftheknapsackis8kg

39. Travelling Salesman Problem
LetGbeadirectedgraphdenotedby(V,E).Edgesaregivenalongwith
theircostC
ij.Atourforthegraphshouldbesuchthatallthevertices
shouldbevisitedonlyonceterminatingatsourcevertexwithtourof
minimumcost(sumofcostofedgesontour).
DynamicProgrammingApproach
•Letfunctiong(1,V-{1})istotallengthoftourterminatingat1.
•Letd[i,j]beshortestpathb/wtwoverticesiandj.
•Principleofoptimality:PathV
i,V
i+1,…V
jmustbeoptimalforall
pathsbeginningatV
iandendingatV
jandpassingthroughall
intermediatevertices{V
i+1,…V
j-1}once.
•g(1,V-{1})=min{c
1k+g(k,V-{1,k})}
•g(i,S)=min{c
1j+g(j,S-{j})}wherejєSandiєS
•g(i,Ф)=c
i1,1≤i≤n
2≤k ≤n
j є S
Shiwani Gupta 39
https://youtu.be/XaXsJJh-Q5Y

40. Travelling Salesman Problem
1234
10101520
250910
3613012
48890
g(2, Ф) = c
21= 5; g(3, Ф) = c
31= 6; g(4, Ф) = c
41= 8
•K=1
Set{2}
g(3,{2})=c
32+ g(2,Ф) = c
32+ c
21= 13+5=18; p(3,{2})=2
g(4,{2})=c
42+ g(2,Ф) = c
42+ c
21= 8+5=13; p(4,{2})=2
Set{3}
g(2,{3})=c
23+ g(3,Ф) = c
23+ c
31= 9+6=15; p(2,{3})=3
g(4,{3})=c
43+ g(3,Ф) = c
43+ c
31= 9+6=15; p(4,{3})=3
Set{4}
g(2,{4})=c
24+ g(4,Ф) = c
24+ c
41= 10+8=18; p(2,{4})=4
g(3,{4})=c
34+ g(4,Ф) = c
34+ c
41= 12+8=20; p(3,{4})=4
•k=2
Set{3,4}: g(2,{3,4}) = min {c
23+ g(3,{4}), c
24+ g(4,{3})}=25; p(2,{3,4})=4
Set{2,4}: g(3,{2,4}) = min {c
32+ g(2,{4}), c
34+ g(4,{2})}=25; p(3,{2,4})=4
Set{2,3}: g(4,{2,3}) = min {c
42+ g(2,{3}), c
43+ g(3,{2})}=23; p(4,{2,3})=2
•k=3
Set{2,3,4}: f= g(1,{2,3,4})= min{c
12+ g(2,{3,4}), c
13+ g(3,{2,4}), c
14+ g(4,{2,3})} =
min {10+25, 15+25, 20+23} = 35; p(1,{2,3,4})=2
ans: 12431
40

41. Shiwani Gupta 41
n!
n*(n*2^n)

42. Shiwani Gupta 42

43. Longest Common Subsequence
Given two strings, find a longest subsequence that they share
substring vs. subsequence of a string
Substring: the characters in a substring of S must occur
contiguouslyin S
Subsequence: the characters can be interspersed with gaps.
INPUT: two strings
OUTPUT: longest common subsequence
ACTGAACTCTGTGCACT
TGACTCAGCACAAAAAC
Shiwani Gupta 32

44. Longest common subsequence
Sequences x
1,…,x
n, and y
1,…,y
m
LCS(i,j) = length of a longest common
subsequence of x
1,…,x
iand y
1,…,y
j
if x
iy
jthen
LCS(i,j) = max (LCS(i-1,j),LCS(i,j-1))
if x
i= y
jthen
LCS(i,j) = 1 + LCS(i-1,j-1)
Running time = O(mn)
Shiwani Gupta 33

45. Let’s give a score M an alignment in this way,
M=sum s(x
i,y
j), where
x
iis the i character in the first aligned sequence
y
jis the j character in the second aligned sequence
s(x
i,y
j)= 1 if x
i= y
j
s(x
i,y
j)= 0 if x
i≠y
j orany of them is a gap
The score for alignment:
ababc.
abd.cb
M=s(a,a)+s(b,b)+s(a,d)+s(b,.)+s(c,c)+s(.,b)=3
To find the longest common subsequence between sequences S
1and
S
2is to find the alignment that maximizes score M.
Shiwani Gupta 34

46. Longest Common Subsequence
Score matrix M Trace back table B
M
7,11=6 (lower right corner of Score matrix)
This tells us that the best alignment has a score of 6
What is the best alignment?
Shiwani Gupta 35

47. Longest Common Subsequence
We need to use trace back table to find out the best alignment,
which has a score of 6
(1)Findthepathfrom
lowerrightcornerto
upperleftcorner
Thus, the optimal alignment is
The longest common subsequence is
G.A.T.C.G.A
Shiwani Gupta 36

48. Longest Common Subsequence
Algorithm LCS(string A, stringB) {
Input strings A and B
Outputthe longest common subsequence of A and B
M: Score Matrix
B: trace back table (use letter a, b, c for )
n=A.length()
m=B.length()
// fill in M and B
for (i=0;i<m+1;i++)
for (j=0;j<n+1;j++)
if (i==0) || (j==0)
then M(i,j)=0;
else if (A[i]==B[j])
M(i,j)=M[i-1,j-1]+1
{update the entry in trace table B}
else
M(i,j)=max {M[i-1,j], M[i,j-1]}
{update the entry in trace table B}
then use trace back table B to print out the optimal alignment
…
Running time = O(mn)

49. Applications of LCS
MolecularBiology:DNAsequences(genes)canbe
representedassequencesoffourlettersACGT,corresponding
tothefoursubmoleculesformingDNA.Whenbiologistsfind
newsequences,theytypicallywanttoknowwhatother
sequencesitismostsimilarto.Onewayofcomputinghow
similartwosequencesareistofindthelengthoftheirlongest
commonsubsequence.
FileCompression:TheUnixprogram"diff"isusedto
comparetwodifferentversionsofthesamefile,todetermine
whatchangeshavebeenmadetothefile.Itworksbyfindinga
longestcommonsubsequenceofthelinesofthetwofiles;any
lineinthesubsequencehasnotbeenchanged,sowhatit
displaysistheremainingsetoflinesthathavechanged.Inthis
instanceoftheproblemweshouldthinkofeachlineofafile
asbeingasinglecomplicatedcharacterinastring.

50. Dynamic Programming to LCS
OptimalSubstructure
Overlappingsubproblems
Themethodofdynamicprogrammingreducesthenumber
offunctioncalls.Itstorestheresultofeachfunctioncallso
thatitcanbeusedinfuturecallswithouttheneedfor
redundantcalls.
Intheabovedynamicalgorithm,theresultsobtainedfrom
eachcomparisonbetweenelementsofXandtheelements
ofYarestoredinatablesothattheycanbeusedinfuture
computations.
So,thetimetakenbyadynamicapproachisthetimetaken
tofillthetable(ie.O(mn)).
Shiwani Gupta 39

51. Task
Determine LCS of <0100110101> and <10101101>.
Find LCS of following strings X=“ABCBDAB”
Y=“BDCABA”
Shiwani Gupta 40