Design and Analysis of Algorithms

Abstract Algorithms 3 - Dynamic

Programming
Introduction
In D&C strategy, the basic method is to divide the
original problem into several subproblems, solve
them, and then combine the results, so as to get the
solution to the original problem. Sometimes the
(sub)sub-problems are the same and it is a waste of
time to recompute them.
Save the results of sub-problems, use again later on to
speed up the computation. A kind of Time-Space
Tradeoff. One strategy which uses this approach to an
advantage is Dynamic Programming.
The idea of dynamic programming: avoid calculating
the same thing twice, usually by keeping a table of
known results that fills up as sub-instances of the
problem are solved.
It is a Bottom-Up technique.
Example: Coinage
A country has coinage 1, 4 and 6 units. Make a
change for 8 units.
Greedy strategy: one 6 unit coin and two 1 unit coins,
for a total of three coins.
However, two 4 unit coins would do the job.
Greedy strategy does not provide optimum answer.

Using Dynamic Programming: The heart of the method

is to set up a table, containing useful intermediate
results, that are then combined to solve the original problem.

A row for every coin value, A column for each

amount from 0 to N units. c[i,j] will be the min
number of coins required to pay an amount of j units,
, using coins only of value 1 to i,
.
Solution Dvelopment
Solution to a particular instance: is c[n, N] if all we
want to know is how many coins are needed.
To fill in the table: c[i,0] = 0 i. The table can be
filled up either row-wise or column-wise. To pay an
amount j, using coins of value 1 to i: two choices:

not to use any coins of value i, even though permitted,

then c[i,j] = c[i-1, j].

Or, use at least one coin of value i. Then, amount

remains to be paid. Requires c[i, ] coins,
so c[i,j] = 1 + c[i, ]. Minimize the number of
coins used, choose whichever alternative is better.
Thus: c[i, j] = min(c[i-1, j], 1+c[i, j- ]).
If i = 1, one of the elements to be compared is not in
table. Similarly when . It is convenient to think
of such elements as having the value . If i = 1 and
, then both elements to be compared fall outside
the table. In this case we set c[i,j] to to indicate
that it is impossible to pay an amount j using coins of
type i.
j
Amount 0 1 2 3 4 5 6 7 8
d[1] = 1 0 1 2 3 4 5 6 7 8
i d[2] = 4 0 1 2 3 1 2 3 4 2
d[3] = 6 0 1 2 3 1 2 1 2 2
For example, c[3,8] is obtained in this case as smaller
of c[2,8] = 2 and 1 + c[3, 8 - ] = 1 + c[3,2] = 3.
 Algorithm 1: Algorithm coin(N)
