Dynamic Programming

Dr. Navjot Singh

Design and Analysis of Algorithms
Dynamic Programming
⚫ Dynamic Programming is an algorithm design technique for optimization
problems: often minimizing or maximizing.
⚫ Invented by American mathematician Richard Bellman in the 1950s to solve
optimization problems.
⚫ “Programming” here means “planning”.
⚫ Like divide and conquer, DP solves problems by combining solutions to
subproblems.
⚫ Unlike divide and conquer, subproblems are not independent.
⚫ Subproblems may share subsubproblems,

⚫ However, solution to one subproblem may not affect the solutions to other
subproblems of the same problem. 2
Dynamic Programming
⚫ DP reduces computation by
⚫ Solving subproblems in a bottom-up fashion.
⚫ Storing solution to a subproblem the first time it is solved.
⚫ Looking up the solution when subproblem is encountered again.
⚫ Key Elements:
⚫ Optimal Substructure
⚫ Overlapping Subproblems

3
Optimal Substructure
⚫ Show that a solution to a problem consists of making a choice, which leaves
one or more subproblems to solve.
⚫ Suppose that you are given this last choice that leads to an optimal solution.
⚫ Given this choice, determine which subproblems arise and how to
characterize the resulting space of subproblems.
⚫ Show that the solutions to the subproblems used within the optimal solution
must themselves be optimal. Usually use cut-and-paste.
⚫ Need to ensure that a wide enough range of choices and subproblems are
considered.

