We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>
Assignment No. 02
Semester: Spring 2016
CS502: Fundamentals of Algorithms
Please read the following instructions carefully before submitting assignment:
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).
The objective of this assignment is to:
Learn solving Chain Matrix Multiplication Problem using Dynamic Programming approach
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
.+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)
+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)+ Click Here to Search (Looking For something at vustudents.ning.com?) + Click Here To Join (Our facebook study Group)
Please koi correct or pura solution shair kar day.
Watch this video for help,
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
A matrix comprises of "m" rows and "n" columns, so dimension of a matrix becomes "m x n"
e.g. dimension of matrix:
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
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
(matrices 1 to k) x (matrices k+1 to n)
i.e. if k=3 then
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.
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
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
Semester Spring 2016
Note: Just download the attached file and edit it to create difference and upload it.