DESIGN AND ANALYSIS OF ALGORITHMS

UNIT-III
DYNAMIC PROGRAMMING
Dynamic Programming: General method, Applications- Multi-stage graph, All pairs shortest
path problem, Optimal binary search trees, Reliability design, Travelling sales-person
problem, Reliability design.
------------------------------------------------------------

INTRODUCTION
The drawback of greedy method is, we will make one decision at a time. This can be
overcome in dynamic programming. In this we will make more than one decision at a time.

Dynamic programming is an algorithm design method that can be used when the solution to a
problem can be viewed as the result of a sequence of decisions. Dynamic programming is
applicable when the sub-problems are not independent, that is when sub-problems share sub-
sub-problems. A dynamic programming algorithm solves every sub-sub-problem just once
and then saves its answer in a table, there by avoiding the work of re-computing the answer
every time the sub-problem is encountered.

Definition:
It is a programming technique in which solution is obtained from a sequence of decisions

General Method:
The fundamental dynamic programming model may be written as,

F (R) max P (R)  F (R  R )

n 0Rn R n n1 n
Where n = 2,3,4…
Fn(0)=0
F1(R)=P1(R)

Once F1(R) is known equation(1) provides a relation for evaluation of F2(R), F3(R)…. This
recursive process ultimately leads to the value of Fn-1(R) and finally Fn(R) at which process
stops.

A dynamic programming problem can be divided into a number of stages where an optimal
decision must be made at each stage. The decision made at each stage must take into account
its effects not only on the next stage, but also on the entire subsequent stages. Dynamic
programming provides a systematic procedure whereby starting with the last stage of the
problem and working backwards one makes an optimal decision for each stage of problem.
The information for the last stage is the information derived from the previous stage.

Dynamic programming design involves 4 major steps.

1) Characterize the structure of optimal solution.
2) Recursively define the value of an optimal solution.
3) Compute the value of an optimum solution in a bottom up fashion.
4) Construct an optimum solution from computed information.

The Dynamic programming technique was developed by Bellman based upon his principle
known as principle of optimality. This principle states that “An optimal policy has the
property that, what ever the initial decisions are, the remaining decisions must constitute an
optimal policy with regard to the state resulting from the first decision”.

M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 1

General Characteristics of Dynamic Programming:
The general characteristics of Dynamic programming are
1) The problem can be divided into stages with a policy decision required at each stage.
2) Each stage has number of states associated with it.
3) Given the current stage an optimal policy for the remaining stages is independent of
the policy adopted.
4) The solution procedure begins be finding the optimal policy for each state of the last
stage.
5) A recursive relation is available which identifies the optimal policy for each stage
with n stages remaining given the optimal policy for each stage with (n-1) stages
remaining.

APPLICATIONS OF DYNAMIC PROGRAMMING

1) Multi stage Graph
2) All pair shortest path
3) Optimal Binary search Trees
4) Reliability Design
5) Traveling sales person problem

1) OPTIMAL BINARY SEARCH TREE

A Binary search tree is a binary tree that is either empty or in which every node
contains a key and satisfies the following conditions.

1. The key in the left child of a node (if it exists) is less than the key in its parent
node.
2. The key in the right child of a node is greater than the key in its parent node.
3. The left and right subtrees of the root are again binary search trees.

No two entries in a binary search tree may have equal keys.

Ex) Binary Search Trees

(1) (2)

If we want to search an element in binary search tree, first that element is compared
with root node. If element is less than root node then search continue in left subtree.
If element is greater than root node then search continue in right subtree. If element
is equal to root node then print search was successful (element found) and terminate
search procedure.

algorithm search(t,x)
M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 2
 {
if (t==0) then return 0;
else
if (x = t->data) then return t;
else
if ( x< t->data) then return search (t->left, x);
else
return search (t->right, x);
}

The possible binary search trees for the identifier set (a1,a2,a3=do, if, stop)
Hence n=3
1 2n 1 2 x3
The number of possible binary search trees = Cn = C3
n 1 3 1
1 1 1 2  3 4  5 6 1
= 6C3 =    20  5
4 4 1 2  31 2  3 4

M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 3

 The sequence of key words to construct a BST may be one of the following
stop,if,do if,do,stop do,if,stop

(a) (b) (c)

stop,do,if do,stop,if

(d) (e)

cos t(T )  ∑ p(i)  level(ai )  ∑ q(i)  level(E 1) i

1in 0in

1
p(i)  q(i) 
7
a) 1 1 1 1 1 1 1 15
1  2  3   1 2  3   3  
7 7 7 7 7 7 7 7

b) 1 1 1 1 1 1 1 13
1 2  2   2 2  2   2 
7 7 7 7 7 7 7 7

c) 1 1 1 1 1 1 1 15
1 2  3   1 2  3   3 
7 7 7 7 7 7 7 7

d) 1 1 1 1 1 1 1 15
1 2  3   1 2  3   3 
7 7 7 7 7 7 7 7

e) 1 1 1 1 1 1 1 15
1 2  3   1 2  3   3 
7 7 7 7 7 7 7 7

In the above binary search tree the cost of the tree 2 is minimum. Hence it is optimal
binary search tree.

M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 4

 A binary search tree have maximum of two childs. i.e 0, 1 or 2 childs.
p(i) - probability of searching an internal node.
Q(i) – probability of searching an external node.
A successful search is terminated at an internal node denoted by circle (O) ans
unsuccessful search is terminated at an external node by square ( ).

cos t(T )  ∑
1in
p(i)  level(ai )  ∑ q(i)  level(E 1)
0in
i

Example 2) Let n=4 and (a1, a2, a3, a4 ) = ( do, if , read, while ) -- internal nodes
p(1:4)=(3,3,1,1)
q(0:4)=(2,3,1,1,1)

External nodes (E0,E1,E2,E3,E4)

As there are 4 internal nodes (a1, a2, a3, a4 ) = ( do, if , read, while )
1 2n
the number of possible binary search trees = Cn = 14
n 1
w(i,j) = p(j) + q(j) + w(i,j-1) weight of tij
ik  j c(i, k 1)  c(k, j) w(i, j)
c(i, j)  min cost of tij
r(i,j) = k root of tij

