[New] Matrix Chain Multiplication using Dynamic Programming Formula

hyah topic of this video is Matt exchange multiplication already I have one video in my playlist but there are few things I have missed there in that video so it may be a little bit confusing for the students who are making a new video on the same topic the problem in YouTube is we cannot edit the video I cannot add something to the video so I have to make a new video once again so the contents of the video are what is Mattox multiplication I'll explain this then what does it mean by matrix chain multiplication and how to apply dynamic programming so here I will be giving you the idea approach for solving a problem using dynamic programming right then if you're interested in learning problem solving then don't miss this part then I use the formula of dynamic programming and show you how to solve the problem what should be the approach for solving the problem now the last thing I will show you a example problem and if you are here one day before the examination then you need this one directly so you can directly jump on to this part of the video and you can finish it so you learn how to solve a problem that's all right so how the formula is obtained and all details you have to spend time definitely and if you are watching for learning the problem and learning problem solving then this there are a lot of things to learn from this video so let us start with matrix multiplication first of all matrix multiplication see there are two matrices in this example a and B as of dimension two rows three columns two rows and three columns and B's of dimension three rows and two columns three rows and two columns first of all the condition for multiplying two matrices is the number of columns of the first matrix must be equal to number of rows of second Matrix means these two must be equal that is these two must be equal then multiplication can be done this is the condition for multiplication and how we multiply us we multiply all the elements of a row single row with all the elements of a single column multiply the elements and add their products so that is shown here this is how multiplication is done so this is how one single element is obtained but what is the dimension of the resultant matrix the resultant matrix a into B let us call it as C this is of dimension 2 cross 2 then one more thing total how many multiplications I have done let us see 1 2 3 1 2 3 so 3 how many times 4 times so 2 L multiplications I have done so actually if you see the number of multiplications I have done for getting this result as 2 3 2 to do so so trees 2 and 12 multiplications I have done for obtaining this resultant matrix that is a into B so from this we have to pick a few things first is when two medicines can be multiplied this condition that this must be equal then only multiplication can be done does the important thing second thing what will be the resultant matrix dimension of the resulting matrix the dimension of the resultant matrix will be these two extremes that is number of rows of first matrix and the number of columns of second Matrix that is - gross - this is the second point and the third point that we have to pick up is for generating or multiplying the matrix total how many multiplications are required that is this dimension into this one and this one this is common right this is same so 2 into 3 into 2 so 2 into 3 into 2 these many multiplications are required so these are the important things and one more important thing I will show you that we must know for further understanding see I have two minuses a and B and if you take dimensions total how many are there first second third fourth so two medicines total for dimension but these two must be same so let us call it as one so if we call it as one then total how many dimensions one two three so total three dimensions are the three different values are there right and this is the first matrix of dimension and these are the second matrix dimension and one of the dimension is common so for the two matrices total three different dimensions are there where one of the dimension is common for them so that's all the important things I have highlighted here that is useful for matrix chain multiplication now let us learn about what does it mean by a matrix chain multiplication for explaining Mattox chain multiplication I have an example here I have three medicines even a 2 a 3 and I want to multiply them so there are more than two matrices so and I want to multiply them so first of all check whether they can be multiplied or not see if I take these two medicines than the dimensions this should be matching number of columns of first one should be equal to number of rows of second one yes they are matching they can be multiplied and if I take these two and then see this are matching yes they can be multiplied now these are a 1 a 2 a 3 dimensions also I will label them let us call this as a d 0 and these two are same so let us call both of them as D 1 D 1 and these two are same so this let us call this as and D 2 D 2 and D 3 this labeling may help us afterwards let us I have given the labels now let us proceed so I want to multiply these three medicines now the question is can I multiply all three together no I have to multiply two matrices at a time then what are the possible ways see the first method is I can multiply a 1 with a 2 and the result of it a 3 this is one possible and another possible method is even as it is then a 2 and a 3 I should multiply first then the even should be multiplied with the result of product of a two and a dream so there are two possible methods see whether this one and this one gives same result yes they are associative associative property holds on matrix multiplication whether you multiply these two first then the result with this one or first these two and this with the result you get the same answer so the product of three minuses will be same so you can multiply it any either way now whatever the elements may be there in a 1 a 2 a 3 I am NOT interested in that I am NOT really trying to multiply them I want to know how much efforts I have to put in for multiplying them so let us see if I multiply a 1 with a 2 then total how many multiplications I have to do how many multiplications I have to perform so what are those dimensions 2 3 & 3 4 so total how many multiplications will be done here for multiplying this this is 2 into 3 into 4 these are 24 multiplications this side total 24 multiplications if I'm multiplying madiso say one with a 2 total 24 multiplications I have to perform for those elements now what about this one this is dimensions are 4 2 but how many this if you take this separately no multiplications required for this one so 24 multiplications for this and this is nothing now I have to multiply these two together right this whole thing this whole thing with this one so total how many multiplications required for this this this will be having dimensions to cross 4 right see you remember the resultant matrix will have the dimensions of these two number of rows of first one and number of columns of second one these two and this 1 4 2 so these 2 are same yes multiplication can be done so total how many multiplications for this this is 2 into 4 into 2 so these are 16 multiplications right these are total 16 now if you find out altogether 24 multiplications this side plus 0 multiplication that site plus the sixteen multiplications so this is how much 24 plus 16 40 multiplications I have to do multiplying these two takes twenty four multiplications and this is nothing there's a single matrix is zero then multiplying these two together as two for two so total 40 multiplications are required what about this let us take this the dimensions are 2 3 and this is 3 4 & 4 2 first of all I have to multiply this this is 3 into 4 into 2 so this is 24 and the result of this the dimensions will be 3 2 and what about this side this side will be 0 no multiplications required on this side now when I have to multiply these two together the dimensions are 2 3 and this is 3 do right these are the dimensions like this one and this one so these two are common so same we can multiply these 2 are same we can multiply so total how many multi predictions required for this one 2 into 3 into 2 then plus what about this side 0 what about this side this is total multiplications are 24 24 so 24 plus this is 2 3 6 12 so this is 36 multiplication so total 36 modifications are required so observe this carefully you wash it once again this portion is very important this calculation and from this we can say that if I multiply these 2 first and the result with this one or this is the result of this one the cost of multiplication is different means the number of multiplications I have to perform for getting the results are different so which parentheses ation is better means first I should multiply these two matrices then this with the result of this one that will take only 36 multiplication so it's a small example of just three matrices and there are there is a difference of just 4 so 4 is not a small figure right because the number of matrices are very small we are looking at a very small level if suppose you have mattis's a 1 multiplied with a 2 multiplied with a 3 goes on to a 10 their total cost of multiplication means which mattresses should be multiplied first it is a big problem there so you cannot simply start multiplying a a 1 with a 2 then the result with a trill result is a 4 so it will be very very huge if you find out easier method for multiplying them then it's better so first find out how to multiply them then multiply the matricis so that's it if you have the chain of mattresses for multiplication then first of all find out which multiplication should be performed such that the total efforts put in for multiplying them should be minimized this is Matt exchange multiplication problem so if the chain of mattresses are there that has to be multiplied how the parents addition should be done such that the efforts required for multiplying the medicine should be less see here you can see that if you multiply these two and the result with this one is 40 and this way it is 36 so this is better and if you have 10 mattresses then there may be different possibilities and one of the possibility maybe a best possibility so that's it we have to find out the best possible parenthesis ation such that the total cost of multiplication is minimized now we need a approach for finding the minimum one so dynamic programming approach say is that you should try all possible parenthesis ation and pick up the best one possible all possible one and pick up the best one so for 10 we have to try all possibilities and then whichever is giving minimum you have to take that pattern of multiplication so for 3 how many are there only 2 are there so we tried both of them and we found this is better so we have already done this but this we can't think of doing on 10 mattresses imagine how many possibilities you will have but we must find out all possible from that we should pick up the best one so for this we need some formula that is by using this approach we need some formula let us frame a formula for dynamic programming format exchange multiplications so here already I have an example so this I will convert it into a formula right I have two examples here from this only I will make a formula first of all watch this very carefully am creating or generating a formula from this example so let us say I want to find out the minimum cost for multiplication so I have to find out the cost of one two three so there are three matrices let us say cost of 1 2 3 so I just write C now for cost ok then let us look at this observe this what is this 24 this is the cost of multiplying 1 and do so I will remove this as I move this and this I will say cost of multiplying 1 to 2 and what is the 0 see a was writing 0 that was not required that time I should have skipped but now this is useful you see this is cost of multiplying third matrix with the third Matic something so the cost of this side is 1 to 2 cost of that side is radio 3 and that was 0 and this was 24 this was 24 I will write it right this is 0 24 and 0 so cost of this one and cost of this one so final result what I was getting this was cost of 1 to 2 and this was cost of 3 to 3 and 3 to 3 is 0 because the single matrix then what was this the cost of multiplying these two together these two together so these are the dimensions I have what is this dimension this one this is a d 0 this is d 0 what is this dimension this 1 this is what D 2 this is D 2 so this is nitu and what is this dimension this one last one right what is that D 3 this is d 3 so what are these this is D 0 and this is D 2 and this is D B 0 D 2 D 3 I have multiplied these three and I got the result as 40 now let us convert this also into the formula this is first cost off one come upon cost of multiplying 1 comma 1 itself that 0 it is a single matrix only and what is this cost of 2 2 3 and what is this 24 how to get this 1 this is 3 into 4 into 2 we know interval so and it is cost of multiplying 2 root 3 then what is this cost of 1 comma 1 and this is what cost of 2 comma 3 and what are these dimensions this is this is the first one and that is D 0 this is D 0 right and this is 3 this is an e 1 3 3 is in D 1 yes this is d 1 and this is the last one that is D 3 this is d 3 and this is 36 so I have made it like a formula cost of this side left side cost of right side then cost of multiplying two together so I got it in the form of formula let us observe this if you observe 1 2 3 3 1 1 2 3 so if you observe the first one and the last one are same let us call this as I and this as J and this as I and this as J in both I and J are same then what about this D 0 D 3 D 0 D 3 and this is d1 and this is d2 so let us call this as D I minus 1 and this is J is 3 right this is DG let us call this as D of I minus 1 and this is DJ then what is this this is a 2 & 3 this is 1 & 2 so if this is 1 this is 2 if this is 2 this is 3 this is what I am observing right this is my from the observation I am creating a formula then this is a d1 and this is d2 so it means that that part should come first so let me write a formula so I'll write the formula here I'll write it here see I have to find out the cost off for I Comanche is what this site cost of I comma what is this I should call it as K and this is K plus 1 so I'm here also I should call it as K and this is K plus 1 so now if you observe everything is perfect see see you off or I ke k plus 1 to J see off of I k k plus 1 to J so when you say I J that are 1 3 and these are also 1 3 k is here 2 & 3 k is here 1 & 2 and this is 0 & 3 this is 0 & 3 so I minus 1 J I minus 1 J and this is DK k is 1 first time and k is to that second time so let us call it as DK okay this is K so based on this I will write a formula now this side see off I can cost of left side plus cost of right side k plus 1 to j then plus d of i minus 1 k and DJ dimension i minus 1 into as remove this dimension K into dimension J so have combined these two together in terms of ijk then what K is taking the value K is here first time 1 and second time - so that should come first then this one Sookie can takes the values that are starting from I is what 1 1 so K takes the values from I but less than J K is not becoming 3 K became 1 and K became two that's all out of these two I want minimum I want minimum so this is the formula for Mack Chane multiplication so from examples of just three matrices I have prepared the formula so the idea here is that once again I will tell you this is the cost of multiplying these two sides then what is the cost of left side cost of right side those two are it done here cost of left side and cost of right side how I multiply these by multiplying three dimensions right what about this cost this also multiply these dimensions three dimensions and give the result multiply these three dimensions and get the result it's the same thing so the cost of multiplying two minuses you have to multiply the dimensions and you get the number of multiplications so here is a formula this formula will give you minimum so you should try different values of K here we tried K as 1 than K as a 2 as you have three matrices so only K value can be one and two if you have more mattresses than K value give me 1 2 3 4 so on if you have 10 mattresses up to 9 it will go so this formula says that try all possibilities and pick up the best one minimum 1 what are the possibilities you change the K value so some on this side some on that side so now I will write down the formula here and I will remove this and I will show you how it looks like for for mattresses then afterwards we will solve a problem here I have four mattresses and let us say dimensions are d0 d1 and d2 d3 d4 these are the dimensions what are the possible ways of multiplying those mattresses before match actually multiplying mattresses we want to know which parentheses ation will require less efforts of multiplication so there are many methods of parenthesis ation this is the first one a one with this one a two with the result of 2 3 right 3 4 then a 1 then inside this 3 first I can multiply these 2 then this 1 so this is another pattern solution or even a two-bit result of a 3 or 4 or this site a 4 is left over a 1 with result of a 2 a 3 then this entire thing with a for a first you need to delicately resolute therefore there are five different methods of parents inhalation so if you want to know for four mattresses how many patterns installations are possible five so if you want to know how many multiplications are required for this one so there is a formula called Catalan number as we have four mattresses so you can use that actually the formula is a 2 NC n by n plus 1 but here you have to take n as number of mattresses minus 1 so n should be 4 minus 1 you should not take and as a for just you take 3 and then you get dancer so if there are four mattresses then actual value if I write here is 2 into n minus 1 C of n minus 1 by n minus 1 plus 1 is n only so this will be the formula modified format exchange multiplication so let us put this one I have for Madison so this will be what if I take four mattresses 2 into 4 minus 1 that is a 3 and see this is also 3 by this is n for mattresses are there where n is 4 I have taken in as 4 so this will be 6 C 3 by 4 so 63 by 4 is 6 into 5 into 4 divided by 3 into 2 into 1 whole divided by 4 4 4 gives cancel teeth 2 3 6 cancel so 5 is the answer and if you take n is equals to 5 mantises then take one less for N and put this in this formula then you will get 14 so 4 5 Madison's 14 multiplications are required right foot impossible parent solutions are there for this 5 possible parent solutions are there so out of these 5 we have to pick up the best parenthesis ation that is giving minimum result so this we will do it using the formula so now I will remove this I will use this formula and show you how I can apply that formula on these four mattresses and if I apply what problems I faced then I will show you the solution for that problem then later on we will find example problem so I will use the formula on this for mattresses we don't have the dimensions let them be D 0 D 1 D 2 only when we see the example that time I take some values if I apply the formula the cost of CEO of one to four because four 9s asada that are one before so I is 1 and J is for this should be minimum of minimum of K should take the values greater than or equal to I is what 1 and less than J that is 4 so what are the possible values K can take K can be 1 K can be 2 and K can be 3 3 values are possible for K less than 4 so if I put K as a 1 in this one right what it looks like CEO of I is 1 J is for remember this one comma K is what 1 plus C of k plus 1 K is 1 min ski is 2 k plus 1 is 2 and G is a 4 plus this is D of I minus 1 I is what I got 1 this is 0 D 0 plus K DK k is what now K I'm taking in s 1 K is 1 and this is into sorry and this is into D for this is K value as 1 if I take K value has a 2 this is 1 2 2 plus C or 4 3 2 4 + D 0 + D - sorry into D 2 into D for then if I take K value as a 3 then this is 1 3 plus C of 4 4 plus D 0 into D 3 in 2d for if I expand the formula I get a 3 different tones 3 different values all of this I have to take minimum I'm not writing them in a single line it will be very lengthy on paper and you can do that right so comma comma this common this come on this one so K is 1 K is 2 K is 3 out of this it is trying all possible parenthesis ation right so actually these means if I draw first one means a1 with a2 a3 a4 how they are multiplied we don't know so this is a 1 1 this is 2 2 4 the cost of this and how what is the cost of multiplying these two their dimensions D 0 D 1 and D for then what the second one means second one means a1 with a 2 and this parenthesis then this is a3 and a4 so the parent isolation is done at Matt X 2 K is a 2 so want to go on this side 3 to 4 on this side then cost of this and cost of this then cost of multiplying these two cost of multiplying these 2 then this one last one says a1 a2 a3 and this side is a 4 so the cost of multiplying all 3 with this result 1 2 3 & 4 2 4 1 2 3 & 4 2 4 then the cost of multiplying these two together these 2 together so this is trying all possibilities now if I know the answer if I know the values I can put these values and get the answer so from this you already know two values what are those c1 1 single matrix 0 you remember we have taken it and see for 4 it is 0 this is 0 then what about c2 for let me put it here this I can take it as 0 but C 2 for let me expand c2 for is minimum or it's a formula again K takes the values from 2:00 till 4 so K can take what values K can be 2 and K can be 3 so 2 values it can take now from this if I take the formula C is a 2 J is a 4 I do G's for remember this 2 comma 2 plus C of 3 comma 4 plus dimension 2 into dimension sorry this is 1 and 2 and this is dimension so see I k k plus 1 2 j k is 1 right this is di minus 1 DK and each so you can check it you can pause and check it i have used the formula here where k values 2 IJ and r2 for now see i k k is 3 plus c of k plus 1 that is 4 2 j that is 4 then plus D I minus 1 I is a 2 so d1 into d k k is 3 3 in 2d for oh it means that for finding C of 2 comma 4 again I need formulas 2 comma 4 I need again formula so in this one this value I know 0 4 4 0 then what about the 3 4 so on n I will find out C this thing this thing this entire formula is just one cost here this one what about this what about this what about this I have to find out all of them so it's too lengthy for finding this one first of all I should find out this right and find out these so why can't we first find out these smaller values then go for larger value so what does it mean by smaller value larger value let us check this 4-1 how much 3 so this require three formulas three values right very different values this is 4 minus 2 this is 2 so this required to value sort of which we will pick up anyone then what about 3 1 comma 2 it will have only 1 value and what about three comma four it will have only one value see the difference is one difference is one and differences zero difference is a - right difference is two so it means first I should find out which formulas where the difference of I and J is zero then it is 1 then it is a two then it is a three in this way I should proceed I should not put the formula and first find out this one then for this I have to find out this it will be going expanding like this it's not practical it's not practical then how I should do this one so first I should find smaller values then I can get the larger value and one more important thing you observe here see I have three comma four in this formula I have three comma four here also so if I find out three comma four it is useful at a different places right not just at one place it is useful that a difference list is 4 comma 4 that's the same thing only right so it means how actually we should solve this problem so for this we will prepare a table we will prepare our table four rows four columns now this represents so this is one two three four and one two three four these are row numbers let us call them as I and these are column numbers let us call them as J so what I will do is first I will find out smaller values that is C of 1 1 C of 2 to see off 3 3 and C or 4 for this I will find out means one 1 two 2 three 3 four 4 so this will already 0 I know it right so already I have shown you this one so this will be 0 so I fill them with 0 already then I will find out the values which differences one difference is 1 Mills 4 1 2 2 3 3 4 right C 1 2 & 2 3 & 3 for these values I will find out then the difference with two difference with 3 finally so in this way I will have filled this diagonal than this diagonal than this diagonal and this diagonal so in this way let us find out the cost so let us start finding the cost from smaller values not from the larger value this is okay and what should be the name of that table let us call it as I am calling it as sina cost cost so let us see see in the previous video I wrote it as M because this was a Desai was taking it as M M so M for Mattox multiplications the cost of matrix multiplication you can use any name that is not a shoe now one more table I will make what is that table I'll prepare a table first so this is again four rows four columns four rows four columns I will prepare this is one two three four and one two three four what is this for see out of these three aisle between the minimum one and that cost I'll be writing there yes remember this out of these two I'll be taking the minimum one and I will be writing the cost of 2 comma 4 here 2 comma 4 I will be filling it so I will find out minimum of these 2 so what is the difference between these 2 k value is different k value so k value is a 2 and k values 3 so i need to know for which K value I got this minimum answer k can be 1 K can be 2 k can be 3 so which k has given me a minimum answer so DISA table let us call it as k table okay and in the previous video I was calling it as si table so in the textbooks you will find s as the name so I have taken s only but now here I am using variable K so let us call it as key table K values will be there now I will take an example problem and I will solve it let us see how we can solve it by first solving smaller problems then with the larger problem so in this table already we knows 1 1 2 2 3 3 right and for food now let us fill up the list of the value so I will take some dimensions for the for mattresses and I will solve it so I have taken the dimensions for mitosis are there this is a dimension B 0 and this is D 1 this is D 2 D 3 before for dimensions that is total 5 dimensions starting from 0 onwards 0 1 2 3 4 so format assess I have now as I said that we will use this formula but we will not directly put 1 comma 4 here we will put smaller value so in which way we will start with differences that is a difference 0 difference 1 and defense 2 different 0 already I have fill there so it is just like C of 1 comma 1 if I want C of 1 comma 1 so formula says minimum all right K takes the values greater than or equal to 1 but less than 1 so greater than equal to 1 equal to 1 I can take but less than 1 how I can take so I cannot take any K value so the result of a sea of 1 comma 1 s is ego that's where all that it is 0 similarly for 2 2 3 3 4 4 also it is 0 now we will find out difference 1 so here I will write down C of 1 comma 2 so let us find out C of 1 comma 2 this one I am finding so its minimum of let us put it in the formula formula says that k10 take the values starting from 1 but it should be less than 2 so yes K can take only 1 value that is 1 so let us put it if I make K as 1 then what it will be C of 1 comma k k is what 1 K I'm taking it as 1 so 1 C of 1 comma 1 plus C of k plus 1 case what 1 so 2 then J J's what to this is I this is J remember this so 2 2 plus D of I minus 1 is 1 so B 0 into D K that is a d1 into DJ that is d2 with only one K value possible so this is only the value so that itself is minimum so find out what are D 0 D 1 D 2 so D 0 is how much 3 right and D 1 is how much D 1 is a 2 and D 2 is how much D 2 is a 4 then what about C 0 0 already we have it in a table that is the benefit we will get now if you start from smaller values for soldering such formulas this is 0 plus 0 plus this one how much it is two-three-six-six for 34 so the result of 1 comma 2 is 34 so I will write here 24 first time I do I got and for which value of K I got that 24 1 comma 2 here K value K value was 1 so put it as 1 so key of 1 comma 2 is 1 that K value has given us the result now let us find out C of 2 comma 3 cost of 2 comma 3 so here I write score of 2 3 I is 2 and J is 3 so this is minimum of K can take the values starting from 2 but should be less than 3 so only one value that K can take that is 2 so C of I comma k k is what only possible values 2 i comma k plus c of k plus 1 to j j is 3 right then plus dimension of a k minus 1 that is a D 1 into K then jc2 2 we already have it in the table 0 3 3 also 0 plus D 1 D 2 D 3 D 1 D 2 D 3 2 4 2 so two for two so how much this is 0 plus 0 2 4 8 and 8 into 2 16 so this value is 16 so I will land on the value 16 here this is 16 + 4 which value of K we got that as 16 4 K value as a 2 so 2 comma 3 is 2 right now next value C of next is 3 comma 4 okay so I will not explain simply I will write off okay to save your time and my time so here already I have written it so only your time is saved because I have written this one so C of 3 food 3 food so K takes values from 3 to 4 so only 1 K value is possible that is 3 so I have taken K value as 3 so these are the costs plus the dimension so tossed a zero cost is zero and this is 4 into 2 into 5 so that is 4 into 2 into 5 so 5 force 20 in 20 into 2 and that is 40 what is the answer so the cost of 3 4 is how much 40 cost of 3 comma 4 is 44 which value of K we got this K value as a 3 so this is 3 comma 4 is 3 which K value has given so one diagonal is over now next diagonal these 2 values with a difference of 2 so I will remove this and I will find out the values for those 2 so the first one is 1 comma 3 so cost of 1 comma 3 cost of 1 comma 3 formula says that minimum K takes the values greater than equal to 1 and less than 3 right so what are the possible values ki can take K can be 1 and K can be 2 K cannot be 3 because it should be less than 3 so let us try both these K as 1 C is 1 and J is 3 remember this 1 comma 3 you remember this so 1 comma 1 see off 2 to 3 plus D 0 into D 1 into D 3 K value is 1 here you put this in the formula you get this one then here C of 1/2 C of 3 3 plus D 0 into D 2 into D 3 these are the two now what are the values this is 0 1 1 is 0 2 3 C 1 1 is 0 2 3 is 16 16 Plus this has to be added dimensions 0 1 3 0 is a 3 1 is the to 3 years - so how much this is 3 - 6 6 - 12 12 plus 16 s 28 so this is 28 so here I will write on 28 many K is 1 what about this c1 2 c1 2 is 24 this is 24 c3 3 is 0 + D 0 D 2 D 3 D 0 3 4 + 2 so 3 into 4 into 2 3 4 - L to L into 2 24 24 plus 24 this is what he ain't so which one has minimum this one is minimum so what is the value of K K is 1 and it is 28 so CEO of 1 3 is 28 and 4 which value of K we got this one K value is 1 that's it now the next one this one right this is to the for C of 2 - 4 I will write down this and explain you so here C of 2 to 4 K can take the values from 2 to 3 so 2 + 3 so if you put 2 here get this n3 it is this one so what is this let us take them and it's 2 2 2 is 0 & 3 to 4 3 to 4 is how much 40 40 plus dimensions I will right afterwards first let us fill up this C of 2 to 3 C of 2 to 3 is how much is 16 16 plus 0 so this looks a smaller ok let us first put the dimensions of first one right what are the dimensions of this D 1 D 2 D for D 1 D 2 D 4 2 4 5 2 into 4 into 5 what about this d1 d3 d4 2 2 5 so 2 into 2 into 5 how much is this 5 4 is 20 into 2 that is 14 40 80 this is 80 and how much is this - 2 4 4 5 20 and this is 36 this is 36 so this is minimum what is the value of K K is at 3 right so how much is this 36 so 2 comma 4 is 36 and for which value of AK a we got this one K as a 3 so kick ass 3 this is 2 comma 4 is 3 only one value is remaining what is that C of 1 comma 4 so I'll remove this and I will find out C of 1 comma 4 C of 1 comma 4 minimum what are the possible values of K K can take the values from 1 2 less than 4 minutes 3 so K can be 1 K can be 2 and K can be 3 so I will expand these then we will put the values and see the result so here I have taken different K values K 1 and K s 2 and K s T so let us write down the values and get the result C 1 1 is 0 C 2 4 is 36 this is 36 and plus D 0 D 1 D 0 and d 4 C this is a 3 and this is a 5 so this is 3 and this is 5 and in between D 1 is 2 B 1 is 2 and what about this C of 1 2 1 2 is 24 and 3/4 3/4 is how much 40 40 plus these dimensions this is 3 and this is a 5 and in between we have D 2 D 2 is 4 then 1 comma 3 1 comma 3 is 28 28 one gamma-rays 28 this 1 plus 4 comma 4 is 0 Plus this is 3 and this is 5 in between D 3 is there that is true sort of this which is minimum let us check 3 2 6 6 5 30 and this is 36 so this is 86 and this is four fives 20 20 into 360 so this is 101 24 this is 124 and this one is 28 and this is 3 2 6 6 5 30 30 and 28 this is 58 so which value K has a 3 has given us minimum value that is 58 and K as a 3 that's it so I got the table filled based on the formula now this means that cost of multiplying these four matrices of these dimensions minimum cost is 58 imagine if you follow other methods the number of multiplications may be 124 or maybe this is 86 so it is much more than this one this is more than double so if you have a 10 Brandi mattis's and you want to multiply them first of all find out how you should multiply to save your time then start multiplication right so we got that the best method will give you 58 number of multiplications so you have to perform only 58 multiplications for performing multiplication of these four matrices so that is the optimal result a minimal result right now how the parent this ization should be done which should be multiplied first then next what how the multiplication should be done that's what the important task is we want the parent is ization so who will give you the parent station this table will give you the K values will give you so let us find the parent in addition by following this K table right that is s table so I will remove this and I will parenthesize these four mattresses based on this so I have four mattresses that is a 1 a 2 a 3 a 4 right now how the parenthesis addition should be done follow this see this is the final answer the final answer I remember this this is 1 comma 4 so when you have 1 2 4 then may the paranthesis addition should be done at a tree at a tree you have to do from one before you have to do parents in a tree so at a tree you put the balances for step algorithm once again so that you can separately see them ok this is a 4 so I have written them once again so this is the first parent is happenin so I have taken once again now this is only one matrix when one more text is there you don't have to worry what about these 3 comma 3 1 comma 3 is how much 1 so parent isolation should be done at 2 1 so this has to be separated then definitely what is left over now this is 2 2 trees left over because you will be multiplying two minuses this is separated like how I have separated this ok I should have put parentheses here also see when it was 1 2 4 again I am showing you so it was said that K is 3 we said that K is 3 so I had the 3 I have separated and that side separated now within this bracket 1 2 3 1 2 3 said that 1 2 3 is 1 so put a bracket at 1 then to do 3 goes on that side no this is complete this is total parenthesis Asia so this means that a 1 should be multiplied with the result of a-two a-three and their result should be multiplied with a four so I will show you diagrammatically so as per the brackets if you see a 2 a 3 are multiplied right these two are multiplied then a 1 is multiplied with this then a 4 is multiplied with this final result so this is how multiplication should be done this should be multiplied with the product of this and this should be multiplied with the product of this that's all so from this table I have done the parentheses ation once again I will show you one to four say is three so put a bracket at the three so from one to three right this is food to four separate then one two three says one two three says put a bracket on one put a bracket one one remaining are two and three so two three is a single product that is two minus S one multiplication right don't have to check further so if you check this is 2 comma 3 then you will get 2 only so this says that put a bracket like this like this ok so don't have to do it further if you are doing also you will get the brackets like this so this or the multiplication should be done all right so that's all about the example problem no if you are interested in knowing how much time it will take for finding out the parenthesis ation of matte exchange multiplication how much time it has taken so I have filled the table right that table and this one how many values are there in that one so if you come from here 1 then 2 then 3 then 4 so it means 1 plus 2 Plus 3 plus 4 so this is nothing but 4 into 5 by 2 for n mattis's it will be n into n plus 1 by 2 so the time taken for filling that is n square but how I am getting each value so if you consider this 158 I tried all possible values of K and I got that one so key is taken the values from I to J so let us assume that is all so and so that value is not just computed in a so that value is computed by taking different K values so let us say n values we are taking so it is into n n square into n so it is n cube and we can say this is upper bound we can say upper bomb Big O and cube so at most n cube that is the meaning because K is not always taking n value so if you want to go in detail analysis and take all possible values of KS and check it thoroughly also it may be somewhat less than n cube so let us say upper bound is ng so that's all about maddux chain multiplication problem that's all in this video

Channel: Abdul Bari

Views: 281,428

Keywords: Matrix Chain Multiplication, Dynamic Programming, DP

Id: _WncuhSJZyA

Length: 52min 1sec (3121 seconds)

Published: Sun May 12 2019