Advanced Computational

Models and Algorithms

Fall 2025

Dr. Nadir Shah (Professor)

Department of Computer Science
Comsats University Islamabad, Wah Campus
Dynamic Programming

Chain Matrix Multiply

 Chain Matrix Multiply

• Suppose we wish to multiply a series of matrices:

A1A2…An

• In what order should the multiplication be done?

• Goal: To achieve the multiplication in minimum number

of scalar multiplications.
 Matrix Multiplication
• A p × q matrix A can be multiplied with a q × r matrix B.
• The result will be a p × r matrix C.

• In particular, for 1≤i≤p and 1≤j≤r:

• There are (p · r) total entries in C, and each takes O(q) to

compute.
• Thus, the total number of multiplications is p · q · r.
 Matrix Multiplication (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]
rows[A]
 Chain Matrix Multiplication
• Consider the case of 3 matrices:
A1​is 5 × 4, A2​is 4 × 6, and A3 is 6 × 2

• The multiplication can be carried out either as:

((A1A2)A3) or (A1(A2A3))

• The cost of the two using formula [Link]+1= rows[Ai]  cols[Ai] 

cols[Ai+1] is:
• ((A1A2)A3) = (5⋅4⋅6)+(5⋅6⋅2) = 180
• (A1(A2A3)) = (4⋅6⋅2)+(5⋅4⋅2) = 88

• There is considerable savings achieved even for this simple example.

• Problem: In what order should we multiply a series of matrices
A1A2…An​?
 Chain Matrix Multiplication Problem
• Given a sequence A1,A2,…,An and dimensions p0,p1,…,pn where:
Ai is of dimension pi−1×pi​
Ai+1 is of dimension pi×pi+1
.

An is of dimension pn-1×pn

• Determine the order of multiplication that minimizes the number of

operations.
• The order of multiplication is influenced by the way of parenthesizations.
• We could write a procedure that tries all possible parenthesizations.
• Unfortunately, the number of ways of parenthesizing an expression is
very large.
 Chain Matrix Multiplication (CMM)

• If there are n items, there are n − 1 ways in which the

outermost pair of parentheses can be placed.

(A1​)(A2​A3​A4​…An​)

or (A1A2)(A3A4…An)

or (A1A2A3)(A4…An)

or (A1A2A3A4…An−1)(An)
 CMM Problem Formulation

• The optimal way of parenthesizations depends on how multiplication

sequence is split.
• For the given multiplication sequence A1…An, let kth matrix determines
the split.
A1…An = A1A2A3…AkAk+1…An =(A1A2…Ak)(Ak+1…An)
• This creates two sub-sequences to be parenthesized.
• Left split with k matrices.
• Right split with n − k matrices.
(A1A2…Ak)(Ak+1…An)

• This is just one of many ways of parenthesizing.

• We could consider all the ways of parenthesizing these two.
 Recurrence to count matrix Parenthesizations

• Since, each sub-sequence is independent, we can further split L and

R subsequences.
• Suppose, if there are L ways of parenthesizing the left sublist and R
ways to parenthesize the right sublist, then the total ways are L ×
R.
• We could represent this using a recurrence relation

• This suggests the following recurrence for P(n), the number of

different ways of parenthesizing n items:
Expanding the Recurrence
Expanding the Recurrence
• In particular, P(n)=C(n−1)

• The dominating term is the exponential 4n; thus P(n) will grow large
very quickly.
•
So this approach is not practical.
 Dynamic Programming - Chain Matrix
Multiplication

• At the highest level of parenthesization, we multiply two matrix chains.

A1..n​=(A1..k​)(Ak+1..n​), 1 ≤ k ≤ n−1

• Each possible value of k represents a different place to split the

product.

• The key question is:

Q. What is the optimum value of k that minimizes the total number of

scalar multiplications?

Q. How to find the number of scalar multiplications done for each

parenthesizations for sequence A1..n​=(A1..k​)(Ak+1..n​)?
 Chain Matrix Multiplication

