Question

This is from algorithm's class:

4. 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: M9,3* M3,9* M9,1*M1,8*M8,4.

Answer 1

#include<iostream>
using namespace std;

// Matrix Ai has dimension p[i-1] x p[i]
// for i = 1..n

int MaxMultiplicationsMatrix(int p[], int i, int j)
{
    if(i == j)
        return 0;
    int k;
    int max = -1;
    int count;

    // place parenthesis at different places
    // between first and last matrix, recursively
    // count of multiplications for
    // each parenthesis placement and return the
    // minimum count
    for (k = i; k < j; k++)
    {
        count = MaxMultiplicationsMatrix(p, i, k) +
                MaxMultiplicationsMatrix(p, k + 1, j) +
                p[i - 1] * p[k] * p[j];

        if (count > max) {
       /* cout<<p[i-1]<<' '<<p[k]<<' '<<p[j]<<endl;
           If we print this, we'll know that last 3 lines are:
           9 3 9 (meaning that dimension 9*3 and 3*9 got multiplied before below, it becomes 9*9)
           9 9 1 (now 9*9 and 9*1 will get multiplied, it will become 9*1 and then multiply 1*8 with this so it becomes 9*8 size).
           9 8 4 (this means that dimension of the last 2 matrices are 9*8 and 8*4
       */
            max = count;
       }
    }
   //cout<<max<<endl;
    // Return minimum count
    return max;
}

// Driver Code
int main()
{
    int arr[] = {9,3,9,1,8,4};
    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "Maximum number of multiplications is "
         << MaxMultiplicationsMatrix(arr, 1, n - 1);
}

/*
Answer explanation steps:
Matrices sizes: 9x3, 3x9, 9x1, 1x8, 8x4
For multiplying 2 matrices, it will follow below order:
(((M93 * M39)*(M91*M18))*M84)

Matrics       No. of multiplications       Final matrix

M93*M39   -> 9*3*9 = 243   -> M99
M91*M18 -> 9*1*8 = 72   -> M98
M99*M98 -> 9*9*8 = 648   -> M98
M98*M84 -> 9*8*4 = 288   -> M94
Total = 243+72+648+288 = 1251

*/