Thanks for an excellent explanation of the matrix chain multiplication problem! Using a separate object to encapsulate the details of matrix multiplication does make the algorithm a lot easier to follow.
Thanks for such clear explanation of the subject, it was a great help for me while preparing for job interview. I would love to see more of your videos on algorithm interview preparation.
You are very welcome and thanks for the compliment! I hope you got the job =) By the way, I am putting together a list of interview-prep problems so pleas do you let me know if you come across problems that are interesting to discus.
Love the explanation thank u can u explain some example problems that use the mcm? Example given a string "1+2-3+4" we have to place paranthesis such that the result is maximum Or minimum i.e (1+2) -(3+4) is minimum (1+2) -(3) +(4) is maximum
To be honest, I personally have never faced a problem myself where an optimal solution to a problem similar to "matrix chain multiplication" was required. The closest real world use case that I could come up with is in database query optimization. When joining tables, the optimization is tied to the number of rows and columns that each table has. But still, usually there are a lot of other points to consider, like the indexes that are defined on each table, cached results, etc. So some simple greedy rule may actually perform just as well. By the way, in my explanation of the problem, I tried to remove the algebra involved in doing the actual matrix multiplication via MxCost object to make the problem simpler to understand. Ultimately, the goal was to practice Dynamic Programming without getting bogged down too much with the algebra of all the variables involved in filing a table one diagonal at a time. But hey, if you do come across a real world application, please do let me know!
In your recursive, code uploaded in MatrixChainMultiplicationRecursive.java file, static int cost(int p[], int i, int j), what is the array p storing? At 9:17, you created variables of class inside the class itself? Wouldn't it lead to memory allocation issues(stackoverflow.com/questions/9780742/how-can-a-class-have-a-member-of-its-own-type-isnt-this-infinite-recursion)?
It stores the dimensions of matrices. p[0] is the number of rows of the 1st matrix, p[1] is the number of columns of the 1st matrix. Then p[1] is reused as the number of rows of the 2nd matrix, and p[2] is the number of columns of the 2nd matrix. The p[2] is then reused as the number of rows of the 3rd matrix, and so on. Note that I included that function just for reference purposes to illustrate that typical implementation is very hard to read and understand (it's not actually used by my code). It is, however, more memory efficient. Since this is an exercise of DP programming, I feel that it's better to focus on the concept of dynamic programming, rather than debugging i/j/k variable incrementing. Hence the use of the MxCost object. To answer your second question, having a reference to an object of the same type is perfectly OK to do. Think of it this way - when you create a linked list, that's exactly what you are doing. The "node" object has some value AND a reference to another object of the same type as the node. I hope this helps but let me know if you have other questions. Cheers!
It's coming, I promise! I am working on it now. The covid-19 lock down has made it difficult to do this, but I want to make quality episodes that are worth waiting for. On a different note, I added subtitles to old episodes, per your suggestion =)
Thanks for an excellent explanation of the matrix chain multiplication problem! Using a separate object to encapsulate the details of matrix multiplication does make the algorithm a lot easier to follow.
Glad it was helpful!
Great Explaination!!! You truely deserves more views
Thanks! I started this channel not too long ago (at the start of this year). So I hope that as the time goes by, the good word will spread =)
couldn't believe such less views with that sort of explanation
Thanks! And please, spread the word =)
Nice simplified explanation , it make the complex of Matrix Multiplication problem easy to understand and solve
Glad to hear it!
Thanks for such clear explanation of the subject, it was a great help for me while preparing for job interview. I would love to see more of your videos on algorithm interview preparation.
You are very welcome and thanks for the compliment! I hope you got the job =) By the way, I am putting together a list of interview-prep problems so pleas do you let me know if you come across problems that are interesting to discus.
very well explained...best explanation that I know of.Thanks a lot :)
Most welcome! Thank you for leaving a compliment!
Amazing explanation and video quality. Thank you.
Thanks for the compliment; I am glad you liked it!
awesome explanation professor.
Thanks for the compliment =)
amazing video!
I do not understand how we got 354, it is clear that 330 is (A1 * A2 * A3), but where did the rest 24?
Great help ! Thank u
Wonderful! Glad to hear it!
Love the explanation thank u can u explain some example problems that use the mcm?
Example given a string "1+2-3+4" we have to place paranthesis such that the result is maximum Or minimum
i.e (1+2) -(3+4) is minimum
(1+2) -(3) +(4) is maximum
To be honest, I personally have never faced a problem myself where an optimal solution to a problem similar to "matrix chain multiplication" was required. The closest real world use case that I could come up with is in database query optimization. When joining tables, the optimization is tied to the number of rows and columns that each table has. But still, usually there are a lot of other points to consider, like the indexes that are defined on each table, cached results, etc. So some simple greedy rule may actually perform just as well.
By the way, in my explanation of the problem, I tried to remove the algebra involved in doing the actual matrix multiplication via MxCost object to make the problem simpler to understand. Ultimately, the goal was to practice Dynamic Programming without getting bogged down too much with the algebra of all the variables involved in filing a table one diagonal at a time.
But hey, if you do come across a real world application, please do let me know!
May I know what editor did u used for making these video ?
I use HitFilm Express. There is a free version and for my basic needs it's got more than enough fire power.
In your recursive, code uploaded in MatrixChainMultiplicationRecursive.java
file,
static int cost(int p[], int i, int j), what is the array p storing?
At 9:17, you created variables of class inside the class itself? Wouldn't it lead to memory allocation issues(stackoverflow.com/questions/9780742/how-can-a-class-have-a-member-of-its-own-type-isnt-this-infinite-recursion)?
It stores the dimensions of matrices. p[0] is the number of rows of the 1st matrix, p[1] is the number of columns of the 1st matrix. Then p[1] is reused as the number of rows of the 2nd matrix, and p[2] is the number of columns of the 2nd matrix. The p[2] is then reused as the number of rows of the 3rd matrix, and so on. Note that I included that function just for reference purposes to illustrate that typical implementation is very hard to read and understand (it's not actually used by my code). It is, however, more memory efficient.
Since this is an exercise of DP programming, I feel that it's better to focus on the concept of dynamic programming, rather than debugging i/j/k variable incrementing. Hence the use of the MxCost object.
To answer your second question, having a reference to an object of the same type is perfectly OK to do. Think of it this way - when you create a linked list, that's exactly what you are doing. The "node" object has some value AND a reference to another object of the same type as the node.
I hope this helps but let me know if you have other questions. Cheers!
when do u release next episode🤣
It's coming, I promise! I am working on it now. The covid-19 lock down has made it difficult to do this, but I want to make quality episodes that are worth waiting for.
On a different note, I added subtitles to old episodes, per your suggestion =)