W01 = E0 a1 E1
W12 = E1 a2 E2
W23 = E2 a3 E3
W34 = E3 a4 E4
W02 = E0 a1 E1 a2 E2
W13 = E1 a2 E2 a3 E3
W24 = E2 a3 E3 a4 E4
W03 = E0 a1 E1 a2 E2 a3 E3
W14 = E1 a2 E2 a3 E3 a4 E4
W04 = E0a1E1a2E2a3E3a4E4

In order to solve above problem, first we will draw one table by taking ‘I’ corresponds
to columns. The cells in the table can be indicated as wj,j+i, cj,j+i,Rj,j+i.
0 1 2 3 4
W00=2 W11=3 W22=1 W33=1 W44=1
0 C00=0 C11 =0 C22=0 C33=0 C44=0
R00=0 R11=0 R22=0 R33=0 R44=0
W01= W12= W23= W34=
1 C01= C12 = C23= C34 =
R01= R12 = R23= R34 =
W02= W13= W24=
2 C02 = C13 = C24=
R02 = R13 = R24=
W03= W14=
3 C03 = C14 =
R03 = R14 =
W04=
4 C04 =
R04 =
Principle of optimality was applied.

M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 5

 The first row is initiated as W(i,i)=q(i) R(i,i)=0 C(i,i)) = 0
It means
W00 = q(0) = 2 C00 = R00 = 0
W11 = q(1) = 3 C11 = R11 = 0
W22 = q(2) = 1 C22 = R22 = 0
W33 = q(3) = 1 C33 = R33 = 0
W44 = q(4) = 1 C44 = R44 = 0
The remaining values of cells can be calculated using equations as follows
w(i,j)=p(j) + q(j) + w(i,j-1)
w(0,1)=p(1) + q(1) + w(0,0) = 3+3+2 = 8
w(1,2) = p(2) + q(2) + w(1,1) = 3+1+3 = 7
w(2,3) = p(3) + q(3) + w(2,2) = 1+1+1 = 3
w(3,4) = p(4) + q(4) + w(3,3) = 1+1+1 = 3
w(0,2) = p(2) + q(2) + w(0,1) = 3+1+8 = 12
w(1,3) = p(3) + q(3) + w(1,2) = 1+1+7 = 9
w(2,4) = p(4) + q(4) + w(2,3) = 1+1+3 = 5
w(0,3) = p(3) + q(3) + w(0,2) = 1+1+12 = 14
w(1,4) = p(4) + q(4) + w(1,3) = 1+1+9 = 11
w(0,4) = p(4) + q(4) + w(0,3) = 1+1+14 = 16

c(i, j)  min c(i, k 1)  c(k, j) w(i, j)

ik  j

C(0,1) = min { c(0,0) + c(1,1) } + w(0,1) = 0 + 0 + 8 = 8 when k=1

R(0,1)=1

C(1,2) = min { c(1,1) + c(2,2) } + w(1,2) = 0 + 0 + 7 = 7 when k=2

R(1,2)=2

C(2,3) = min { c(2,2) + c(3,3) } + w(2,3) = 0 + 0 + 3 = 3 when k=3

R(2,3)=3

C(3,4) = min { c(3,3) + c(4,4) } + w(3,4) = 0 + 0 + 3 = 3 when k=4

R(3,4)=4

When k=2
C(0,2) = min { c(0,1) + c(2,2) } + w(0,2) = 8 + 0 + 12 = 20

When k=1
C(0,2) = min { c(0,0) + c(1,2) } + w(0,2) = 0 + 7 + 12 = 19

C(0,2) = min{20,19} = 19
r(0, 2) = 1

When k=3 or 2
C(1,3) = min { c(1,1) + c(2,3), c(1,2) + c(3,3) } + w(1,3) ={ 0 + 3, 7 + 0} + 9 = 12
r(1, 3) = 2

When k=3
C(2,4) = min { c(2,2) + c(3,4) } + w(2,4) = 0 + 3 + 5 = 8
When k=4
C(2,4) = min { c(2,3) + c(4,4) } + w(2,4) = 3 + 0 + 5 = 8
r(2,4)=3

M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 6

When k=1 or 2 or 3
C(0,3) = min { c(0,0) + c(1,3), c(0,1) + c(2,3), c(0,2)+c(3,3) } + w(1,3)
=min{12,11,10} + 14 = 10 + 14 = 24
r(0,3)=2

When k=2 or 3 or 4
C(1,4) = min { c(1,1) + c(2,4), c(1,2) + c(3,4), c(1,3)+c(4,4) } + w(1,4)
=min{0+8, 7+3, 12+0} + 11 = 8 + 11 = 19
r(1,4)=2

When k=1 or 2 or 3 or 4
C(1,4) = min { c(0,0) + c(1,4), c(0,1) + c(2,4), c(0,2)+c(3,4), c(0,3)+c(4,4) } + w(0,4)
=min{19, 16, 23, 25} + 16 = 16 + 16 = 32
R(0,4)=2

0 1 2 3 4
W00=2 W11=3 W22=1 W33=1 W44=1
0 C00=0 C11 =0 C22=0 C33=0 C44=0
R00=0 R11=0 R22=0 R33=0 R44=0
W01=8 W12=7 W23=3 W34=3
1 C01=8 C12 =7 C23=3 C34 =3
R01=1 R12 =2 R23=3 R34 =4
W02=12 W13=9 W24=5
2 C02 =19 C13 =12 C24=8
R02 =1 R13 =2 R24=3
W03=14 W14=11
3 C03 =25 C14 =19
R03 =2 R14 =2
W04=16
4 C04 =32
R04 =2

Now observe the tables last cell i.e. 4th row 0th column, contains r04 = 2 i.e. r04 = a2
( 2 corresponds to second node a2).
R04=k, then k=2
To build OBST R(0,4)=2=k=2

Hence a2 become the root node

