4.3 Matrix Chain Multiplication - Dynamic Programming
ฝัง
- เผยแพร่เมื่อ 26 ก.ย. 2024
- Matrix Chain Multiplication
Dynamic Programming
PATREON : www.patreon.co...
Courses on Udemy
================
Java Programming
www.udemy.com/...
Data Structures using C and C++
www.udemy.com/...
C++ Programming
www.udemy.com/...
![[New] Matrix Chain Multiplication using Dynamic Programming Formula](http://i.ytimg.com/vi/_WncuhSJZyA/mqdefault.jpg)
![[New] Matrix Chain Multiplication using Dynamic Programming Formula](/img/tr.png)
For those who are wondering how S table is filled...
Assume your answer come out to be : [ A1 A2 ] [ A3 ] so you've partitioned the whole multiplication at 2nd matrix, thus answer is 2
Assume another answer come out to be : [A1] [A2 A3 A4] so you've partitioned the whole multiplication at 1st matrix, thus answer is 1
Another example : [A1 A2 A3] [A4] so you've partitioned the whole multiplication at 3rd matrix, thus answer is 3.
Give a thumbs up if u got this.
Impressive 👍
what about s[1,2] =1?
@@Rock28099 Yep..because you can multiply two matrix in only one way given they satisfy multiplication condition, not only s[1,2] = 1 but also s[2,3] = 2 and s[3,4] = 3. Watch the video from 3:10. I hope u'll understand.
@AkashUpadhyay u said the values in Matrix S represent the partition where matrix was divided...but in the case of M[2,3] its 2 and M[3,4] its 3...so how the partition was done In these two case?
Thanks in advance
My God..you are next level Man...from where did you get that?? I wish I could meet you once and take your autograph...
Sir, you've saved my time by investing yours.
Mr. Bari, Thank you so much for providing free content that explains algorithms simply but also comprehensively.
The best video I've ever seen. Referring this video from the University of Texas,USA. Thank you for such a beautiful narration.
Thanks for the video bro
thandav63 bhai tu pagal hai kya??
Hook 'Em!
Kya bhai US ja kr bhi YT par padhai kar rhe ho 😶
@@vinayak186f3 University/Country changes but YT is constant!
Mr. Bari must be tired from carrying me through my algorithms course
carrying us all lmao
How can we select no of rows and columns for m. And s matrices
Bsdk sir tujhe jaante v nhi honge!!
@@shivaramgoli6333 number of matrices that u r multiplying
Ex: A1,A2,A3,.....An then take n*n matrix of m and s
@@shivaramgoli6333 On the basis of number of matrices attempt to multiply. here are 4*4 because A1 * A2 * A3 * A4.
4:32 He used Catalan number to find possible number of binary trees with n nodes
Thanks
After that [1,3] Bari sir why u dont take value [1,4] if some one known that plz answer
After that [1,3] Bari sir why u dont take value [1,4] if some one known that plz answer
Sir, thank you very much.. despite the lack of explanation of the S matrix (which the comments section made up for), I am very satisfied with this (free) content you are providing helping us fellow students get through exams! You are doing social service here!
Literally the best channel for learning things in my algorithms class
thank you sir... it helped alot.. its very easy understanding your explanation.. i have my algorithms exam tomorrow and your lectures saved me alot of time ... keep uploading more videos
for the formula we must write under min i
I was stumped on facing this question,
but sir you're my saviour, cannot thank u enough for explaining such complex algo in elegant & simple way.
s matrix not explained properly
He explained it properly
i like how he stares directly at the camera, feels personal lol... great video, helped me a lot
I won't even bother watching the whole video to make this comment.
Your video is awesome, very descriptive and clean. Really one of the best explanation if not the best.
Thanks for the effort! (continuing the video)
Awesome video!!! Really appreciate the great work you do. A little trick i found to do these problems is simply write out which parenthesization gave the best answer, then you can actually work backwards. ie) you find the best with 4 which is (A1 A2 A3) (A4) Then comebine that with what you get for the best with 3 parentheses (A1) (A2 A3) and add them around A2 A3 etc
wonderful
We all appreciate your hardwork !!
May be we all not get good teacher however the person like you are still on Earth who are putting effort to make good student
Thanks for full fill our hunger knowledge.
I hope you will always be blessed by God and may God full fill your all dreams.
Once again thank you for your time and efforts.
The best teacher I have come across till now...
An example is worth a thousand words. Simple and clear video. thank you
really thank you so much sir ...i understand very clearly...my mam follows your classes and then she is
explaining in the class same as u told
Sir, you are awesome. Cause it's important, I`ll say it again. YOU ARE AWESOME.
all professors across the nation should take notes from your teaching, and thank you so much
I searched a lot more videos for matrix chain multiplication using dynamic programming nobody able to explain or persuade such a way of clarity...thanks sir #i_m your big #fan
Sir honestly you are the best teacher that I have ever learnt from. You make algorithm so easy subject to understand. Thanks sir
if you are wondering abt s table .those are the values of k used to get minimum
Apka tahedil se bahut bahut shukriya Kal ke paper (rtu exam) k liye jitni bhi padhai Kari sab apke video se Kari... thanks a lot
Abdul Bari bahut hi acha explain krte h sir aap, saare concept ache se clear karwae, thanks once again I'll definitely score good in my exam, hum jese students ki dua hamesha apke saath h 😊
I am also from RTU, 6th Sem CSE. How was your DAA paper?
sourabh khandelwal good, what about you?
Ashraf Mansuri Good paper was easy ,☺
sourabh khandelwal for me all credit goes to Abdul Bari sir... I prepared in very less time with these videos.. as you know 1 or 2 day before the exam.. 🙂
Well explained abdul!!
Just want to correct. T(3) != 5 at 4:40.
Number of ways to insert n pairs of parentheses in a word of n+1 letters, e.g., for n=2 there are 2 ways: ((ab)c) or (a(bc)).
So, to get number of distinct ways with which we can perform matrix chain multiplication, we have to find T(n+1)
hii im confused on T(n) = 2n Cn / n+1. What is Cn? What does it do? Thank you
@@aoyukialquen2835 It's math. Check Permutations and Combinations topic. C for combinations. If you have 4 letters and want to find how many combinations of these letters can be formed with size 2, then the answer is 4C2 = 4!(4-2)!/2! = 4!2!/2! = 4! = 24. But the formula 2nCn/n+1 is taken from a topic "Catalan Number". Hope it helps!
This man literally carries all the computer science students in the world on his back
One of the best tutor... thank you so much sir for such a good explanation.
So thankful to you sir for explaining such complex topics so easily. Thank you very very much.
To all Those who are not understanding he (sir) is filling the table watch at 17:10 min you
will probably understand
explanation
he is filling second table with matrix dimension which gives minimal value thats's it :)
then for m[2,4] entry should be 2 in S table . . but how its 3 ? .... pl explain. TIA
Pl check the next video . . I found the answer there
I see a lot of people asking about the s matrix. I may be wrong as I am learning this rn to but I'll see if I can explain this. The fourth step in dynamic programming is to develop an optimal solution. So we need the s matrix to give us information on where we will put the parentheses when displaying our solution.
This pseudo code is from the Introduction to algorithms textbook on this problem
print0ptimal-parens(s, i, j)
if i == j
print "A"i
else print "("
print0ptimal-parens(s, i, s[i, j])
print0ptimal-parens(s, i[i, j] + 1, j)
print ")"
So essentially the optimal solution is broken down into subproblems which are solved optimally. Once we solve the subproblem optimally, the k value which is where we put the parenthesize will be stored in the s matrix. Lastly, on step 4 of dynamic programming, we recursively go through the s array printing out where the optimal brackets go giving our solution.
Just for reference the four steps of dynamic programming are
1. Characterize the structure of an optimal solution.
2. Recursively define the value of an optimal solution.
3. Compute the value of an optimal solution.
4. Construct an optimal solution from computed information.
Best video for this category. Thx from Italy University.
watch in 1.5x. It is perfect
Don't try and rush. 1x has always been the best.
2x is still slow for me
Exactly been watching his videos at 2x all the time
@@nikhilbalwani2285 well if you've got an exam in less than 24 hours you know you gotta rush
@@avokadotropical3362 Then you've got to start preparing earlier than this. When you watch things 1.5x, 2x, all of it boils down to just procedure, and you lose the essence of teaching.
My prof is insufferable and I can't learn anything from him but Chaddul taught me this in 20 minutes. Not all heroes wear capes. ❤
Every time I was stuck at some problem I would watch your videos :D
Great explanation! I finally completed one topic properly :)
Thank you sir!!
Clear explanation without unnecessary information!!
Thank you sir. I've learned a lot from your videos. Keep teaching us.
For those who are wondering how S-table is filled:
It's more like the value of K we choosing for the minimum value in M-table.
i have gone through all your previous videos and your explanation and everything is really helpful, thanks a lot for making this series of videos , would like you to make videos on different topics , and once again thanks a lot :)
bundle of thanks, I wish Virtual University select instructer like you for Fundamental of algorithem course
At 21:35 Time complexity is not Theta, it is the worst case time complexity so it should be ' big O'
Amazingly explained! Thank youso much!
Thanks a lot sir
Best found Matrix Chain Multiplication explanation 👏🏻
Mr. Bari, Thank you from Yerevan, Armenia
you teach better than every single one of my uni professors
Assalamualiakum Sir, Your Videos have helped me get through my exams.
Sir you are the best.....
Long live Sir 🙏 🤗 may God bless you
sir u r legend .... i was't able to understood the topic untill i watch ur video ....... u r mindblowing sir .......thank you sir.
Mr. Bari is a god. My teacher of data structures & algorithms at University was so bad, Mr. Bari teach me how it's done. When people ask how I passed and learned all of this I reply: Abdul Bari.
Nice..Before watching this video....DP is rocket science for me...But now its been bit easier... Thnx...I recommended this to all my frnds.
Thank You Sir for your simplified explanation.
Sir, Your are the best to visualize DSA, Thank you very much.
This has been a godsend, thank you so much!
thanks alot .. before this video i was totally demoralized ,,almost gave up on topic . after this video.. i am happy now :D . easy and sophistacated.
Such an amazing and lucid video as usual!
Thank you sir your videos helped me understand the concept.
awesome video, much better than my college lessons, thank a lot ❤
Thankyou sir.
May God give you ultimate happiness.
Sir, would you plz explain the method for filling up the "s" table as you are not using a constant rule here.
Mr. Bari has anyone ever told you that you are a suave man because you are!
I guess the S table is getting filled by the value that is on the right of first pair of minimum solution. For example at 14:01 the minimum value is given by 2nd option. 2nd option is (A2.A3).A4 . Here 3 is being considered. Second value of the first pair.
Similarly at 17:15 minimum solution is given by m[1,3]+m[1,4]+5.2.7 . Here 3 is considered. Second value of first pair.
Bro it is value of k it is filled by value of k at which value of k is given the minimum no. Of multiplication
every day I get more impressed of the knowlegde of this guy
My eager to learn and this TH-cam algorithms brought us together
Right now I am only thinking about people who came here for dislike....How can someone just do this...Such a great teacher with awesome explanation and that also for free...Just think before doing this
Sir u r my savior, I love the way u explain its soooo simple and informative
very good! I was confused when reading this topic in an algorithms book. it helps me a lot! Thank!
Thank you sir, this is the best algorithm lesson that I have learned.
Phenomenal explanation, sir! Thank you!
You forgot to explain how you're filling the S matrix.
Yes. It will be the value of the minimum term's 'k'
At the end of the video he explains how do you read the S matrix and there you really understand how he filled it.
This video refers to the logical explanation of the above one th-cam.com/video/_WncuhSJZyA/w-d-xo.html .There you will get the logic behind filling the S matrix
for those who still no understand how S is filled:
just check the variable number which comes before the multiplication (not counting multiplication inside brackets)
if (A2*A3)*A4 then we can see multiplication symbol is after A3 and therefore the value to be filled in S will be 3
^ (not counting multiplication symbol inside brackets)
in [ A1 * A2 ] * [ A3 ] the * symbol comes after A2 thus s value will be 2
this is the easiest way I could think of
im confused on T(n) = 2n Cn / n+1. What is Cn? What does it do? (minute 4:40) Thank you
way better than my professor's teaching, thank you
Sir you're God
Thanks for explanation
Construct the m and s tables by Matrix Chain Multiplication for n = 6 using dynamic programming
technique based on following matrix dimensions.
Hint: by using recurrence relation formula, compute minimum cost of each cell in memorization table.
Matrix. Dimensions
A1. 30*35
A2. 35*15
A3. 15*5
A4. 5*10
A5. 10*20
A6. 20*25
What is tha answer?
Respect respect.. Sir u saved me and i took victory from judgment day (exam) :) : p
Thank you sir, this explanation was amazing!
When you say "who has given us minimum" -- we find which summation is smaller, but HOW are you deciding which matrix to select? at 14:00, for example, why is "3" our result?
Sir , Your way of teaching is very nice .
In 10 minutes I have exam I see video just now
I found a nifty shortcut...multiply the dimensions to get a value for each matrix
e.g. from video 5 4 6 2 7
A1 = 5x4 = 20 - 3rd smallest
A2 = 4x6 = 24 - 4th smallest
A3 = 6x2 = 12 - 1st smallest
A4 = 2x7 = 14 - 2nd smallest
Usually I would connect the two smallest together and build up connecting (multiplying) the next smallest ones
(A1(A2(A3 A4)))
This only seems to work with 4 matrices...I'm looking at a video with 5 matrix chain and I'm thinking of a new handy rule...You label the dimensions according to their relative values:
from the example used (from least to greatest): 2(1), 4(2), 5(3), 6(4), 7(5)
A1 = 5x4 = 20 -> 3-2
A2 = 4x6 = 24 -> 2-4
A3 = 6x2 = 12 -> 4-1
A4 = 2x7 = 14 -> 1-5
This is better to visualize side by side, starting from A1:
A1 A2 A3 A4
3-2 2-4 4-1 1-5
then starting from the dimension with the lowest one (A3), look at the adjacent matrices and ask this question: which one will give me a smaller relative dimension?
Will it be (2-4)(4-1) or (4-1)(1-5)?
(2-4)(4-1) will so then that becomes (2-1)
then continue on. If there are several instances where the same relative smallest dimensions appears, then continue to ask that question and connect adjacent matrices.
now it looks like
3-2 2-1 1-5
(3-2)(2-1) or (2-1)(1-5)?
(3-1) will be the answer, so connect them and repeat
It was just one of my moments getting carried away trying to find a simple pattern :) I'll use the table during my exam though XP great video
@@skylarkenneth3784 awesome trick
@skylarkenneth3784 Great analysis
You are an awesome instructor sir. Thank you very much for your teaching.
A better explanation to the problem than my professor at Georgia Tech ..
Sir teaching method is great please make more videos on programming concepts 🙏
Thank you sir! You helped me a lot understanding analysis of algorithm!
Thank you sir. This was very helpful :)
for those who are not understanding about the s table :-> at which element partition it is giving min .
Sir this video changed my life💀💀💀💀 I love you sir🥰🥰🥰🥰😍😍😍😍😻😻😻😻💘💘💘💘💝💝💝💝💖💖💖💖💗💗💗💗💓💓💓💓💞💞💞💞❣❣❣❣
You are a class teacher sir,just loved all your videos. The way you explain,makes everything look so easy ! Thank you sir :)
Really a good explanation... Really helped me... Thanks 4 this good explanation video... 😊
I learned more from this 20 minutes than staring at CLRS for 10 hours
Are sir aap Kya padhate ho ....ek dum chumma😍😃.....ek hi bar main samj aa gaya☺
According my point view u r the 🌎's best lecturer who teach an algorithms such a nicely & a student understandable language 😊😇 u r filling the student life with full of 🌈thank you very much sir 😊
He teaches with so much patience...
A very good teacher you r
Apke video ko samjhne ke liy phle hmko koi or video dekh ke ana hota h
amazing explaination sir, thank you so much.
sir can you tell me how the fill the second table and select the minmum one diget 17:17
this is why i pay my internet bills
excellent way of communication sir.
I did not get the part of connecting the number nodes with the number of placements of the brackets. For instance, the number of binary trees that can be generated with n=3 is 5 but the number of parantheses for n=3 is 2(n-1). Please clarify.