Chain Matrix Multiplication

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).$ Applying 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 matrix 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.)$