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 Matrix Chain Multiplication algorithm?

DSA C

int arr[] = {10, 20, 30, 40};
int n = 4;
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] = 1000000;
            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 result = matrixChainOrder(arr, n);
printf("%d", result);

A 18000

B 30000

C 24000

D 36000

💡 Hint

Think about the cost of multiplying matrices in different orders and choose the minimum.

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

🧠 Conceptual

intermediate

Understanding Matrix Chain Multiplication Dimensions

Given matrices A (5x10), B (10x3), C (3x12), what is the dimension of the resulting matrix after multiplying A * B * C?

A 5 x 3

B 5 x 12

C 10 x 12

D 3 x 12

💡 Hint

The resulting matrix dimension after multiplication is the number of rows of the first matrix and the number of columns of the last matrix.

When multiplying matrices, the resulting matrix has the number of rows of the first matrix and the number of columns of the last matrix. Here, A is 5x10 and C is 3x12, so the result is 5x12.

❓ Predict Output

advanced

Output of Matrix Chain Multiplication Parenthesization Count

What is the number of ways to fully parenthesize a chain of 4 matrices for multiplication?

DSA C

int countParenthesizations(int n) {
    if (n <= 1) return 1;
    int count = 0;
    for (int i = 1; i < n; i++) {
        count += countParenthesizations(i) * countParenthesizations(n - i);
    }
    return count;
}

int result = countParenthesizations(4);
printf("%d", result);

A 5

B 14

C 4

D 2

💡 Hint

The number of ways to parenthesize n matrices is the (n-1)th Catalan number.

For 4 matrices, the number of ways to parenthesize is 5, which is the 3rd Catalan number.

🔧 Debug

advanced

Identify the Error in Matrix Chain Multiplication Code

What error does the following code produce when run?

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] = 1000000;
            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];
}

A No error, runs correctly

B Syntax error due to missing semicolon

C Array index out of bounds error

D Type error due to incompatible types

💡 Hint

Check the loop boundaries carefully for array indexing.

The loop 'for (int i = 1; i <= n; i++)' accesses m[i][i] where i can be equal to n, but m is declared as m[n][n] with zero-based indexing, causing out of bounds access.

🚀 Application

expert

Minimum Multiplication Cost for Large Matrix Chain

Given the matrix dimensions array arr = [40, 20, 30, 10, 30], what is the minimum number of scalar multiplications needed to multiply the chain of matrices?

DSA C

int arr[] = {40, 20, 30, 10, 30};
int n = 5;
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] = 1000000;
            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 result = matrixChainOrder(arr, n);
printf("%d", result);

A 27000

B 30000

C 35000

D 26000

💡 Hint

Try different parenthesizations and calculate the cost for each.

The minimum cost is 26000 scalar multiplications, achieved by the optimal parenthesization ((A1(A2A3))A4).