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

Looking For Something at vustudents.ning.com? Click Here to Search

www.bit.ly/vucodes

+ Link For Assignments, GDBs & Online Quizzes Solution

www.bit.ly/papersvu

+ Link For Past Papers, Solved MCQs, Short Notes & More

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
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).

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?


See Your Saved Posts Timeline

Views: 6377

.

+ 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)

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

Note: Just download the attached file and edit it to create difference and upload it.

Attachments:

RSS

Latest Activity

+AAg❤️ replied to + "αяsαℓ " Ќąƶµяɨ •"'s discussion Muhabato me li gaye kasmain
4 minutes ago
+ ! ! No Name updated their profile
13 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked + Iuuoɔǝut+'s blog post Things about Arabic Language in an info graphic
45 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked + Iuuoɔǝut+'s blog post The End Is Not Near, But If An 'Insect Apocalypse' Ever Happens, How Would We Know?
45 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked + Iuuoɔǝut+'s blog post Dengue fever facts
45 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked Atif Tariq's discussion Redmi Note 8 Pro 6GB Ram 64 MP Camera Mazey ka Phone hai ya nh ?
45 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked + "Jɨyą's discussion okey :x
45 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked + "Jɨyą's discussion Kia fark perta h...! XD
45 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked + "AS"'s discussion Log tou Masla Banaty Hain..
45 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked + "AS"'s discussion Jesi Ab hai ..
45 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked + "AS"'s discussion Dil Behlane K liye Log..
45 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked + "AS"'s discussion Suna Hai Ab ..
45 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked + "αяsαℓ " Ќąƶµяɨ •"'s discussion Muhabato me li gaye kasmain
45 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked + M.Tariq Malik's group STA301 Statistics and Probability
47 minutes ago
+ ! ! ! ! ! ! ! ! ! AG joined + M.Tariq Malik's group
48 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked + M.Tariq Malik's group MTH401 Differential Equations
48 minutes ago
+ ! ! ! ! ! ! ! ! ! AG joined + M.Tariq Malik's group
50 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked + M.Tariq Malik's group MCM301 Communication skills
50 minutes ago
+ ! ! ! ! ! ! ! ! ! AG joined + M.Tariq Malik's group
50 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked + M.Tariq Malik's group CS602 Computer Graphics
50 minutes ago

© 2019   Created by + M.Tariq Malik.   Powered by

Promote Us  |  Report an Issue  |  Privacy Policy  |  Terms of Service