GATE CS 2011 Q38 — Algorithm Design: Dynamic Programming

The dimensions of the four matrices are:

• $M_1: 10 \times 100$
• $M_2: 100 \times 20$
• $M_3: 20 \times 5$
• $M_4: 5 \times 80$

For $4$ matrices, there are $5$ possible parenthesizations. Let's evaluate the most promising ones to find the minimum cost:

Case 1: $(M_1 \times (M_2 \times M_3)) \times M_4$

• Cost of $(M_2 \times M_3)$ [resulting in a $100 \times 5$ matrix]:
  $100 \times 20 \times 5 = 10000$
• Cost of $M_1 \times (M_2 \times M_3)$ [resulting in a $10 \times 5$ matrix]:
  $10 \times 100 \times 5 = 5000$
• Cost of multiplying the result with $M_4$:
  $10 \times 5 \times 80 = 4000$
• Total cost = $10000 + 5000 + 4000 = 19000$

Case 2: $((M_1 \times M_2) \times M_3) \times M_4$

• Cost of $(M_1 \times M_2)$ [resulting in a $10 \times 20$ matrix]:
  $10 \times 100 \times 20 = 20000$
• Cost of multiplying with $M_3$ [resulting in a $10 \times 5$ matrix]:
  $10 \times 20 \times 5 = 1000$
• Cost of multiplying with $M_4$:
  $10 \times 5 \times 80 = 4000$
• Total cost = $20000 + 1000 + 4000 = 25000$

Evaluating other parenthesizations yields even larger values (e.g., $(M_1 \times M_2) \times (M_3 \times M_4)$ costs $44000$). Thus, the minimum number of scalar multiplications is $19000$.