DYNAMIC PROGRAMMING
Lecture 8
Dynamic Programming
•Dynamic Programming is a general algorithm design technique
for solving problems defined by or formulated as recurrences with
overlapping subinstances.
• “Programming” here means “planning”
• Main idea:
- set up a recurrence relating a solution to a larger instance to
solutions of some smaller instances
- solve smaller instances once
- record solutions in a table
- extract solution to the initial instance from that table
Examples of DP algorithms
• Warshall’s algorithm for transitive closure
• Floyd’s algorithm for all-pairs shortest paths
• Some instances of difficult discrete optimization problems:
- knapsack
Warshall’s and Floyd’s algorithm
These algorithms are based on essentially the same
idea: exploit a relationship between a problem and
its simpler rather than smaller version.
Warshall and Floyd published their algorithms
without mentioning dynamic programming.
Nevertheless, the algorithms certainly have a
dynamic programming flavor and have come to be
considered applications of this technique
Warshall’s Algorithm: Transitive Closure
• Computes the transitive closure of a directed graph
• Example of transitive closure:
3 3
1 1
4 4 0 0 1 0
2 0 0 1 0 2
1 0 0 1 1 1 1 1
0 0 0 0 0 0 0 0
0 1 0 0 1 1 1 1
Brute force approach to solve problem
We can generate the transitive closure of a digraph
with the help of depth-first search or breadth-first
search.
Performing either traversal starting at the ith vertex
gives the information about the vertices reachable
from the it and hence this is the columns that
contain ones in the ith row of the transitive clousre.
Thus doing such a traversal for every vertex as a
starting point yields the transitive clousre in its
entirety.
Warshall’s Algorithm
Constructs transitive closure T as the last matrix in the sequence of n-
by-n matrices R(0), … , R(k), … , R(n) where
R(k)[i,j] = 1 iff there is nontrivial path from i to j with only the first k
vertices allowed as intermediate
Note that R(0) = A (adjacency matrix), R(n) = T (transitive closure)
3 3 3 3 3
1 1 1 1 1
4 4 4 2 4 4
2 2 2 2
R(0) R(1) R(2) R(3) R(4)
0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0
1 0 0 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1
Warshall’s Algorithm (matrix generation)
Recurrence relating elements R(k) to elements of R(k-1) is:
R(k)[i,j] = R(k-1)[i,j] or (R(k-1)[i,k] and R(k-1)[k,j])
It implies the following rules for generating R(k) from R(k-1):
Rule 1 If an element in row i and column j is 1 in R(k-1),
it remains 1 in R(k)
Rule 2 If an element in row i and column j is 0 in R(k-1),
it has to be changed to 1 in R(k) if and only if
the element in its row i and column k and the element
in its column j and row k are both 1’s in R(k-1)
Warshall’s Algorithm (example)
3
1 0 0 1 0 0 0 1 0
1 0 0 1 1 0 1 1
R(0) = 0 0 0 0 R(1) = 0 0 0 0
0 1 0 0 0 1 0 0
4
2
0 0 1 0 0 0 1 0 0 0 1 0
1 0 1 1 1 0 1 1 1 1 1 1
R(2) = 0 0 0 0 R(3) = 0 0 0 0 R(4) = 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1
Warshall’s Algorithm (pseudocode and analysis)
Time efficiency: Θ(n3)
Floyd’s Algorithm: All pairs shortest paths
Problem: In a weighted digraph, find shortest paths between
every pair of vertices
Same idea: construct solution through series of matrices D(0), …,
D (n) using increasing subsets of the vertices allowed
as intermediate
2
Example: 1 2 0 ∞ 3 ∞
2 0 ∞ ∞
3 6 7
∞ 7 0 1
6 ∞ ∞ 0
3 1 4
Floyd’s Algorithm (matrix generation)
On the k-th iteration, the algorithm determines shortest paths
between every pair of vertices i, j that use only vertices among
1,…,k as intermediate
D(k)[i,j] = min {D(k-1)[i,j], D(k-1)[i,k] + D(k-1)[k,j]}
D(k-1)[i,k]
k
D(k-1)[k,j]
D(k-1)[i,j]
j
Initial condition?
Floyd’s Algorithm (example)
2
1 2 0 ∞ 3 ∞ 0 ∞ 3 ∞
6 7 2 0 ∞ ∞ 2 0 5 ∞
3 ∞ 7 0 1 ∞ 7 0 1
D(0) = D(1) =
6 ∞ ∞ 0 6 ∞ 9 0
3 1 4
0 ∞ 3 ∞ 0 10 3 4 0 10 3 4
2 0 5 ∞ 2 0 5 6 2 0 5 6
D(2) = 9 7 0 1 D(3) = 9 7 0 1 D(4) = 7 7 0 1
6 ∞ 9 0 6 16 9 0 6 16 9 0
Floyd’s Algorithm (pseudocode and analysis)
Time efficiency: Θ(n3)
Knapsack Problem by DP
Given n items of integer weights: w1 w2 … wn values:
v1 v2 … vn a knapsack of integer capacity W find most
valuable subset of the items that fit into the knapsack
Consider instance defined by first i items and capacity j
(j W).
Let V[i,j] be optimal value of such an instance. Then
max {V[i-1,j], vi + V[i-1,j- wi]} if j- wi 0
{
V[i,j] =
V[i-1,j] if j- wi < 0
Initial conditions: V[0,j] = 0 and V[i,0] = 0
Knapsack Problem by DP (example)
Example: Knapsack of capacity W = 5
item weight value
1 2 $12
2 1 $10
3 3 $20
4 2 $15
w1 = 2, v1= 12 Backtracing
w2 = 1, v2= 10 finds the actual
w3 = 3, v3= 20 optimal subset,
i.e. solution.
w4 = 2, v4= 15
Con…
Optimal solution:
Item1, item2, item4.
The time efficiency and space efficiency of this
algorithm are both in O(nW).
The time needed to find the composition of an
optimal solution is in O(n).
Assignment
Apply Warshall’s algorithm to find the transitive
closure of the digraph defined by the following
adjacency matrix:
0 1 0 0
0 0 1 0
0 0 0 1
0 0 0 0
Con…
Solve the all-pairs shortest-path problem for the
digraph with the weight matrix:
0 2 ∞ 1 8
6 0 3 2 ∞
∞ ∞ 0 4 ∞
∞ ∞ 2 0 3
3 ∞ ∞ ∞ 0