Minimum Multiplication in Matrix Chain Multiplication in C

Posted by LAHAUL SETH ~ Comments

In this post, I will show how to write a program in C which will calculate the minimum number of multiplications required in a matrix chain multiplication. There are two algorithms for calculating the minimum no. of multiplication, one is recursive and another is non recursive.

First let us look at the pseudo code.

The recursive programs are always easy to understand but difficult for a programmer to keep it in control. The non recursive programs are longer and difficult to understand but they can be controlled more easily.

Since the theory part can be found in any algorithm book, I am only going to show the programming part.

Let us look at the Non-Recursive Code in C :

#include<stdio.h>
#include<limits.h>
int mat(int p[], int n)
{
 int m[n][n];
 int i, j, k, L, q;
 for (i = 1; i < n; i++)
  m[i][i] = 0;
 for (L=2; L<n; L++)  
 {
       for (i=1; i<=n-L+1; i++)
         {
          j = i+L-1;
          m[i][j] = INT_MAX;
          for (k=i; k<=j-1; k++)
          {
                   q = m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                    if (q < m[i][j])
                  m[i][j] = q;
          }
         }
 }
 return m[1][n-1];
}
main()
{
 printf("\nProgram to find minimum multiplications:\n");
 int i,n;
 printf("\nEnter number of matrices : ");
 scanf("%d",&n);      
 int a[n];
 printf("\nEnter the dimensions of matrices: ");
 for(i=0;i<=n;i++)
  scanf("%d",&a[i]);      
 printf("\nMinimum multiplications = %d\n\n",mat(a,n+1));
}

Let us look at the Recursive Code in C :

#include<stdio.h>
#include<limits.h>
int mat(int p[], int i, int j)
{
   if(i == j)
         return 0;
     int k,min = INT_MAX,count;
  for (k = i; k <j; k++)
     {
         count=mat(p,i,k)+mat(p,k+1,j)+p[i-1]*p[k]*p[j];
         if (count < min)
          min = count;
     }    
    return min;
}
main()
{
 printf("\nProgram to find the minimum multiplications :\n");
 int i,n;
 printf("\nEnter number of matrices : ");
 scanf("%d",&n);      
 int a[n];
 printf("\nEnter the dimensions of matrices : ");
 for(i=0;i<=n;i++)
  scanf("%d",&a[i]);  
     printf("Minimum multiplications=%d\n\n",mat(a,1,n));    
}