4
Optimal Substructure
⚫ Optimal substructure varies across problem domains:
⚫ How many subproblems are used in an optimal solution.
⚫ How many choices in determining which subproblem(s) to use.
⚫ Informally, running time depends on (# of subproblems overall)  (# of choices).
⚫ How many subproblems and choices do the examples considered contain?
⚫ Dynamic programming uses optimal substructure bottom-up.
⚫ First find optimal solutions to subproblems.
⚫ Then choose which to use in optimal solution to the problem.

5
Optimal Substucture
⚫ Does optimal substructure apply to all optimization problems? No.
⚫ Applies to determining the shortest path but NOT the longest simple path of
an unweighted directed graph.
⚫ Why?
⚫ Shortest path has independent subproblems.
⚫ Solution to one subproblem does not affect solution to another subproblem of the same problem.
⚫ Subproblems are not independent in longest simple path.
⚫ Solution to one subproblem affects the solutions to other subproblems.

6
Overlapping Subproblems
⚫ The space of subproblems must be “small”.
⚫ The total number of distinct subproblems is a polynomial in the
input size.
⚫ A recursive algorithm is exponential because it solves the same problems
repeatedly.
⚫ If divide-and-conquer is applicable, then each problem solved will be brand
new.

7
Overlapping sub-problems

divide and
conquer

dynamic
programming

…
8
Steps in Dynamic Programming

1. Characterize structure of an optimal solution.

2. Define value of optimal solution recursively.
3. Compute optimal solution values either top-down with caching or
bottom-up in a table.
4. Construct an optimal solution from computed values.

9
Fibonacci numbers
1, 1, 2, 3, 5, 8, 13, 21, 34, …
What is the recurrence for the nth Fibonacci
number?

F(n) = F(n-1) + F(n-2)

The solution for n is defined with respect to the

solution to smaller problems (n-1 and n-2)

10
Fibonacci: a first attempt

11
Is it correct?

F(n) = F(n-1) + F(n-2)

12
Running time

Each call creates two recursive calls

Each call reduces the size of the problem by 1 or 2

Creates a full binary of depth n

O(2n)
13
Can we do better?
Fib(n)

Fib(n-1) Fib(n-2)

Fib(n-2) Fib(n-3) Fib(n-3) Fib(n-4)

Fib(n-3) Fib(n-4) Fib(n-4) Fib(n-5) Fib(n-4) Fib(n-5) Fib(n-5) Fib(n-6)

14
A lot of repeated work!
Fib(n)

Fib(n-1) Fib(n-2)

Fib(n-2) Fib(n-3) Fib(n-3) Fib(n-4)

Fib(n-3) Fib(n-4) Fib(n-4) Fib(n-5) Fib(n-4) Fib(n-5) Fib(n-5) Fib(n-6)

15
Creating a dynamic programming solution
Step 1: Identify a solution to the problem with respect to smaller subproblems (pretend like you
have a solver, but it only works on smaller problems):
⚫ F(n) = F(n-1) + F(n-2)

Step 2: bottom up - start with solutions to the smallest problems and build solutions to the larger
problems
use an array to
store solutions
to subproblems

16
Is it correct?

F(n) = F(n-1) + F(n-2)

17
Running time?

Θ(n)

18
Longest common subsequence (LCS)
For a sequence X = x1, x2, …, xm, a subsequence
is a subset of the sequence defined by a set of
increasing indices (i1, i2, …, ik) where
1 ≤ i 1 < i2 < … < i k ≤ m

X=ABACDABAB

ABA?
19
Longest common subsequence (LCS)
For a sequence X = x1, x2, …, xm, a subsequence
is a subset of the sequence defined by a set of
increasing indices (i1, i2, …, ik) where
1 ≤ i 1 < i2 < … < i k ≤ m

X=ABACDABAB

ABA
20
Longest common subsequence (LCS)
For a sequence X = x1, x2, …, xm, a subsequence
is a subset of the sequence defined by a set of
increasing indices (i1, i2, …, ik) where
1 ≤ i 1 < i2 < … < i k ≤ m

X=ABACDABAB

ACA?
21
Longest common subsequence (LCS)
For a sequence X = x1, x2, …, xm, a subsequence
is a subset of the sequence defined by a set of
increasing indices (i1, i2, …, ik) where
1 ≤ i 1 < i2 < … < i k ≤ m

X=ABACDABAB

ACA
22
Longest common subsequence (LCS)
For a sequence X = x1, x2, …, xm, a subsequence
is a subset of the sequence defined by a set of
increasing indices (i1, i2, …, ik) where
1 ≤ i 1 < i2 < … < i k ≤ m

X=ABACDABAB

DCA?
23
Longest common subsequence (LCS)
For a sequence X = x1, x2, …, xm, a subsequence
is a subset of the sequence defined by a set of
increasing indices (i1, i2, …, ik) where
1 ≤ i 1 < i2 < … < i k ≤ m

X=ABACDABAB

DCA
24
Longest common subsequence (LCS)
For a sequence X = x1, x2, …, xm, a subsequence
is a subset of the sequence defined by a set of
increasing indices (i1, i2, …, ik) where
1 ≤ i 1 < i2 < … < i k ≤ m

X=ABACDABAB

AADAA?
25
Longest common subsequence (LCS)
For a sequence X = x1, x2, …, xm, a subsequence
is a subset of the sequence defined by a set of
increasing indices (i1, i2, …, ik) where
1 ≤ i 1 < i2 < … < i k ≤ m

X=ABACDABAB

AADAA
26
LCS problem
Given two sequences X = x1, x2, …, xm and Y = y1, y2, …, yn,
a common subsequence is a subsequence that occurs in
both X and Y

What is the longest common subsequence?

X=ABCBDAB
Y=BDCABA
27
LCS problem
Given two sequences X = x1, x2, …, xm and Y = y1, y2, …, yn,
a common subsequence is a subsequence that occurs in
both X and Y

What is the longest common subsequence?

X=ABCBDAB
Y=BDCABA
28
Naïve Algorithm
⚫ For every subsequence of X, check whether it’s a
subsequence of Y .
⚫ Time: Θ(n2m).
⚫ 2m subsequences of X to check.
⚫ Each subsequence takes Θ(n) time to check:
scan Y for first letter, for second, and so on.

29
Step 1: Define the problem with respect
to subproblems
X=ABCBDAB

Y=BDCABA

Assume you have a solver for smaller problems

30
Step 1: Define the problem with respect
to subproblems
X=ABCBDA?

Y=BDCAB?

Is the last character part of the LCS?

31
Step 1: Define the problem with respect
to subproblems
X=ABCBDA?

Y=BDCAB?

Two cases: either the characters

are the same or they’re different

32
Step 1: Define the problem with respect
to subproblems
X = A B C B D AA
LCS The characters are
part of the LCS
Y=BDCABA What is the recursive
relationship?

If they’re the same

33
Step 1: Define the problem with respect
to subproblems
X=ABCBDAB
LCS

Y=BDCABA

If they’re different

34
Step 1: Define the problem with respect
to subproblems
X=ABCBDAB
LCS

Y=BDCABA

If they’re different

35
Step 1: Define the problem with respect
to subproblems
X=ABCBDAB
Y=BDCABA

X=ABCBDAB
?
Y=BDCABA

If they’re different 36
Optimal Substructure
Theorem
Let Z = z1, . . . , zk be any LCS of X and Y.
1. If xm = yn, then zk = xm = yn and Zk-1 is an LCS of Xm-1 and Yn-1.
2. If xm  yn, then either zk  xm and Z is an LCS of Xm-1 and Y.
3. or zk  yn and Z is an LCS of X and Yn-1.

Notation:
prefix Xi = x1,...,xi is the first i letters of X.

37
 Optimal Substructure
Theorem
Let Z = z1, . . . , zk be any LCS of X and Y.
1. If xm = yn, then zk = xm = yn and Zk-1 is an LCS of Xm-1 and Yn-1.
2. If xm  yn, then either zk  xm and Z is an LCS of Xm-1 and Y.
3. or zk  yn and Z is an LCS of X and Yn-1.

Proof: (case 1: xm = yn)

Any sequence Z’ that does not end in xm = yn can be made longer by adding xm =
yn to the end. Therefore,
(1) longest common subsequence (LCS) Z must end in xm = yn.
(2) Zk-1 is a common subsequence of Xm-1 and Yn-1, and
(3) there is no longer CS of Xm-1 and Yn-1, or Z would not be an LCS. 38
 Optimal Substructure
Theorem
Let Z = z1, . . . , zk be any LCS of X and Y.
1. If xm = yn, then zk = xm = yn and Zk-1 is an LCS of Xm-1 and Yn-1.
2. If xm  yn, then either zk  xm and Z is an LCS of Xm-1 and Y.
3. or zk  yn and Z is an LCS of X and Yn-1.

Proof: (case 2: xm  yn, and zk  xm)

Since Z does not end in xm,
(1) Z is a common subsequence of Xm-1 and Y, and

(2) there is no longer CS of Xm-1 and Y, or Z would not be an LCS.

39
 Recursive Solution
⚫ Define c[i, j] = length of LCS of Xi and Yj .
⚫ We want c[m,n].

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 − 1, j ], c[i, j − 1]) if i, j  0 and x  y .
 i j