• Subproblem: Determine the minimum cost of parenthesizing:

• Cost of Parenthesizing: It shows the number of scalar multiplications done for the
parenthesizations. For example:
((A1A2)A3) = (5⋅4⋅6)+(5⋅6⋅2) = 180
(A1(A2A3)) = (4⋅6⋅2)+(5⋅4⋅2) = 88
• An optimal parenthesizing gives the minimum cost for the multiplication.
• (A1(A2A3)) is optimal parenthesizations for the multiplication of A1, A2, A3.

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

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

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

 Parenthesizing Cost

• Assume that the optimal parenthesizations splits the product Ai Ai+1  Aj at k (i  k < j)
pi-1pkpj
Ai Ai+1  Aj = Ai…k Ak+1…j for i  k < j
m[i, k]
m[k+1,
j]

m[i, j] =m[i, k] + m[k+1, j] + p i-1pkpj

min # of multiplications # of
min # of multiplications
to compute Ai…k to compute Ak+1…j multiplications
to compute Ai…kAk…
• We do not know the value of k. j

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

 Parenthesizing Cost
• 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:

m[i, j] = 0 if i = j
m[i, j] = min {m[i, k] + m[k+1, j] + pi-1pkpj} if i < j
ik<j
 Chain Matrix Multiplication
• Step 1: Set all m[i,i]=0 using the base condition, because multiplying one
matrix requires no computation.

• Step 2: Compute the cost for multiplying chains of two matrices at a time
(chain length = 2). These are:
m[1,2],m[2,3],m[3,4],…,m[n−1,n]

• Each chain can be computed as: m[i, j] = min {m[i, k] + m[k+1, j] +

pi-1pkpj}
• Therefore:
m[1,2] = m[1,1]+m[2,2] + p0⋅p1⋅p2

• Step 3: Continue for longer chains — 3 matrices, 4 matrices, and so on —

until m[1,n] is computed.

• Thus, m[1,n] gives the minimum number of scalar multiplications

needed for the entire chain.
Dynamic Programming Implementation Idea

• The recursive formulation has overlapping subproblems i.e. the

same m[i,j] values are recomputed multiple times.

• To avoid redundant computations, we use a bottom-up DP approach:

• We will store solutions to subproblems in a table and build the table
bottom-up, ensuring that each subproblem is solved only once.
• Store all values of m[i,j] in a table.
• Fill the table in increasing order of chain length.

• This bottom-up approach is efficient because:

• The cost of multiplying smaller sub-chains is computed first.
• Each larger subproblem depends only on previously computed
smaller ones.
 Example - Chain Matrix Multiplication

• For the multiplication of 5 matrices A1 to A5 having

with dimensions as given below:

(5×4), (4×6), (6×2), (2×7), (7×3)

• Find the optimal way of multiplying A1.A2.A3.A4.A5.

• In other words, Find the min(m[1,5])

• We can find it using top-down approach using

dynamic programming.
 Dynamic Programming Approach

• Initialization:
• Start by creating a table of 5x5.
• Set m[i,i] = 0 for all i=1,2,…,n. (Why?)

1 2 3 n
1 0

2 0
j
0
3
0

n 0