Let T be OBST Ti,j = Ti,k-1, and Tk,j

T04 is divided into two parts i.e T01 and T24

T01=r(0,1)=1=k=1
T24=r(2,4)=3=k=3

T01 is divided into two parts T00 and T11 where k=1
T24 is divided into two parts T22 and T34 where k=3
T34 is divided into two parts T33 and T44 where k=4

Since r00, r11, r22, r33, r44 = 0 these are external nodes and can be neglected.

M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 7

 Let T be the optimal binary search tree

Algorithm OBST(p,q,n)
{
for i:=0 to n-1 do
{
w[i,i]:=q[i];
r[i,i]:=0;
c[i,i]:=0;
w[i,i+1]:=q[i]+q[i+1]+p[i+1];
r[i,i+1]:=i+1;
c[i,i+1]=q[i]+q[i+1]+p[i+1];
}
w[n,n]:=q[n];
r[n,n]:=0;
c[n,n]:=0.0;
for m:=2 to n do
for i:=0 to n-m do
{
j:=i+m;
w[i, j]:=w[i, j-1]+p[j]+q[j];
k:=find(c, r, i, j);
c[i, j]:=w[i, j]+c[i, k-1]+c[k, j];
r[i,j]:=k;
}
write(c[0,n],w[0,n],r[0,n];
}

algorithm find(c, r, i, j)
{
min := ∞;
for m := r[i, j-1] to r[i+1, j] do
if ((c[i, m-1]+c[m, j]) < min) then
{
min:=c[i, m-1]+c[m, j];
l:=m;
}
return l;
}

Time complexity O(n log(n))

M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 8

2) MULTISTAGE GRAPH: A multi stage Graph G=(V,E) is a directed graph in which the
vertices are partitioned into k>=2 disjoint sets, Vi where 1<=i<=k. If <u,v> is an edge in E,
then uЄvi, vЄvi+1 where 1<=i<=k. The sets vi and vk are such that |vi| = |vk| = 1. Let s and T
be 2 vertices in vi and vk respectively then the vertex s is called the source and T is called the
Sink” or “Destination”. Let c(i,j) be the cost of the edge <i,j>. The cost of a path from S to T
is the sum of the costs of edges on the path. The multistage graph problem is to find
minimum cost path from S to T. Each set Vi defines a stage in the graph. Because of the
constraints on E, every path from s to t starts in stage 1, goes to stage2, then stage 3, then to
stage 4 and so on. And eventually terminates in stage k. figure shows a five stage graph. A
minimum cost s to t path is indicated by broken edges.

Consider a resource allocation problem in which n units of resources are to be allocated to r

projects. If j 0<=j<=n, units of the resource are allocated to project I, then the resulting net
profit is N(i,j). The problem is to allocate the resource to the r projects is such a way as to
maximize total net profit. This problem can be formulated as r+1 stage graph problem.

A dynamic programming formulation for a k-stage graph problem is obtained by first

noticing that every S to T path is the result of k-2 decisions. The ith decision involves in
determining which vertex vi+1 where 1<=i<=k-2 is to be on the path. Let p(i,j) be a minimum
cost path from vertex ‘j’ in vi to vertex ‘T’. Let cost(i,j) be the cost of this path. This
multistage graph problem can be solved using 2 approaches.
1) Forward approach 2) Backward approach

Forward Approach:
cost(i,j) = min { c(j,l) + cost(i+1,l )}
lЄVi+1
<j,l>ЄE
STAGES V1 V2 V3 V4 V5

Five-Stage Graph
First compute cos t[k  2, j]j  vk 2 and then compute cos t[k  3, j]j  vk 3 and so
on, and finally compute cost[1,S]

There are 5 stages in the graph V1 V2 V3 V4 V5

Stage 4 contains 3 vertices (9,10,11) cost of each vertex at stage 4 to the destination
cost(4,9) = c(9,12) = 4 stage 4 cost from vertex 9 to vertex 12
cost(4,10) = c(10,12) = 2 stage 4 cost from vertex 10 to vertex 12
cost(4,11) = c(11,12) = 5 stage 4 cost from vertex 11 to vertex 12

M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 9

 Stage 1: cos t[k  2, j]j  vk 2
cos t[3, j] j  v3 6, 7,8
cost(3,6) means that 3 refers to stage. At stage 3 cost for vertex 6 to destination
cost(3,6) =min c(6,9) + cost(4,9) = 6 + 4 =10 7
c(6,10) + cost(4,10) = 5 + 2 = 7
cost(3,7) =min c(7,9) + cost(4,9) = 4 + 4 = 8 5
c(7,10) + cost(4,10) = 3 + 2 = 5
cost(3,8) = min c(8,10) + cost(4,10) = 5 + 2 =7 7
c(8,11) + cost(4,11) = 6 + 5 = 11
cost(2,2) =min 4 + cost(3,6)
2 + cost(3,7) 7
1 + cost(3,8)

cost(2,3) = 9
cost (2,4)=18
cost(2,5)=15
cost(1,1) = min 9+cost(2,2) 16
7+cost(2,3)
3+cost(2,4)
2+cost(2,5)

Note that in the calculation of cost(2,2), we have reused the values of cost (3,6), cost
(3,7) and cost(3,8) and so avoided their recomputation. A minimum cost s to t path
has a cost of 16. This path can be determined easily if we record the decision made at
each stage (vertex).

Backward approach:

M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 10

 3) TRAVELLING SALES PERSON

The tour of graph G is a directed simple cycle that includes every vertex in V. The
cost of the tour is the sum of cost of the edges on the tour. The travelling sales-
person problem is to find a tour of minimum cost.

Applications: Suppose we have to route a postal van to pick up mail from mailbox
located at ‘n’ different sites. An (n+1) vertex graph can be used to represent the
situation. One vertex represents the post office from which the postal van starts and
to which it must return. Edge <i,j> is assigned a cost equal to the distance from site
‘I’ to site ‘j’. Route taken by the postal van is a tour and we are interested in finding
tour of minimum length.

Every tour consist of an edge <1, k> for some k Є V-{1} and a path from vertex k to
vertex 1, which goes through each vertex in V-{1,k} exactly once. It is easy to see
that if the tour is optimal, then the path from k to 1 must be a shortest k to 1 path
going through all vertices in V-{1, k}. Hence, the principle of optimality holds.

Let g(i,S) be the length of a shortest path starting at vertex ‘i’ going through all
vertices in ‘S’ & terminating at vertex 1. The function g(1,V-{1}) is the length of an
optimal salesperson tour. From the principle of optimality
g (1, V  {1}) 
m in { C1 k  g ( k , V  {1, k })}
2 k n

Generalizing the above equation we obtain ( for iS )

g (i , S )  m in { C i j  g ( j , S  { j})}
j S

Find g(1,{2,3,4}) V{1,2,3,4}

Solution:
Stage 1) compute g(i,S) where |S| = ø, with no intermediate nodes.
i Є {v-{1} } i  1, 1S and i S
i={2,3,4}
g(2,ø)=c21=5
g(3,ø)=c31=6
g(4,ø)=c41=8

Stage 2) Compute g(i,S) where |S|=1, with one intermediate node

iЄ{v-{1}} i  1, 1S and i S
i={2,3,4} s={2/3/4} & <i,s> should be an edge (j=s)
g (i , S )  m in { C i j  g ( j , S  { j})}
j S

g(2,{3}) = c23+g(3,s-{3}) = 9 + g(3,ø) = 9 + c31 = 9+6 = 15

g(2,{4}) = c24+g(4,s-{4}) = 10 + g(4,ø) = 10 + c41 = 10+8=18
g(3,{2}) = c32+g(2,s-{2}) = 13 + g(2,ø) = 13 + c21 = 13+5=18
g(3,{4}) = c34+g(4,s-{4}) = 12 + g(4,ø) = 12 + c41 = 12+8=20
g(4,{2}) = c42+g(2,s-{2}) = 8 + g(2,ø) = 10 + c21 = 8 + 5=13
g(4,{3}) = c43+g(3,s-{3}) = 9 + g(3,ø) = 9 + c31 = 9 + 6=15

M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 11

 Step 3) Compute g(i,s) where |S|=2, with two intermediate nodes
iЄ(v-{2}} i  1, 1S and i S
i={2,3,4}, S={{2,3}/{3,4}/{2,4}}
g (i , S )  m in { C i j  g ( j , S  { j})}
j S

j={3,4}
g(2,{3,4}) = min c23 + g(3,s-{3}) when j=3
c24 + g(4,s-{4}) when j=4

min c23 + g(3,{4}) = min 9+20 = min{29,25} =25

c24 + g(4,{3}) 10+15

g(3,{2,4}) = min c32 + g(2,s-{2}) j={2,4}

c34 + g(4,s-{4})

min 13 + g(2,{4}) = min 13+18 = 25

12 + g(4,{2}) 12+13

g(4,{2,3}) = min c42 + g(2,s-{2}) j={2,3}

c43 + g(3,s-{3})

min 8 + g(2,{3}) = min 8+15 = min{23,27} =23

9 + g(3,{2}) 9+18

Stage 4) Compute g(i,S) where |S|=3, with three intermediate nodes

i Є{v-{1}} and i={1} ,
S={2,3,4}
j={2/3/4}
g (i , S ) 
m in { C i j  g ( j , S  { j})}
j S

g(1,{2,3,4}) = min C12 + g(2,S-{2}) when j=2

C13 + g(3,S-{3}) when j=3
C14 + g(4,S-{4}) when j=4

min 10 + g(2,{3,4}) = min 10 + 25 = min{35,40,43}=35

15 + g(3,{2,4}) 15 + 25
20 + g(4,{2,3}) 20 + 23

Optimal cost of tour is 35

g(1,{2,3,4}) = {C12+g(2,{3,4}) } thus the tour starts form 1 and goes to 2

g(2,{3,4}) = {C24+g(4,{3})} then from 2 to 4
g(4,{3}) = {C43+g(3,{Φ}) } then from 4 to 3
g(3,{Φ} = C31 and from 3 to 1
C12 C24 C43 C31
The sequence of tour is 1 2 4 3 1

M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 12

 Example 2) Travelling Salesperson

Compute g(1,{2,3,4,5}) V={1,2,3,4,5}

Stage 1) Compute g(i,s) where |s|=ø , i Є {v- { s }}

i={2,3,4,5} with no intermediate nodes

g (2,ø)=C21 =1
g (3,ø)=C31 =6
g (4,ø)=C41 =1
g (5,ø)=C51 =3

Stage 2) Compute g(i,s) where |s|=1 , i Є {v- { s }}

With one intermediate node
i={2,3,4,5} s = {2,3,4,5} & <i,s> should be an edge
g (i , S )  m in { C i j  g ( j , S  { j})}
j S

g(2,{3}) = C23 + g(3,s-{3}) = 3 + g(3,ø) = 3 + 6 = 9

g(2,{4}) = C24 + g(4,s-{4}) = 2 + g(4,ø) = 2 + 1 = 3
g(2,{5}) = C25 + g(5,s-{5}) = 5 + g(5,ø) = 5 + 3 = 8

g(3,{1}) = C31 + g(1,s-{1}) = 6 + g(1,ø) = 6 + 0 = 6

g(3,{2}) = C32 + g(2,s-{2}) = 2 + g(2,ø) = 2 + 1 = 3
g(3,{4}) = C34 + g(4,s-{4}) = 2 + g(4,ø) = 2 + 1 = 3
g(3,{5}) = C35 + g(5,s-{5}) = 1 + g(5,ø) = 1 + 3 = 4

g(4,{1}) = C41 + g(1,s-{1}) = 1 + g(1,ø) = 1 + 0 = 1

g(4,{2}) = C42 + g(2,s-{2}) = 1 + g(2,ø) = 1 + 1 = 2
g(4,{3}) = C43 + g(3,s-{3}) = 2 + g(3,ø) = 2 + 6 = 8
g(4,{5}) = C45 + g(5,s-{5}) = 2 + g(5,ø) = 2 + 3 = 5