This gives a recursive algorithm and solves the problem.

40
 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 − 1, j ], c[i, j − 1]) if i, j  0 and x  y .
 i j

j 0 1 2 34 5 6
i yj B D C A B A
0 xi
1 A
2 B Lets fill in the entries
3 C
4 B
5 D
6 A
7 B
41
 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 − 1, j ], c[i, j − 1]) if i, j  0 and x  y .
 i j

j 0 1 2 34 5 6
i yj B D C A B A
0 xi 0 0 0 000 0
1 A 0
2 B 0 Need to initialize values within 1
smaller in either dimension.
3 C 0
4 B 0
5 D 0
6 A 0
7 B 0
42
 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 − 1, j ], c[i, j − 1]) if i, j  0 and x  y .
 i j

j 0 1 2 34 5 6
i yj B D C A B A
0 xi 0 0 0 000 0
1 A 0 ? LCS(A, B)
2 B 0
3 C 0
4 B 0
5 D 0
6 A 0
7 B 0
43
 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 − 1, j ], c[i, j − 1]) if i, j  0 and x  y .
 i j

j 0 1 2 34 5 6
i yj B D C A B A
0 xi 0 0 0 000 0
1 A 0 0
2 B 0
3 C 0
4 B 0
5 D 0
6 A 0
7 B 0
44
 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 − 1, j ], c[i, j − 1]) if i, j  0 and x  y .
 i j

j 0 1 2 34 5 6
i yj B D C A B A
0 xi 0 0 0 000 0
1 A 0 0 0 0? LCS(A, BDCA)
2 B 0
3 C 0
4 B 0
5 D 0
6 A 0
7 B 0
45
 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 − 1, j ], c[i, j − 1]) if i, j  0 and x  y .
 i j

j 0 1 2 34 5 6
i yj B D C A B A
0 xi 0 0 0 000 0
1 A 0 0 0 01 LCS(A, BDCA)
2 B 0
3 C 0
4 B 0
5 D 0
6 A 0
7 B 0
46
 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 − 1, j ], c[i, j − 1]) if i, j  0 and x  y .
 i j

j 0 1 2 34 5 6
i yj B D C A B A
0 xi 0 0 0 000 0
1 A 0 0 0 011 1
LCS(ABCB, BDCAB)
2 B 0 1 1 112 2
3 C 0 1 1 222 2
4 B 0 1 1 22?
5 D 0
6 A 0
7 B 0
47
 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 − 1, j ], c[i, j − 1]) if i, j  0 and x  y .
 i j