[Return: minimum coins for a
change for N units. Array
d[1..n] specifies the coinage;]
integer array d[1..n] = [1, 4, 6];
integer array array c[1..n, 0..N];
for i 1 to n do c[i,0] 0;
for i 1 to n do
for j 1 to n do
if i = 1 and j d[i] then c[i,j] ;
else if i = 1 and j d[i] then c[i,j] 1+
c[1, j-d[1]];
else if j d[i] then c[i,j] c[i-1, j];
else c[i,j] min(c[i-1, j], 1 + c[i, j -d[i]);
end
end
return c(n, N).
 Principle of Optimality
In dynamic programming an optimal sequence of
decisions is arrived at by using the Principle of
Optimality. This principle states that:
An optimal sequence of decisions has a property that what-
ever be the initial state and the decision, the remaining de-
cisions must constitute an optimal decision sequence with
regard to the state resulting from the first decision.
An essential difference between Greedy methods and
Dynamic programming: in Greedy methods only one
decision sequence is generated, but in Dynamic
Programming strategy, several of them may be
generated. Dynamic Programming ensures that
sub-optimal decisions are not explored further.
Dynamic Programming process

x x optimal
0 11
1

2
t
x x
x0 0 12
3

x x
0 13

S 1st t

optimal

optimal
Application of Opt Principle
The principle can be applied in
The Forward direction, i.e., x , i = 0 to n, be the
problem state variables; then take a decision
about x from x ,x , ...x ; or
The Backward direction, i.e., x, i = 0 to n, be the
problem state variables; then take a decision
about x from x , x , ...x ;
Employing any of these strategies results in a
recursive approach to the problem solution. For
example, in the case of the Backward approach, the
values of x , x , ...are computed successively.
Optimal solutions to sub-problems are retained to
avoid recomputing them. Then it is possible to
convert the recursive algorithms into iterative ones.
Multistage Graphs
A directed graph G = V, E , in which the nodes are
partitioned into k 2 disjoint sets V , 1 i k.
Also, every edge (u,v) in E has u in V and v in V ,
for some i. This means that we can visualize the graph
as a number of layers or stages, defined by V and the
edges go from one stage to the next.

A typical practical example arises in project

management, where, in order to complete a project,
activities performed in several stages and at each
stage a particular action is selected from the several
alternatives available.
Multistage Graphs-2
V2
V1 V3 V4 V5
2 4
6
1 2 6 9 4
9 5
3
2
7 4 t
7 2
S 1 7 10 12
3 3

4 11
5
2 5
8 11
11
6
5
8
Dynamic programming formu-
lation
For the k-stage graph problem: Every s to t path is a
result of k-2 decisions, because there are k-1 edges in
the path and the last edge going to node t does not
require any decision.
The decision is concerned with which node in
stage V ,1 i k-2, has to be on the path.
Principle of Optimality holds.

Let path[i][j] be a minimum cost path from node j in

the stage V node-set to node t. Let c[i][j] be the cost
of this path.

Then in the forward approach: c[i][j] = min{ cost[j][l]

+ c[i+1][l] } for l in V and (j,l) in edges.
Dynamic Programming step
Since c[k-1][j] = cost[j][t] if (j,t) is in edges and
c[k-1][j] = if (j,t) is not in edges, the above
equation may be solved for c[1][s], by first computing
c[k-2][j] for all j in V , then c[k-3][j] for all j in
V , ..., and finally c[1][s].
Vi Vi + 1
V1

j
cost[j][l]
l t
S
For Example graph
c[3][6] = min{ 6 +c[4][9], 5 + c[4][10] } = 7
c[3][6] = 7 c[3][7] = 5 c[3][8] = 7
c[2][2] = 7 c[2][3] = 9 c[2][4] = 18 c[2][5] = 15
c[1][1] = 16,
which is the minimum cost. It matches with the result
obtained by Dijkstra’s algorithm.
An array d[i][j] which stores the value of l which
minimizes cost[j][l] + c[i+1][l]. Then the minimum
cost path is s = 1, v = d[1][1], v = d[2][d[1][1]], etc.
As the nodes are numbered in the order as shown, i.e.
the node number increases successively within a
stage, then first subscript in the arrays can be dispense
with . This ensures that all the nodes in a particular
stage V have numbers less than the lowest numbered
node in stage V .
Traveling Salesman
TS problem tried by exhaustive search method.
Problem is untractable because n! permutations for
the path are to be considered.

Try to apply dynamic programming approach.

Assume that the tour starts at node no. 1 and

terminates on the same node. Every possible tour can
be viewed as consisting of edge (1, k) for some k in
V-{1} and a path from node k to 1.

This path goes through each node in V-{1,k} exactly

once. It is clear that the path [k,1] should be optimal.
Thus the Principle of Optimality holds.
TS problem step V
V
V -{1} V -{1,k}
k
1 1

s(i, S) = length of shortest path starting at node i,

going through all the nodes in S, and terminating at
node 1. s(1, V-{1}) is the length of an optimal tour.
Thus we have from the Principle of Optimality,
s(1, V-{1}) = min{ cost[1][k] + s(k, V-{1,k}) } for 2
k n.
Generalizing this equation for :
s(i, S) = min{ cost[i][j] + s(j, S-{j}) } for j in S.
 S

s(i, S)
i 1

j
cost[i][j]
s(i, S)
i 1

S - {j}

This can be viewed as: (i) [S] (1)

We find that s(i, ϕ)=cost[i][1] for 1<=i<=n,where ϕ is an empty set.we can then use
the above equation to obtain s(i,S) for all S of size 1.Thus we obtain s(i,S) for all S of
size 2 and so on.
Example
Connection matrix for a 4-nodes graph:
0 10 15 20
5 0 9 10 s(2, ) = 5
6 13 0 12 s(3, ) = 6
8 8 9 0 s(4, ) = 8
for S = 1 :
s(2,{3}) = cost[2][3] + s(3, ) = 9 + 6 = 15
s(2,{4}) = cost[2][4] + s(4, ) = 10 + 8 = 18
s(3,{2}) = ... = 18
s(3,{4}) = ... = 20
s(4,{2}) = ... = 13
s(4,{3}) = ... = 15
then for S = 2 :
s(2,{3,4}) = min{ cost[2][3] + s(3,{4}), cost[2][4] +
s(4,{3}) } = 10 + 15 = 25.
 s(3,{2,4}) = ... = 25
s(4,{2,3}) = ... = 23 Continuing as formulated above,
ultimately we arrive at :
s(1, {2,3,4}) = min{cost[1][2]+s(2,{3,4}), ... }
= min{35, 40, 43}
= 35.
The path can be found by noting the node which
resulted in minimum cost at each stage.

A tour of this length may be constructed if we retain with each s(i, S) the
value of j that minimizes the right hand side. Let s(i, S) be this value.
s(1, {2,3,4}) = 2.
Thus the tour starts from 1 and goes to 2. The remaining tour may be
obtained from s(2, {3,4}). s(2, {3,4}) = 4. Thus the next edge is <2,4>. The
remaining tour is for s(4,{3}). s(4, {3}) = 3.
The optimal tour is <1, 2, 4, 3, 1>
Complexity of the algorithm
The number N of s(i, S) to be computed before the
above equation for s(1, V-{1}) can be used, is:
N= for k = 0 to n-2,
because for each value of S there are (n-1) choices
for i and the number of distinct sets of size k, not
considering 1 and i in S, is comb(n-2,k).

From the above equation, N = (n-1)2 , thus the

algorithm is O(n 2 ), as the computation of s(i, S) for
S = k, requires (k-1) comparisons and this has to be
repeated for all the n nodes. This is better than n! with
ETS algorithm. The main objection is that it requires
a large amount of space to store the S sets at each
stage. Space required is O(n2 ).
Matrix Multiplication
Find the optimal parenthesisation of a chain of
matrices to be multiplied such that the number of
scalar multiplications is minimized.
Recall the matrix multiplication algorithm:
Matrix Mult Algorithm
Algorithm 2: MatrixMultiply(A,B)
for i = 1 to rows(A) do
for j = 1 to cols(B) do
C[i,j] = 0;
for k = 1 to cols(A) do
C[i,j] = C[i,j] + A[i,k] * B[k,j];
end
end
end
When A, B are multiplied to get C: A[p*q] B[q*r] =
C[p*r], the number of multiplications required is
p*q*r.
How to reduce the number of scalar
multiplications?
Example
Parenthesisation: For example, A[1] A[2] A[3] can be
rewritten as (A[1] A[2]) A[3] or A[1] (A[2] A[3]).
Suppose A[1] is 10x100, A[2] is 100x5, and A[3] is
5x50.
Then A[1] (A[2] A[3]) 100*5*50 + 10*100*50 =
25,000 + 50,000 = 75,000 scalar multiplications.
(A[1] A[2]) A[3] 10*100*5 + 10*5*50 = 5,000 +
2,500 = 7,500 scalar multiplications.

Importance of proper parenthesisation, or the order in

which the multiplication should proceed is evident.
In example, two possible parenthesisations can be
symbolized as A[1] A[2] A[3] and A[1] A[2] A[3].
Number of possible parenthesizations is P(n) = 2.
Brute Force Solution
Try all possible parenthesisations. the number of
possible parenthesisations will be P(n), which can
grow rapidly with n, the number of matrices. A
typical recursive step to find this value is

the multiplication chain is shown partitioned. As this

partitioning can be done at k = 1 to (n-1), P(n) = sum
of P(k)*P(n-k) for k = 1 to (n-1).
Solution
The solution is:

which is exponential in n.
Using Dynamic Programming
Steps in Dynamic Programming Solution:
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
bottom-up fashion.
4. Construct an optimal solution from the computed
information.
Step 1: Characterise Structure of Optimal Solution:
Parenthesisation of two subchains A[1]...A[k] and
A[k+1]...A[n] must each be optimal for A[1]...A[n]
to be optimal, as is the case with ALL Dynamic
Programming solutions, an optimal solution to the
problem consists of optimal solutions to subproblems.
This is called optimal substructure.
Step 2: Define recursive solu-
tion:
Let , where has dimensions
P[i-1] P[i]. P is an array of dimensions.
For now, the subproblems will be finding the
minimum number of scalar multiplications m[i,j] for
computing (1 i j n).
Define m[i,j]:
If i = j, m[i,j] = 0 (single matrix).
If i j, assume an optimal split between A[k]
and A[k+1](i k j).
m[i,j] = cost of computing A[i .. k] + cost of
computing A[k+1 .. j] +
cost of computing A[i ...k] A[k+1 ...j]
= m[i,k] + m[k+1,j] + P[i-1]P[k]P[j].
However, value of k is not known, so try all j-i
possibilities.
Show that running time is at least exponential, T(n) =
.
Assume: T(k) for

If , or (okay for large

enough n).
Thus, ; this is still exponential.
There are a number of Duplicate Subproblems.
Unique Subproblems
Assume that 1 i j n or 1 i=j n. The
number of unique subproblems is given by:

Possible i and j for problem m[i,j] when i j+

possible i and j for problem m[i,j] when i = j

Only polynomial number of unique subproblems.

Step 3: Bottom-Up Approach
Algorithm 4: Matrix-Chain-Order(p)
n = length(p) - 1;
for i = 1 to n do m[i,i] = 0;
for ws = 2 to n do
for i = 1 to n - (ws - 1) do
j = i + (ws - 1);
m[i,j] = ;
for k = i to j-1 do
q = m[i,k] + m[k+1, j] + P[i-1]P[k]P[j];
if q m[i,j] then
m[i,j] = q;
s[i,j] = k;
end
end
end
end
Step 4: Construct Optimal Solu-
tion
The complexity of the above algorithm is: time
and memory.

Let A = . Call Matrix-Chain-Order

then Matrix-Chain-Multiply:
Algorithm 5: Matrix-Chain-Multiply(A, s, i, j)
if i j then
x = Matrix-Chain-Multiply(A, s, i, s[i,j]);
y = Matrix-Chain-Multiply(A, s, s[i,j]+1, j);
return Matrix-Multiply(x, y)
else
return A[i];
end
Characteristic elements of DP
evident
The characteristic elements of Dynamic Programming
evident in this formulation are:
1. Optimal Substructure. Optimal solution to
problem involves optimal solutions to
subproblems.
2. Overlapping Subproblems. Of the typically
exponential number of subproblems referred to
by a recursive solution, only a polynomial
number of them are distinct.
Memoization:
A Top-Down recursive method that remembers
intermediate results. For example, intermediate results
found in m[2,4] are useful in determining the value of
m[1,3].
Algorithm 6: Memoized-Matrix-Chain(p)
n = length(p) - 1;
for i = 1 to n do
for j = i to n do m[i,j] = ;
end
return Lookup-Chain(p, 1, n);
 Algorithm 7: Lookup-Chain(p, i, j)
if m[i,j] then return m[i,j];
if i = j then m[i,j] = 0;
else
for k = i to j-1 do
q = Lookup-Chain(p, i, k) +
Lookup-Chain(p, k+1, j) + P[i-1]P[k]P[j];
if q m[i,j] then m[i,j] = q;
end
end
return m[i,j];

Each of entries is initialised once and is filled

in by one call to Lookup-Chain. Each of calls
to Lookup-Chain takes n steps ignoring recursion, so
the total time required is .
The algorithm requires memory.
Longest Common Subsequence
(LCS)
Given two sequences X = and Y =
, find the longest subsequence Z =
that is common to x and y.
A subsequence is a subset of elements from the
sequence with strictly increasing order (not
necessarily contiguous).
Brute Force method: Check all subsequences of X
for an occurrence in Y.
Dynamic Programming:
Optimal Substructure:
Given X = , the prefix of X, i = 0, ...,
m, is , where X[0] is empty.
Optimal Substructure
Theorem 1 Let X = and Y =
be sequences, and Z = be any
LCS of X and Y.
1. If x[m] = y[n], then z[k] = x[m] = y[n] and
Z[k-1] is an LCS of X[m-1] and Y[n-1].
2. If , then implies that Z is an
LCS of X[m-1] and Y.
3. If , then implies that Z is an
LCS of X and Y[n-1].
Thus the LCS problem has optimal substructure.
Overlapping Subproblems
Define: c[i,j] = length of LCS for X[i] and Y[j].
c[i,j] =

Distinct Subproblems: An exponential recursive

algorithm possible, but there are only m*n distinct
subproblems.
The solution is shown as Algorithm given next:
Algorithm 8: LCSLength(x, y)
[c[i,j] maximum length array]
m = length(x);
n = length(y);
for i = 1 to m do c[i,0] = 0;
for j = 0 to n do c[0,j] = 0;
for i = 1 to m do
for j = 1 to n do
if x[i] = y[j] then c[i,j] = c[i-1,j-1] + 1;
else if c[i-1,j] c[i,j-1] then c[i,j] =
c[i-1,j];
else c[i,j] = c[i,j-1];
end
end
return c and b;
LCSLength has a time complexity of O(mn).
Single Source Shortest Paths
Given a weighted, directed graph G = (V, E) with edge
weights w and a path definition of
p= with weight w(p) =
, find the shortest path weight from
vertex u to vertex v:

From your past study of data structures you may have

seen that Breadth-First Search worked on unweighted
graphs, but here the problem is more involved.
Shortest Paths variants
Single Source – shortest path from some vertex s to
every other vertex.
Single Destination – shortest path to some vertex d
from every other vertex (reverse the direction on
edges and run single source algorithm).
Single Pair – shortest path from u to v (run single
source algorithm with s = u; nothing better
asymptotically than other variants).
All Pairs – shortest path from u to v for every pair of
vertices (single source for every vertex, but can
do better).
We encounter problems when the input graphs contain
cycles with arcs having negative weight.
Edge with a negative weight
s d
5 5
-10

a 5 b

Shortest Path from s (a) to d (b) can become

arbitrarily short (there is no shortest path).

Some well known algorithms for the various

variations of this problem are:
Dijkstra’s Algorithm: non negative weights.
Bellman-Ford: negative weights are allowed; detects
negative cycles.
Shortest Paths Tree (single source)
Predecessor Subgraph for G
= (V, E).

The unique simple path from s to v in is the

shortest path from s to v in G.
The Shortest Path problem has optimal substructure.
If the shortest path p from s to v can be decomposed
into , then p’ is a shortest path from s to u,
and . Since the problem
has an optimal substructure, we can try to use
dynamic programming and greedy algorithms.
Relaxation method
A stricter upper bound is achieved for the d(v) on the
shortest path weight from s to v, maintaining d(v) and
pred(v) for each vertex v.
d(u) w(u,v) d(v)

s u v

Algorithm 9: Relax(u, v, w)
if d(v) d(u)+w(u,v) then
d(v) = d(u) + w(u,v);
pred(v) = u;
end
The following initialisation should be done before
applying this algorithm:
Initialise
Algorithm 10: Init-Single-Source(G, s)
[G = (V, E)]
for each v V do
d(v) = ;
pred(v) = NIL;
end
d(s) = 0;
It can be shown that applying Relaxation after
Init-Single-Source will eventually result in the
shortest path weight and the predecessor graph will be
a shortest path tree (assuming no negative-weight
cycles).
Dijkstra’s Algorithm
Algorithm 11: Shortest Path: Dijkstra [1959]
Q = V;
S= ;
repeat
extract a vertex u from Q;
Use to update other values;
S=S {u};
until Q = ;
Use a priority queue for Q with d(v) as the key
and extract the u with minimum key value from
Q. The function changes d(v) for each v.
The Greedy choice is used for the next vertex to
add to S, which contains vertices whose shortest
path is known. We can do this because of optimal
substructure.
Efficiency: Dijkstra’s
Works for nonnegative weights only.

It is known that Dijkstra’s algorithm takes

and time for Q implemented as a
linear array and Q implemented as binary search tree
respectively.

Note that in the latter case, the reduction in the

running time is due to the faster extraction of a node
V from Q implemented as a Binary Search Tree, with
time of order of log n instead of n. Thus the
improvement is due to a more suitable data structure
and not the algorithm.

Thus Dijkstra’s algorithm produces a shortest path

tree, under the conditions mentioned.
Bellman-Ford Algorithm
Accepts negative weights and detects negative cycles.
Algorithm 12: Bellman-Ford(G, w, s)
Init-Single-Source(G, s);
[ O(V) ]
for i = 1 to ( - 1) do
for each (u,v) in E do Relax(u, v, w);
[ O(VE)]
end
for each edge (u,v) in E do
[ O(E) ]
if d(v) d(u) + w(u,v) then return false;
end
return true;
[ O(VE) ]
All-Pairs Shortest Paths
Given a directed graph G = (V,E) with weight
function w: E R, mapping edges to real-valued
weights, find the shortest path between every pair of
vertices u,v V, that minimizes the sum of the
weights along the edges of the path.
Solution 1: Run the Single-Source Shortest Path on
every vertex.
Gives a time complexity using a binary
heap and a priority queue.
Bellman-Ford algorithm: a time complexity .
E= in the worst case.
Solution 2: Dynamic Programming approach.
The Matrix Multiplication method with repeated
squaring: time complexity .
The Floyd-Warshall time complexity .