Matrix Chain Multiplication in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Matrix Chain Multiplication Cost Calculation

What is the minimum number of scalar multiplications needed to multiply the chain of matrices with dimensions [10, 20, 30, 40] using the standard Matrix Chain Multiplication algorithm?

DSA C++

int matrixChainOrder(int p[], int n) {
    int m[n][n];
    for (int i = 1; i < n; i++)
        m[i][i] = 0;
    for (int L = 2; L < n; L++) {
        for (int i = 1; i < n - L + 1; i++) {
            int j = i + L - 1;
            m[i][j] = INT_MAX;
            for (int k = i; k <= j - 1; k++) {
                int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (q < m[i][j])
                    m[i][j] = q;
            }
        }
    }
    return m[1][n - 1];
}

int main() {
    int arr[] = {10, 20, 30, 40};
    int size = sizeof(arr) / sizeof(arr[0]);
    int result = matrixChainOrder(arr, size);
    std::cout << result << std::endl;
    return 0;
}

A 24000

B 18000

C 30000

D 36000

💡 Hint

Think about the order of multiplication that minimizes the total scalar multiplications.

The minimum cost is calculated by trying all possible splits. For matrices with dimensions 10x20, 20x30, and 30x40, the minimum cost is 18000 scalar multiplications.

🧠 Conceptual

intermediate

Understanding Matrix Chain Multiplication Dimensions

Given matrices A1 (5x10), A2 (10x3), A3 (3x12), and A4 (12x5), how many matrices are involved in the chain multiplication and what is the length of the dimension array used in the algorithm?

A 4 matrices, dimension array length 5

B 4 matrices, dimension array length 4

C 3 matrices, dimension array length 4

D 3 matrices, dimension array length 3

💡 Hint

Remember the dimension array length is one more than the number of matrices.

For n matrices, the dimension array length is n+1 because it stores the row count of the first matrix and the column count of each matrix.

❓ Predict Output

advanced

Output of Matrix Chain Multiplication Parenthesization

What is the optimal parenthesization output of the following code for matrices with dimensions [40, 20, 30, 10, 30]?

DSA C++

#include <iostream>
#include <vector>
#include <climits>

void printOptimalParens(std::vector<std::vector<int>>& s, int i, int j) {
    if (i == j) {
        std::cout << "A" << i;
        return;
    }
    std::cout << "(";
    printOptimalParens(s, i, s[i][j]);
    printOptimalParens(s, s[i][j] + 1, j);
    std::cout << ")";
}

int matrixChainOrder(int p[], int n) {
    int m[n][n];
    std::vector<std::vector<int>> s(n, std::vector<int>(n, 0));
    for (int i = 1; i < n; i++)
        m[i][i] = 0;
    for (int L = 2; L < n; L++) {
        for (int i = 1; i < n - L + 1; i++) {
            int j = i + L - 1;
            m[i][j] = INT_MAX;
            for (int k = i; k <= j - 1; k++) {
                int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (q < m[i][j]) {
                    m[i][j] = q;
                    s[i][j] = k;
                }
            }
        }
    }
    printOptimalParens(s, 1, n - 1);
    return m[1][n - 1];
}

int main() {
    int arr[] = {40, 20, 30, 10, 30};
    int size = sizeof(arr) / sizeof(arr[0]);
    int cost = matrixChainOrder(arr, size);
    std::cout << std::endl << cost << std::endl;
    return 0;
}

A (A1(A2(A3A4)))

B ((A1A2)A3)A4

C (A1((A2A3)A4))

D (A1(A2A3))A4

💡 Hint

Look at the split points stored in s to find the optimal parenthesization.

The optimal parenthesization for these dimensions is (A1(A2(A3A4))) which minimizes the scalar multiplications.

🔧 Debug

advanced

Identify the Error in Matrix Chain Multiplication Code

What error will the following code produce when run, and why?

DSA C++

int matrixChainOrder(int p[], int n) {
    int m[n][n];
    for (int i = 1; i < n; i++)
        m[i][i] = 0;
    for (int L = 2; L < n; L++) {
        for (int i = 1; i < n - L + 1; i++) {
            int j = i + L - 1;
            m[i][j] = INT_MAX;
            for (int k = i; k <= j - 1; k++) {
                int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (q < m[i][j])
                    m[i][j] = q;
            }
        }
    }
    return m[1][n - 1];
}

