4.3 Matrix Chain Multiplication - Dynamic Programming

[@yt_akashupadhyay]

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.

[@kunalchouhan3829]

Impressive 👍

[@GateCSE280]

what about s[1,2] =1?

[@yt_akashupadhyay]

@@GateCSE280 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.

[@GateCSE280]

@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

[@aadityaojha1756]

My God..you are next level Man...from where did you get that?? I wish I could meet you once and take your autograph...

[@studyonline3236]

Sir, you've saved my time by investing yours.

[@umangsomani7224]

5:47 se dekh aur 5 min bachege

[@amirshariatmadari9810]

Mr. Bari, Thank you so much for providing free content that explains algorithms simply but also comprehensively.

[@SachinMooZZ]

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.

[@benji1570]

Even though a Taiwanese like me could understand what he is teaching(with his accent), what a miracle

[@Rei816kgu]

Mr. Bari must be tired from carrying me through my algorithms course

[@DG-kv3qi]

carrying us all lmao

[@shivaramgoli6333]

How can we select no of rows and columns for m. And s matrices

[@xiping-pongfatherofchinese3551]

Bsdk sir tujhe jaante v nhi honge!!

[@ramagirisaiganesh3044]

@@shivaramgoli6333 number of matrices that u r multiplying Ex: A1,A2,A3,.....An then take n*n matrix of m and s

[@Alchemace]

@@shivaramgoli6333 On the basis of number of matrices attempt to multiply. here are 4*4 because A1 * A2 * A3 * A4.

[@aadishjoshi2525]

The best video I've ever seen. Referring this video from the University of Texas,USA. Thank you for such a beautiful narration.

[@Thandav0]

Thanks for the video bro

[@kamrancamy1997]

thandav63 bhai tu pagal hai kya??

[@michap21]

Hook 'Em!

[@vinayak186f3]

Kya bhai US ja kr bhi YT par padhai kar rhe ho 😶

[@sanjayvasnani988]

@@vinayak186f3 University/Country changes but YT is constant!

[@viplavkhode2742]

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 👍👍👍👍

[@viplavkhode2033]

Thank you sooo much, you saved my life 🙌🙌🙌🙌🙌

[@rushikeshchoudhary5433]

Beautiful 💓❣️❣️💕❤️❤️

[@khalilkhanmamakhel3951]

dear i am still confused ? are the value of k put in the s table ?

[@viplavkhode2742]

@@khalilkhanmamakhel3951only minimum value of K is added to table S

[@khalilkhanmamakhel3951]

@@viplavkhode2742 tnx dear

[@exapsy]

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)

[@Pixelatory]

Literally the best channel for learning things in my algorithms class

[@manavssingh]

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!

[@ritik84629]

4:32 He used Catalan number to find possible number of binary trees with n nodes

[@nigahrehem9094]

Thanks

[@ibadshakil4051]

After that [1,3] Bari sir why u dont take value [1,4] if some one known that plz answer

[@ibadshakil4051]

After that [1,3] Bari sir why u dont take value [1,4] if some one known that plz answer

[@krishanpalsinghrajput2530]

underrated comment!

[@jaatharsh]

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.

[@avonflex5031]

for the formula we must write under min i

[@adityakumar-kj3ch]

The best teacher I have come across till now...

[@bran_rx]

i like how he stares directly at the camera, feels personal lol... great video, helped me a lot

[@kabichan1]

all professors across the nation should take notes from your teaching, and thank you so much

[@manojmaurya9683]

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

[@ryanhull2472]

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

[@abdullahafzal4768]

wonderful

[@gouravjindal297]

Sir honestly you are the best teacher that I have ever learnt from. You make algorithm so easy subject to understand. Thanks sir

[@jacopotoso6573]

An example is worth a thousand words. Simple and clear video. thank you

[@ubaidhunts]

s matrix not explained properly

[@aryansrikumar347]

He explained it properly

[@umangsomani7224]

Bakchodi mat de

[@hardikvansia3293]

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.

[@sasa_lilac6295]

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

[@ashraf645615]

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

[@ashraf645615]

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 😊

