Lecture 5

Dynamic Programming
 Divide and Conquer
• Divide the problem into subproblems.
• Conquer the subproblems by solving
them recursively.
• Combine the solutions to subproblems
into the solution for original problem.
 Quiz Sample
• True or false?
• Every algorithm that contains a divide step
and a conquer step is a divide-and-
conquer algorithm.
 Quiz Sample
• True or false?
• Every algorithm that contains a divide step
and a conquer step is a divide-and-conquer
algorithm.
• Answer: No
• A dynamic programming contains a divide
step and a conquer step and may not be a
divide-and-conquer algorithm.
 Dynamic Programming
Two hallmark :
Solution substructure : a solution to a problem contains
solutions to subproblems. Self-reducibility
Overlapping subproblems : a recursive solution contains
a " small" number of distinct subproblems possibly
repeated many times. Self-reduction may not have
tree structure
 Dynamic Programming
• Divide the problem into subproblems.
• Conquer the subproblems by solving
them recursively.
• Combine the solutions to subproblems
into the solution for original problem.
Remark on Divide and Conquer

Key Point: Self - reducibility!!!

A recursive structure reduces the problem to some
subproblems (i.e., some problems with smaller sizes).

Divide-and-Conquer is a DP-type technique.

Algorithms with Self-reducibility

Greedy

Divide and
Conquer
Local
Ratio
Dynamic
Algorithms Programming
with Self-Reducibility
Matrix-chain Multiplication

Given a chain { A1 , A2 ,..., An } of n matrices,

where for i 1,2,..., n, matrix Ai has dimension
pi  1 pi , fully parenthesize the product
A1 A2  An in a way that minimizes the number
of scaler multiplications.
 Fully Parenthesize
A product is fully parenthesized if it is either
a single matrix or the product of two fully
parenthesized products.

(( A1 ( A2 A3 )) A4 )
(( A1 A2 )( A3 A4 ))
 Scalar Multiplications
Consider p q matrix A (aij ) and q r
matrix B (b jk ). Then
q
AB ( aij b jk ) pr
j 1

Thus, the number of scalar multiplications

to do this matrix product is pqr.
Different fully parenthesized products may
give different numbers of scalar multiplications.

e.g.,
# of scalar multiplications

( A1 ( A2 A3 )) p0 p1 p3  p1 p2 p3
(( A1 A2 ) A3 ) p0 p1 p2  p0 p2 p3
 Step 1. Find recursive structure of
optimal solution

Suppose optimal fully parenthesized product

is the product of two fully parenthesized
products of A1  Ak and Ak 1  An . Then
they are optimal fully parenthesized products
of A1  Ak and Ak 1  An , respectively.
 Step 2. Build recursive formula about
optimal value

Let m[i, j ] be the minimum number of scalar

multiplication for computing Ai  A j . Then
m[i, j ] 0 if i  j;
m[i, j ] min (m[i, k ]  m[k  1, j ]  pi  1 pk p j )
i k  j

if i  j.
 Step 3. Computing optimal value

function m[i, j ]
if i  j
then return 0;
else begin
u  ;
for k  i to j  1 do
u  min(u , m[i, k ]  m[k  1, j ]  pi 1 pk p j );
end - else
return u;
Step 3. Computing optimal value
Matrix - Chain - Order( p )
n  length( p )  1;
for i  1 to n do m[i, i ] 0;
for l  2 to n do
for i  1 to n  l  1
do j  i  l  1
m[i, j ]  
for k  i to j  1
do q  m[i, k ]  m[k  1, j ]  pi  1 pk p j
if q  m[i, j ]
then m[i, j ]  q
s[i, j ]  k
return m and s
Step 4. Constructing an optimal
solution

Follow values of s[i, j ].

 m
6 1
15
j 5 15,125
1 2 i
4 11,875 10,500 3
3 9,375 7,125 5,375
4
2 7,875 4,375 2,500 3,500 5
1 15,700 2,625 750 1,000 5,000 6
0 0 0 0 0 0

A1 A2 A3 A4 A5 A6
3035 3515 155 510 1020 2025
 (s )
6 1
15
j 5
15,125
1
(3) 2 i
4 11,875
(3)
10,500
(3)
3
9,375 7,125 5,375
3 (3) (3) (3) 4
2
7,875
(1)
4,375
(3)
2,500
(3)
3,500
(5)
5
1
15,700
(1)
2,625
(2)
750
(3)
1,000
(4)
5,000
(5)
6
0 0 0 0 0 0