int main() {
    int arr[] = {10, 20, 30};
    int size = sizeof(arr) / sizeof(arr[0]);
    int result = matrixChainOrder(arr, size);
    std::cout << result << std::endl;
    return 0;
}

A No error, outputs correct minimum cost

B Compilation error due to missing header files

C Runtime error due to out-of-bounds array access

D Logical error producing incorrect minimum cost

💡 Hint

Check the loop boundaries for array indexing.

The loop 'for (int i = 1; i <= n; i++)' accesses m[i][i] where i can be equal to n, which is out of bounds for array of size n x n indexed from 0 to n-1.

🚀 Application

expert

Number of Scalar Multiplications for Large Chain

Given the matrix dimensions array [5, 10, 3, 12, 5, 50, 6], what is the minimum number of scalar multiplications needed to multiply the entire chain?

DSA C++

int matrixChainOrder(int p[], int n) {
    int m[n][n];
    for (int i = 1; i < n; i++)
        m[i][i] = 0;
    for (int L = 2; L < n; L++) {
        for (int i = 1; i < n - L + 1; i++) {
            int j = i + L - 1;
            m[i][j] = INT_MAX;
            for (int k = i; k <= j - 1; k++) {
                int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (q < m[i][j])
                    m[i][j] = q;
            }
        }
    }
    return m[1][n - 1];
}

int main() {
    int arr[] = {5, 10, 3, 12, 5, 50, 6};
    int size = sizeof(arr) / sizeof(arr[0]);
    int result = matrixChainOrder(arr, size);
    std::cout << result << std::endl;
    return 0;
}

A 2010

B 4050

C 2700

D 1510

💡 Hint

Use dynamic programming to find the minimum cost by checking all splits.

The minimum number of scalar multiplications for the given dimensions is 1510, calculated by the matrix chain multiplication dynamic programming approach.

Practice

1. What is the main goal of the Matrix Chain Multiplication problem?

easy

A. To find the maximum number of matrices that can be multiplied

B. To multiply all matrices in the chain directly without optimization

C. To find the minimum number of scalar multiplications needed to multiply a chain of matrices

D. To count the total number of matrices in the chain

Solution

1. Step 1: Understand the problem objective

   The Matrix Chain Multiplication problem aims to find the best way to multiply matrices to minimize computation.

2. Step 2: Identify the correct goal

   The goal is to minimize the number of scalar multiplications, not just multiply or count matrices.

3. Final Answer:

   To find the minimum number of scalar multiplications needed to multiply a chain of matrices -> Option C

4. Quick Check:

   Goal = Minimum multiplications [OK]

Hint: Remember: minimize multiplication cost, not just multiply [OK]

Common Mistakes:

• Thinking the goal is to multiply matrices directly without optimization
• Confusing counting matrices with minimizing operations
• Assuming maximum multiplications is the goal

2. Which of the following is the correct way to declare the dimensions array for 4 matrices with dimensions 10x20, 20x30, 30x40, and 40x50 in C++?

easy

A. int dims[] = {10, 20, 30, 40, 50};

B. int dims[] = {10, 20, 30, 40};

C. int dims[] = {10, 20, 30, 40, 50, 60};

D. int dims[] = {20, 30, 40, 50};

Solution

1. Step 1: Understand the dimensions array format

   For n matrices, the dimensions array has n+1 elements representing rows and columns of each matrix.

2. Step 2: Apply to given matrices

   For matrices 10x20, 20x30, 30x40, 40x50, dims = {10, 20, 30, 40, 50}.

3. Final Answer:

   int dims[] = {10, 20, 30, 40, 50}; -> Option A

4. Quick Check:

   Dimensions array length = number of matrices + 1 [OK]

Hint: Dimensions array length = matrices count + 1 [OK]

Common Mistakes:

• Using fewer elements than needed in the dimensions array
• Including extra unrelated numbers
• Confusing matrix dimensions order

3. What is the output of the following C++ code snippet for Matrix Chain Multiplication cost calculation?

