Question

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,1*M1,8*M8,2*M2,10*M10,4.

Answer 1

For basics of the algorithm you can refer to Abdul Bari Matrix chain multiplication problem explanation, here you will find the implementation/ cost calculation using dynamic programming

We take the dimensions of the matrices in the form of an array where the first element is number of rows of the first matrix, all the other elements refer to the column values of the first uptil the last element.

Although the original MCM problem calculates minimum cost, we can simply reverse this condition by taking the maximum cost while splitting ( find in comments )

we store the split points in a 2d array of brackets. Here in an array 1...3 we take the element at bracket[1][3] to determine the split point and recursively print the the left portion and right portion of the split.

I have taken the matrices names as A, B, C, D and E in the order given in the question

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;

// Function for printing the optimal
// parenthesization of a matrix chain product
void print_brackets(int start, int end, int n,
                    vector<vector<int>> &bracket, char &name)
{
  // If only one matrix left in current segment
  if (start == end)
  {
    cout << name++;
    return;
  }

  cout << "(";

  // Recursively put brackets around subexpression
  // from i to bracket[i][j].

  print_brackets(start, bracket[start][end], n,
                 bracket, name);

  // Recursively put brackets around subexpression
  // from bracket[i][j] + 1 to j.
  print_brackets(bracket[start][end] + 1, end,
                 n, bracket, name);
  cout << ")";
}

// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
// Please refer below article for details of this
// function
// https://goo.gl/k6EYKj
void max_MCM(vector<int> &dim, int n)
{
  /*0th row and 0th column of m[][] 
        are not used */
  vector<vector<int>> m(n, vector<int>(n, 0));

  // bracket[i][j] stores optimal break point in
  // subexpression from i to j.
  vector<vector<int>> brackets(n, vector<int>(n, 0));

  /* m[i,j] = Minimum number of scalar multiplications 
    needed to compute the matrix A[i]A[i+1]...A[j] = 
    A[i..j] where dimension of A[i] is p[i-1] x p[i] */

  // cost is zero when multiplying one matrix.
  for (int i = 1; i < n; i++)
    m[i][i] = 0;

  //dynamic programming table is filled up diagonally
  // L is chain length.
  for (int L = 2; L < n; L++)
  {
    for (int i = 1; i < n - L + 1; i++)
    {
      int j = i + L - 1;
      m[i][j] = INT_MIN;
      for (int k = i; k <= j - 1; k++)
      {
        // q = cost/scalar multiplications
        int cost = m[i][k] + m[k + 1][j] + dim[i - 1] * dim[k] * dim[j];
        if (cost > m[i][j])
        {
          //taking maximum possible cost each time
          m[i][j] = cost;

          // Each entry bracket[i,j]=k shows
          // where to split the product arr
          // i,i+1....j for the minimum cost.
          brackets[i][j] = k;
        }
      }
    }
  }

  // The first matrix is printed as 'A', next as 'B',
  char name = 'A';

  cout << "worst parenthesization is : ";
  print_brackets(1, n - 1, n, brackets, name);
  cout << "\nmaximum possible cost is : " << m[1][n - 1];
}

// Driver code
int main()
{
  vector<int> arr = {9, 1, 8, 2, 10, 4};
  int n = arr.size();
  max_MCM(arr, n);
  return 0;
}

Output: