1. Show that none of the following greedy algorithms for chained matrix multiplica- tion work. At each step
a. Compute the cheapest multiplication.
b. Compute the most expensive multiplication.
c. Compute the multiplication between the two matrices Mi and Mi+1, such that the number of columns inMi is minimized (breaking ties by one of the rules above).
2. Write a program to compute the best ordering of matrix multiplication. Include the routine to print out the actual ordering.
3. Show the optimal binary search tree for the following words, where the frequency of occurrence is in parentheses: a (0.18), and (0.19), I (0.23), it (0.21), or (0.19).