Matrices A₁,A₂,A₃,A₄ have dimensions 10×5, 5×20, 20×10 and 10×5. Find the minimum scalar-multiplication count for A₁A₂A₃A₄ using ordinary matrix multiplication.
Pair costs are m₁₂=1000, m₂₃=1000, m₃₄=1000. Matrix-chain dynamic programming gives m₁₃=min(1000+500,1000+2000)=1500 and m₂₄=min(1000+500,1000+250)=1250. The three final splits cost 1500,2500,2000. Thus A₁((A₂A₃)A₄) is optimal, costing 1000+250+250=1500.
More Dynamic Programming questions
GATE 2011 CS (CS1) Q35– For A[0…n−1], define Lᵢ as the longest monotonically increasing run beginning at i. Set…
GATE 2011 CS (CS1) Q48– Matrices M₁,M₂,M₃,M₄ have dimensions p×q,q×r,r×s,s×t. With p=10,q=100,r=20,s=5,t=80, find…
GATE 2010 CS (CS1) Q44– The weight of a sequence a 0,,a n-1 is a 0+a 1/2++a n-1/2n-1. Subsequences preserve order…
GATE 2026 CS (CS2) Q39– Consider a table T where the entries T[i][j], 0 i,j n, represent costs of subproblems in a…
GATE 2024 CS (CS2) Q35– Let A be an array containing integer values. The distance of A is defined as the minimum…
GATE 2024 CS (CS2) Q42– Consider an array X of n positive integers. The C code below computes the length of the…