g(5,{1}) = C51 + g(1,s-{1}) = 3 + g(1,ø) = 3 + 0 = 3

g(5,{2}) = C52 + g(2,s-{2}) = 1 + g(2,ø) = 1 + 1 = 2
g(5,{3}) = C53 + g(3,s-{3}) = 2 + g(3,ø) = 2 + 6 = 8
g(5,{4}) = C54 + g(4,s-{4}) = 1 + g(4,ø) = 1 + 1 = 2

M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 13

 Stage 3) Compute g(i,s) where |s|=2 ,i.e i Є {v- { s }}
With two intermediate nodes
i={2,3,4,5} s = {2,3,4,5}
g (i , S ) 
m in { C i j  g ( j , S  { j})}
j S

g(2,{3,4})= min C23 + g(3,S-{3})

C24 + g(4,S-{4})

min 3 + g(3,{4}) = min 3 + 3 = min 6 = 6

2 + g(4,{3}) 2+8 10

g(2,{4,5})= min C24 + g(4,S-{4})

C25 + g(5,S-{5})

min 2 + g(4,{5}) = min 2 + 5 = min 7 = 7

5 + g(5,{4}) 5+2 7

g(3,{2,4})= min C32 + g(2,S-{2})

C34 + g(4,S-{4})

min 2 + g(2,{4}) = min 2 + 3 = min 5 = 4

2 + g(4,{2}) 2+2 4

g(3,{2,5})= min C32 + g(2,S-{2})

C35 + g(5,S-{5})

min 2 + g(2,{5}) = min 2 + 8 = min 10 = 3

1 + g(5,{2}) 1+2 3

g(4,{2,3})= min C42 + g(2,S-{2})

C43 + g(3,S-{3})

min 1 + g(2,{3}) = min 1 + 9 = min 10 = 5

2 + g(3,{2}) 2+3 5

g(4,{2,5})= min C42 + g(4,S-{2})

C45 + g(4,S-{5})

min 1 + g(4,{5}) = min 1 + 5 = min 6 = 4

2 + g(5,{2}) 2+2 4

g(5,{2,3})= min C52 + g(2,S-{2})

C53 + g(3,S-{3})

min 1 + g(2,{3}) = min 1 + 9 = min 10 = 5

2 + g(3,{2}) 2+3 5

g(5,{2,4})= min C52 + g(2,S-{2})

C54 + g(4,S-{4})

min 1 + g(2,{4}) = min 1 + 3 = min 4 = 3

1 + g(4,{2}) 1+2 3

M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 14

 g(2,{3,5})= min C23 + g(3,S-{3})
C25 + g(5,S-{5})

min 3 + g(3,{5}) = min 3 + 4 = min 7 = 7

5 + g(5,{3}) 5+8 13

g(3,{4,5})= min C34 + g(4,S-{4})

C35 + g(5,S-{5})

min 2 + g(4,{5}) = min 2 +5 = min 7 = 3

1 + g(5,{4}) 1+2 3

