Consider the problem of a chain <A1 ,A2, A3, A4> of four matrices. Suppose…

2016

Consider the problem of a chain <A1 ,A2, A3, A4> of four matrices. Suppose that the dimensions of the matrices A1 , A2 , A3 and A4 are 30 × 35, 35 × 15, 15 × 5 and 5 × 10 respectively. The minimum number of scalar multiplications needed to compute the product A1A2A3A4 is ____.

  1. A.

    14875

  2. B.

    21000

  3. C.

    9375

  4. D.

    11875

Attempted by 117 students.

Show answer & explanation

Correct answer: C

Solution: compute the number of scalar multiplications for each parenthesization and pick the minimum.

  1. Parenthesization ((A1 A2) A3) A4: A1*A2 = 30*35*15 = 15750; (A1A2)*A3 = 30*15*5 = 2250; ((A1A2)A3)*A4 = 30*5*10 = 1500; total = 15750 + 2250 + 1500 = 19500.

  2. Parenthesization (A1 (A2 A3)) A4: A2*A3 = 35*15*5 = 2625; A1*(A2A3) = 30*35*5 = 5250 (cumulative 7875); then *A4 = 30*5*10 = 1500; total = 7875 + 1500 = 9375.

  3. Parenthesization A1 ((A2 A3) A4): A2*A3 = 35*15*5 = 2625; (A2A3)*A4 = 35*5*10 = 1750 (cumulative 4375); then A1*(that) = 30*35*10 = 10500; total = 2625 + 1750 + 10500 = 14875.

  4. Parenthesization (A1 A2) (A3 A4): A1*A2 = 30*35*15 = 15750; A3*A4 = 15*5*10 = 750; then multiply results = 30*15*10 = 4500; total = 15750 + 750 + 4500 = 21000.

  5. Parenthesization A1 (A2 (A3 A4)): A3*A4 = 15*5*10 = 750; A2*(that) = 35*15*10 = 5250 (cumulative 6000); then A1*(that) = 30*35*10 = 10500; total = 6000 + 10500 = 16500.

Conclusion: the smallest total cost is 9375 scalar multiplications, achieved by computing A2*A3 first, then A1*(A2*A3), then multiplying by A4.

Explore the full course: Coding For Placement