4.3 Matrix Chain Multiplication - Dynamic Programming
HTML-код
- Опубликовано: 8 сен 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...
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.
Sir, you've saved my time by investing yours.
I was freaking out about taking a quiz on this topic and feeling hopeless till I stumbled upon this guy's explanation. He instantly put me at ease. His voice is so calming.
Even though a Taiwanese like me could understand what he is teaching(with his accent), what a miracle
For those who are still confused with the table S:
It is filled with the min. value of K (K is introduced at 17:50 ).
Example:
for M[2,4] we have selected -> (A2*A3)*A4
which gives
-> M[2,3]+M[4,4]+4*2*7
compare this with :
-> M[i][j] = min { M[i,K]+ M[K+1,j] + .... }
we get K=3
Put the minimum value of K into the table S
Let me know, if you got this 👍👍👍👍
Thank you sooo much, you saved my life 🙌🙌🙌🙌🙌
Beautiful 💓❣️❣️💕❤️❤️
dear i am still confused ? are the value of k put in the s table ?
@@khalilkhanmamakhel3951only minimum value of K is added to table S
@@viplavkhode2742 tnx dear
Mr. Bari, Thank you so much for providing free content that explains algorithms simply but also comprehensively.
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
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!
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!
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.
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
i like how he stares directly at the camera, feels personal lol... great video, helped me a lot
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
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
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.
Great ! You are a great Teacher. Thanks for saving my Design and analysis of Algorithm Paper.
#Respect
for the formula we must write under min i
if you are wondering abt s table .those are the values of k used to get minimum
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)
s matrix not explained properly
Sir, you are awesome. Cause it's important, I`ll say it again. YOU ARE AWESOME.
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!
The best teacher I have come across till now...
An example is worth a thousand words. Simple and clear video. thank you
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 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
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.
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.. 🙂
Sir honestly you are the best teacher that I have ever learnt from. You make algorithm so easy subject to understand. Thanks sir
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. ❤
This man literally carries all the computer science students in the world on his back
all professors across the nation should take notes from your teaching, and thank you so 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
bundle of thanks, I wish Virtual University select instructer like you for Fundamental of algorithem course
One of the best tutor... thank you so much sir for such a good explanation.
Assalamualiakum Sir, Your Videos have helped me get through my exams.
Best video for this category. Thx from Italy University.
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.
Great explanation! I finally completed one topic properly :)
So thankful to you sir for explaining such complex topics so easily. Thank you very very much.
sir u r legend .... i was't able to understood the topic untill i watch ur video ....... u r mindblowing sir .......thank you sir.
Every time I was stuck at some problem I would watch your videos :D
Sir you are the best.....
Long live Sir 🙏 🤗 may God bless you
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. I've learned a lot from your videos. Keep teaching us.
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
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 ruclips.net/video/_WncuhSJZyA/видео.html .There you will get the logic behind filling the S matrix
Best found Matrix Chain Multiplication explanation 👏🏻
Thank you sir!!
Clear explanation without unnecessary information!!
you teach better than every single one of my uni professors
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
Mr. Bari, Thank you from Yerevan, Armenia
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 :)
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.
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
At 21:35 Time complexity is not Theta, it is the worst case time complexity so it should be ' big O'
Thankyou sir.
May God give you ultimate happiness.
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.
Amazingly explained! Thank youso much!
Thank You Sir for your simplified explanation.
Sir, Your are the best to visualize DSA, Thank you very much.
Mr. Bari has anyone ever told you that you are a suave man because you are!
Respect respect.. Sir u saved me and i took victory from judgment day (exam) :) : p
very good! I was confused when reading this topic in an algorithms book. it helps me a lot! Thank!
awesome video, much better than my college lessons, thank a lot ❤
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
Thank you sir your videos helped me understand the concept.
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?
Thank you sir, this explanation was amazing!
every day I get more impressed of the knowlegde of this guy
Thanks a lot for such a video. Saved my tons of time. I wish my instructor was like you
Thanks a lot sir
My eager to learn and this RUclips algorithms brought us together
Thank you sir, this is the best algorithm lesson that I have learned.
Sir u r my savior, I love the way u explain its soooo simple and informative
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 😊
This has been a godsend, thank you so much!
Sir, please tell me how the combination formula came up or rather the logic behind it??
Such an amazing and lucid video as usual!
Sir you're God
Thanks for explanation
way better than my professor's teaching, thank you
Phenomenal explanation, sir! Thank you!
Sir this video changed my life💀💀💀💀 I love you sir🥰🥰🥰🥰😍😍😍😍😻😻😻😻💘💘💘💘💝💝💝💝💖💖💖💖💗💗💗💗💓💓💓💓💞💞💞💞❣❣❣❣
Sir teaching method is great please make more videos on programming concepts 🙏
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☺
A better explanation to the problem than my professor at Georgia Tech ..
for those who are not understanding about the s table :-> at which element partition it is giving min .
Sir , Your way of teaching is very nice .
Really a good explanation... Really helped me... Thanks 4 this good explanation video... 😊
You are an awesome instructor sir. Thank you very much for your teaching.
You are a class teacher sir,just loved all your videos. The way you explain,makes everything look so easy ! Thank you sir :)
Sir, would you plz explain the method for filling up the "s" table as you are not using a constant rule here.
This video lacks something so he has uploaded one more video on the same topic where he explains the same stuffs in much more detailed manner.Great learning!
In 10 minutes I have exam I see video just now
Thank you sir. This was very helpful :)
Thank you sir! You helped me a lot understanding analysis of algorithm!
Aap aagar samne hote to pair pakad leta. 3 din ho gaye aaj Jake example smja hai aapki video ki vajese. 😂. Dil se shukriya sir. ❤
Apke video ko samjhne ke liy phle hmko koi or video dekh ke ana hota h