Design and Analysis of

Algorithms
Study material on

Matrix Chain Multiplication

Dilip Kumar Maity

Computer Science and Engineering
Academy of Technology
dilip.maity@aot.edu.in
June 12, 2021
Matrix Chain Multiplication
The matrix chain multiplication problem can be stated as follows: 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 scalar multiplications.
Note that in the matrix-chain multiplication problem, we are not actually multiplying matrices.
Our goal is only to determine an order for multiplying matrices that has the lowest cost.

Reminders of matrix multiplication:

• Direct matrix multiplication:

Let Ap×q and Bq×r are two matrices of dimensions p × q and q × r respectively. If C be
the product of A and B then the dimension of C must be p × r. And the resultant matrix
C is evaluated as:

q
X
C[i, j] = A[i, k] × B[k, j]
k=1
where 1 ≤ i ≤ p and 1 ≤ j ≤ r

• Complexity of matrix multiplication:

Note that C has p × r entries and each entry takes Θ(q) time to compute so the total
procedure takes Θ(pqr).
• The commutative property of multiplication does not hold!

If AB is dened, BA may not be dened and quite possible that AB 6= BA

• Parenthenization does not change result:

We have many options to multiply a chain of matrices because matrix multiplication is asso-
ciative. In other words, no matter how we parenthesize the product, the result will be the
same. For example, if we had four matrices A, B , C , and D, we would have:

P rod((A)(BCD)) = P rod((AB)(CD)) = P rod((ABC)(D))

• Multiplication is recursively define:

Product of n number of matrices can be evaluated recursively as:
P rod(A1 A2 ...An−1 An ) = P rod(A1 (A2 (A3 ...(An−1 An )...)))

2
Direct matrix multiplication of ABC
Given matrix A of dimension p × q , B of dimension q × r and C of dimension r × s, then ABC
can be computed in two ways A(BC) and (AB)C .
The number of scaler/arithmetic multiplications needed are:
cost[A(BC)] = qrs + pqs
cost[(AB)C] = qrs + pqs

If p = 3, q = 4, r = 5 and s = 6 then,

cost[A(BC)] = qrs + pqs = 120 + 72 = 192

cost[(AB)C] = pqr + prs = 60 + 90 = 150

There is a big dierence! the order in which we parenthesize the product aects the number of
simple arithmetic operations needed to compute the product, or the eciency.

Note that the multiplication sequence (parenthesization) is important!!!

3
Developing a Dynamic Programming Approach:

• Step 1: Characterize the structure of an optimal solution.:

The rst step of the dynamic programming paradigm is to characterize the structure of
an optimal solution. For the matrix chain problem, like other dynamic programming problems,
involves determining the optimal structure (in this case, a parenthesization).
We would like to break the problem into sub − problems, whose solutions can be combined
to obtain a solution to the global problem.
In parenthesizing the expression, we can consider the highest level of parenthesization. At
this level we are simply multiplying two matrices together. That is, for any k, 1 ≤ k ≤ n−1,

A1 A2 A3 ...An = (A1 A2 ...Ak )(Ak+1 Ak+2 ...An )

Example:

In a chain of matrices of size n, we can place the rst set of parenthesis in n − 1 ways. For
example, if the given chain is of 4 matrices. let the chain be A1 A2 A3 A4 , then there are 3
ways to place rst set of parenthesis outer side:

(A1 )(A2 A3 A4 ) if k = 1


A1 A2 A3 A4 = (A1 A2 )(A3 A4 ) if k = 2
(A1 A2 A3 )(A4 ) if k = 3



• Step 2: Recursively define the value of an optimal solution.:

Next, we dene the cost of an optimal solution recursively in terms of the optimal solutions
to sub-problems. For the matrix-chain multiplication problem, we pick as our sub-problems
the problems of determining the minimum cost of a parenthesization of Ai Ai+1 ...Aj for
1 ≤ i ≤ j ≤ n.
Let c[i, j] be the minimum number of scalar multiplications needed to compute the ma-
trix Ai Ai+1 ...Aj ; for the whole problem, the cost of a cheapest way to compute Ai Ai+1 ...Aj
would thus be c[1, n].

 We can dene c[i, j] recursively as follows. If i = j , the problem is trivial; the chain
