Dynamic Programming - I
Matrix Chain Multiplication
Click to add text
Instructor: Ashok Singh Sairam
Lecture Plan
• Introduction to DP
How it is different from divide and conquer
• Understand the 4 steps of DP using an example
matrix chain multiplication
MA512: Data Structures and Algorithms
2
Dynamic Programming
• An algorithm design technique (like divide and
conquer)
• Divide and conquer
Partition the problem into independent subproblems
Solve the subproblems recursively
Combine the solutions to solve the original problem
MA512: Data Structures and Algorithms
3
Dynamic Programming
• Applicable when subproblems are not independent
Subproblems share subsubproblems
E.g.: Fibonacci Series
A divide and conquer approach would repeatedly solve the common
subproblems
Dynamic programming solves every subproblem just once and
stores the answer in a table
MA512: Data Structures and Algorithms
4
Dynamic Programming
• Used for optimization problems
Such problems may have many solutions (eg. shortest
path)
Each solution has a value, want to find a solution with
the optimal value (minimum or maximum)
We call such a solution as an optimal solution
MA512: Data Structures and Algorithms
5
Dynamic Programming Algorithm
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 computed
information (not always necessary)
MA512: Data Structures and Algorithms
6
Matrix-Chain Multiplication
Problem: given a sequence A1, A2, …, An, compute
the product:
A1 A2 An
• Matrix compatibility:
C=AB C=A1 A2 Ai Ai+1 An
colA = rowB coli = rowi+1
rowC = rowA rowC = rowA1
colC = colB colC = colAn
MA512: Data Structures and Algorithms
7
Clickto add text
MATRIX-MULTIPLY(A, B)
k cols[B]
j cols[B] j
i * k =i
rows[A] A C
rows[A]
MA512: Data Structures and Algorithms
8
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
MA512: Data Structures and Algorithms
9
Ex: Matrix Multiplication
A1 A 2 A3
• 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!!
MA512: Data Structures and Algorithms
10
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 Click… Atoi add
. A text … A
i+1 n
p0 x p1 p1 x p2 pi-1 x pi pi x pi+1 pn-1 x pn
MA512: Data Structures and Algorithms
11
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)
MA512: Data Structures and Algorithms
12
Apply dynamic programming
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 computed
information
MA512: Data Structures and Algorithms
13
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
ik<j
Ai…j = Ai Ai+1 Aj
= Ai Ai+1 Ak Ak+1 Aj
= Ai…k Ak+1…j
MA512: Data Structures and Algorithms
14
Optimal Substructure
Ai…j = Ai…k Ak+1…j
• The parenthesization of the “prefix” Ai…k must be an
optimal parenthesization
• 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
MA512: Data Structures and Algorithms
15
Apply dynamic programming
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 computed
information
MA512: Data Structures and Algorithms
16
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
MA512: Data Structures and Algorithms
17
2. A Recursive Solution
• Consider the subproblem of parenthesizing
Ai…j = Ai Ai+1 Aj for 1 i j n
pi-1pkpj
m[i, k]= Ai…k Ak+1…j m[k+1,j] for i k < 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
MA512: Data Structures and Algorithms
18
2. A Recursive Solution – contd.
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
ik<j
MA512: Data Structures and Algorithms
19
Apply dynamic programming
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 computed
information
MA512: Data Structures and Algorithms
20
3. Computing the Optimal Costs
• Requires solving the recursion, will take exponential time
0 if i = j
𝑚 𝑖, 𝑗 = ൝
min m[i, k] + m[k+1, j] + pi−1pkpj} if i < j
• How many subproblems? (n2)
Parenthesize Ai…j , for 1 i j n
One problem for each choice of i and j
• A recursive problem may encounter the same subproblem
multiple times in the recursion tree
Overlapping subproblems, the second hallmark of dynamic
programming
MA512: Data Structures and Algorithms
21
3. Computing the Optimal Costs
• Instead of computing the solution to the recurrence, we
follow the third step of DP
Compute optimal cost by using a
tabular bottom-up approach
• 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
MA512: Data Structures and Algorithms
22
3. Computing the Optimal Costs
• 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
i
MA512: Data Structures and Algorithms
23
Example: Bottom-up Approach
• m[i,j] = min {m[i, k] + m[k+1, j] + pi-1pkpj}
m[2, 2] + m[3, 5] + p1p2p5 k=2
m[2, 5] = min m[2, 3] + m[4, 5] + p1p3p5 k=3
m[2, 4] + m[5, 5] + p1p4p5 k=4
1 2 3 4 5 6
6
Values m[i, j] depend only on values
5
that have been previously computed
4 Overlapping subproblems
3
j
2
1
i
MA512: Data Structures and Algorithms
24
Another example 1 2 3
Compute A1 A2 A3 3 2 7500 225000 0
• A1: 10 x 100 (p0 x p1)
1
• A2: 100 x 5 (p1 x p2) 2 5000 0
• A3: 5 x 50 (p2 x p3)
0
1
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)
MA512: Data Structures and Algorithms
25
Algorithm:Matrix-Chain-Order(p)
O(N3)
MA512: Data Structures and Algorithms
26
Apply dynamic programming
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 computed
information
MA512: Data Structures and Algorithms
27
4. Construct the Optimal Solution
• Algorithm Matrix-Chain-Order(p) determines the optimal
#scalar multiplications, it does NOT show how to multiple
the matrices
• Not difficult to construct the optimal solution
Use a similar matrix s[1..n,1..n]
Each entry s[i,j] records the value of k
s[i, j] = a value of k such that an
optimal parenthesization of Ai..j splits
the product between Ak and Ak+1
MA512: Data Structures and Algorithms
28
Example: Construct 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 -
i
MA512: Data Structures and Algorithms
29
Algorithm: Print-Optimal-Parens()
MA512: Data Structures and Algorithms
30
1 2 3 4 5 6
Example: A1 A6 6 3 3 3 5 5 -
5 3 3 3 4 -
4 3 3 3 -
j
s[1..6, 1..6] 3 1 2 -
2 1 -
P-O-P(s, 1, 6) s[1, 6] = 3 1 -
i = 1, j = 6 “(“ P-O-P (s, 1, 3) s[1, 3] = 1 i
i = 1, j = 3 “(“ P-O-P(s, 1, 1) “A1”
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”
“)”
“)”
MA512: Data Structures and Algorithms
31
Exercise
MA512: Data Structures and Algorithms
32
Acknowledgement
• Dr George Bebis, Foundation Professor, Dept of
Computer Science and Engineering, University of
Nevada Reno
MA512: Data Structures and Algorithms
33
