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

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

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

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

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

[@amirshariatmadari9810]

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

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

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

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

[@avonflex5031]

for the formula we must write under min i

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

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

[@TridibSamanta]

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

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

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

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

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

[@ShadowzSharma]

5 years and this is the hidden gem. not for coding but definitely for academics

[@richasha670]

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

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

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

[@kabichan1]

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

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

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

[@priyankabehera8288]

For s table: Put k value i

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

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

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

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

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

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

[@kuravje484]

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

[@Picklerick8859]

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

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

[@abdulmn]

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

[@m.younaschaudhary9363]

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

[@armanhayrapetyan4551]

Mr. Bari, Thank you from Yerevan, Armenia

[@hobihobi1563]

you teach better than every single one of my uni professors

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

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

[@rajarshiparihar9932]

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

[@domenico2178]

Best video for this category. Thx from Italy University.

[@wajeehsyed5919]

you are my goat, please never change

[@SaumyaSharma007]

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

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

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

[@jenishmonpara]

Best found Matrix Chain Multiplication explanation 👏🏻

[@MagedT]

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

[@supriyajha7823]

Great explanation! I finally completed one topic properly :)

[@daviddelgado6599]

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

[@nox9765]

Sir Bari you are the GOAT!!!!

[@nabhpatel3040]

Timestamps 00:01 - Matrix Chain Multiplication is about multiplying matrices and finding the number of multiplications required. 02:29 - Matrix multiplication involves choosing the optimal way to parenthesize matrices. 04:55 - Dynamic programming is an efficient method to try out all possibilities and pick the best one 07:33 - Matrix Chain Multiplication involves finding the cost of multiplying matrices 10:26 - Matrix Chain Multiplication - Dynamic Programming 13:36 - The minimum cost for matrix chain multiplication is 1 16:28 - Matrix chain multiplication formula is M[i][j] = min(M[i][k] + M[k+1][j] + d[i-1]*d[k]*d[j]) 19:13 - Matrix Chain Multiplication follows a specific formula and determines the order of multiplication. 21:42 - Matrix chain multiplication is an n^3 operation, solving the parent isolation problem.

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

[@evanverma1316]

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

[@jimmyp4584]

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

[@RebeCcaHarOon]

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

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

[@vathsavaidhruthi1260]

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

[@piyushanayak]

Thankyou sir. May God give you ultimate happiness.

[@shreyashankar7955]

Thank you sir your videos helped me understand the concept.

[@prasannareddyisireddy8233]

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

[@Ashishhd7]

Sir , Your way of teaching is very nice .

[@pritpatel4298]

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

[@danishiqbal9826]

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

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

[@william0377]

way better than my professor's teaching, thank you

[@sheikhaman6218]

My eager to learn and this KZbin algorithms brought us together

[@NavidullahMuradi]

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

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

[@wrestling_hd_core6618]

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

[@softwareengineer8923]

Such an amazing and lucid video as usual!

[@venky3867]

Sir you're God Thanks for explanation

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

[@milicamisic4011]

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

[@alex-ek8vt]

Daniel Jung from India. Well done :D

[@IamAnsumanDas]

Thank You Sir for your simplified explanation.

[@AbulAlArabi07]

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

[@damansaroa]

He teaches with so much patience...

[@shauryaawashti9472]

Sir this video changed my life💀💀💀💀 I love you sir🥰🥰🥰🥰😍😍😍😍😻😻😻😻💘💘💘💘💝💝💝💝💖💖💖💖💗💗💗💗💓💓💓💓💞💞💞💞❣❣❣❣

[@dineshbh3837]

At 21:35 Time complexity is not Theta, it is the worst case time complexity so it should be ' big O'

[@patchworky]

This has been a godsend, thank you so much!

[@sicals1720]

This guys needs to be in youtube rewind

[@sicals1720]

Thank You for your video Sir,

[@SzulcMarcin]

Thank you sir, this explanation was amazing!

[@ubaidhunts]

s matrix not explained properly

[@aryansrikumar347]

He explained it properly

[@umangsomani7224]

Bakchodi mat de

[@amindalvand9965]

Forget about that matrix. Just set the parentheses due to the chosen minimum equation from the smallest to the biggest

[@laxmanchoudhary2367]

Best explanation, twist i like after 19:20 about table S

[@Minecraft-hl2ik]

Why I'm writing that, I'll explain after sometime😁.... Thank You so much sir

[@arpansaha7369]

Sir, would you plz explain the method for filling up the "s" table as you are not using a constant rule here.

[@ediellopez1718]

Phenomenal explanation, sir! Thank you!

[@muzammilmueen3487]

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

[@priyankamanna4550]

Sir teaching method is great please make more videos on programming concepts 🙏

[@zamirmushtaq2911]

excellent way of communication sir.

[@swapnilmahmud7746]

I’m from bangladesh.Sir you are best.

[@ethanbai5712]

Amazingly explained! Thank youso much!

[@宋泰官-h4w]

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

[@anayaanson8095]

Really a good explanation... Really helped me... Thanks 4 this good explanation video... 😊

[@CryptosFX]

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?