4.3 Matrix Chain Multiplication - Dynamic Programming 

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

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

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

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.

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

Literally the best channel for learning things in my algorithms class

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!

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

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

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.

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

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

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)

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

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

s matrix not explained properly

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

for the formula we must write under min i

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

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

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

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

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

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

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

Great explanation! I finally completed one topic properly :)

Amazingly explained! Thank youso much!

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

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

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.

Phenomenal explanation, sir! Thank you!

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

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

Best video for this category. Thx from Italy University.

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!

great explanation , got to say it is the best video about D.programing

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

excellent, easy to grasp explanation - thank you!

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

This has been a godsend, thank you so much!

Clearly and Best Explanation thank u for this video Sir.

wow! How did I not find this earlier. Thank you so much!

You are a class teacher sir,just loved all your videos. The way you explain,makes everything look so easy ! Thank you sir :)

sir u r legend .... i was't able to understood the topic untill i watch ur video ....... u r mindblowing sir .......thank you 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. ❤

You are an awesome instructor sir. Thank you very much for your teaching.

Best found Matrix Chain Multiplication explanation 👏🏻

great video, you really helped me with my algorithms class! much appreciation

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

Thanks a lot for such a video. Saved my tons of time. I wish my instructor was like 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.

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

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)

this guy is simply AMAZING !

My eager to learn and this RU-vid algorithms brought us together

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.

Thank you so much sir...it was really awesome explanation...keep it up...

way better than my professor's teaching, thank you

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.

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

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

Mr. Bari, Thank you from Yerevan, Armenia

Thank you sir! You helped me a lot understanding analysis of algorithm!

you teach better than every single one of my uni professors

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

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

Thank you so much... Amazing video... Very helpful !!

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

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

Thank you sir. This was very helpful :)

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

Sir I don't see ur dbms videos online yet!!.... Because of u and Dr GaryBoetticher i learnt dbms concepts..Please upload relational algebra/ tuple calculus topic ...Thanks

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

Sir, please tell me how the combination formula came up or rather the logic behind it??

watch in 1.5x. It is perfect

Thank you sir for this wonderful explanation.

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

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

Awesome... it's very helpful.. love u sir

Awesome explaination Thank you sir

that was absolutely helpful. Thank you!

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

Thank you sir... It helped me a lot😊

Great explanation and visualization!

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

Sir you're God Thanks for explanation

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

Thank you sir your videos helped me understand the concept.

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.

Thank you. You are a savior!

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

very well explained sir!!thankyou

Sir , Your way of teaching is very nice .

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

Thank you from a student at Cal Poly

Very informative. Thank you so much

Thank You Sir for your simplified explanation.