We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>

# www.vustudents.ning.com

 www.bit.ly/vucodes + Link For Assignments, GDBs & Online Quizzes Solution www.bit.ly/papersvu + Link For Past Papers, Solved MCQs, Short Notes & More

Dear Students! Share your Assignments / GDBs / Quizzes files as you receive in your LMS, So it can be discussed/solved timely. Add Discussion

# Assignment No. 02Problem Statement: Consider the following four matrices A1, A2, A3, and A4 along with their dimensions. A1 = 4*3 A2 = 3*2 A3 = 2*3 A4 = 3*5 Questions: 1. Determine the optimal multi

Assignment No. 02
Semester: Spring 2016
CS502: Fundamentals of Algorithms

Instructions

It should be clear that your assignment will not get any credit (zero marks) if:
o The assignment is submitted after due date.
o The submitted assignment is other than .doc file.
o The submitted assignment does NOT open or file is corrupted.
o The assignment is copied (from other student or ditto copy from any other source).

Objective

The objective of this assignment is to:
 Learn solving Chain Matrix Multiplication Problem using Dynamic Programming approach

Submission

You are required to submit your solution through LMS as MS Word document.

For any query about the assignment, contact at CS502@vu.edu.pk
GOOD LUCK

+ How to Join Subject Study Groups & Get Helping Material?

+ How to become Top Reputation, Angels, Intellectual, Featured Members & Moderators?

+ VU Students Reserves The Right to Delete Your Profile, If?

Views: 6410

.

+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)

+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)

### Replies to This Discussion  11

Please koi correct or pura solution shair kar day.

idea cs 502

Consider the following four matrices A1, A2, A3, and A4 along with their dimensions.
A1 = 4*3
A2 = 3*2
A3 = 2*3
A4 = 3*5
Dear Student,
A matrix comprises of "m" rows and "n" columns, so dimension of a matrix becomes "m x n"
e.g. dimension of matrix:
A= ?(1&2@4&3@7&6)
is 3 x 2 (i.e. 3 rows and 2 columns)
for ith matrix we write these dimensions in the form of Pi-1,Pi where Pi-1 represents number of rows and pi represents number of columns.
Now if there are five matrices A1,A2,A3,A4 with dimensions (4x3), (3x2), (2x3) and (3x5) respectively then:
Dimensions for A1 (first matrix i.e. i=1): Pi-1,Pi = P1-1,P1 = P0,P1 = 4,3
Dimensions for A2 (second matrix i.e. i=2): Pi-1,Pi = P2-1,P2 = P1,P2 = 3,2
Dimensions for A3 (third matrix i.e. i=3): Pi-1,Pi = P3-1,P3 = P2,P3 = 2,3
Dimensions for A4 (fourth matrix i.e. i=4): Pi-1,Pi = P4-1,P4 = P3,P4 = 3,5
So,
P0 P1 P2 P3 P 4 = 4,3,2,3,5

Now to multiply two matrices, number of columns of first matrices should be equal to number of rows of second matrix i.e. if there are two matrices such that dimension of first matrix is "3x2" and dimension of second matrix is "2x3", we can multiply them because they are compatible (number of columns of first matrix are equal to number of rows of second matrix)
Multiplication will result P0*P1*P2= 18 multiplications.
A1 = ?(1&2@4&5@3&1)
A2 = ?(3&5&1@6&4&2)
A x B = ?((3*1)+(2*6)&(1*5)+(2*4)&(1*1)+(2*2)@(4*3)+(5*6)&(4*5)+(5*4)&(4*1)+(5*2)@(3*3)+(1*6)&(3*5)+(1*4)&(3*1)+(1*2))

A x B = ?(15&13&5@42&40&14@15&19&5)
Now you can count that in total we had to performed 18 multiplications. Here
P0 = number of rows of first matrix
P1 = number of columns of first matrix (or number of columns of second matrix)
P2 = number of columns of second matrix
in our case P0=3, P1=2 and P2 = 3.
So, P0*P1*P2= 18
Now if we multiply five matrices A1,A2,A3,A4,A5 then we will have to calculate the sequence in which minimum number of multiplications will have to be performed. Number of multiplications will have to be calculated as explained above.
We can write above sequence A1,A2,A3,A4,A5
as
(matrices 1 to k) x (matrices k+1 to n)
i.e. if k=3 then
(A1*A2*A3)(A3*A5)
Now in (A1*A2*A3) again we will have to find the sequence in which minimum number of multiplications can be performed. Similarly in (A3*A5) we will have to find the sequence in which minimum number of multiplications will be performed.
Also note that multiplying (A1*A2*A3) will result into one matrix and similarly multiplying (A3*A5) will result into one matrix. We will have to multiply both of these resultant matrices as well to get final result.
So, overall
Recurrence will be:

Here m[i,k] represents the minimum operations performed by multiplying matrices from i to k. Similarly m[k+1,j] represents multiplying matrices k+1 to j.
And pi-1*pk*pj represents number of multiplications required by multiplying resultant two matrices.
m[i,i]=0 because it represents multiplying a single matrix in which case number of multiplications will be zero.
In our case suppose i=1 and j=5
min[1,5] will be: ?_(1?k<5)??min?(m[i,k]+m[k+1,j]+P_(i-1)*P_K*P_j ?)

Now if we consider k=1
Then
m[1,5]=m[i,k]+m[k+1,j]+P_(i-1)*P_K*P_j = m[1,1]+m[2,5]+P_0*P_1*P_5
Similarly if k= 2 then
m[1,5]=m[i,k]+m[k+1,j]+P_(i-1)*P_K*P_j = m[1,2]+m[3,5]+P_0*P_2*P_5
And so on
Finally from all of these values of m[1,5] for k=1 to k=4, you will pick minimum value.
Now given all that concepts just fill the matrix in the sequence given in handouts and you will get the final answer.

CS502 - Fundamentals of Algorithms
Assignment no.2
Complete solution
Semester Spring 2016