Matrix Chain Multiplication in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the dp table with zeros.

DSA Typescript

const n = dims.length - 1;
const dp: number[][] = Array(n).fill(0).map(() => Array(n).fill([1]));

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

A1

B0

CInfinity

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing dp with 1 instead of 0

Using Infinity which is used for initial max cost, not for dp initialization

The dp table should be initialized with zeros because initially, the cost of multiplying one matrix is zero.

2fill in blank

medium

Complete the code to set the chain length for the outer loop.

DSA Typescript

for (let length = 2; length <= n; length[1]) {

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

A++

B*=

C+=

D--

Attempts:

3 left

💡 Hint

Common Mistakes

Using -- which decreases the length

Using *= which multiplies length

The chain length increases by 1 in each iteration, so we use ++ to increment length.

3fill in blank

hard

Fix the error in the cost calculation inside the nested loops.

DSA Typescript

const cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[[1] + 1];

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

Ai

Bk

Cj

Dk - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using dims[k] instead of dims[j + 1]

Using dims[i] twice

The cost of multiplying matrices from i to j includes dims[i] * dims[k+1] * dims[j + 1].

4fill in blank

hard

Fill both blanks to correctly update the dp table and loop indices.

DSA Typescript

for (let i = 0; i <= n - [1]; i++) {
  let j = i + [2] - 1;

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

Alength

Cn

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using n instead of length

Incorrect calculation of j

The loop runs while i <= n - length, and j is calculated as i + length - 1 to cover the chain segment.

5fill in blank

hard

Fill all three blanks to complete the minimum cost update inside the innermost loop.

DSA Typescript

if (cost < dp[i][j]) {
  dp[i][j] = [1];
  split[i][j] = [2];
}

// Return the minimum cost
return dp[3];

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

Acost

Bk

C[0][n - 1]

Ddp[i][j]

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning dp[i][j] to dp[i][j] instead of cost

Returning dp[i][j] instead of dp[0][n-1]

We update dp[i][j] with cost, record split point k, and finally return dp[0][n-1] for full chain cost.

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 count the total number of matrices in the chain

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 find the best way to multiply matrices to minimize cost.

2. Step 2: Identify what is minimized

   The cost minimized is the number of scalar multiplications, not the number of matrices or direct multiplication.

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:

• Confusing multiplication count with matrix count
• Thinking the problem multiplies matrices directly
• Assuming maximum matrices multiplication is the goal

2. Which of the following is the correct TypeScript function signature for a recursive Matrix Chain Multiplication function that takes an array of matrix dimensions?

easy

A. function matrixChainOrder(dimensions: string): number

B. function matrixChainOrder(dimensions: number): number[]

C. function matrixChainOrder(dimensions: number[]): number

D. function matrixChainOrder(dimensions: number[][]): void

Solution

1. Step 1: Identify input type for matrix dimensions

   Matrix dimensions are given as an array of numbers representing sizes, so number[] is correct.

2. Step 2: Identify return type for minimum cost

   The function returns the minimum number of scalar multiplications, which is a number.

3. Final Answer:

   function matrixChainOrder(dimensions: number[]): number -> Option C

4. Quick Check:

   Input = number[], Output = number [OK]

Hint: Input is array of numbers, output is a single number [OK]

Common Mistakes:

• Using string instead of number array for dimensions
• Returning an array instead of a number
• Using 2D array or void return incorrectly

3. What is the output of the following TypeScript code snippet?

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 + 1; i++) {
      const 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, 40]));

medium

A. 18000

B. 24000

C. 30000

D. 60000

Solution

1. Step 1: Understand the input and matrix dimensions

   The input array [10, 20, 30, 40] represents matrices of dimensions 10x20, 20x30, and 30x40.

2. Step 2: Calculate minimum multiplication cost

   Possible parenthesizations:
   - (A1 x (A2 x A3)) = 20*30*40 + 10*20*40 = 24000 + 8000 = 32000
   - ((A1 x A2) x A3) = 10*20*30 + 10*30*40 = 6000 + 12000 = 18000 (minimum)

3. Final Answer:

   18000 -> Option A

4. Quick Check:

   Minimum multiplications = 18000 [OK]

Hint: Check all splits and pick minimum cost [OK]

Common Mistakes:

• Calculating cost for only one parenthesization
• Mixing matrix dimensions order
• Forgetting to add multiplication costs correctly

4. Identify the error in the following TypeScript code snippet for Matrix Chain Multiplication and select the fix:

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 + 1; i++) {
      const j = i + L - 1;
      m[i][j] = Infinity;
      for (let k = i; k < j; k++) {
        const q = m[i][k] + m[k + 1][j] + p[i] * p[k] * p[j];
        if (q < m[i][j]) m[i][j] = q;
      }
    }
  }
  return m[0][n - 1];
}

medium

A. Change p[i] * p[k] * p[j] to p[i] * p[k + 1] * p[j + 1]

B. Initialize m with Infinity instead of 0

C. Change loop for (let k = i; k <= j; k++) to k < j

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

Solution

1. Step 1: Identify the multiplication cost formula error

   The cost formula uses incorrect indices: p[i] * p[k] * p[j] should use p[k + 1] and p[j + 1] to represent matrix dimensions correctly.

2. Step 2: Confirm other parts are correct

   Initialization with 0 is correct for diagonal, loop ranges are correct, and return index is correct.

3. Final Answer:

   Change p[i] * p[k] * p[j] to p[i] * p[k + 1] * p[j + 1] -> Option A

4. Quick Check:

   Correct cost formula indices fix error [OK]

Hint: Check matrix dimension indices carefully in cost formula [OK]

Common Mistakes:

• Using wrong indices for matrix dimensions in cost calculation
• Changing loop bounds unnecessarily
• Returning wrong matrix cell

5. Given matrices with dimensions [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. 3500

Solution

1. Step 1: Understand matrix dimensions and chain length

   The array represents matrices: 5x10, 10x3, 3x12, 12x5, 5x50, 50x6 (6 matrices).

2. Step 2: Use dynamic programming to find minimum cost

   By calculating all splits and costs:
   - Minimum cost found is 2010 scalar multiplications.

3. Final Answer:

   2010 -> Option B

4. Quick Check:

   Minimum scalar multiplications = 2010 [OK]

Hint: Use DP table to check all splits and pick minimum [OK]

Common Mistakes:

• Calculating only one split option
• Mixing up matrix dimensions order
• Forgetting to add multiplication costs for subproblems