j 0 1 2 34 5 6
i yj B D C A B A
0 xi 0 0 0 000 0
1 A 0 0 0 011 1
LCS(ABCB, BDCAB)
2 B 0 1 1 112 2
3 C 0 1 1 222 2
4 B 0 1 1 223
5 D 0
6 A 0
7 B 0
48
 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 − 1, j ], c[i, j − 1]) if i, j  0 and x  y .
 i j

j 0 1 2 34 5 6
i yj B D C A B A
0 xi 0 0 0 000 0
Where’s the
1 A 0 0 0 011 1
final answer?
2 B 0 1 1 112 2
3 C 0 1 1 222 2
4 B 0 1 1 223 3
5 D 0 1 2 223 3
6 A 0 1 2 233 4
7 B 0 1 2 234 4
49
The algorithm

50
The algorithm

Base case initialization

51
The algorithm

Fill in the matrix

52
The algorithm

53
The algorithm

54
The algorithm

55
Running time?

Θ(nm)

56
Keeping track of the solution
LCS algorithm only calculated the length of the LCS
between X and Y
What if we wanted to know the actual sequence?

Keep track of this as well…

57
 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 − 1, j ], c[i, j − 1]) if i, j  0 and x  y .
 i j

j 0 1 2 34 5 6
i yj B D C A B A
0 xi 0 0 0 000 0
1 A 0 0 0 011 1
2 B 0 1 1 112 2 We can follow the
3 C 0 1 1 222 2 arrows to generate
the solution
4 B 0 1 1 223 3
5 D 0 1 2 223 3
6 A 0 1 2 233 4
7 B 0 1 2 234 4
58
 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 − 1, j ], c[i, j − 1]) if i, j  0 and x  y .
 i j

j 0 1 2 34 5 6
i yj B D C A B A
0 xi 0 0 0 000 0
1 A 0 0 0 011 1
2 B 0 1 1 112 2 We can follow the
3 C 0 1 1 222 2 arrows to generate
the solution
4 B 0 1 1 223 3
5 D 0 1 2 223 3
6 A 0 1 2 233 4 BCBA
7 B 0 1 2 234 4
59
Counting binary search trees
How many unique binary search trees can be
created using the numbers 1 through n?

2 5

1 3 6
60
Step 1:
What is the subproblem?
Assume we have some black box solver (call it T) that
can give us the answer to smaller subproblems

How can we use the answer from this to answer our

question?

How many options for the root are there?

1 2 3 n

…
61
Subproblems
i

How many trees have i as the root?

62
Subproblems
i

1, 2, …, i-1 i+1, i+2, …, n

63
Subproblems
i

1, 2, …, i-1 i+1, i+2, …, n

T(i-1) ?
subproblem of
size i-1

64
Subproblems
i

1, 2, …, i-1 i+1, i+2, …, n

T(i-1) Number of trees for i+1, i+2, …, i+n

is the same as the number of trees
from 1, 2, …, n-i

65
Subproblems
i

1, 2, …, i-1 i+1, i+2, …, n

T(i-1) T(n-i)

Given solutions for T(i-1) and T(n-i) how

many trees are there with i as the root?

66
Subproblems
i

1, 2, …, i-1 i+1, i+2, …, n

T(i-1) T(n-i)

T(i) = T(i-1) * T(n-i)

67
Step 1: define the answer with respect to
subproblems
T(i) = T(i-1) * T(n-i)

T (n) = i =1T (i − 1) *T (n − i)
n

68
Is there a problem?

As with Fibonacci, we’re

repeating a lot of work
69
Step 2: Generate a solution from the
bottom-up

70
0 1 2 3 4 5 … n 71
1 1
0 1 2 3 4 5 … n 72
 c[0]*c[1] + c[1]*c[0]

1 1
0 1 2 3 4 5 … n 73
 1 2

2 1

c[0]*c[1] + c[1]*c[0]

1 1
0 1 2 3 4 5 … n 74
1 1 2
0 1 2 3 4 5 … n 75
1 2 3

c[0]*c[2] + c[1]*c[1] + c[2]*c[0]

1 1 2
0 1 2 3 4 5 … n 76
1 1 2 5
0 1 2 3 4 5 … n 77
1 1 2 5 …
0 1 2 3 4 5 … n 78
Running time?

Θ(n2)

79
Optimal Binary Search Trees
⚫ Problem
⚫ Given sequence K = k1 < k2 <··· < kn of n sorted keys,
with a search probability pi for each key ki.
⚫ Want to build a binary search tree (BST) with minimum expected search
cost.
⚫ Actual cost = # of items examined.
⚫ For key ki, cost = depthT(ki)+1, where depthT(ki) = depth of ki in BST T .

