Chain Matrix Multiplication $($Section $8\mathrm{.}3,$ course slides

"CSIS$\_4610\_11.$pdf$")$

Consider the problem of multiplying a set of matrices $A_1(23),A_2(32),$

$A_3(23),A_4(372),A_5(721),A_6(19),A_7(912),$ and $A_8(1215).$ Ap$-$

plying Dynamic Programming to this problem, the partial $M$ and $S$ arrays were

obtained as follows:

a$)$ Complete the $M$ and $S$ arrays, then draw the optimal tree for this problem.

Determine the location of the parentheses needed to multiply

$A_1{A}_2{A}_3{A}_4{A}_5{A}_6{A}_7{A}_8$ in an optimal way. Show all the parentheses

needed in $A_1{A}_2{A}_3{A}_4{A}_5{A}_6{A}_7{A}_8.[5$ points$]$

b$)$ What is the minimum number of multiplications needed to multiply the ma$-$

trix chain $A_1{A}_2{A}_3{A}_4{A}_5?$ Do not use the tables above. Show all your

work without skipping any details. $[10$ points$]$

$($Hint: fill in the blanks first in tables $M$ and $S.)$