Matrix Chain Multiplication in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the dp array with zeros.

DSA Javascript

const dp = Array(n).fill().map(() => Array(n).fill([1]));

Drag options to blanks, or click blank then click option'

A0

Bnull

Cundefined

DInfinity

Attempts:

3 left

💡 Hint

Common Mistakes

Using null or undefined instead of 0 causes errors in calculations.

Using Infinity here would make all costs infinite initially.

The dp array should be initialized with zeros because it stores minimum multiplication costs starting from zero.

2fill in blank

medium

Complete the code to set the base case where chain length is 1.

DSA Javascript

for (let i = 0; i < n; i++) dp[i][i] = [1];

Drag options to blanks, or click blank then click option'

AInfinity

B0

C1

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Setting dp[i][i] to 1 or Infinity causes wrong results.

Negative values are invalid for cost.

When the chain length is 1, no multiplication is needed, so cost is zero.

3fill in blank

hard

Fix the error in the loop that calculates minimum cost for chain length l.

DSA Javascript

for (let l = 2; l <= n; l++) {
  for (let i = 0; i <= n - l; i++) {
    let j = i + l - 1;
    dp[i][j] = [1];
    for (let k = i; k < j; k++) {
      let cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1];
      if (cost < dp[i][j]) dp[i][j] = cost;
    }
  }
}

Drag options to blanks, or click blank then click option'

A-Infinity

B0

C1

DInfinity

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing with 0 causes the minimum check to fail.

Using negative values is incorrect for cost.

We start with Infinity to find the minimum cost by comparing all possible splits.

4fill in blank

hard

Fill both blanks to complete the recursive function for matrix chain multiplication.

DSA Javascript

function matrixChainOrder(dims, i, j) {
  if (i === j) return [1];
  let minCost = Infinity;
  for (let k = i; k < j; k++) {
    let cost = matrixChainOrder(dims, i, k) + matrixChainOrder(dims, k + 1, j) + dims[i - 1] * dims[k] * dims[j];
    if (cost < minCost) minCost = cost;
  }
  return [2];
}

Drag options to blanks, or click blank then click option'

A0

BminCost

CInfinity

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Returning Infinity or 1 in base case causes wrong results.

Returning 0 instead of minCost after recursion is incorrect.

Base case returns 0 cost for single matrix; function returns minCost after checking all splits.

5fill in blank

hard

Fill all three blanks to complete the memoized recursive function for matrix chain multiplication.

DSA Javascript

function memoizedMatrixChain(dims, i, j, memo) {
  if (i === j) return [1];
  if (memo[i][j] !== [2]) return memo[i][j];
  let minCost = Infinity;
  for (let k = i; k < j; k++) {
    let cost = memoizedMatrixChain(dims, i, k, memo) + memoizedMatrixChain(dims, k + 1, j, memo) + dims[i - 1] * dims[k] * dims[j];
    if (cost < minCost) minCost = cost;
  }
  memo[i][j] = [3];
  return minCost;
}

Drag options to blanks, or click blank then click option'

A0

Bundefined

CminCost

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Using null instead of undefined for memo check causes errors.

Not storing minCost in memo causes repeated calculations.

Base case returns 0; memo check uses undefined; store minCost in memo before returning.

Practice

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

easy

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

B. To multiply all matrices in the chain in the given order without optimization

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

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

Solution

1. Step 1: Understand the problem objective

   The Matrix Chain Multiplication problem aims to multiply a sequence of matrices with minimum cost.

2. Step 2: Identify what is minimized

   The cost minimized is the number of scalar multiplications, not just multiplying in order or counting matrices.

3. Final Answer:

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

4. Quick Check:

   Goal = minimum scalar multiplications [OK]

Hint: Remember: minimize multiplication cost, not count matrices [OK]

Common Mistakes:

• Thinking the problem is about counting matrices
• Assuming multiplication order is fixed without optimization
• Confusing maximum with minimum cost

