Matrix Chain Multiplication in DSA Typescript - 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] using the matrix chain multiplication algorithm?

DSA Typescript

function matrixChainOrder(p: number[]): number {
  const n = p.length - 1;
  const m: number[][] = Array.from({ length: n }, () => Array(n).fill(0));

  for (let L = 2; L <= n; L++) {
    for (let i = 0; i <= n - L; i++) {
      let j = i + L - 1;
      m[i][j] = Number.MAX_SAFE_INTEGER;
      for (let k = i; k < j; k++) {
        const q = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
        if (q < m[i][j]) m[i][j] = q;
      }
    }
  }
  return m[0][n - 1];
}

console.log(matrixChainOrder([10, 20, 30]));

A 9000

B 6000

C 18000

D 15000

💡 Hint

Think about the cost formula for multiplying two matrices and how the algorithm tries all splits.

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

🧠 Conceptual

intermediate

Understanding the Role of the 'k' Variable in Matrix Chain Multiplication

In the matrix chain multiplication dynamic programming solution, what does the variable 'k' represent inside the nested loops?

A 'k' represents the index where the matrix chain is split to compute the cost of multiplication.

B 'k' is the total number of matrices in the chain.

C 'k' is the dimension of the resulting matrix after multiplication.

D 'k' is the minimum cost found so far for multiplying the matrices.

💡 Hint

Think about how the algorithm tries different places to split the chain.

The variable 'k' is used to try all possible places to split the matrix chain between i and j to find the minimum multiplication cost.

🔧 Debug

advanced

Identify the Error in Matrix Chain Multiplication Implementation

What error will the following TypeScript code produce when executed?

DSA Typescript

function matrixChainOrder(p: number[]): number {
  const n = p.length - 1;
  const m: number[][] = Array.from({ length: n }, () => Array(n).fill(0));

  for (let L = 2; L <= n; L++) {
    for (let i = 0; i <= n - L; i++) {
      let j = i + L - 1;
      m[i][j] = Number.MAX_SAFE_INTEGER;
      for (let k = i; k < j; k++) {
        const q = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
        if (q < m[i][j]) m[i][j] = q;
      }
    }
  }
  return m[0][n - 1];
}

console.log(matrixChainOrder([10, 20, 30]));

A TypeError: Cannot read property 'j+1' of undefined

B IndexError: Array index out of bounds

C The function returns 0 instead of the correct minimum cost

D No error, outputs 6000

💡 Hint

Check the loop boundaries carefully, especially the inner loop conditions.

The original code had 'i < n - L' which caused skipping the last valid index. Changing it to 'i <= n - L' fixes the issue and the function outputs the correct minimum cost 6000.

❓ Predict Output

advanced

Output of Matrix Chain Multiplication with Multiple Matrices

What is the minimum number of scalar multiplications needed to multiply the chain of matrices with dimensions [40, 20, 30, 10, 30]?

DSA Typescript

function matrixChainOrder(p: number[]): number {
  const n = p.length - 1;
  const m: number[][] = Array.from({ length: n }, () => Array(n).fill(0));

  for (let L = 2; L <= n; L++) {
    for (let i = 0; i <= n - L; i++) {
      let j = i + L - 1;
      m[i][j] = Number.MAX_SAFE_INTEGER;
      for (let k = i; k < j; k++) {
        const q = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
        if (q < m[i][j]) m[i][j] = q;
      }
    }
  }
  return m[0][n - 1];
}

console.log(matrixChainOrder([40, 20, 30, 10, 30]));

A 26000

B 30000

C 45000

D 35000

💡 Hint

Try to find the optimal split points to minimize multiplications.

The minimum cost is 26000 scalar multiplications by splitting the chain optimally.

🚀 Application

expert

Number of Optimal Parenthesizations for Matrix Chain Multiplication

Given the matrix dimensions [10, 20, 30, 40], how many different ways are there to parenthesize the matrix chain multiplication that achieve the minimum number of scalar multiplications?

A 3

B 2

C 1

D 4

💡 Hint

Consider how many ways the chain can be split to achieve the same minimum cost.

There is exactly 1 way to parenthesize the chain [10,20,30,40] that yields the minimum cost of 18000: ((A1 A2) A3). The other parenthesization (A1 (A2 A3)) costs 32000.