Hello Tushar! Your videos are really very good! They explain exactly how to crack a problem. Just one suggestion, if you could mention complexities (time and space) of each problem giving reason behind it, it would be very useful! Thank for all the videos.
Tum bhot badhiya kaam karta hai Maksood bhai.. Or koi tumko Thank You ni bolta.. Aaj mai tumko Thank you bolne ko aya.. Thankyou bhai.. **jaadu ki jhappi intensifies** tum mereko pass kara dia ❤️🙌
I met a Chinese person on RUclips and now he's with me in WhatsApp. Also, I'm Facebook friends with another person in south China and we met on a Game of thrones fan group. Also try the app 'Hello Pal' it lets you connect with native language speakers around the world.
Great videos tushar. one little thing. Only if you could have told that [2, 3] is the size of the matrix it would have been easier. Great Explanantion anyways. Subscribed already
Time complexity is O(n^3) because number of subproblems is O(n^2) and time per subproblem is O(n). You get the number of subproblems by asking yourself how many subproblems there are where 2 matrices are being multiplied (answer is n-1), then how many subproblems where 3 matrices are multiplied (n-2) and so on until n matrices (n-1 + n-2 + n-3 + n-4 + ... + 1 = O(n^2)). You get the time per subproblem by realizing that the largest subproblem (compute min cost for n matrices) has n possible solutions which you need to compute and then find the minimum of, if the largest subproblem takes O(n) then all other subproblems also take O(n).
For someone doesn't understand why matrix multiplication result is p * q * r, you can look at this article:www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Dynamic/chainMatrixMult.htm
Btw, the reason he keeps track of what is multiplied by what is because *k* = the way you multiplied the matrices. Usually the k you selected (the minimum) is put into a choice table next to the table of multiplications. He doesn't really do much with recording the way he multiplied the matrices in this video.
it would be better if you use bright marker....like black or red...rather than this blue one...because at some places...it was difficult to view clearly. P.s your videos are awesome :)
how to solve Let P be a set of balanced parenthesis strings and P is recursively defined as follows. 1. e is in P, where e is an empty string. 2. If alpha, beta are in P, then (alpha)beta is also in P. Prove that every nonempty balanced parenthesis string can be obtained via rule 2 from a unique alpha-beta pair. Hint: Mathematical induction but induct on what??????
Dear Tushar, great explanation, thank you! Just 1 question, cannot understand the T[i][j] formula you wrote in the end. Could you please elaborate on it a bit more?
it's simple math n-L+1 tells how many continuous groups of L are formed, i+L-1 tells about the last matrix in the current group of L matrices. The rest is self explanatory :)
The formulation you wrote at the end on the table doesn't make sense. You wrote "take the minimum of one number". I guess you wanted to say "take the minimum of the newly computed number and the pre-existing number at T[i][j]". Your code is correct though: T[i][j] = min(T[i][j], q) where q = T[i][k] + T[k][j] + A[i]*A[k]*A[j] and A is the input array.
Hey Tusha, first thanks for cool video. You are assuming the chain is pre sorted in a unique order for multiplication. which could not be the case for [4X2][2X3][3X2][2X4]
***** If in the example above, we call them the matrix 1, 2, 3, 4. In this case, when you consider the two matrix scenario, not only 1x2, 2x3, 3x4, but also it's possible that 4x1 as well. So if (4X1)X2X3 turn out to be the lowest cost, could it still be covered?
in the final recursive equation you said minimu of(something), but there is only one thing inside the bracket. It atleast need 2 things to take a min right? in the equation you shld have put k from i to j
Hi! Can you explain how the formula that you have used in the end will cover all the cases for example will it consider the case T[1][2]+val[0].first*val[0].second*val[2].second for the cell number T[0][2]? As according to the formula for given value of 'i' you are varying 'k' but i can also vary?
thanks for the video,but you should write formula at the begining(clearly) then procede with the table,because after going through the solution now relating it to the formula gets difficult,but thanks anyway :)
This looks like you have crammed the formula and just create video... You should have explained how you thought about the solution rather than just debugging the problem ...
Tushar has done a great job here. If you need further explanation you can request or you can create an explanation video and can provide the link. However, you can refer MIT 6 006 lecture 22 by Prof. Erick and then see this video. You can understand better.
His content is different than the others. He provides the method to fill the table that's it. That's really helpful for many people. If you want deeper explanation you should refer other videos.
If anyone is looking for a more intuitive explanation, I made a 3b1b-styled video, also animating how the DP table is filled at the end ruclips.net/video/wkIUHguF7bs/видео.html
c\10.6 Let A1,...,An be matrices where the dimensions of Ai are di−1 × di, for i = 1,...,n. Here is a proposal for a greedy algorithm to determine the best order in which to perform the matrix multiplications to compute A1×A2×...×An. Algorithm 10.6 (MatrixMultiplicationOrder) Input: Dimension D = (d0, d1,...,dn) of n matrices Output: An array Order in which entry i contains the ith multiplication MaMuOrd(D) 1 At each step, choose the largest remaining dimension 2 (among d1,...,dn−1), and multiply two adjacent matrices 3 that share that dimension. 4 . . . 5 return Order Observe that this strategy produces the optimal order of multiplications for the matrices in the example discussed in class. (a) What is the order of the running time of this algorithm (only to determine the order in which to multiply the matrices, not including the actual multiplications)? (b) Either give a convincing argument that this strategy will always minimize the number of multiplications, or give an example where it does not do so.
Hi Tushar! Very good explanation. Thanks. Between in the link with source code, I see only the optimal cost returned. Do you have a version where the extracting optimal sequence is captured?
The first 3 minutes was complete confusion. You should have atleast introduced by explaining what matrix multiplication is and how matrices can be multiplied. I like your videos, but the dearth of basic intro to problems has always been an issue. I had to go to another video, understand the concept and then come back to listen to the rest of your video. Kindly take this as a constructive suggestion ! Good job otherwise !
There is a lot of comment about Tushar’s video needing an intro. Not every video in every concept needs a long intro. If you need that for every video there are channels that provide that. You come to Tushar’s videos to get to the point. Who else explains CMM in 11 mins?
what is the cost? how are you getting the cost by multiplying those 3 digits? how did you think of filling the table in this manner after knowing the recursive solution? Just filling the table after knowing the solution, I think that's not coding made simple. I hope you see my comment!
greetings from Greece! I have fully understanded this.However,in some exercises they don't give you the actual size of each matrix,but a "size sequence" ...For example, we have matrices A1,A2,A3,A4,A5,A6 with size sequence (2,3,4,5,6,7)...and i cannot understand what that means..Please explain it to me.Btw,I'm not sure if "size sequence" is a valid translation haha
i was a little confused on how to display the odering of multiplication and ur git repo too doesn't have path back tracking implementation ,can u implement path backtracking on ur git repo ?
You know its funny, I watched this video 4 years back when I was in my undergraduate and im returning here today while im doing my Masters.
Thank you
please check this playlist : ruclips.net/p/PLeF0b8iqbx4mogykbd82-HY9Y1-JS9MDr
I Appeared in the Google Inida Interview, In that mail along with JD , they were suggesting to watch @Tushar Roy's video. Great Achievement bro.
You are a Genius , explaining the concept in just 11 minutes . Thanks
You're the only person/resource online that I've seen explain the backtracking well enough to understand. Great job, and thanks!
please check this playlist : ruclips.net/p/PLeF0b8iqbx4mogykbd82-HY9Y1-JS9MDr
Awesome video, this really helped me back when I watched it.
When is your video coming on this problem? He is good but your way of teaching is better.
please check this playlist : ruclips.net/p/PLeF0b8iqbx4mogykbd82-HY9Y1-JS9MDr
the man, the myth, the legend!
Love that recursive code at the end; how it all comes down to a function with only two lines inside it.
Hello Tushar! Your videos are really very good! They explain exactly how to crack a problem. Just one suggestion, if you could mention complexities (time and space) of each problem giving reason behind it, it would be very useful! Thank for all the videos.
Aditi Pawde you saw this video 1 year back??!!!! whyyyyy
those glasses tell you why...
Ravina More you replied to her message 1 year back. Why??
ok
@@pranaytanniru7764 you replied to her message 7 months back. Why??
Tum bhot badhiya kaam karta hai Maksood bhai.. Or koi tumko Thank You ni bolta.. Aaj mai tumko Thank you bolne ko aya.. Thankyou bhai.. **jaadu ki jhappi intensifies** tum mereko pass kara dia ❤️🙌
I have seen all your videos buddy & the code too, these are excellent videos, kudos to you to create them & to have shared them with everyone.
Tushar..this is a very good initiative. Good luck to you! Kudos
watching this video 2024 and its the Best. this man did good job long time ago👏👏👏👏👏
I love Indian people so much! They are so darn good at programming and English, envy envy .. I am from China :) smart Indians
Ha-ha 谢谢你！ By the way I'm helping a person in China learn English and in turn he helps me learn Chinese and Chinese culture :)
I met a Chinese person on RUclips and now he's with me in WhatsApp. Also, I'm Facebook friends with another person in south China and we met on a Game of thrones fan group.
Also try the app 'Hello Pal' it lets you connect with native language speakers around the world.
*on
How do you guys communicate? Whats the common language?
I envy Chinese people so much because of their perseverance and hard working :)
Saving my life on my homework assignment, this and the knapsack problem. Thank you so much!
Best explanation I have seen so far. Thank you.
Seriously good job! explaining the concepts so effectively in that short time...
Thank you Tushar. Your crystal clear explanations really make problems simpler
Beautifully taught! I have watched a bunch of similar videos, and this is the only one that I understood! Thanks Tushar!
Very clear cut and best explanation. Thanks for sharing !!!
Great videos tushar. one little thing. Only if you could have told that [2, 3] is the size of the matrix it would have been easier. Great Explanantion anyways. Subscribed already
+Saras Arya - Good point. I was wondering about that.
m glad i saw this comment before watching the video
exactly
Thanks a lot man! I was looking out for an explanation
在智障边缘被挽救了。。终于理解了动态规划！谢谢小哥哥！
Time complexity is O(n^3) because number of subproblems is O(n^2) and time per subproblem is O(n).
You get the number of subproblems by asking yourself how many subproblems there are where 2 matrices are being multiplied (answer is n-1), then how many subproblems where 3 matrices are multiplied (n-2) and so on until n matrices (n-1 + n-2 + n-3 + n-4 + ... + 1 = O(n^2)).
You get the time per subproblem by realizing that the largest subproblem (compute min cost for n matrices) has n possible solutions which you need to compute and then find the minimum of, if the largest subproblem takes O(n) then all other subproblems also take O(n).
This is great thank you so much. I have an exam today and you cleared this right up for me.
continue doing your thing please cause i see you teach so well
Probably the one of the easiest way of teaching matrix chain :D
sir!! you r best in dynamic programming..........
The savior of my semester
Very nice and easy to understand videos
For someone doesn't understand why matrix multiplication result is p * q * r, you can look at this article:www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Dynamic/chainMatrixMult.htm
your video is still the best one out there! :)
Thank You!!! So much better than my lecture notes
Great Explanation... You made it a lot easier to understand .. Kudos
u nailed it man..... concept clear js b4 exam..
u r far much better than my professors ..
keep up the gud work..bless u
Btw, the reason he keeps track of what is multiplied by what is because *k* = the way you multiplied the matrices. Usually the k you selected (the minimum) is put into a choice table next to the table of multiplications. He doesn't really do much with recording the way he multiplied the matrices in this video.
Thank you Tushar, your videos are wonderful!
Very good teaching!!
it would be better if you use bright marker....like black or red...rather than this blue one...because at some places...it was difficult to view clearly.
P.s your videos are awesome :)
Thanks for the video. The explanation was really clear, video quality was high and overall very well presented. =)
I think I finally understand! Thanks for the explanation. :)
Great tutorial, Simplified to the core , Thanks :D
thanx a lot !! you made it very easy to understand and implement
Came here to find out how to determine the order of multiplication from the table. Thanks.
Recursive solution: product(A,1,3)
product(A,i,j){
i == j ---> return 0;
mini INT_MAX;
for(k=i;k
Awesome Explanation!
The example in the video uses a 4 by 4 matrix. But, the code in github uses a 5 by 5 matrix. And, I think the logic is different for both
Awesome explanation.. now its so clear to me.. tnx.. Subscribed
Arre sir aap toh hero ho
Ohhhh! Thanks man, You are a life Savior!
how to solve
Let P be a set of balanced parenthesis strings and P is recursively defined as follows.
1. e is in P, where e is an empty string.
2. If alpha, beta are in P, then (alpha)beta is also in P.
Prove that every nonempty balanced parenthesis string can be obtained via rule 2 from a unique alpha-beta pair.
Hint: Mathematical induction but induct on what??????
So easily explained!
undoubtedly the clear explanation and thanks for tutorial :)
Dear Tushar, great explanation, thank you! Just 1 question, cannot understand the T[i][j] formula you wrote in the end. Could you please elaborate on it a bit more?
i understood the procedure but how is the code formed.
i am not able to understand the code
Never Give Up Never Give Up !!!
it's simple math n-L+1 tells how many continuous groups of L are formed, i+L-1 tells about the last matrix in the current group of L matrices. The rest is self explanatory :)
This is the best explanation! thanks a lot
very good i understood it very easily thanks
this is just amazing:)
thanx i got the concept in just 11 mins ;)
very good explanation
Good job! Thanks for the help.
Good work !!
The formulation you wrote at the end on the table doesn't make sense. You wrote "take the minimum of one number". I guess you wanted to say "take the minimum of the newly computed number and the pre-existing number at T[i][j]".
Your code is correct though:
T[i][j] = min(T[i][j], q) where q = T[i][k] + T[k][j] + A[i]*A[k]*A[j] and A is the input array.
Nope, its the maximum for the different values of k where k>=i and k
great explanation...thanks alot sir
nice explanation.
Nice explanation! I'm happy that you gave up SimplePickup and that you're teaching computer science now :P
+Tushar Roy There is a guy called Jesse on the youtube channel "SimplePickup" and you reminded me of him. That's why I made this joke :P
nice explanation, thanks a lot!
Sir is looking like Younger brother of ravindra babu ravula
While calculating for l=4, why did we not include the case to multiply 1 and 2 first and then multiply the result with say 0 or 3?
I think there is lack of description of the problem, the pair of number is the dimension of the matrix.
Thanks a lot sir..helped me at the last moment...
This helped so much. Thank you!
beautifully explained :)
Hey Tusha, first thanks for cool video. You are assuming the chain is pre sorted in a unique order for multiplication. which could not be the case for [4X2][2X3][3X2][2X4]
***** If in the example above, we call them the matrix 1, 2, 3, 4. In this case, when you consider the two matrix scenario, not only 1x2, 2x3, 3x4, but also it's possible that 4x1 as well. So if (4X1)X2X3 turn out to be the lowest cost, could it still be covered?
The video just solves the program with no mention of dynamic programming. Forget the code, it doesn't even bring in the concept.
+Tushar Roy , How the matrices are multiplied? I didn't get that. Here every matrices are 1x2. Please reply to me
it would be of great help if you explain the logic behind your solution.
Great Job Man !!!!!
Great Tutorial... i love it....
Awesome way to solve this problem rapidly, brother.
Not recommended for beginners, though.
:-}
what is the relation between i, j and k? How to select k?
in the final recursive equation you said minimu of(something), but there is only one thing inside the bracket. It atleast need 2 things to take a min right? in the equation you shld have put k from i to j
Hi!
Can you explain how the formula that you have used in the end will cover all the cases for example will it consider the case T[1][2]+val[0].first*val[0].second*val[2].second for the cell number T[0][2]? As according to the formula for given value of 'i' you are varying 'k' but i can also vary?
very clear. Thank you!
ekrem hocam
awesome tutorial mann 😀
thanks for the video,but you should write formula at the begining(clearly) then procede with the table,because after going through the solution now relating it to the formula gets difficult,but thanks anyway :)
hi Tushar,
Thanks for your video.I want to practice on white board. One question about your white board.What is size of your white board?
This looks like you have crammed the formula and just create video... You should have explained how you thought about the solution rather than just debugging the problem ...
Exactly!
Tushar has done a great job here. If you need further explanation you can request or you can create an explanation video and can provide the link. However, you can refer MIT 6 006 lecture 22 by Prof. Erick and then see this video. You can understand better.
His content is different than the others. He provides the method to fill the table that's it. That's really helpful for many people. If you want deeper explanation you should refer other videos.
If anyone is looking for a more intuitive explanation, I made a 3b1b-styled video, also animating how the DP table is filled at the end ruclips.net/video/wkIUHguF7bs/видео.html
Thanks! I've forked your GitHub repo.
Thank you! It was really helpful! :)
c\10.6 Let A1,...,An be matrices where the dimensions of Ai are di−1 × di, for i =
1,...,n. Here is a proposal for a greedy algorithm to determine the best order
in which to perform the matrix multiplications to compute A1×A2×...×An.
Algorithm 10.6 (MatrixMultiplicationOrder)
Input: Dimension D = (d0, d1,...,dn) of n matrices
Output: An array Order in which entry i contains the ith multiplication
MaMuOrd(D)
1 At each step, choose the largest remaining dimension
2 (among d1,...,dn−1), and multiply two adjacent matrices
3 that share that dimension.
4 .
.
.
5 return Order
Observe that this strategy produces the optimal order of multiplications for
the matrices in the example discussed in class.
(a) What is the order of the running time of this algorithm (only to determine
the order in which to multiply the matrices, not including the actual
multiplications)?
(b) Either give a convincing argument that this strategy will always minimize
the number of multiplications, or give an example where it does not do
so.
Hi Tushar! Very good explanation. Thanks. Between in the link with source code, I see only the optimal cost returned. Do you have a version where the extracting optimal sequence is captured?
good lecture
In L=-3, you could also multiply 1,2 with 3 which would make the total options of 3 to choose the min cost from. Why did you skip that?
No he did not, at 6:25 he did that.
For L=3 , we have two choices , 0 to 2 and 1 to 3, each with two options.
The first 3 minutes was complete confusion. You should have atleast introduced by explaining what matrix multiplication is and how matrices can be multiplied. I like your videos, but the dearth of basic intro to problems has always been an issue. I had to go to another video, understand the concept and then come back to listen to the rest of your video.
Kindly take this as a constructive suggestion ! Good job otherwise !
Yaeh i felt same
i mean its kinda obvious that if you are learning matrix chain multiplication, you must be having a certain idea about it's basics
Even I felt the same...
There is a lot of comment about Tushar’s video needing an intro. Not every video in every concept needs a long intro. If you need that for every video there are channels that provide that. You come to Tushar’s videos to get to the point. Who else explains CMM in 11 mins?
what is the cost? how are you getting the cost by multiplying those 3 digits? how did you think of filling the table in this manner after knowing the recursive solution? Just filling the table after knowing the solution, I think that's not coding made simple. I hope you see my comment!
Sir ek doubt h ye bataiye hm jo determinant solve krte h to hum usme row ar coloumn dono operation lga skte h yaa fir sirf row or column?
this reminded me of the college lecture to pass the exam
Thanks alot sir !!!
greetings from Greece! I have fully understanded this.However,in some exercises they don't give you the actual size of each matrix,but a "size sequence" ...For example, we have matrices A1,A2,A3,A4,A5,A6 with size sequence (2,3,4,5,6,7)...and i cannot understand what that means..Please explain it to me.Btw,I'm not sure if "size sequence" is a valid translation haha
i don't think so.If that was the case,we would need 1 more number.
It means you have matrices of order 2x3, 3x4, 4x5, 5x6, 6x7.
Do Full video on Theory of Computation
According to sylllabus of IPU/Delh MCA..
i was a little confused on how to display the odering of multiplication and ur git repo too doesn't have path back tracking implementation ,can u implement path backtracking on ur git repo ?
Just Awesome !!!