consists of just one matrix Ai , so that no scalar multiplications are necessary to
compute the product. Thus, c[i, i] = 0 for i = 1, 2, ..., n.

4
  To compute c[i, j] when i < j , we take advantage of the structure of an optimal
solution from step 1. Let us assume that the optimal parenthesization splits the product
Ai Ai+1 ...Aj between Ak and Ak+1 , where i ≤ k < j . Then, c[i, j] is equal to the
minimum cost for computing the sub products Ai Ai+1 ...Ak and Ak+1 ...Aj , plus
the cost of multiplying these two matrices together.
 Recalling that each matrix Ai is pi−1 × pi , we see that computing the matrix product
Ai Ai+1 ...Ak Ak+1 ...Aj takes pi−1 × pk × pj scalar multiplications. Thus, we
obtain

c[i, j] = c[i, k] + c[k + 1, j] + pi−1 × pk × pj

Example 1:

For example let there are for matrices A1 , A2 , A3 , A4 and A5 and dimension of A1 , A2 ,
A3 , A4 and A5 are 2 × 3, 3 × 4, 4 × 5, 5 × 3 and 3 × 6 respectively.
Array dimmentions : size of Ai =⇒ pi−1 × pi :

i 0 1 2 3 4 5
pi 2 3 4 5 3 6

Let a sub problem A2 A3 A4 A5 i.e. i = 2, j = 5. If k = 3 then the number of scalar

multiplication for the sub chain will be,

 Two sub problems are A2 A3 and A4 A5 .

 Cost of the sub problems A2 A3 is c[2, 3].
 Cost of the sub problems A4 A5 is c[4, 5].
 The dimension of product A2 A3 will be 3 × 5.
 The dimension of product A4 A5 will be 5 × 6.
 The cost of (A2 A3 ) × (A4 A5 ) will be 3 × 5 × 6.
 The total cost will be c[2, 5] = c[2, 3] + c[4, 5] + 3 × 5 × 6.

Now from the above equation we get,

c[2, 5] = c[2, 3] + c[3 + 1, 5] + p2−1 × p3 × p5

= c[2, 3] + c[4, 5] + 3 × 5 × 6

How do we decide where to split the chain? (What is k?)

5
 This recursive equation assumes that we know the value of k, which we do not. There are
only j − i possible values for k, however, namely k = i, i + 1, ..., j − 1. Since the optimal
parenthesization must use one of these values for k, we need only check them all to nd
the best. Thus, our recursive denition for the minimum cost of parenthesizing the product
Ai Ai+1 ...Aj becomes