[@sourabhkhandelwal1568]

I am also from RTU, 6th Sem CSE. How was your DAA paper?

[@ashraf645615]

sourabh khandelwal good, what about you?

[@sourabhkhandelwal1568]

Ashraf Mansuri Good paper was easy ,☺

[@ashraf645615]

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

[@hobihobi1563]

you teach better than every single one of my uni professors

[@TridibSamanta]

Great ! You are a great Teacher. Thanks for saving my Design and analysis of Algorithm Paper. #Respect

[@sierr1302]

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

[@FootyPick]

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

[@udbharat_official]

then for m[2,4] entry should be 2 in S table . . but how its 3 ? .... pl explain. TIA

[@udbharat_official]

Pl check the next video . . I found the answer there

[@matthewzarate8851]

This exact recurrence relation was explained in my lecture and in my textbook but it made absolutely no sense. Thank you for explaining it so well! You made it 100% clear.

[@abhishekpatyal7480]

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)

[@aoyukialquen2835]

hii im confused on T(n) = 2n Cn / n+1. What is Cn? What does it do? Thank you

[@coolone5561]

@@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!

[@richasha670]

Sir, you are awesome. Cause it's important, I`ll say it again. YOU ARE AWESOME.

[@anishpaudel29]

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.

[@SARCASMOOO]

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.

[@dharaneeswari-wi8ef]

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

[@Picklerick8859]

Every time I was stuck at some problem I would watch your videos :D

[@mrAmal45]

watch in 1.5x. It is perfect

[@nikhilbalwani2285]

Don't try and rush. 1x has always been the best.

[@praharsh_bhatt]

2x is still slow for me

[@prudvi01]

Exactly been watching his videos at 2x all the time

[@avokadotropical3362]

@@nikhilbalwani2285 well if you've got an exam in less than 24 hours you know you gotta rush

[@nikhilbalwani2285]

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

[@GrumpyCoder]

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.

[@kuravje484]

This man literally carries all the computer science students in the world on his back

[@evanverma1316]

Mr. Bari has anyone ever told you that you are a suave man because you are!

[@jaikrishnapandey632]

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

[@armanhayrapetyan4551]

Mr. Bari, Thank you from Yerevan, Armenia

[@anoygolui1057]

sir u r legend .... i was't able to understood the topic untill i watch ur video ....... u r mindblowing sir .......thank you sir.

[@wajeehsyed5919]

you are my goat, please never change

[@ramneeksehgal1760]

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.

[@nox9765]

Sir Bari you are the GOAT!!!!

[@rajarshiparihar9932]

One of the best tutor... thank you so much sir for such a good explanation.

[@daviddelgado6599]

every day I get more impressed of the knowlegde of this guy

[@giornogiovanna9378]

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

[@aoyukialquen2835]

im confused on T(n) = 2n Cn / n+1. What is Cn? What does it do? (minute 4:40) Thank you

[@ecmuppet9538]

My exam is tomorrow and it has 3 questions and this is one that is on the exam, thank you good sir for your service

[@m.younaschaudhary9363]

bundle of thanks, I wish Virtual University select instructer like you for Fundamental of algorithem course

[@domenico2178]

Best video for this category. Thx from Italy University.

[@abdulmn]

Assalamualiakum Sir, Your Videos have helped me get through my exams.

[@jenishmonpara]

Best found Matrix Chain Multiplication explanation 👏🏻

[@william0377]

way better than my professor's teaching, thank you

[@raviraj8209]

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.

[@jimmyp4584]

So thankful to you sir for explaining such complex topics so easily. Thank you very very much.

[@muzammilmueen3487]

A better explanation to the problem than my professor at Georgia Tech ..

[@SaumyaSharma007]

Sir you are the best..... Long live Sir 🙏 🤗 may God bless you

[@supriyajha7823]

Great explanation! I finally completed one topic properly :)

[@sicals1720]

This guys needs to be in youtube rewind

[@sicals1720]

Thank You for your video Sir,

[@damansaroa]

He teaches with so much patience...

[@MagedT]

