We are going to use matrix multiplication algorithms that use nmp multiplications to multiply an nxm matrix A by an mxp matrix B (the product matrix will be nxp.) Although matrix multiplcation is not commutative, it is associative. So the product ABCD can be evaluated as (AxB)x(CxD), or Ax(Bx(CxD)), or ((AxB)xC)xD, or ...

a. Give an example where the different ways above yield different number of multiplications.

b. Write down a recurrence for C(n) the number of different parenthetizations of the product A1 x A2 x ... An of n matrices.

c. Show that C(n)=Omega(n^2 )

d. Use dynamic programming to sketch an algorithm that computes the number of multiplications in the optimal parenthetization. You need to show correctness, and a good upper bound on the running time (big Theta)