if i = j
(
0
c[i, j] =
mini≤k<j c[i, k] + c[k, j] + pi−1 pk pj if i < j

Example 2:

From the problem given in Example 1 and applying the above recurrence we get:

c[2, 2] + c[3, 5] + p1 p2 p5 if

 k=2
c[2, 5] = min c[2, 3] + c[4, 5] + p1 p3 p5 if k=3
c[2, 4] + c[5, 5] + p1 p4 p5 if

k=4


if k = 2

c[2, 2] + c[3, 5] + 3 × 4 × 6

= min c[2, 3] + c[4, 5] + 3 × 5 × 6 if k = 3
if k = 4

c[2, 4] + c[5, 5] + 3 × 3 × 6


• Step 3: Compute the value of an optimal solution in a bottom-up

fashion.

At this point, it is a simple matter to write a recursive algorithm based on recurrence to

compute the minimum cost c[1, n] for multiplying A1 A2 ...An . Instead of computing the
solution to recurrence recursively, we perform the third step of the dynamic-programming
paradigm and compute the optimal cost by using a tabular, bottom − up approach.

 Cost matrix (M [1..n, 1..n]) :

The dynamic programming paradigm is to dene the value of an optimal solution recursively
in terms of the optimal solutions to sub-problems. To help us keep track of solutions to
sub-problems, we will use a table, and build the table in a bottom − up manner. For
1 ≤ i ≤ n and 1 ≤ j ≤ n, let M [i, j] be the minimum number of scalar multiplications
needed to compute the Ai Ai+1 ...Aj .

6
 M[i, j] 1 2 3 4

(A1 )(A2 A3 A4 )
( 
(A1 )(A2 A3 )
1 (A1) (A1A2) min min (A1 A2 )(A3 A4 )
(A1 A2 )(A3 ) 
(A A A )(A4 )

( 1 2 3
(A2 )(A3 A4 )
2 (A2) (A2A3) min
(A2 A3 )(A4 )
3 (A3) (A3A4)
4 (A4)
Compute the value of an optimal solution in a bottom-up fashion. That is, we calculate
in the order given below

M [1, 1], M [2, 2], M [3, 3], M [4, 4]

M [1, 2], M [2, 3], M [3, 4]
M [1, 3], M [2, 4]
M [1, 4]

Here, M [i, i] indicates the sub-problems of length one. The cost is zero when multi-
plying one matrix i.e. M [i, i]ni=1 = 0.

 T able S[1..n, 1..n] :

To keep track of optimal sub-solutions, we store the value of k in a table s[i, j]. Recall,
k is the place at which we split the product Ai Ai+1 ...Aj to get an optimal parenthesiza-
tion. That is, S[i, j] = k such that m[i, j] = m[i, k] + m[k + 1, j] + pi−1 × pk × pj .

7
Algorithm:

Algorithm 1: Matrix-Chain-Order(p)
// Matrix A[i] has dimension p[i − 1] × p[i] for i = 1..n
// Let M [i, j] is equal to Minimum number of scalar multiplications (i.e., cost)
m[i,j] needed to compute the matrix A[i] × A[i + 1] × ... × A[j] = A[i..j].
1 n := length(p) − 1; // length(p) = n + 1
// The cost is zero when multiplying one matrix
2 for i := 1 to n do M [i, i] := 0;
// Subsequence lengths
3 for len := 2 to n do
4 for i := 1 to n − len + 1 do
5 j := i + len − 1;
6 M [i, j] := ∞;
7 for k := i to j − 1 do
8 cost := M [i, k] + M [k + 1, j] + p[i − 1] × p[k] × p[j];
9 if cost < M [i, j] then
10 M [i, j] := cost;
11 S[i, j] := k; // Index of the subsequence split that achieved minimal cost
12 end
13 end
14 end
15 end

• The algorithm rst computes m[i, i] = 0 for i = 1, 2, ..., n (the minimum costs for chains
of length 1) in lines 23.
• It then uses recurrence to compute m[i, i + 1] for i = 1, 2, ..., n − 1 (the minimum costs
for chains of length l = 2) during the rst execution of the loop in lines 412.
• The second time through the loop, it computes m[i, i + 2] for i = 1, 2, ..., n − 2 (the
minimum costs for chains of length l = 3), and so forth.
• At each step, the m[i, j] cost computed in lines 912 depends only on table entries m[i, k]
and m[k + 1, j] already computed.
• Time and space complexity: A simple inspection of the nested loop structure of MATRIX-
CHAIN-ORDER yields a running time of O(n3 ) for the algorithm. The loops are nested
three deep, and each loop index (l, i, and k) takes on at most n − 1 values. The algorithm
requires Θ(n2 ) space to store the M and S tables.

8
Example Showing Tables and Calculations:

• Array dimensions:
A1 : 2×3 Array dimmentions : size of Ai =⇒ pi−1 × pi :
A2 : 3×5
A3 : 5×2
A4 : 2×4 i 0 1 2 3 4 5
A5 : 4×3
pi 2 3 5 2 4 3

• Find the cost when multiplying one matrix (l = 1):

M[i, j] 1 2 3 4 5
1. The cost is zero when
multiplying one matrix. 1 0

2. Multiplying number of 2 0
matrices i.e. chain length = |i − j|+1. 3 0
3. Fill the diagonal of M table. 4 0
5 0

• Find the cost when multiplying two matrices (l = 2):

M [1, 2] = (A1 × A2 ) = p0 × p1 × p2 = 30
M [2, 3] = (A2 × A3 ) = p1 × p2 × p3 = 30
M [3, 4] = (A3 × A4 ) = p2 × p3 × p4 = 40
M [4, 5] = (A4 × A5 ) = p3 × p4 × p5 = 24

M[i, j] 1 2 3 4 5 S[i, j] 1 2 3 4 5
1 0 30 1 1
2 0 30 2 2
3 0 40 3 3
4 0 24 4 4
5 0 5

9
• Find the cost when multiplying three matrices (l = 3):

(
(A1 )(A2 A3 )
M [1, 3] = min
(A1 A2 )(A3 )
(
M [1, 1] + M [2, 3] + p0 × p1 × p3
= min
M [1, 2] + M [3, 3] + p0 × p2 × p3
(
0 + 30 + 2 × 3 × 2 = 42 M[i, j] 1 2 3 4 5
= min
30 + 0 + 2 × 5 × 2 = 50 1 0 30 42
= 42
2 0 30 54
( 3 0 40 54
(A2 )(A3 A4 )
M [2, 4] = min
(A2 A3 )(A4 )
4 0 24
(
M [2, 2] + M [3, 4] + p1 × p2 × p4 5 0
= min
M [2, 3] + M [4, 4] + p1 × p3 × p4
(
0 + 40 + 3 × 5 × 4 = 100 S[i, j] 1 2 3 4 5
= min
30 + 0 + 3 × 2 × 4 = 54
1 1 1
= 54
2 2 3
( 3 3 3
(A3 )(A4 A5 )
M [3, 5] = min
(A3 A4 )(A5 ) 4 4
5
(
M [3, 3] + M [4, 5] + p2 × p3 × p5
= min
M [3, 4] + M [5, 5] + p2 × p4 × p5
(
0 + 24 + 5 × 2 × 3 = 54
= min
40 + 0 + 5 × 4 × 3 = 100
= 54

10
• Find the cost when multiplying four matrices (l = 4):


(A1 )(A2 A3 A4 )

M [1, 4] = min (A1 A2 )(A3 A4 )

(A1 A2 A3 )(A4 )


M[i, j] 1 2 3 4 5

M [1, 1] + M [2, 4] + p0 × p1 × p4

= min M [1, 2] + M [3, 4] + p0 × p2 × p4

1 0 30 42 58
M [1, 3] + M [4, 4] + p0 × p3 × p4

 2 0 30 54 72
0 + 54 + 2 × 3 × 4 = 78

3 0 40 54
= min 30 + 40 + 2 × 5 × 4 = 110


42 + 0 + 2 × 2 × 4 = 58
4 0 24
= 58 5 0


(A2 )(A3 A4 A5 )
 S[i, j] 1 2 3 4 5
M [2, 5] = min (A2 A3 )(A4 A5 )
 1 1 1 3
(A2 A3 A4 )(A5 )

 2 2 3 3
M [2, 2] + M [3, 5] + p1 × p2 × p5

= min M [2, 3] + M [4, 5] + p1 × p3 × p5 3 3 3

M [2, 4] + M [5, 5] + p1 × p4 × p5 4 4


0 + 54 + 3 × 5 × 3 = 99
 5
= min 30 + 24 + 3 × 2 × 3 = 72

54 + 0 + 3 × 4 × 3 = 90


= 72

11
• Find the cost when multiplying five matrices (l = 5):

M[i, j] 1 2 3 4 5
1 0 30 42 58 78



(A1 )(A2 A3 A4 A5 )
2 0 30 54 72

(A A )(A A A )
1 2 3 4 5
M [1, 5] = min
(A A A )(A 4 A5 )
1 2 3
3 0 40 54




(A A A A )(A )
1 2 3 4 5
 4 0 24
 M [1, 1] + M [2, 5] + p0 × p1 × p5
5 0



M [1, 2] + M [3, 5] + p × p
0 2 × p5
= min


 M [1, 3] + M [4, 5] + p0 × p3 × p5

M [1, 4] + M [5, 5] + p × p
0 4 × p5
 S[i, j] 1 2 3 4 5
0 + 72 + 2 × 3 × 3 = 90
1 1 1 3 3




30 + 54 + 2 × 5 × 3 = 114
= min 2 2 3 3
42 + 24 + 2 × 2 × 3 = 78


3 3 3

58 + 0 + 2 × 4 × 3 = 82

= 78 4 4
5

• Step 4: Constructing an optimal solution:

Although M atrix − Chain − Order determines the optimal number of scalar multiplica-
tions needed to compute a matrix-chain product, it does not directly show how to multiply the
matrices. It is not dicult to construct an optimal solution from the computed information
stored in the table S[1..n, 1..n]. Each entry S[i, j] records the value of k such that the
optimal parenthesization of Ai Ai+1 ...Aj splits the product between Ak and Ak+1 .
The following recursive procedure prints an optimal parenthesization of AiAi+1 ...Aj , given
the S table computed by Matrix-Chain-Order and the indices i and j . The initial call
Print-Optimal-Parens(S, 1, n) prints an optimal parenthesization of A1 A2 ...An .

Algorithm 2: Print-Optimal-Parens(S, i, j)
1 if i = j then print "A" i;
2 else
3 print "(";
4 Print-Optimal-Parens(S, i, S[i, j]);
5 Print-Optimal-Parens(S, S[i, j] + 1, j);
6 print ")";
7 end

12
 Example:

References:

1. Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest Cliord Stein, Introduction to

Algorithms. To download pdf click here.

2. M IT Lecture here

13
MCQ on Matrix Chain Multiplication
1. Which of the following methods can be used to solve the matrix chain multiplication problem?
a) Dynamic programming
b) Brute force
c) Recursion
d) Dynamic Programming, Brute force, Recursion
Answer: d
Explanation: Dynamic Programming, Brute force, Recursion methods can be used to
solve the matrix chain multiplication problem.
2. Which of the following is the recurrence relation for the matrix chain multiplication problem
where mat[i-1] * mat[i] gives the dimension of the ith matrix?
a)
dp[i, j] = 1 if i = j
dp[i, j] = min{dp[i, k] + dp[k + 1, j]}

b)
dp[i, j] = 0 if i = j
dp[i, j] = min{dp[i, k] + dp[k + 1, j]}

c)
dp[i, j] = 1 if i = j
dp[i, j] = min{dp[i, k] + dp[k + 1, j]} + mat[i − 1] ∗ mat[k] ∗ mat[j].

d)
dp[i, j] = 0 if i = j
dp[i, j] = min{dp[i, k] + dp[k + 1, j]} + mat[i − 1] ∗ mat[k] ∗ mat[j].

Answer: d
Explanation: The recurrence relation is given by:
dp[i, j] = 0 if i = j
dp[i, j] = min{dp[i, k] + dp[k + 1, j]} + mat[i − 1] ∗ mat[k] ∗ mat[j].

14
 3. Consider the two matrices P and Q which are 10 × 20 and 20 × 30 matrices respectively.
What is the number of multiplications required to multiply the two matrices?
a) 10*20 b) 20*30 c) 10*30 d) 10*20*30
Answer: d
Explanation: The number of multiplications required is 10*20*30.
4. Consider the matrices P, Q and R which are 10×20, 20×30 and 30×40 matrices respectively.
What is the minimum number of multiplications required to multiply the three matrices?
a) 18000 b) 12000 c) 24000 d) 32000
Answer: a
Explanation: The minimum number of multiplications are 18000. This is the case when
the matrices are parenthesized as (P × Q) × R.
5. Consider the matrices P, Q, R and S which are 20 × 15, 15 × 30, 30 × 5 and 5 × 40 matrices
respectively. What is the minimum number of multiplications required to multiply the four
matrices?
a) 6050 b) 7500 c) 7750 d) 12000
Answer: c
Explanation: The minimum number of multiplications required is 7750.
6. Consider the brute force implementation in which we nd all the possible ways of multiplying
the given set of n matrices. What is the time complexity of this implementation?
a) O(n! ) b) O(n3 ) c) O(n2 ) d) Exponential
Answer: d
Explanation: The time complexity of nding all the possible ways of multiplying a set
of n matrices is given by (n − 1)th Catalan number which is exponential.

