NPTEL WEEK-7.3

Programming Assignment 7.3:Matrix Chain Multiplication

Due on 2016-03-10, 23:55 IST

Write a C++ implementation of Matrix Chain Multiplication using the concepts of Dynamic Programming.

Code for two functions

1. Verify- to check whether a given set of input matrices can be multiplied in the given sequence. It will return -1, if matrices cannot be multiplied
2. MatrixOrder-  It will return the minimum number of multiplications

Input:

3

1 2

2 3

3 4

The first line indicate the number of matrices, Then each row indicates line number of rows and columns in a matrix  respectively

Output:

String “Error”  If matrix multiplication is not possible else the number of minimum operations required.

Example:

18

PROGRAM:

#include<stdio.h>

#include<stdlib.h>

#include<limits.h>

int MatrixOrder(int p[], int n);

int verify(int row[],int col[],int no_of_mat);

int main()

{

    int no_of_mat;

    scanf("%d",&no_of_mat);

    

    int *row=(int*)malloc(sizeof(int)*no_of_mat);

    int *col=(int*)malloc(sizeof(int)*no_of_mat);

    int i,j;

    for (i=0;i<no_of_mat;i++)

    {

scanf("%d",&row[i]);

scanf("%d",&col[i]);

    }

    int ans=verify(row,col,no_of_mat);

    if(ans == -1 )

    printf("Error");

    else 

    {

int size = no_of_mat+1;

    int *arr=(int*)malloc(sizeof(int)*(size));

   arr[0]=row[0];

   for (j=1;j<no_of_mat+1;j++)

   {

    arr[j]=col[j-1];

   }

  printf("%d",MatrixOrder(arr, size));

      }

    return 0;

}

CODING:

int MatrixOrder(int p[], int n)

{

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

 int m[n][n];

 // the function should be defined such that  m[1][n-1] stores the minimum number of //multiplications.

  int number=n-1,i,j,k,temp;

 m[1][n-1]=func(p,n,1,number);

 

  return m[1][n-1];

}

int verify(int row[],int col[],int no_of_mat){

// Verify, Matrix A,B,C can be multiplied in the order A*B*C.

  int flag,temp,i;

temp=col[0];

flag=0;

for(i=1;i<no_of_mat;i++)

{

  if(temp==row[i])

  {

   temp=col[i];

   }

   else

   {

    flag=1;

    break;

    }

   }

  

   if(flag==0)

   {

    return 1;

    }

    else

    {

     return -1;

     }

// returns 1-- if can be multiplied else -1

}

int func(int *p,int ni,int ini,int n)

{

 int temp,temp2,k;

 //printf("func called\n");

 if(ini==n)

 {

  return 0;

 }

 else

 {

  temp=func(p,ni,ini,ini)+func(p,ni,ini+1,n)+p[ini-1]*p[ini]*p[n];

  for(k=ini+1;k<n;k++)

  {

   temp2=func(p,ni,ini,k)+func(p,ni,k+1,n)+p[ini-1]*p[k]*p[n];

   if(temp2<temp)

   {

    temp=temp2;

  //  printf("new temp is %d\n",temp2);

   }

  }

 }

 return temp;

 }