Pi..Pj = (5, 4, 6, 2, 7,
 Dynamic Programming Approach

• Initialization:
• Set m[i,i] = 0 for all i=1,2,…,5. (A single matrix requires no
multiplication.)

• Compute for chains of length 2 to n: 1 2 3 5

1 0
• For each chain length L=2,3,…,n:
• For each starting index i=1,2,…,n−L+1: 2 0
j
• Compute the ending index j=i+L−1. 3
0
• For all k between i and j−1: 0

5 0
m[i,j]=min(m[i,k]+m[k+1,j]+pi−1​pk​pj​) i
Pi..Pj = (5, 4, 6, 2, 7,
 Dynamic Programming Approach

• Order in which each entry in the table is calculated as:

1 2 3 5
1 0 1 5 8 10

2 0 2 6 9
j
0 3 7
3
0 4

5 0

i
Pi..Pj = (5, 4, 6, 2, 7,
3)
 Dynamic Programming Approach

• Compute for chains of length 2:

m[1,2] = m[1,1]+m[2,2]+p0​⋅p1​⋅p2​
= 0+0+5×4×6 = 120
m[2,3] = m[2,2]+m[3,3]+p1​⋅p2​⋅p3​ m[i,j]=min(m[i,k]+m[k+1,j]+pi−1​pk​pj​
) for ik<j
= 0+0+4×6×2 = 48​ 1 2 3 5
1 0

2 0
j
0
• m[1,2] → cost of multiplying matrices A1 and A2​.3
• m[2,3] → cost of multiplying matrices A2 and A3.​ 0

5 0

i
Pi..Pj = (5, 4, 6, 2, 7,
 Dynamic Programming Approach

• Compute for chains of length 2:

m[1,2] = m[1,1]+m[2,2]+p0​⋅p1​⋅p2​
= 0+0+5×4×6 = 120
m[2,3] = m[2,2]+m[3,3]+p1​⋅p2​⋅p3​ m[i,j]=min(m[i,k]+m[k+1,j]+pi−1​
pk​pj​) for ik<j
1 2 3 5
= 0+0+4×6×2 = 48​
1 0 12
0
2 0
j
• m[1,2] → cost of multiplying matrices A1 and A2​.3 0

• m[2,3] → cost of multiplying matrices A2 and A3.​ 0

5 0
i
Pi..Pj = (5, 4, 6, 2, 7,
 Dynamic Programming Approach

• Compute for chains of length 2:

m[1,2] = m[1,1]+m[2,2]+p0​⋅p1​⋅p2​
= 0+0+5×4×6 = 120
m[2,3] = m[2,2]+m[3,3]+p1​⋅p2​⋅p3​ m[i,j]=min(m[i,k]+m[k+1,j]+pi−1​
pk​pj​) for ik<j
1 2 3 5
= 0+0+4×6×2 = 48​
1 0 12
0
2 0 48
j
• m[1,2] → cost of multiplying matrices A1 and A2​.3 0

• m[2,3] → cost of multiplying matrices A2 and A3.​ 0

5 0
i
Pi..Pj = (5, 4, 6, 2, 7,
 Dynamic Programming Approach

• Compute for chains of length 2:

m[3,4] = m[3,3]+m[4,4] + p2​⋅p3​⋅p4
= 0 + 0 + 6×2×7 = 84
m[4,5]​​=m[4,4]+m[5,5] + p3​⋅p4​⋅p5​ m[i,j]=min(m[i,k]+m[k+1,j]+pi−1​
pk​pj​) for ik<j
1 2 3 5
=0+0+2×7×3 = 42​ 0 12
1
0

• m[3,4] → cost of multiplying matrices A3 and A4​.2 0 48

j
• m[4,5] → cost of multiplying matrices A4 and A5.​3 0 84

0 42
5 0
i
Pi..Pj = (5, 4, 6, 2, 7,
 Dynamic Programming Approach

• Compute for chains of length 3:

• For example, m[1,3] represents the minimum cost to multiply A1,A2,A3.

m[1,3] ​= m[1,1]+m[2,3]+p0​⋅p1​⋅p3 m[i,j]=min(m[i,k]+m[k+1,j]+pi−1​

pk​pj​) for ik<j
1 2 3 5
​ =0+48+5×4×2 0 12 88
1
0
=88
2 0 48
m[1,3] = m[1,2]+m[3,3] + p0​⋅p2​⋅p3 j
3 0 84
​=120+ 0+5×6×2
0 42
=180​
5 0
i
Minimum m[1,3] = 88 at k=1 Pi..Pj = (5, 4, 6, 2, 7,
 Dynamic Programming Approach

• Compute for chains of length 3:

• For example, m[1,3] represents the minimum cost to multiply
A1,A2,A3.

m[2,4] ​= min (104, 252)

1 2 3 5
= 104 m[i,j]=min(m[i,k]+m[k+1,j]+p
0 12 88 i−1​
p k​
1
pj​) for ik<j 0
2 0 48 10
​ 4 j
3
0 84

0 42
5
0
i
Pi..Pj = (5, 4, 6, 2, 7,
 Dynamic Programming Approach

• Compute for chains of length 3:

• For example, m[1,3] represents the minimum cost to multiply
A1,A2,A3.

m[2,4] ​= min (104, 252)

1 2 3 5
= 104 m[i,j]=min(m[i,k]+m[k+1,j]+p
0 12 88 i−1​
p k​
1
pj​) for ik<j 0
2 0 48 10
​ 4 j
3
m[3,5] = min (210, 78) 0 84 78

​= 78 0 42
5
0
i
Pi..Pj = (5, 4, 6, 2, 7,
 Dynamic Programming Approach

• Compute for chains of length 4:

• For example, m[1,4] represents the minimum cost to multiply A1,A2,A3,A4.

m[1,4] ​= m[1,1]+m[2,4]+p0​⋅p1​⋅p4 (k = 1)

= 0 + 104 + 5x4x7 1 2 3
m[i,j]=min(m[i,k]+m[k+1,j]+p 5 ​)
i−1​
pk​p j
for ik<j 1 0 12 88
0
​ = 244 2 0 48 10
4 j
m[1,4] = m[1,2]+m[3,4]+p0​⋅p2​⋅p4 (k = 2) 3
0 84 78
​= 120 + 84 + 5x6x7
0 42
= 120 + 84 + 210 5
0
= 414 i
Pi..Pj = (5, 4, 6, 2, 7,
 Dynamic Programming Approach

• Compute for chains of length 4:

• For example, m[1,4] represents the minimum cost to multiply A1,A2,A3,A4.

m[1,4] ​= m[1,3]+m[4,4]+p0​⋅p3​⋅p4 (k = 3)

= 88 + 0 + 5x2x7 m[i,j]=min(m[i,k]+m[k+1,j]+p i−1​pk​pj​) for ik<j

1 2 3 5
​ = 88 + 70 0 12 88 15
1
0 8
= 158
2 0 48 10
4 j
3
min (m[1,4]) = min(244, 414, 158) 0 84 78

​= 158 at k = 3 0 42
5
0
i
Pi..Pj = (5, 4, 6, 2, 7,
 Dynamic Programming Approach

• Compute for chains of length 4:

• For example, m[2,5] represents the minimum cost to multiply A2,A3,A4,A5.

m[2,5] ​= m[2,2]+m[3,5]+p1​⋅p2​⋅p5 (k = 2)
= 0 + 78 + 4x6x3 m[i,j]=min(m[i,k]+m[k+1,j]+pi−1​pk​pj​) for ik<j
1 2 3 5
​ = 78 + 72 0 12 88 15
1
= 150 0 8
2 0 48 10 11
4 4 j
m[2,5] ​= m[2,3]+m[4,5]+p1​⋅p3​⋅p5 (k = 3) 3
0 84 78
= 48 + 42 + 4x2x3 0 42
= 114 (minimum) 5
0
i
Pi..Pj = (5, 4, 6, 2, 7, 3)
 Dynamic Programming Approach

• Compute for chains of length 5:

• For example, m[1,5] represents the minimum cost to multiply A1, A2,A3,A4,A5.

m[1,5] ​= m[1,1]+m[2,5]+p0​⋅p1​⋅p5 (k = 1)
= 0 + 114 + 5x4x3 m[i,j]=min(m[i,k]+m[k+1,j]+pi−1​pk​pj​) for
ik<j 1 2 3 5
0 12 88 15
​ = 114 + 60 1
0 8
= 174 2 0 48 10 11
4 4 j
3
0 84 78
m[1,5] ​= m[1,2]+m[3,5]+p0​⋅p2​⋅p5 (k = 2)
0 42
= 120 + 78 + 5x6x3 5
= 288 (minimum) 0
i
Pi..Pj = (5, 4, 6, 2, 7, 3)
 Dynamic Programming Approach

• Compute for chains of length 5:

• For example, m[1,5] represents the minimum cost to multiply A1, A2,A3,A4,A5.

m[1,5] ​= m[1,3]+m[4,5]+p0​⋅p3​⋅p5 (k = 3)

= 88 + 42 + 5x2x3 m[i,j]=min(m[i,k]+m[k+1,j]+p i−1​pk​pj​) for ik<j

1 2 3 5
​ = 130 + 30 0 12 88 15 16
1
= 160 (minimum) at k = 3 0 8 0
2 0 48 10 11
4 4 j
m[1,5] ​= m[1,4]+m[5,5]+p0​⋅p4​⋅p5 (k = 4) 3
0 84 78

0 42
= 158 + 0 + 5x7x3 5
= 263 0
i
Pi..Pj = (5, 4, 6, 2, 7, 3)
 Dynamic Programming Approach

• Split Values Table:

• In each cell of Split value table, we store the k value for which we
computed minimum value for that cell.

1 2 3 5
1 0 1 1 3 3

2 0 2 3 3
j
0 3 3
3
0 4

5 0

Pi..Pj = (5, 4, 6, 2, 7, 3)
 Dynamic Programming Approach

• Optimal Order to multiplication of A1A2A3A4A5

• The values in the table give the optimal way of parenthesizations,
such that:
• The minimum value in the table is m[4, 5] = 42.
• It means, we first multiply A4.A5.
• The parenthesization so far: A1A2A3(A4A5)
1 2 3 5
1 0 12 88 15 16
0 8 0
2 0 48 10 11
4 4 j
3
0 84 78

0 42
5
0
i
 Dynamic Programming Approach

• Optimal Order to multiplication of A1A2A3A4A5

• The next minimum value is m[2,3] = 48.

• So, we multiply A2 with A3.

• The parenthesization so far: A1(A2A3)(A4A5)

1 2 3 5
1 0 12 88 15 16
0 8 0
2 0 48 10 11
4 4 j
3
0 84 78

0 42
5
0
i
 Dynamic Programming Approach

• Optimal Order to multiplication of A1A2A3A4A5

• The parenthesization so far: A1(A2A3)(A4A5)

• We have two options, either compute A1(A2A3) or (A2A3)(A4A5) first.

• M[1,3] = 88

• M[2,5] = 114 1 2 3 5
• We select the minimum which is m[1,3] = 88. 1 0 12 88 15 16
0 8 0
2 0 48 10 11
4 4 j
3
0 84 78

0 42
5
0
i
 Dynamic Programming Approach

• Optimal Order to multiplication of A1A2A3A4A5

• The parenthesization so far: A1(A2A3)(A4A5)

• We have two options, either compute A1(A2A3) or (A2A3)(A4A5) first.

• M[1,3] = 88

• M[2,5] = 114 1 2 3 5
• We select the minimum which is m[1,3] = 88. 1 0 12 88 15 16
0 8 0
• Thus, the updated parenthesization 2 0 48 10 11
4 4 j
3
0 84 78
(A1(A2A3))(A4A5)
0 42
5
0
i
 Dynamic Programming Approach

• Optimal Order to multiplication of A1A2A3A4A5

• The parenthesization so far: A1(A2A3)(A4A5)

• We have two options, either compute A1(A2A3) or (A2A3)(A4A5) first.

• M[1,3] = 88

• M[2,5] = 114

• We select the minimum which is m[1,3] = 88.

• Thus, the updated parenthesization

(A1(A2A3))(A4A5)
Matrix-Chain-Order(p)

O(N3)

42