15
 7. Consider the following dynamic programming implementation of the matrix chain problem:
1 #include<stdio.h>
2 #include<limits.h>
3 int mat_chain_multiplication(int *mat, int n){
4 int arr[n][n];
5 int i,k,row,col,len;
6 for(i=1;i<n;i++)
7 arr[i][i] = 0;
8 for(len = 2; len < n; len++){
9 for(row = 1; row <= n - len + 1; row++){
10 col = row + len - 1;
11 arr[row][col] = INT_MAX;
12 for(k = row; k <= col - 1; k++){
13 int tmp = ________________________;
14 if(tmp < arr[row][col])
15 arr[row][col] = tmp;
16 }
17 }
18 }
19 return arr[1][n - 1];
20 }
21 int main(){
22 int mat[6] = {20,5,30,10,40};
23 int ans = mat_chain_multiplication(mat,5);
24 printf("%d",ans);
25 return 0;
26 }

Which of the following lines should be inserted to complete the above code?
a) arr[row][k]˘arr[k + 1][col] + mat[row˘1] ∗ mat[k] ∗ mat[col];
b) arr[row][k] + arr[k + 1][col]˘mat[row˘1] ∗ mat[k] ∗ mat[col];
c) arr[row][k] + arr[k + 1][col] + mat[row˘1] ∗ mat[k] ∗ mat[col];
d) arr[row][k]˘arr[k + 1][col]˘mat[row˘1] ∗ mat[k] ∗ mat[col];
Answer: c
Explanation: The line arr[row][k] + arr[k + 1][col] + mat[row˘1] ∗ mat[k] ∗
mat[col] should be inserted to complete the above code.