int dims[] = {5, 10, 3, 12, 5};
int n = 4;
int m[5][5] = {0};
for (int L = 2; L <= n; L++) {
  for (int i = 1; i <= n - L + 1; i++) {
    int j = i + L - 1;
    m[i][j] = 1000000;
    for (int k = i; k < j; k++) {
      int cost = m[i][k] + m[k+1][j] + dims[i-1]*dims[k]*dims[j];
      if (cost < m[i][j]) m[i][j] = cost;
    }
  }
}
std::cout << m[1][n] << std::endl;

medium

A. 270

B. 150

C. 201

D. 405

Solution

1. Step 1: Understand matrix dimensions and indices

   Dimensions: 5x10, 10x3, 3x12, 12x5; n=4 matrices; m[i][j] stores min cost from i to j.

2. Step 2: Calculate minimum multiplication cost

   Length 2: m[1][2]=150, m[2][3]=360, m[3][4]=180
   Length 3: m[1][3]=min(0+360+600,150+0+180)=330; m[2][4]=min(0+180+150,360+0+600)=330
   Length 4: m[1][4]=min(0+330+250,150+180+75,330+0+300)=405

3. Final Answer:

   405 -> Option D

4. Quick Check:

   Minimum cost = 405 [OK]

Hint: Trace splits and pick minimum cost [OK]

Common Mistakes:

• Mixing up indices i, j, k
• Incorrect cost formula application
• Forgetting to initialize m[i][j] to max

4. Identify the error in the following C++ code snippet for Matrix Chain Multiplication and choose the correct fix:

int dims[] = {40, 20, 30, 10, 30};
int n = 4;
int m[5][5];
for (int i = 1; i <= n; i++)
  m[i][i] = 0;
for (int L = 2; L <= n; L++) {
  for (int i = 1; i <= n - L + 1; i++) {
    int j = i + L - 1;
    m[i][j] = 0;
    for (int k = i; k < j; k++) {
      int cost = m[i][k] + m[k+1][j] + dims[i-1]*dims[k]*dims[j];
      if (cost < m[i][j])
        m[i][j] = cost;
    }
  }
}

medium

A. Change dims indexing to dims[i-1]*dims[k]*dims[j]

B. Initialize m[i][j] to INT_MAX instead of 0 before inner loop

C. Start i loop from 0 instead of 1

D. Remove the if condition inside the inner loop

Solution

1. Step 1: Identify initialization mistake

   m[i][j] is set to 0 before checking for minimum cost, which causes incorrect comparisons.

2. Step 2: Correct initialization

   m[i][j] should be initialized to a very large number (INT_MAX) to find minimum cost correctly.

3. Final Answer:

   Initialize m[i][j] to INT_MAX instead of 0 before inner loop -> Option B

4. Quick Check:

   Use INT_MAX to find minimum cost [OK]

Hint: Initialize costs to max before minimizing [OK]

Common Mistakes:

• Setting m[i][j] to 0 instead of INT_MAX
• Incorrect dims indexing causing wrong cost
• Ignoring initialization leading to wrong min

5. Given matrices with dimensions 10x15, 15x20, 20x25, and 25x30, what is the minimum number of scalar multiplications needed to multiply the entire chain? Use the Matrix Chain Multiplication approach.

hard

A. 15500

B. 15000

C. 13000

D. 11250

Solution

1. Step 1: List matrix dimensions and possible splits

   Matrices: A1(10x15), A2(15x20), A3(20x25), A4(25x30). dims=[10,15,20,25,30]. Calculate costs for chain length 2 to 4.

2. Step 2: Calculate minimum costs for each subchain

   Length 2: m[1][2]=10*15*20=3000; m[2][3]=15*20*25=7500; m[3][4]=20*25*30=15000
   Length 3: m[1][3]=min(0+7500+10*15*25=11250, 3000+0+10*20*25=8000)=8000;
   m[2][4]=min(0+15000+15*20*30=24000, 7500+0+15*25*30=18750)=18750
   Length 4: m[1][4]=min(0+18750+10*15*30=23250, 3000+15000+10*20*30=24000, 8000+0+10*25*30=15500)=15500

3. Final Answer:

   15500 -> Option A

4. Quick Check:

   Minimum scalar multiplications = 15500 [OK]

Hint: Calculate costs for smaller chains first, then combine [OK]

Common Mistakes:

• Incorrectly calculating subproblems costs
• Mixing up matrix dimensions in cost formula
• Not checking all split points k