Compute optimal matrix-chain multiplication order
AppleData Scientist · Onsite
Last updated
This question evaluates dynamic programming, algorithmic analysis, and sensitivity reasoning for matrix-chain multiplication, and it belongs to the Coding & Algorithms domain; it is commonly asked because it tests understanding of optimal substructure, trade-offs in parenthesization, and correctness versus greedy heuristics.
Matrix Chain Multiplication optimal parenthesization. Given matrices with dimensions: A1 (10×30), A2 (30×5), A3 (5×60), A4 (60×2), A5 (2×100). (a) Use dynamic programming to compute the minimum scalar multiplications and the optimal parenthesization; show your DP tables m[i,j] and s[i,j] and the final order. (b) Prove optimal substructure and explain why a greedy choice on local smallest dimension fails. (c) Analyze time and space complexity; discuss when Strassen‑like algorithms could reduce cost in practice given these skinny/fat shapes. (d) If A3 is 5×k and A4 is k×2 with k unknown at design time, derive the threshold on k where the optimal parenthesization changes.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.