16
 8. What is the time complexity of the following dynamic programming implementation of the
matrix chain problem?
1 #include<stdio.h>
2 #include<limits.h>
3 int mat_chain_multiplication(int *mat, int n){
4 int arr[n][n];
5 int i,k,row,col,len;
6 for(i=1;i<n;i++)
7 arr[i][i] = 0;
8 for(len = 2; len < n; len++){
9 for(row = 1; row <= n - len + 1; row++){
10 col = row + len - 1;
11 arr[row][col] = INT_MAX;
12 for(k = row; k <= col - 1; k++){
13 int tmp = arr[row][k] + arr[k + 1][col] + mat[row -
1] * mat[k] * mat[col];
14 if(tmp < arr[row][col])
15 arr[row][col] = tmp;
16 }
17 }
18 }
19 return arr[1][n - 1];
20 }
21 int main(){
22 int mat[6] = {20,5,30,10,40};
23 int ans = mat_chain_multiplication(mat,5);
24 printf("%d",ans);
25 return 0;
26 }

a) O(1) b) O(n) c) O(n2 ) d) O(n3 )

Answer: d
Explanation: The time complexity of the above dynamic programming implementation
of the matrix chain multiplication is O(n3 ).

17
 9. What is the space complexity of the following dynamic programming implementation of the
