Gate2018 cs Q54

0. Assume that multiplying a matrix G₁ of dimension p×q with another matrix G₂ of dimension q×r requires pqr scalar multiplications. Computing the product of n matrices G₁G₂G₃ ….. G_n can be done by parenthesizing in different ways. Define G_iG_i+1 as an explicitly computed pair for a given paranthesization if they are directly multiplied. For example, in the matrix multiplication chain G₁G₂G₃G₄G₅G₆ using parenthesization (G₁(G₂G₃))(G₄(G₅G₆)), G₂G₃ and G₅G₆ are only explicitly computed pairs.
Consider a matrix multiplication chain F₁F₂F₃F₄F₅, where matrices F₁,F₂,F₃,F₄ and F₅ are of dimensions 2×25,25×3,3×16,16×1 and 1×1000, respectively. In the parenthesization of F₁F₂F₃F₄F₅ that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are

Answer
Comment
Array

Option : C
Explanation :
Total number of scalar multiplications are 48 + 75 + 50 + 2000 = 2173 and optimal parenthesis is ((F₁(F₂(F₃ F₄))) F₅). As concluded, F₃, F₄ are explicitly computed pairs.

Forgot your password?

I agree with the Terms.