80
Expected Search Cost
E[search cost in T ]
n
=  (depth T (ki ) + 1)  pi
i =1
n n
=  depth T (ki )  pi +  pi
i =1 i =1
n
= 1 +  depth T (ki )  pi Sum of probabilities is 1.
i =1

81
Example
⚫ Consider 5 keys with these search probabilities:
p1 = 0.25, p2 = 0.2, p3 = 0.05, p4 = 0.2, p5 = 0.3.

k2
i depthT(ki) depthT(ki)·pi
1 1 0.25
2 0 0
k1 k4 3 2 0.1
4 1 0.2
5 2 0.6
1.15
k3 k5

Therefore, E[search cost] = 2.15.

82
Example
⚫ p1 = 0.25, p2 = 0.2, p3 = 0.05, p4 = 0.2, p5 = 0.3.
k2
i depthT(ki) depthT(ki)·pi
1 1 0.25
2 0 0
k1 k5 3 3 0.15
4 2 0.4
5 1 0.3
1.10
k4

Therefore, E[search cost] = 2.10.

k3
This tree turns out to be optimal for this set of keys.
83
Example
⚫ Observations:
⚫ Optimal BST may not have smallest height.
⚫ Optimal BST may not have highest-probability key at root.
⚫ Build by exhaustive checking?
⚫ Construct each n-node BST.
⚫ For each,
assign keys and compute expected search cost.
⚫ But there are (4n/n3/2) different BSTs with n nodes.

84
Optimal Substructure
⚫ Any subtree of a BST contains keys in a contiguous range ki, ..., kj for some
1 ≤ i ≤ j ≤ n.

T

⚫ If T is an optimal BST and

T contains subtree T with keys ki, ... ,kj,
then T must be an optimal BST for keys ki, ..., kj.

85
Optimal Substructure
⚫ One of the keys in ki, …,kj, say kr, where i ≤ r ≤ j,
must be the root of an optimal subtree for these keys.
⚫ Left subtree of kr contains ki,...,kr−1.
kr
⚫ Right subtree of kr contains kr+1, ...,kj.

ki kr-1 kr+1 kj

⚫ To find an optimal BST:

⚫ Examine all candidate roots kr , for i ≤ r ≤ j

⚫ Determine all optimal BSTs containing ki,...,kr−1 and containing kr+1,...,kj

86
Recursive Solution
⚫ Find optimal BST for ki,...,kj, where i ≥ 1, j ≤ n, j ≥ i−1. When j = i−1, the tree is
empty.
⚫ Define e[i, j ] = expected search cost of optimal BST for ki,...,kj.

⚫ If j = i−1, then e[i, j ] = 0.

⚫ If j ≥ i,
⚫ Select a root kr, for some i ≤ r ≤ j .

⚫ Recursively make an optimal BSTs

⚫ for ki,..,kr−1 as the left subtree, and

⚫ for kr+1,..,kj as the right subtree.

87
Recursive Solution
⚫ When the OPT subtree becomes a subtree of a node:
⚫ Depth of every node in OPT subtree goes up by 1.
⚫ Expected search cost increases by
j
w(i, j ) =  pl
l =i

⚫ If kr is the root of an optimal BST for ki,..,kj :

⚫ e[i, j ] = pr + (e[i, r−1] + w(i, r−1))+(e[r+1, j] + w(r+1, j))
= e[i, r−1] + e[r+1, j] + w(i, j). (because w(i, j)=w(i,r−1) + pr + w(r + 1, j))

⚫ But, we don’t know kr. Hence,


0 if j = i − 1
e[i, j ] = 
min {e[i, r − 1] + e[r + 1, j ] + w(i, j )} if i  j
ir  j
88
Computing an Optimal Solution
For each subproblem (i,j), store:
⚫ expected search cost in a table e[1 ..n+1 , 0 ..n]
⚫ Will use only entries e[i, j ], where j ≥ i−1.
⚫ root[i, j ] = root of subtree with keys ki,..,kj, for 1 ≤ i ≤ j ≤ n.
⚫ w[1..n+1, 0..n] = sum of probabilities
⚫ w[i, i−1] = 0 for 1 ≤ i ≤ n.
⚫ w[i, j ] = w[i, j-1] + pj for 1 ≤ i ≤ j ≤ n.

