Compute optimal matrix-chain multiplication order

Q: Compute optimal matrix-chain multiplication order

This is a Coding & Algorithms interview question from Apple for Data Scientist roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Matrix Chain Multiplication: Optimal Parenthesization and Analysis

You are given five matrices to multiply: A1 (10×30), A2 (30×5), A3 (5×60), A4 (60×2), A5 (2×100). Assume the standard cost model: multiplying a (p×q) matrix by a (q×r) matrix costs p·q·r scalar multiplications. Matrix multiplication is associative but not commutative.

Tasks:

(a) Use dynamic programming to compute the minimum number of scalar multiplications and the optimal parenthesization. Show the DP tables m[i,j] (minimum cost) and s[i,j] (split point) and give the final order.

(b) Prove optimal substructure and explain why a greedy choice based on the locally smallest multiplication cost (or smallest local dimension) can fail; provide a concrete counterexample.

(c) Analyze time and space complexity. Discuss when Strassen-like algorithms could reduce cost in practice for skinny/fat matrices like these.

(d) Now let A3 be 5×k and A4 be k×2, where k is unknown at design time. Derive the threshold on k (integer) at which the optimal parenthesization changes, and state the optimal order on each side of the threshold.

Compute optimal matrix-chain multiplication order

Matrix Chain Multiplication: Optimal Parenthesization and Analysis

Solution (Locked)

Comments (0)