matrix chain problem?
1 #include<stdio.h>
2 #include<limits.h>
3 int mat_chain_multiplication(int *mat, int n){
4 int arr[n][n];
5 int i,k,row,col,len;
6 for(i=1;i<n;i++)
7 arr[i][i] = 0;
8 for(len = 2; len < n; len++){
9 for(row = 1; row <= n - len + 1; row++){
10 col = row + len - 1;
11 arr[row][col] = INT_MAX;
12 for(k = row; k <= col - 1; k++){
13 int tmp = arr[row][k] + arr[k + 1][col] + mat[row -
1] * mat[k] * mat[col];
14 if(tmp < arr[row][col])
15 arr[row][col] = tmp;
16 }
17 }
18 }
19 return arr[1][n - 1];
20 }
21 int main(){
22 int mat[6] = {20,5,30,10,40};
23 int ans = mat_chain_multiplication(mat,5);
24 printf("%d",ans);
25 return 0;
26 }

a) O(1) b) O(n) c) O(n2) d) O(n3)

Answer: c
Explanation: The space complexity of the above dynamic programming implementation
of the matrix chain multiplication is O(n2 ).

18
10. What is the output of the following code?
1 #include<stdio.h>
2 #include<limits.h>
3 int mat_chain_multiplication(int *mat, int n){
4 int arr[n][n];
5 int i,k,row,col,len;
6 for(i=1;i<n;i++)
7 arr[i][i] = 0;
8 for(len = 2; len < n; len++){
9 for(row = 1; row <= n - len + 1; row++){
10 col = row + len - 1;
11 arr[row][col] = INT_MAX;
12 for(k = row; k <= col - 1; k++){
13 int tmp = arr[row][k] + arr[k + 1][col] + mat[row -
1] * mat[k] * mat[col];
14 if(tmp < arr[row][col])
15 arr[row][col] = tmp;
16 }
17 }
18 }
19 return arr[1][n - 1];
20 }
21 int main(){
22 int mat[6] = {20,30,40,50};
23 int ans = mat_chain_multiplication(mat,4);
24 printf("%d",ans);
25 return 0;
26 }