Sir, Your are the best to visualize DSA, Thank you very much.

[@prasannareddyisireddy8233]

Thank you sir!! Clear explanation without unnecessary information!!

[@RebeCcaHarOon]

Thank you sir. I've learned a lot from your videos. Keep teaching us.

[@pritpatel4298]

Are sir aap Kya padhate ho ....ek dum chumma😍😃.....ek hi bar main samj aa gaya☺

[@pratikgupta534]

You forgot to explain how you're filling the S matrix.

[@RamkrishanYT]

Yes. It will be the value of the minimum term's 'k'

[@jdurefaccini]

At the end of the video he explains how do you read the S matrix and there you really understand how he filled it.

[@tamzidmahmud6129]

This video refers to the logical explanation of the above one kzbin.info/www/bejne/lYjRlKieiK-Nr6M .There you will get the logic behind filling the S matrix

[@danishiqbal9826]

Respect respect.. Sir u saved me and i took victory from judgment day (exam) :) : p

[@nidhirohani]

Apke video ko samjhne ke liy phle hmko koi or video dekh ke ana hota h

[@dogbertlover2410]

I learned more from this 20 minutes than staring at CLRS for 10 hours

[@vathsavaidhruthi1260]

if you are wondering abt s table .those are the values of k used to get minimum

[@alex-ek8vt]

Daniel Jung from India. Well done :D

[@jixingbian4911]

This dude is my test saver

[@UmangMundhara]

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

[@bancrusher]

The value 𝑆 [ 1 ] [ 3 ] = 2 , S[1][3]=2 means that the best place to split the sequence of matrices 𝐴 1 , 𝐴 2 , 𝐴 3, to (A 1 ​ ,A 2) ​ ,A 3 ​ to minimize the multiplication cost is after the second matrix, dividing the problem into two subproblems: ( 𝐴 1 𝐴 2 ) (A 1 ​ A 2 ​ ) and 𝐴 3 A 3 ​ .

[@milicamisic4011]

awesome video, much better than my college lessons, thank a lot ❤

[@Ashishhd7]

Sir , Your way of teaching is very nice .

[@sheikhaman6218]

My eager to learn and this KZbin algorithms brought us together

[@SRNR_PODCAST.]

a gold mine in youtube

[@NavidullahMuradi]

Thank you sir, this is the best algorithm lesson that I have learned.

[@piyushanayak]

Thankyou sir. May God give you ultimate happiness.

[@venky3867]

Sir you're God Thanks for explanation

[@IvanIvanov-qx5oz]

Says a lot about a problem if it is still kinda hard to follow when this man explains it.

[@AbulAlArabi07]

Thanks a lot for such a video. Saved my tons of time. I wish my instructor was like you

[@shreyashankar7955]

Thank you sir your videos helped me understand the concept.

[@wrestling_hd_core6618]

Sir u r my savior, I love the way u explain its soooo simple and informative

[@宋泰官-h4w]

very good! I was confused when reading this topic in an algorithms book. it helps me a lot! Thank!

[@softwareengineer8923]

Such an amazing and lucid video as usual!

[@himanshusalunke]

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

[@programming_hut]

Thanks a lot sir

[@skylarkenneth3784]

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

[@skylarkenneth3784]

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

[@skylarkenneth3784]

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

[@meet.patel18]

@@skylarkenneth3784 awesome trick

[@Dhoni_7_]

@skylarkenneth3784 Great analysis

[@IamAnsumanDas]

Thank You Sir for your simplified explanation.

[@patchworky]

This has been a godsend, thank you so much!

[@GSEDITZAMV]

Awe mann love your explanation

[@deepanshijain1620]

A very good teacher you r

[@LiLPWNY000]

this guys is the GOAT

[@ethanbai5712]

Amazingly explained! Thank youso much!

[@SRNR_PODCAST.]

for those who are not understanding about the s table :-> at which element partition it is giving min .

[@nitinraja8127]

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!

[@nibeditamisra8999]

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.

[@AnkitTiwari-lf4gb]

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

[@ediellopez1718]

Phenomenal explanation, sir! Thank you!