Algorithm

Consider the problem of multiplying n rectangular matrices discussed in class. Assume, in contrast to what we did in class, that we want to determine the maximum number of scalar multiplications that one might need (that is, compute the maximum of all possible parenthesizations). Formulate precisely an algorithm that determines this value. Then carry out your method on the following product to show what is the worst-possible parenthesization and how many scalar multiplications are required to carry it out M_9, 2* M_9, 1* M_1, 8* M_8, 4