2. Which of the following is the correct way to declare the dimensions array p for matrices A1 (10x30), A2 (30x5), A3 (5x60) in JavaScript?

easy

A. const p = [10, 30, 5, 60];

B. const p = [[10, 30], [30, 5], [5, 60]];

C. const p = [10, 30, 5];

D. const p = [30, 5, 60];

Solution

1. Step 1: Understand the dimensions array format

   The array p stores dimensions such that matrix Ai has dimensions p[i-1] x p[i].

2. Step 2: Apply to given matrices

   For A1 (10x30), A2 (30x5), A3 (5x60), p = [10, 30, 5, 60].

3. Final Answer:

   const p = [10, 30, 5, 60]; -> Option A

4. Quick Check:

   Dimensions array = [10,30,5,60] [OK]

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

Common Mistakes:

• Using nested arrays instead of flat array
• Missing last dimension in array
• Confusing matrix dimensions order

3. What is the output of the following JavaScript code snippet for matrix dimensions p = [40, 20, 30, 10, 30]?

function matrixChainOrder(p) {
  const n = p.length - 1;
  const m = 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] = Infinity;
      for (let k = i; k < j; k++) {
        let 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(p));

medium

A. 45000

B. 30000

C. 26000

D. None of the above

Solution

1. Step 1: Understand the code logic

   The code implements the dynamic programming solution for matrix chain multiplication to find minimum cost.

2. Step 2: Calculate minimum multiplication cost for p = [40,20,30,10,30]

   Minimum cost is 26000 scalar multiplications after checking all splits.

3. Final Answer:

   26000 -> Option C

4. Quick Check:

   Minimum cost for given p = 26000 [OK]

Hint: Use DP table to find minimum cost, result is m[0][n-1] [OK]

Common Mistakes:

• Confusing indices i, j, k in loops
• Incorrectly calculating multiplication cost
• Returning wrong DP table value

4. Identify the error in the following JavaScript code snippet for matrix chain multiplication and select the fix:

function matrixChainOrder(p) {
  const n = p.length - 1;
  const m = 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] = Infinity;
      for (let k = i; k < j; k++) {
        let 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];
}

medium

A. Initialize m with Infinity instead of 0

B. Change inner loop condition to i <= n - L

C. Use for (let k = i; k <= j; k++) instead of k < j

D. Return m[0][n] instead of m[0][n - 1]

Solution

1. Step 1: Analyze the outer loop range for i

   The loop for (let i = 0; i < n - L; i++) misses the case when i equals n - L, causing incomplete computation.

2. Step 2: Fix loop condition to include i = n - L

   Changing to i <= n - L ensures all subproblems are covered correctly.

3. Final Answer:

   Change inner loop condition to i <= n - L -> Option B

4. Quick Check:

   Loop range fix = i <= n - L [OK]

Hint: Check loop boundaries carefully for full coverage [OK]

Common Mistakes:

• Off-by-one error in loop ranges
• Incorrect DP table initialization
• Wrong return index from DP table

5. Given matrices with dimensions p = [5, 10, 3, 12, 5, 50, 6], what is the minimum number of scalar multiplications needed to multiply the entire chain? Use the matrix chain multiplication approach.

hard

A. 1510

B. 2010

C. 4050

D. None of the above

Solution

1. Step 1: Understand the problem and dimensions

   We have 6 matrices with dimensions from p array: A1(5x10), A2(10x3), A3(3x12), A4(12x5), A5(5x50), A6(50x6).

2. Step 2: Apply matrix chain multiplication DP to find minimum cost

   Calculating minimum scalar multiplications yields 1510 as the optimal cost.

3. Final Answer:

   1510 -> Option A

4. Quick Check:

   Minimum scalar multiplications = 1510 [OK]

Hint: Use DP table and check all splits for minimum cost [OK]

Common Mistakes:

• Calculating cost for wrong matrix pairs
• Missing optimal parenthesization
• Confusing dimensions order in multiplication