a) 64000 b) 70000 c) 120000 d) 150000

Answer: a
Explanation: The program prints the minimum number of multiplications required,
which is 64000.

19
11. What is the value stored in arr[2][3] when the following code is executed?
1 #include<stdio.h>
2 #include<limits.h>
3 int mat_chain_multiplication(int *mat, int n){
4 int arr[n][n];
5 int i,k,row,col,len;
6 for(i=1;i<n;i++)
7 arr[i][i] = 0;
8 for(len = 2; len < n; len++){
9 for(row = 1; row <= n - len + 1; row++){
10 col = row + len - 1;
11 arr[row][col] = INT_MAX;
12 for(k = row; k <= col - 1; k++){
13 int tmp = arr[row][k] + arr[k + 1][col] + mat[row -
1] * mat[k] * mat[col];
14 if(tmp < arr[row][col])
15 arr[row][col] = tmp;
16 }
17 }
18 }
19 return arr[1][n - 1];
20 }
21 int main(){
22 int mat[6] = {20,30,40,50};
23 int ans = mat_chain_multiplication(mat,4);
24 printf("%d",ans);
25 return 0;
26 }

a) 64000 b) 60000 c) 24000 d) 12000

Answer: b
Explanation: The value stored in arr[2][3] when the above code is executed is 60000.

20
12. What is the output of the following code?
1 #include<stdio.h>
2 #include<limits.h>
3 int mat_chain_multiplication(int *mat, int n){
4 int arr[n][n];
5 int i,k,row,col,len;
6 for(i=1;i<n;i++)
7 arr[i][i] = 0;
8 for(len = 2; len < n; len++){
9 for(row = 1; row <= n - len + 1; row++){
10 col = row + len - 1;
11 arr[row][col] = INT_MAX;
12 for(k = row; k <= col - 1; k++){
13 int tmp = arr[row][k] + arr[k + 1][col] + mat[row -
1] * mat[k] * mat[col];
14 if(tmp < arr[row][col])
15 arr[row][col] = tmp;
16 }
17 }
18 }
19 return arr[1][n-1];
20 }
21 int main(){
22 int mat[6] = {10,10,10,10,10,10};
23 int ans = mat_chain_multiplication(mat,6);
24 printf("%d",ans);
25 return 0;
26 }

a) 2000 b) 3000 c) 4000 d) 5000

Answer: c
Explanation: The program prints the minimum number of multiplications required to
multiply the given matrices, which is 4000.

21
13. What is the output of the following code?
1 #include<stdio.h>
2 #include<limits.h>
3 int mat_chain_multiplication(int *mat, int n){
4 int arr[n][n];
5 int i,k,row,col,len;
6 for(i=1;i<n;i++)
7 arr[i][i] = 0;
8 for(len = 2; len < n; len++){
9 for(row = 1; row <= n - len + 1; row++){
10 col = row + len - 1;
11 arr[row][col] = INT_MAX;
12 for(k = row; k <= col - 1; k++){
13 int tmp = arr[row][k] + arr[k + 1][col] + mat[row -
1] * mat[k] * mat[col];
14 if(tmp < arr[row][col])
15 arr[row][col] = tmp;
16 }
17 }
18 }
19 return arr[1][n-1];
20 }
21 int main(){
22 int mat[6] = {20,25,30,35,40};
23 int ans = mat_chain_multiplication(mat,5);
24 printf("%d",ans);
25 return 0;
26 }

a) 32000 b) 28000 c) 64000 d) 70000

Answer: c
Explanation: The output of the program is 64000.

22