Matrix Chain Multiplication in DSA Rust - Build from Scratch

Matrix Chain Multiplication

📖 Scenario: You work in a company that processes large batches of matrix multiplications. To optimize the computation time, you want to find the best order to multiply a chain of matrices.Each matrix is represented by its dimensions (rows and columns). Multiplying two matrices takes time proportional to the product of their dimensions.

🎯 Goal: Build a Rust program that calculates the minimum number of scalar multiplications needed to multiply a chain of matrices in the most efficient order.

📋 What You'll Learn

Create a vector called dimensions with the exact values: [40, 20, 30, 10, 30]

Create a variable called n that stores the length of dimensions

Implement the matrix chain multiplication dynamic programming logic using nested for loops and a 2D vector dp

Print the minimum multiplication cost stored in dp[1][n-1]

💡 Why This Matters

🌍 Real World

Matrix chain multiplication optimization is used in computer graphics, scientific computing, and machine learning to speed up large matrix calculations.

💼 Career

Understanding dynamic programming and optimization techniques is valuable for software engineers working on performance-critical applications.

1

Create the dimensions vector

Create a vector called dimensions with the exact values [40, 20, 30, 10, 30].

DSA Rust

# Create the dimensions vector
# Your code here

Hint

Use let dimensions = vec![40, 20, 30, 10, 30]; to create the vector.

2

Create the length variable

Create a variable called n that stores the length of the dimensions vector.

DSA Rust

fn main() {
    let dimensions = vec![40, 20, 30, 10, 30];
    // Create variable n for length of dimensions
    // Your code here
}

Hint

Use let n = dimensions.len(); to get the length.

3

Implement the matrix chain multiplication logic

Create a 2D vector called dp of size n x n filled with zeros of type usize. Use nested for loops with variables length, i, and k to fill dp with minimum multiplication costs according to the matrix chain multiplication algorithm.

DSA Rust

fn main() {
    let dimensions = vec![40, 20, 30, 10, 30];
    let n = dimensions.len();
    // Create dp vector and implement matrix chain multiplication logic
    // Your code here
}

Hint

Initialize dp with zeros. Use three nested loops: outer for length, middle for i, inner for k. Update dp[i][j] with minimum cost.

4

Print the minimum multiplication cost

Print the minimum multiplication cost stored in dp[1][n-1] using println!.

DSA Rust

fn main() {
    let dimensions = vec![40, 20, 30, 10, 30];
    let n = dimensions.len();

    let mut dp = vec![vec![0_usize; n]; n];

    for length in 2..n {
        for i in 1..=(n - length) {
            let j = i + length - 1;
            dp[i][j] = usize::MAX;
            for k in i..j {
                let cost = dp[i][k] + dp[k + 1][j] + dimensions[i - 1] * dimensions[k] * dimensions[j];
                if cost < dp[i][j] {
                    dp[i][j] = cost;
                }
            }
        }
    }
    // Print the minimum multiplication cost
    // Your code here
}

Hint

Use println!("{}", dp[1][n - 1]); to print the minimum 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 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 goal

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

2. Step 2: Identify the cost metric

   The cost is measured by the number of scalar multiplications needed, not just multiplying matrices directly.

3. Final Answer:

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

4. Quick Check:

   Goal = minimize scalar multiplications [OK]

Hint: Focus on minimizing multiplication cost, not counting matrices [OK]

Common Mistakes:

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

2. Which of the following Rust function signatures correctly represents a function to compute the minimum multiplication cost for matrix chain multiplication?

easy

A. fn matrix_chain_order(dimensions: usize) -> usize

B. fn matrix_chain_order(dimensions: Vec<usize>) -> Vec<usize>

C. fn matrix_chain_order(dimensions: &mut [usize]) -> bool

D. fn matrix_chain_order(dimensions: &[usize]) -> usize

Solution

1. Step 1: Analyze parameter type

   The function should take a slice of dimensions because matrices are represented by their dimensions in order.