89
Pseudo-code
OPTIMAL-BST(p, q, n)
1. for i ← 1 to n + 1
2. do e[i, i− 1] ← 0
Consider all trees with l keys
3. w[i, i− 1] ← 0
4. for l ← 1 to n Fix the first key
5. do for i ← 1 to n−l + 1 Fix the last key
6. do j ←i + l−1
7. e[i, j ]←∞
8. w[i, j ] ← w[i, j−1] + pj
9. for r ←i to j
10. do t ← e[i, r−1] + e[r + 1, j ] + w[i, j ] Determine the root
11. if t < e[i, j ] of the optimal
12. then e[i, j ] ← t (sub)tree
13. root[i, j ] ←r
14. return e and root

90
Time: O(n3)
Pseudo-code with dummy keys
OPTIMAL-BST(p, q, n)
1. for i ← 1 to n + 1
2. do e[i, i− 1] ← 0 e[i, i− 1] ← qi-1
k2
3. w[i, i− 1] ← 0 w[i, i− 1] ← qi-1
4. for l ← 1 to n
5. do for i ← 1 to n−l + 1
6. do j ←i + l−1 k1 k4
7. e[i, j ]←∞
8. w[i, j ] ← w[i, j−1] + pj + qj
d0 d1
9. for r ←i to j
10. do t ← e[i, r−1] + e[r + 1, j ] + w[i, j ] k3 k5
11. if t < e[i, j ]
12. then e[i, j ] ← t d2 d3 d4 d5
13. root[i, j ] ←r
14. return e and root

91
Time: O(n3)
 0.1x1

0.15x2 0.1x2

0.05x3 0.2x3
0.05x3 0.1x3

0.05x4 0.05x4 0.05x4 0.1x4

Cost of node in red: total cost 2.80

ki are keys (k1 < k2 < … < k5), di are dummy values representing “space between” keys
k-i and ki+1.

Check the expected

←probability of ki search cost of the
←probability of di two trees!

92
e[i, j] = e[i, r−1] + e[r + 1, j ] + w[i, j ] w[i, j ] ← w[i, j−1] + pj + qj
When r=1 w[1, 2] ← w[1, 1] + p2 + q2
e[1,2] = e[1,0] + e[2,2] + w[1,2] = 0.30 + 0.10 + 0.05 = 0.45
=0.05 + 0.40 + 0.45 = 0.90

When r=2
e[1,2] = e[1,1] + e[3,2] + w[1,2]
=0.45 + 0.05 + 0.45 = 0.95

93
Matrix-Chain Multiplication
Problem: given a sequence A1, A2, …, An,
compute the product:
A1  A2  An

⚫ Matrix compatibility:
C=AB C = A1  A2  Ai  Ai+1  An
colA = rowB coli = rowi+1
rowC = rowA rowC = rowA1
colC = colB colC = colAn

94
MATRIX-MULTIPLY(A, B)
if columns[A]  rows[B]
then error “incompatible dimensions”
else for i  1 to rows[A]
do for j  1 to columns[B] rows[A]  cols[A]  cols[B]
multiplications
do C[i, j] = 0
for k  1 to columns[A]
do C[i, j]  C[i, j] + A[i, k] B[k, j]
k
j cols[B]
j cols[B]

i = i
* k
A B C
rows[A]
95
rows[A]
Matrix-Chain Multiplication
⚫ In what order should we multiply the matrices?
A1  A2  An
⚫ Parenthesize the product to get the order in which matrices are multiplied
⚫ E.g.: A1  A2  A3 = ((A1  A2)  A3)
= (A1  (A2  A3))
⚫ Which one of these orderings should we choose?
⚫ The order in which we multiply the matrices has a significant impact on the cost of evaluating
the product

96
Example
A1  A2  A 3
⚫ A1: 10 x 100
⚫ A2: 100 x 5
⚫ A3: 5 x 50
1. ((A1  A2)  A3): A1  A2 = 10 x 100 x 5 = 5,000 (10 x 5)
((A1  A2)  A3) = 10 x 5 x 50 = 2,500
Total: 7,500 scalar multiplications
2. (A1  (A2  A3)): A2  A3 = 100 x 5 x 50 = 25,000 (100 x 50)
(A1  (A2  A3)) = 10 x 100 x 50 = 50,000
Total: 75,000 scalar multiplications
one order of magnitude difference!! 97
Matrix-Chain Multiplication:
Problem Statement
⚫ Given a chain of matrices A1, A2, …, An, where Ai has
dimensions pi-1x pi, fully parenthesize the product
A1  A2  An in a way that minimizes the number of scalar
multiplications.
A1  A2  Ai  Ai+1  An
p0 x p1 p1 x p2 pi-1 x pi pi x pi+1 pn-1 x pn