`
g(4,{3,5})= min C43 + g(3,S-{3})
C45 + g(5,S-{5})

min 2 + g(3,{5}) = min 2 +4 = min 6 = 6

2 + g(5,{3}) 2+8 10

g(5,{3,4})= min C53 + g(3,S-{3})

C54 + g(4,S-{4})

min 2 + g(3,{4}) = min 2 +3 = min 5 = 5

1 + g(4,{3}) 1+8 9

Stage 4) Compute g(i,s) where |s|=3 ,i.e i Є {v- { s }}

With three intermediate nodes
i={2,3,4,5} s = {2,3,4,5}
g (i , S )  m in { C i j  g ( j , S  { j})}
j S

g(2,{3,4,5})= min C23 + g(3,S-{3})

C24 + g(4,S-{4})
C25 + g(5,S-{5})

= min 3 + g(3,{4,5}) = min 3 + 3 = min 6 = 6

2 + g(4,{3,5}) 2+6 8
5 + g(5,{3,4}) 5+5 10

g(3,{2,4,5})= min C32 + g(2,S-{2})

C34 + g(4,S-{4})
C35 + g(5,S-{5})

= min 2 + g(2,{4,5}) = min 2 + 7 = min 9 = 4

2 + g(4,{2,5}) 2+4 6
1 + g(5,{2,4}) 1+3 4

g(4,{2,3,5})= min C42 + g(2,S-{2})

C43 + g(3,S-{3})
C45 + g(5,S-{5})

= min 1 + g(2,{3,5}) = min 1 + 7 = min 8 = 5

2 + g(3,{2,5}) 2+3 5
2 + g(5,{2,3}) 2+5 7

M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 15

 g(5,{2,3,4})= min C52 + g(2,S-{2})
C53 + g(3,S-{3})
C54 + g(4,S-{4})

= min 1 + g(2,{3,4}) = min 1 + 6 = min 7 = 6

2 + g(3,{2,4}) 2+4 6
1 + g(4,{2,3}) 1+5 6

Stage 5) Compute g(i,s) where |s|=4 ,i.e i Є {v- { 1 }}

With 4 intermediate nodes
i={1} s = {2,3,4,5}
g (i , S )  m in { C i j  g ( j , S  { j})}
j S

g(1,{2,3,4,5})= min C12 + g(2,S-{2})

C13 + g(3,S-{3})
C14 + g(4,S-{4})
C15 + g(5,S-{5})

= min 2 + g(2,{3,4,5}) = min 2 + 6 = min 8 = 5

1 + g(3,{2,4,5}) 1+4 5
2 + g(4,{2,3,5}) 2+5 7
1 + g(5,{2,3,4}) 1+6 7
Optimal Cost tour is 5
g(1,{2,3,4,5}) = C13 + g(3,{2,4,5}) thus tour stars from 1 and goes to 3
g(3,{2,4,5} = C35 + g(5,{2,4}) then from 3 to 5
g(5,{2,4}) = C52 + g(2,{4}) then from 5 to 2
g(2,{4}) = C24 + g(4,{ø}) then from 2 to 4
g (4,ø) = C41 then from 4 to 1

Optimal tour is 1-3-5-4-2-1

M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 16

4) RELIABILITY DESIGN:
In this section we look at an example of how to use dynamic programming to
solve a problem with a multiplicative optimization function. The problem is to
design a system that is composed of several devices connected in series. Let r i be
the reliability of device Di. Then the reliability of the entire system is ∏ ri. Even if
the individual devices are very reliable, the reliability of the system may not be
very good.

For example if n=10 and ri=0.99, 1<=i<=10 then ∏ ri.= 0.904. Hence it is
desirable to duplicate devices. Multiple copies of same device type connected in
parallel through the use of switching circuits. The switching circuits determine
which devices in any given group are functioning properly. They then make use
of one such device at each stage.

If stage i contains mi copies of device di, then the probability that all mi have a
malfunction is (1- ri )mi . Hence the reliability of stage i becomes 1- (1- ri)mi .
Thus if ri =0.80 and mi = 2, the stage reliability becomes 0.96.

Reliability = 1- (1 - 0.80)2
= 1- (0.2)2
= 1 – 0.04
= 0.96 The reliability of this stage increased with duplication.

n Devices Di, 1<=i<=n connected in series

Multiple devices connected in parallel in each stage

Our problem is to use device duplication to maximize reliability. The

maximization is to be carried out under a cost constraint. Let Ci be the cost of
system being designed we wish to solve the following maximization problem.

Maximize  i
(mi ) (reliability function)
Subject to ∑
1 i  m
ci mi  C (total allowable cos t) mi  ci 1  i  n

We may assume that each ci>0

Each mi must be in the range 1<= mi <= Ui can be calculated as follows

Upper bound is the maximum number of devices that can be kept in one stage.
n

Ui  c  ci  ∑ c j / c i
j1

Clearly F0 (x)  1  x 0  x  c

It may be solved using an approach similar to that used for knapsack problem.

M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 17

 Example : we are to design a 3 stage system with device types d1, D2, d3. The
costs are $30, $15 and $20 respectively. The cost of the system is to be no more
than $105.

The reliability of each device type is 0.9, 0.8 and 0.5 respectively.
We assume that if stage i has mi devices of type i in parallel then
 (m ) 1 (1 r )m i

i i i

In terms of the notation used earlier,

c1=30, c2=15, c3=20, c=105
r1=0.9, r2=0.8, r3=0.5
n

Ui  c  ci  ∑ c j / c i upper bound
j1

Upper bound at Stage 1

U1  105  30  (30 15  20) / 30
U1  135  65) / 30
U1  2.333
U1  2

Upper bound at Stage 2

U2  105 15  (30 15  20) /15
U2  120  65) /15
U2  3.666
U2  3

Upper bound at Stage 3

U3  105  20  (30 15  20) / 20
U3  125  65) / 20
U3  3
U3  3

U1  2 U2  3 U3  3

Reliability function for ith stage

 (m ) 1 (1 r )mi is a reliability function. Each pair in this is represented by (r,x)
i i i
where r is reliability and x is cost.

Using Sij to represent all tuples that are obtainable from Si1 by choosing mi = j.

Beginning with S {(1, 0)}

0
initial assumption
{reliability, cost}
As there are no devices no chance for failure. So reliability is 1.
As there are no devices cost of devices is 0.

M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 18

Since 1  mi Ui
1  m1  2 m1=1 or 2, it means j=1 or 2.
i
So, by using S calculate S11 here
j i=1, j=1 i.e. m1=1
The reliability function for ith stage is
 (m ) 1 (1 r )m i

i i i
 (m ) 1 (1 r ) 1
reliability function for 1st stage
1 1 1
= 1 – ( 1 -0.9)
= 1-0.1
= 0.9
(Reliability, cost)= (0.9, 30)
S0 {(1, 0)} no devices
In each tuple (r,x) reliability is multiplied with previous reliability and cost is added to
previous cost.
S11 {(10.9, 0  30)}
S11 {( 0.9,30)} stage=1 number of devices=1
Here reliability 0.9 is multiplied with 1 and cost c1=30 is added to 0.
1
Now S2 is calculated as follows. i.e. Stage=1, number of devices =2
i=1 j=2 m1=2
 (m ) 1 (1 r )m i

i i i
 (m ) 1 (1 r )2
1 1 1
= 1 – ( 1 -0.9)2
= 1- 0.01
= 0.99
(Reliability,cost)= (0.99,60)
S21 {(10.99, 0  60)}
S21 {( 0.99, 60)}

S1 can be obtained by merging the sets S1  S11 S12

S1 {(0.9,30),(0.99, 60)}
1
We cannot calculate S3 since upper bound is 2 i.e. U1=2.

Similarly S12 , S 22 , S 23 can be calculated from S1.

Stage 2 one device
2
S1 here i=2, j=1 i.e. m2 = 1
 (m ) 1 (1 r )m 2

2 2 2

2 (m2 ) 1 (1 0.8 )1

= 1 – 0.2
= 0.8

M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 19

 (Reliability,cost)=(0.8,15)
S12 {(0.90.8,30 15),(0.990.8, 60 15)}.
S12 {(0.72, 45),(0.792, 75)}

Stage 2 two devices

2
S2 here i=2, j=2 i.e. m2 = 2
 (m ) 1 (1 r )m 2

2 2 2

2 (m2 ) 1 (1 0.8 )2

= 1 – 0.2*0.2
= 0.96
(reliability,cost)=(0.96,30)
Since j=2, cost of 2 devices 2C2 = 2*15 = 30 is added to S1 pairs.
S22 {(0.90.96,30  30),(0.990.96, 60  30)}.
S22 {(0.864, 60),(0.9504,90)}

Stage 2 three devices

2
S3 here i=2, j=3 i.e. m2 = 3
 (m ) 1 (1 r )m 2

2 2 2

2 (m2 ) 1 (1 0.8 )3

= 1 – 0.23
= 0.992
( reliability,cost)= (0.992,45)
Since j=3, cost of 3 devices 3C2 = 3*15 = 45 is added to S1 pairs.
S32 {(0.90.992,30  45),(0.990.992, 60  45)}.
S32 {(0.8928, 75),(0.98208,105)}

S2 can be obtained by merging the sets S 2  S2  S 2  S2

1 2 3

S2 {(0.72, 45),(0.792,75),(0.864,60),(0.9504,90),(0.8928,75),(0.98208,105)}
Now by applying purge rule : by observing the successive tuples (0.792,75),(0.864,60) the
second one dominates first one as the second one has more reliability with less cost. So we
purge i.e. eliminate the tuple (0.792,75).
S2 {(0.72, 45),(0.864,60),(0.9504,90),(0.8928,75),(0.98208,105)}
Now observe that the cost must be in increasing order. 45<60<90<75<105 false
i.e. 90<75 fails so pair (0.9504,90) is not in appropriate order so remove (0.9504,90).

S2 {(0.72, 45),(0.864,60), (0.8928,75),(0.98208,105)}

M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 20

Similarly S13, S23, S33 can be calculated from S2.

Stage 3 one device

3
S1 here i=3, j=1 i.e. m3 = 1
 (m ) 1 (1 r )m 3
3 3 3
 (m ) 1 (1 0.5 )1
3 3
= 1 – 0.5
= 0.5
Cost of the device at stage 3 = 20. So (0.5, 20) is added to S2
S13 {(0.720.5, 45  20),(0.8640.5, 60  20),(0.89280.5,75  20),(0.982080.5,105  20)}
3
Last tuple is removed from S1 since cost exceeds budget 105.
S13 {(0.720.5, 45  20),(0.8640.5, 60  20),(0.89280.5,75  20)}
S13 {(0.36,65),(0.432,80),(0.4464,95)}

Stage 3 two devices

3
S2 here i=3, j=2 i.e. m3 = 2
 (m ) 1 (1 r )m 3
3 3 3
 (m ) 1 (1 0.5 )2
3 3
= 1 – 0.25*0.25
= 0.75 reliability
Since j=2, cost of 2 devices 2C2 = 2*20 = 40 so the pair (0.75,40) is added to S2 pairs.
S23 {(0.720.75, 45  40),(0.8640.75, 60  40)}.

S23 {(0.54,85),(0.648,100)}

Stage 3 three devices

3
S3 here i=3, j=3 i.e. m3 = 3
 (m ) 1 (1 r ) m3
3 3 3
 (m ) 1 (1 0.5 )3
3 3
= 1 – 0.53
= 0.875 reliability
Since j=3, cost of 3 devices 3C2 = 3*20 = 60 the pair (0.875,60) is added to S2 pairs.

S33 {(0.720.875, 45  60)}.

S33 {(0.63,105)} In all other pairs the cost exceeds 105 so not included.
S 3 can be obtained by merging the sets S 3  S3  S 3  S3
1 2 3

S3 {(0.36,65),(0.432,80),(0.4464,95),(0.54,85),(0.648,100),(0.63,105)}

M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 21

Now by applying purge and dominance rule : by observing the successive tuples
(0.4464,95),(0.54,85) the second one dominates first one as the second one has more
reliability with less cost. So we purge i.e. eliminate the tuple (0.4464,95) and by observing
the successive tuples (0.648,100),(0.63,105) the first one dominates second one. As the first
one has more reliability with less cost we purge i.e. eliminate the tuple (0.63,105)
S3 {(0.36,65),(0.432,80), (0.54,85),(0.648,100)}
The best design has reliability of 0.648 and a cost of 100.

3
The pair (0.648,100) present in S2 i.e. i=3 and j=2 two devices at stage 3
so m3=2 cost = 40
2
The pair (0.648,100) obtained from (0.864, 60) which is present in S2 i.e. i=2, j=2 so m2=2
i.e two devices at stage two. So cost will be 15*2=30 at stage two.

1
The pair (0864.60) obtained from (0.9,30) which is in S1 i.e. i=1, j=1 so m1=1
One device at stage 1 i.e cost =30
 m1 1, m2 2, m3 2

An alternate method for finding the solution for the above problem:
The pair of tuple with the maximum reliability is in S3 represents the value of the solution.
Therefore the reliability of the system is 0.648 that has a cost of 100. To get the values of M1,
M2 and M3 we will trace back.
The pair (0.648,100)  S i  3, j  2, m  2
3
2 3
As there are 2 copies of the device at stage 3 subtracting the cost of 2 copies of the device D3
from the total cost 100 i.e
= 100 - 2*20
= 100-40
= 60.
2 2 2
Search (x,60) belongs to S1 or S2 or S3
(0.864, 60)  S 2 i  2, j  2, m  2
2 2
2
(0.864,60) belongs to S 2 so m2=2 as there are 2 devices at stage 2 the cost of 2 copies of
device type D2 is subtracted from total cost 60
=60-2*15
=60-30
=30

1 1
Now Search (x,30) belongs to S1 or S2
(0.9,30)  S1 i  1, j  1, m  1
1 1
1
(0.9,30) belongs to S1 i.e m1=1

 m1 1, m2 2, m3 2

M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 22

5) All pairs shortest path problem

Let G=(V,E) be a directed graph consisting of n vertices and each edge is

associated with a weight. The problem of finding the shortest path between all
pairs of vertices in a graph is called all pairs shortest path problem. This problem
can be solved by using Dynamic programming Technique.

The all pair shortest path problem is to determine a matrix A such that A(i,j) is the
length of a shortest path from vertex i to j. Assume that this path contains no
cycles. If k is an intermediate vertex on this path, then the sub paths form i to k
and from k to j are the shortest paths from I to k and from k to j respectively.

Otherwise the path from i to j is not shortest path. If k is intermediate vertex with
highest index then the path i to k is the shortest path going through no vertex with
index greater than k-1. similarly the path k to j is shortest path going through no
vertex with index greater than k-1.

The shortes path can be computed using following recursive method.

Ak (i, j) W(i, j) if k  0
Ak (i, j) min{Ak1(i, j), Ak1(i, k)  Ak1(k, j)} if k 1

Example : Compute all pairs shortest path for the following graph

1 2
4

11
2
3
3

Graph G

[0 4 11]
cost Adjacency Matrix A0(i, j)  W(i, j)  [6 0 2]
[3  0]

M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 23

Step 1
For k=1 i.e. going from i to j through intermediate vertex 1
When i=1 j=1/2/3
A1(1,1) min{A0(1,1), A0(1,1)  A0(1,1)}  min{0,0  0}  0
A1(1, 2) min{A0(1, 2), A0(1,1)  A0(1, 2)}  min{4,0  4}  4
A1(1,3) min{A0(1,3), A0(1,1)  A0(1,3)}  min{11,0 11} 11
When i=2 j=1/2/3
A (2,1) min{A0(2,1), A0(2,1)  A0(1,1)}  min{6,6  0}  6
1

A1(2, 2) min{A0(2, 2), A0(2,1)  A0(1, 2)}  min{0,6  4}  0

A1(2,3) min{A0(2,3), A0(2,1)  A0(1,3)}  min{2,611}  2
When i=3 j=1/2/3
A (3,1) min{A0(3,1), A0(3,1)  A0(1,1)}  min{3,3 0}  3
1

A1(3,2) min{A0(3, 2), A0(3,1)  A0(1,2)}  min{,3 4}  7

A1(3,3) min{A0(3,3), A0(3,1)  A0(1,3)}  min{0,311}  0

[0 4 11]
cost Adjacency Matrix A1(i, j)  [6 0 2 ]
[3 7 0 ]

Step 2
For k=2 i.e. going from i to j through intermediate vertex 2
When i=1 k=2 j=1/2/3
Ak (i, j) min{Ak1(i, j), Ak1(i, k)  Ak1(k, j)}
A2(1,1) min{A1(1,1), A1(1,2)  A1(2,1)}  min{0, 4  6}  0
A2(1, 2) min{A1(1, 2), A1(1, 2)  A1(2, 2)}  min{4, 4  0}  4
A2(1,3) min{A1(1,3), A1(1, 2)  A0(2,3)}  min{11, 4  2}  6
When i=2 j=1/2/3
A (2,1) min{A1(2,1), A1(2, 2)  A1(2,1)}  min{6,0 6}  6
2

A2(2, 2) min{A1(2, 2), A1(2, 2)  A1(2, 2)}  min{0,0  0}  0

A2(2,3) min{A1(2,3), A1(2, 2)  A1(2,3)}  min{2,0  2}  2
When i=3 j=1/2/3
A (3,1) min{A1(3,1), A1(3, 2)  A1(2,1)}  min{3,7  6}  3
2

A2(3, 2) min{A1(3,2), A1(3, 2)  A1(2, 2)}  min{7,7  0}  7

A2(3,3) min{A1(3,3), A1(3,2)  A1(2,3)}  min{0,0  2}  0

M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 24

 [0 4 6]
cost Adjacency Matrix A (i, j)  [6 0 2]
2

[3 7 0]

Step 3
For k=3 i.e. going from i to j through intermediate vertex 3
When i=1 k=3 j=1/2/3
Ak (i, j) min{Ak1(i, j), Ak1(i, k)  Ak1(k, j)}
A3(1,1) min{A2(1,1), A2(1,3)  A2(3,1)}  min{0,6  3}  0
A3(1, 2) min{A2(1, 2), A2(1,3)  A2(3, 2)}  min{4,6  7}  4
A3(1,3) min{A2(1,3), A2(1,3)  A2(3,3)}  min{6,6  0}  6
When i=2 j=1/2/3
A3(2,1) min{A2(2,1), A2(2,3)  A2(3,1)}  min{6, 2 3}  5
A3(2, 2) min{A2(2, 2), A2(2,3)  A2(3, 2)}  min{0, 2  7}  0
A3(2,3) min{A2(2,3), A2(2,3)  A2(3,3)}  min{2,2  0}  2
When i=3 j=1/2/3
A3(3,1) min{A2(3,1), A2(3,3)  A2(3,1)}  min{3,0  3}  3
A3(3, 2) min{A2(3, 2), A2(3,3)  A3(3, 2)}  min{7,0  7}  7
A3(3,3) min{A2(3,3), A2(3,3)  A3(3,3)}  min{0,0  0}  0

[0 4 6]
cost Adjacency Matrix A (i, j)  [5 0 2]
3

[3 7 0]
This matrix gives the all pairs shortest path solution

Algorithm all_pairs_shortest_path(W,A,n)
// W is weighted array matrix, n is the number of vertices,
// A is the cost of shortest path from vertex i to j.
{
for i:= 1 to n do
for j:= 1 to n do
A[i,j]:= W[i,j]

for k:=1 to n do
for i:= 1 to n do
for j:= 1 to n do
A[i,j]:=min(A[i,j],A[i,k]+A[k,j]
}

The Time Complexity for this method is O(n3)

M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 25

Important Questions
1) Write a pseudo code of the dynamic programming algorithm for solving optimal
binary search tree.
2) Using algorithm of OBST, compute w(i,j), r(i,j) and c(i,j), 0<=i<=j<=4 for
identifier set (a1, a2, a3, a4) = ( cout, float, int, while) with p1=1/20, p2=1/5,
p3=1/10, p4=1/20, q0=1/5, q1=1/10, q2=1/5, q3=1/20, q4=1/20 using r(i,j)
construct the optimal binary search tree.
3) Write an algorithm of all pair shortest path problem
4) Discuss the dynamic programming solutions for the traveling sales person
problem
5) Discuss the dynamic programming solutions for the problems of reliability
design.
6) Design a system with 3 components D1, D2, D3 each costs Rs.30, Rs.15 Rs.30
respectively. The cost of the system is to be no more than Rs.105. The reliability
of each device type is 0.9, 0.8 and 0.5 respectively.

M Yogi Reddy III CSE-- DAA UNIT-III Dynamic Programming Page 26