2. Step 2: Analyze return type

   The function returns the minimum cost as a single number (usize), not a vector or boolean.

3. Final Answer:

   fn matrix_chain_order(dimensions: &[usize]) -> usize -> Option D

4. Quick Check:

   Input slice, output cost number [OK]

Hint: Use slice input and usize output for cost [OK]

Common Mistakes:

• Using Vec instead of slice for input unnecessarily
• Returning a vector instead of a single cost
• Using incorrect parameter types like usize alone

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

medium

A. 18000

B. 24000

C. 30000

D. 36000

Solution

1. Step 1: Identify matrices and dimensions

   There are 3 matrices: A1 (10x20), A2 (20x30), A3 (30x40).

2. Step 2: Calculate costs for parenthesizations

   Option 1: (A1 x A2) x A3 = cost1 + cost2 = (10*20*30) + (10*30*40) = 6000 + 12000 = 18000
   Option 2: A1 x (A2 x A3) = cost1 + cost2 = (20*30*40) + (10*20*40) = 24000 + 8000 = 32000

3. Final Answer:

   18000 -> Option A

4. Quick Check:

   Minimum cost = 18000 [OK]

Hint: Try both parenthesizations, pick minimum cost [OK]

Common Mistakes:

• Calculating only one parenthesization cost
• Mixing up matrix dimensions order
• Adding dimensions instead of multiplying

4. Consider this Rust code snippet for matrix chain multiplication cost calculation:

fn matrix_chain_order(dimensions: &[usize]) -> usize {
    let n = dimensions.len();
    let mut dp = vec![vec![0; n]; n];
    for length in 2..n {
        for i in 0..n - length {
            let j = i + length;
            dp[i][j] = usize::MAX;
            for k in i..j {
                let cost = dp[i][k] + dp[k+1][j] + dimensions[i] * dimensions[k+1] * dimensions[j+1];
                if cost < dp[i][j] {
                    dp[i][j] = cost;
                }
            }
        }
    }
    dp[0][n-1]
}

What is the main error causing a panic or wrong result?

medium

A. Index out of bounds due to accessing dimensions[j+1]

B. Incorrect initialization of dp matrix size

C. Loop ranges do not cover all matrix pairs

D. Using usize::MAX causes overflow in cost calculation

Solution

1. Step 1: Check dimensions indexing

   dimensions has length n, valid indices 0 to n-1. Accessing dimensions[j+1] when j = n-1 causes out of bounds.

2. Step 2: Confirm loop ranges and indexing

   Loop runs j up to n-1, so j+1 equals n, which is invalid index for dimensions.

3. Final Answer:

   Index out of bounds due to accessing dimensions[j+1] -> Option A

4. Quick Check:

   dimensions[j+1] out of range [OK]

Hint: Check array indices carefully, especially j+1 [OK]

Common Mistakes:

• Ignoring array bounds on dimensions
• Assuming dp size matches dimensions length
• Not verifying loop end conditions

5. You have matrices with dimensions [5, 10, 3, 12, 5, 50, 6]. Using matrix chain multiplication, what is the minimum number of scalar multiplications needed to multiply the entire chain?

hard

A. 1510

B. 2010

C. 4050

D. 3500

Solution

1. Step 1: Identify matrices and dimensions

   There are 6 matrices: A1(5x10), A2(10x3), A3(3x12), A4(12x5), A5(5x50), A6(50x6).

2. Step 2: Use dynamic programming or known solution

   Using DP or known results, minimum cost is 2010 scalar multiplications for this chain.

3. Final Answer:

   2010 -> Option B

4. Quick Check:

   Minimum cost = 2010 [OK]

Hint: Use DP table or trusted calculator for complex chains [OK]

Common Mistakes:

• Calculating only partial parenthesizations
• Mixing matrix dimensions order
• Forgetting to multiply correct dimension triples