98
What is the number of possible
parenthesizations?
⚫ Exhaustively checking all possible parenthesizations is not efficient!
⚫ It can be shown that the number of parenthesizations grows as Ω(4n/n3/2)

99
1. The Structure of an Optimal
Parenthesization
⚫ Notation:
Ai…j = Ai Ai+1  Aj, i  j

⚫ Suppose that an optimal parenthesization of Ai…j splits the

product between Ak and Ak+1, where i  k < j

Ai…j = Ai Ai+1  Aj

= Ai Ai+1  Ak Ak+1  Aj
= Ai…k Ak+1…j

100
Optimal Substructure
Ai…j = Ai…k Ak+1…j

⚫ The parenthesization of the “prefix” Ai…k must be an optimal parentesization

⚫ If there were a less costly way to parenthesize Ai…k, we could substitute that
one in the parenthesization of Ai…j and produce a parenthesization with a
lower cost than the optimum  contradiction!
⚫ An optimal solution to an instance of the matrix-chain multiplication
contains within it optimal solutions to subproblems

101
2. A Recursive Solution
⚫ Subproblem:

determine the minimum cost of parenthesizing

Ai…j = Ai Ai+1  Aj for 1  i  j  n

⚫ Let m[i, j] = the minimum number of multiplications needed to compute Ai…j

⚫ full problem (A1..n): m[1, n]

⚫ i = j: Ai…i = Ai  m[i, i] =0, for i=1,2,…,n

102
2. A Recursive Solution
⚫ Consider the subproblem of parenthesizing Ai…j = Ai Ai+1  Aj for
1ijn
pi-1pkpj
= Ai…k Ak+1…j for i  k < j
m[i, k] m[k+1,j]

⚫ Assume that the optimal parenthesization splits the product Ai Ai+1  Aj at k
(i  k < j)
m[i, j] = m[i, k] + m[k+1, j] + pi-1pkpj

min # of multiplications min # of multiplications # of multiplications

to compute Ai…k to compute Ak+1…j to compute Ai…kAk…j
103
2. A Recursive Solution (cont.)
m[i, j] = m[i, k] + m[k+1, j] + pi-1pkpj

⚫ We do not know the value of k

⚫ There are j – i possible values for k: k = i, i+1, …, j-1

⚫ Minimizing the cost of parenthesizing the product Ai Ai+1  Aj

becomes:

0 if i = j
m[i, j] = min {m[i, k] + m[k+1, j] + pi-1pkpj} if i < j
ik<j

104
3. Computing the Optimal Costs
0 if i = j
m[i, j] = min {m[i, k] + m[k+1, j] + pi-1pkpj} if i < j
ik<j

⚫ Computing the optimal solution recursively takes

exponential time! 1 2 3 n

⚫ How many subproblems? n

 (n2)
⚫ Parenthesize Ai…j j
3
for 1  i  j  n
2
⚫ One problem for each
1
choice of i and j 105

i
3. Computing the Optimal Costs (cont.)
0 if i = j
m[i, j] = min {m[i, k] + m[k+1, j] + pi-1pkpj} if i < j
ik<j

⚫ How do we fill in the tables m[1..n, 1..n]?

⚫ Determine which entries of the table are used in computing m[i, j]

Ai…j = Ai…k Ak+1…j

⚫ Subproblems’ size is one less than the original size

⚫ Idea: fill in m such that it corresponds to solving problems of

increasing length

106
3. Computing the Optimal Costs (cont.)
0 if i = j
m[i, j] = min {m[i, k] + m[k+1, j] + pi-1pkpj} if i < j
ik<j

⚫ Length = 1: i = j, i = 1, 2, …, n
⚫ Length = 2: j = i + 1, i = 1, 2, …, n-1
1 2 3 n
n
m[1, n] gives the optimal
solution to the problem

j
Compute rows from bottom to top 3
and from left to right 2
1
107
i
Example:
min {m[i, k] + m[k+1, j] + pi-1pkpj}

m[2, 2] + m[3, 5] + p1p2p5 k=2

m[2, 5] = min k=3

m[2, 3] + m[4, 5] + p1p3p5
k=4
m[2, 4] + m[5, 5] + p1p4p5
1 2 3 4 5 6
6
5
• Values m[i, j] depend only
4
j on values that have been
3
previously computed
2
1
108

i
Example:
min {m[i, k] + m[k+1, j] + pi-1pkpj}
1 2 3
Compute A1  A2  A3 2
3 2
7500 25000 0
⚫ A1: 10 x 100 (p0 x p1)
1
2 5000 0
⚫ A2: 100 x 5 (p1 x p2)
⚫ A3: 5 x 50 (p2 x p3) 1 0

