6.4. Base Case and Recursive Formulation

Try these first

1. 1.

   What are the conditions for two matrices to be multiplied?

   Hint

   Think of the dimensions involved.

2. 2.

   If Matrix A is 2x2 and Matrix B is 2x3, what is the dimension of Matrix C when A is multiplied by B?

   Hint

   Apply the multiplication rule.

3. 3.

   What is the order of operations needed for multiplying matrices A (4x3) and B (3x2)?

   • 12
   • 6
   • 8
   • 9

   Hint

   Remember the multiplication rule.

4. 4.

   True or False: The order of multiplication does not impact the minimum cost of multiplying matrices.

   • True
   • False

   Hint

   Think about how dimensions vary.

5. 5.

   Calculate the optimal order and the minimum multiplication cost for matrices of dimensions A (5x5), B (5x10), C (10x2), D (2x8).

   Hint

   Analyze several matrix multiplication orders.

6. 6.

   Using dynamic programming, derive and implement a solution to find the minimum number of multiplications needed to multiply a sequence of matrices.

   Hint

   Pay attention to the overlapping subproblems to reduce computation.