A1 A2 A3 A4 A5 A6

Optimal solution (( A1 ( A2 A3 ))(( A4 A5 ) A6 ))

 Running Time
Matrix - Chain - Order( p )
n  length( p )  1;
for i  1 to n do m[i, i ] 0; O(n)
for l  2 to n do O(n)
for i  1 to n  l  1 O(n)
do j  i  l  1
m[i, j ]  
for k  i to j  1 O(n)
do q  m[i, k ]  m[k  1, j ]  pi  1 pk p j
if q  m[i, j ]
then m[i, j ]  q
s[i, j ]  k
O(n 3 )
return m and s
 Running Time
function m[i, j ]
if i  j
then return 0;
else begin
u  ;
for k  i to j  1 do O(n)

u  min(u , m[i, k ]  m[k  1, j ]  pi 1 pk p j );

end - else
return u;
How many recursive calls?
How many m[I,j] will be computed?
 # of Subproblems

How many m[i, j ] may be computed?

2
O(n )
 Running Time

Let m[i, j ] be the minimum number of scalar

multiplication for computing Ai  A j . Then
m[i, j ] 0 if i  j;
m[i, j ] min (m[i, k ]  m[k  1, j ]  pi  1 pk p j )
i k  j

if i  j.
 Remark on Running Time
(1) Time for computing recursive formula.
(2)The number of subproblems.
(3) Multiplication of (1) and (2)
Longest Common
Subsequence
 Problem
Given two sequences X and Y , find a longest common
subsequence Z of X and Y .

10110110

00100100
 Recursive Formula
c[i, j ] the length of the longest commen subsequence
of following two sequences
x1 , x2 , ..., xi ;
y1 , y2 , ..., y j .

0 if i 0 or j 0,

c[i, j ] c[i  1, j  1]  1 if i, j  0 and xi  y j ,
max(c[i, j  1], c[i  1, j ]) if i, j  0 and x  y .
 i j
 Related Problem
Given two sequences X and Y , find a longest consecutive
common subsequence Z of X and Y .

10110110
00100100
 Recursive Formula
s[i, j ] the length of the longest consecutive commen
subsequence of following two sequences
x1 , x2 , ..., xi ;
y1 , y2 , ..., y j .

0 if i 0 or j 0,

s[i, j ]  ? if i, j  0 and xi  y j ,
max(s[i, j  1], s[i  1, j ]) if i, j  0 and x  y .
 i j
 Recursive Formula
s[i, j ] the length of the longest consecutive commen
subsequence of following two sequences
x1 , x2 , ..., xi ;
y1 , y2 , ..., y j .

0 if i 0 or j 0,

s[i, j ] max( s[i, j  1], s[i  1, j ], t[i, j ]) if i, j  0 and xi  y j ,
max( s[i, j  1], s[i  1, j ]) if i, j  0 and xi  y j .

0 if xi  y j or i 0 or j 0
t[i, j ] 
 t[i  1, j  1]  1 if xi  y j
 Related Problem
t[i, j ] the length of the longest consecutive commen
tail of following two sequences
x1 , x2 , ..., xi ;
y1 , y2 , ..., y j .

10110110
00100110
More Examples
 A Rectangle with holes

Given a rectangle with point - holes inside, partition it

into smaller rectangles without hole inside to minimize
the total length of cuts.
NP-Hard!!!
Guillotine cut
 Guillotine Partition
A sequence of guillotine cuts

Canonical one: every cut passes a hole.

Minimum length Guillotine Partition
• Given a rectangle with holes, partition it
into smaller rectangles without hole to
minimize the total length of guillotine
cuts.
 Minimum Guillotine Partition

Dynamic programming
In time O(n 5 ):

Each cut has at most 2n

choices.
4
There are O(n ) subproblems.

Minimum guillotine partition can be a polynomial-time

approximation.
 What we learnt in this lecture?
• How to design dynamic programming.
• Two ways to implement.
• How to analyze running time.
 Quiz Sample
• True or False
• Analysis method for dynamic programming
can also be applied to divide-and-conquer
algorithms.
• Answer: True
 Quiz Sample
• True or False
• Every dynamic programming can be
analyzed with formula:
Run-time = (table size)
x (computation time of recursive formula).
• Answer: False
• A counterexample can be seen in study of
the shortest path problem.
 Puzzle
In Matrix - Chain Multiplication, is it true that for i  i ' ,
s (i, i  l ) s (i ' , i 'l ) ?
If this monotone property holds, can we improve running
time with it?