Question 48

Given matrix dimensions:

• $A_1: 10 \times 5$ ($p_0 = 10, p_1 = 5$)
• $A_2: 5 \times 20$ ($p_2 = 20$)
• $A_3: 20 \times 10$ ($p_3 = 10$)
• $A_4: 10 \times 5$ ($p_4 = 5$)
  Dimension array: $p = [10, 5, 20, 10, 5]$.

Let $m[i, j]$ denote the minimum number of scalar multiplications required to compute $A_i \dots A_j$.

1. Chains of length 2:

• $m[1, 2] = p_0 p_1 p_2 = 10 \times 5 \times 20 = 1000$
• $m[2, 3] = p_1 p_2 p_3 = 5 \times 20 \times 10 = 1000$
• $m[3, 4] = p_2 p_3 p_4 = 20 \times 10 \times 5 = 1000$

2. Chains of length 3:

• $m[1, 3] = \min\{ m[1, 1] + m[2, 3] + p_0 p_1 p_3 = 0 + 1000 + 10 \times 5 \times 10 = 1500, m[1, 2] + m[3, 3] + p_0 p_2 p_3 = 1000 + 0 + 10 \times 20 \times 10 = 3000 \} = 1500$

• $m[2, 4] = \min\{ m[2, 2] + m[3, 4] + p_1 p_2 p_4 = 0 + 1000 + 5 \times 20 \times 5 = 1500, m[2, 3] + m[4, 4] + p_1 p_3 p_4 = 1000 + 0 + 5 \times 10 \times 5 = 1250 \} = 1250$

3. Chain of length 4 ($m[1, 4]$):

• Split at $k = 1$: $m[1, 1] + m[2, 4] + p_0 p_1 p_4 = 0 + 1250 + 10 \times 5 \times 5 = 1250 + 250 = 1500$
• Split at $k = 2$: $m[1, 2] + m[3, 4] + p_0 p_2 p_4 = 1000 + 1000 + 10 \times 20 \times 5 = 2000 + 1000 = 3000$
• Split at $k = 3$: $m[1, 3] + m[4, 4] + p_0 p_3 p_4 = 1500 + 0 + 10 \times 10 \times 5 = 1500 + 500 = 2000$

The minimum scalar multiplications required is:

This optimal cost corresponds to the parenthesization $A_1 ((A_2 A_3) A_4)$.