m[i, i] = 0 for i = 1, 2, 3
m[1, 2] = m[1, 1] + m[2, 2] + p0p1p2 (A1A2)
= 0 + 0 + 10 *100* 5 = 5,000
m[2, 3] = m[2, 2] + m[3, 3] + p1p2p3 (A2A3)
= 0 + 0 + 100 * 5 * 50 = 25,000
m[1, 3] = min m[1, 1] + m[2, 3] + p0p1p3 = 75,000 (A1(A2A3))
m[1, 2] + m[3, 3] + p0p2p3 = 7,500 ((A1A2)A3) 109
Matrix-Chain-Order(p)
1. n  length[p] - 1
2. for i  1 to n // initialization: O(n) time
3. do m[i, i]  0
4. for L  2 to n // L = length of sub-chain
5. do for i  1 to n - L+1
6. do j  i + L - 1 O(n3)
7. m[i, j]  
8. for k  i to j - 1
9. do q  m[i, k] + m[k+1, j] + pi-1 pk pj
10. if q < m[i, j]
11. then m[i, j]  q
12. s[i, j]  k
13. return m and s 110
4. Construct the Optimal Solution

⚫ In a similar matrix s we 1 2 3 n
keep the optimal values of k n
⚫ s[i, j] = a value of k such
that an optimal
parenthesization of Ai..j k
j
splits the product between 3
Ak and Ak+1 2
1

111
4. Construct the Optimal Solution
⚫ s[1, n] is associated with 1 2 3 n
the entire product A1..n n
⚫ The final matrix
multiplication will be split
at k = s[1, n] j
3
A1..n = A1..s[1, n]  As[1, n]+1..n
2
⚫ For each subproduct
recursively find the 1
corresponding value of k i
that results in an optimal
parenthesization
112
4. Construct the Optimal Solution
⚫ s[i, j] = value of k such that the optimal parenthesization
of Ai Ai+1  Aj splits the product between Ak and Ak+1

1 2 3 4 5 6
6 3 3 3 5 5 -
• s[1, n] = 3  A1..6 = A1..3 A4..6
5 3 3 3 4 -
• s[1, 3] = 1  A1..3 = A1..1 A2..3
4 3 3 3 -
• s[4, 6] = 5  A4..6 = A4..5 A6..6
3 1 2 -
j
2 1 -
1 -
113

i
4. Construct the Optimal Solution (cont.)
PRINT-OPT-PARENS(s, i, j)
1 2 3 4 5 6
if i = j 6 3 3 3 5 5 -
then print “A”i 5 3 3 3 4 -
else print “(” 4 3 3 3 -
j
3 1 2 -
PRINT-OPT-PARENS(s, i, s[i, j])
2 1 -
PRINT-OPT-PARENS(s, s[i, j] + 1, j)
1 -
print “)”
i

114
Eg: A1  A6 ( ( A1 ( A2 A3 ) ) ( ( A4 A5 ) A6 ) )

PRINT-OPT-PARENS(s, i, j)
if i = j
s[1..6, 1..6] 1 2 3 4 5 6
then print “A”i
else print “(” 6 3 3 3 5 5 -
PRINT-OPT-PARENS(s, i, s[i, j]) 5 3 3 3 4 -
PRINT-OPT-PARENS(s, s[i, j] + 1, j) 4 3 3 3 -
print “)” j
3 1 2 -
2 1 -
P-O-P(s, 1, 6) s[1, 6] = 3
i = 1, j = 6 “(“ P-O-P (s, 1, 3) s[1, 3] = 1 1 -
i = 1, j = 3 “(“ P-O-P(s, 1, 1)  “A1” i
P-O-P(s, 2, 3) s[2, 3] = 2
i = 2, j = 3 “(“ P-O-P (s, 2, 2)  “A2”
P-O-P (s, 3, 3)  “A3”
“)” 115
…
“)”
Example for Practice
⚫ The initial set of dimensions are <5, 4, 6, 2, 7>: we are multiplying A1
(5x4) times A2 (4x6) times A3 (6x2) times A4 (2x7). Optimal sequence is
(A1 (A2A3 )) A4.

116
Acknowledgements
⚫ Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C.,
Introduction to algorithms. MIT press, 2009
⚫ Dr. David Kauchak, Pomona College
⚫ Prof. David Plaisted, The University of North Carolina at Chapel
Hill

117