Question

show that none of the following greedy algorithms for chained matrix multiplication work. at each step.1. Compute the cheapest multiplication2. Compute the most expensive multiplication3. Compute the multiplication between the two matrices Mi and Mi+1 such that the number of columns in Mi is minimized (breaking ties by one of the rules above).

Answer 1

This question requires demonstrating that proposed greedy algorithms for chained matrix multiplication do not lead to the optimal solution by providing examples where these approaches increase the number of operations compared to an optimally parenthesized product.

Step-by-step explanation:

The question is about demonstrating why greedy algorithms are not effective for chained matrix multiplication problems. The algorithms proposed are based on cost evaluations at each step: computing the cheapest multiplication, the most expensive multiplication, and the multiplication of adjacent matrices with the least number of columns. To show these do not work, one could provide examples where following these rules does not lead to the optimal solution, which in this context is the sequence of multiplications that minimizes the total number of scalar multiplications required.

A common example is a set of matrices of varying dimensions that, when multiplied using a greedy approach, would significantly increase the number of operations compared to an optimally parenthesized product derived through dynamic programming approaches such as the one described by the Matrix Chain Multiplication algorithm.