1
00:00:00,050 --> 00:00:00,470
All right.

2
00:00:00,500 --> 00:00:07,550
Now that we know how the recursive tree looks like, writing the code for this would be pretty straightforward.

3
00:00:07,550 --> 00:00:10,880
Let's go ahead and write the pseudocode for this approach.

4
00:00:10,880 --> 00:00:16,550
So we are going to have a helper function which in this case we have just called find cost.

5
00:00:16,550 --> 00:00:23,420
And to this function we'll have to pass two input parameters which is the start index and end index

6
00:00:23,420 --> 00:00:29,930
to identify the range of indices that we are considering in the array, which is given to us to form

7
00:00:29,930 --> 00:00:31,730
the applicable matrices.

8
00:00:31,730 --> 00:00:38,270
So to find cost, I will be passing I and j and I'll have the body of the function.

9
00:00:38,270 --> 00:00:42,500
And when you first call the function after we have written this right.

10
00:00:42,500 --> 00:00:49,340
So when we first call the function, we have discussed that we have to pass the start index as one and

11
00:00:49,340 --> 00:00:53,600
the last index of the array, which is given to us as the end index.

12
00:00:53,600 --> 00:00:56,810
So over here I have one and n minus one.

13
00:00:56,810 --> 00:01:03,080
And again the reason why this is one and not zero is because to form the first matrix I'll need the

14
00:01:03,080 --> 00:01:05,300
first two values in the array.

15
00:01:05,330 --> 00:01:11,930
Now to write the body of the find cost function, we'll have to consider the base case as well as the

16
00:01:11,930 --> 00:01:12,950
recursive case.

17
00:01:12,950 --> 00:01:14,630
Now the base case will be.

18
00:01:14,630 --> 00:01:19,490
If I is equal to j then we can just return zero okay.

19
00:01:19,490 --> 00:01:21,020
Now why is this the case?

20
00:01:21,020 --> 00:01:26,240
It's the case because when I is equal to J we are just dealing with one matrix.

21
00:01:26,240 --> 00:01:30,800
And to reduce one matrix to one matrix there are no multiplications involved.

22
00:01:30,800 --> 00:01:31,100
Right.

23
00:01:31,100 --> 00:01:35,450
So that's why we are returning zero which implies zero multiplications.

24
00:01:35,450 --> 00:01:37,340
Now you can see an example over here.

25
00:01:37,340 --> 00:01:42,320
When we had find cost one comma one, we were just considering this matrix over here.

26
00:01:42,320 --> 00:01:45,410
And we were able to return zero in a similar manner.

27
00:01:45,410 --> 00:01:46,070
Find cost.

28
00:01:46,070 --> 00:01:52,220
Let's say three comma three would just mean this one matrix over here which has the dimensions 30 into

29
00:01:52,220 --> 00:01:52,760
five.

30
00:01:53,090 --> 00:01:53,630
All right.

31
00:01:53,630 --> 00:01:55,580
So we're done writing the base case.

32
00:01:55,580 --> 00:01:58,430
Now let's go ahead and write the recursive case.

33
00:01:58,430 --> 00:02:05,480
Now when we see that I is not equal to J then we would use another variable which we typically call

34
00:02:05,480 --> 00:02:05,900
k.

35
00:02:05,900 --> 00:02:09,440
And k will take the values from I to j minus one.

36
00:02:09,440 --> 00:02:16,880
And for each value of k we will find the cost, or we'll find the number of multiplications involved.

37
00:02:16,880 --> 00:02:21,230
When we partition the array in a way such that k takes the value at hand.

38
00:02:21,230 --> 00:02:25,130
For example, when k takes I, we're doing one particular partitioning.

39
00:02:25,130 --> 00:02:30,920
When k takes the value I plus one, we are taking another way of partitioning array and it goes on in

40
00:02:30,950 --> 00:02:31,550
that manner.

41
00:02:31,550 --> 00:02:34,520
So k will take the values from I to j minus one.

42
00:02:34,520 --> 00:02:39,320
And then we'll find the cost involved for all the values k can take.

43
00:02:39,320 --> 00:02:44,420
And then the minimum between these would be the value that we ascribe to cost.

44
00:02:44,420 --> 00:02:44,810
Okay.

45
00:02:44,810 --> 00:02:46,640
Now let's make some space over here.

46
00:02:46,640 --> 00:02:51,620
We have already discussed over here how to find the cost for a particular value of k.

47
00:02:51,620 --> 00:02:51,980
Okay.

48
00:02:51,980 --> 00:03:00,020
So when k for example in this case k was equal to one, we had to find the cost from I up to k and from

49
00:03:00,020 --> 00:03:01,280
k plus one up to j.

50
00:03:01,280 --> 00:03:04,340
And then the cost of multiplying these two matrices.

51
00:03:04,340 --> 00:03:12,110
So in a general manner we can say that the cost for a particular value of k would be find cost I comma

52
00:03:12,110 --> 00:03:19,760
k plus fine cost k plus one comma j plus the cost of multiplying these two matrices.

53
00:03:21,160 --> 00:03:24,880
Once they are reduced to just one matrix on each side.

54
00:03:24,910 --> 00:03:30,760
Now, these two things, these two aspects are pretty straightforward because we have done this many

55
00:03:30,760 --> 00:03:36,760
times, but this aspect is sometimes a little bit confusing to students.

56
00:03:36,760 --> 00:03:41,140
And for that reason, let's take a closer look at that for this.

57
00:03:41,140 --> 00:03:42,970
First, let's take an example.

58
00:03:42,970 --> 00:03:45,910
Let's say we are trying to multiply two matrices.

59
00:03:45,910 --> 00:03:50,890
And let's say the dimensions involved are one into two and two into three.

60
00:03:50,890 --> 00:03:57,100
Now we have already seen that the cost of multiplying these two arrays is one into two into three.

61
00:03:57,100 --> 00:03:59,050
Now we have discussed that in a previous video.

62
00:03:59,050 --> 00:04:05,080
Notice that in this example over here, the matrices involved when this is the array which is given

63
00:04:05,080 --> 00:04:13,450
to us are 20 into ten, which is what is represented by this side into ten into 40 which is represented

64
00:04:13,450 --> 00:04:14,320
by this side.

65
00:04:14,320 --> 00:04:21,430
So we are trying to actually multiply two matrices which have the dimension 20 into ten and ten into

66
00:04:21,430 --> 00:04:21,940
40.

67
00:04:21,970 --> 00:04:23,530
In this example over here.

68
00:04:23,530 --> 00:04:25,750
And this was pretty straightforward.

69
00:04:25,750 --> 00:04:28,510
We are just considering this single matrix.

70
00:04:28,510 --> 00:04:32,710
But this was formed by multiplying these three matrices.

71
00:04:32,710 --> 00:04:42,280
And when we multiply these three matrices which had the dimension ten into 30 and 30 into five and five

72
00:04:42,280 --> 00:04:48,970
into 40, notice that the final matrix will have the dimensions ten into 40.

73
00:04:49,000 --> 00:04:56,350
Now let's use this to generalize it and try to clearly understand what the cost is for multiplying the

74
00:04:56,350 --> 00:04:58,630
two matrices at the two sides at hand.

75
00:04:58,630 --> 00:05:05,830
So we have seen that this side over here will be a matrix of dimensions array at I minus one into array

76
00:05:05,830 --> 00:05:06,340
at k.

77
00:05:06,400 --> 00:05:11,650
Similarly this side over here, which in the example over here reduces to.

78
00:05:11,650 --> 00:05:17,620
This matrix will have the dimensions array at k into array at j.

79
00:05:17,620 --> 00:05:22,300
Because notice k plus one is equal to two in this example.

80
00:05:22,300 --> 00:05:23,980
And over here we have ten.

81
00:05:23,980 --> 00:05:29,500
And that's index one which is one less than k plus one okay which is just k.

82
00:05:29,500 --> 00:05:32,980
So that's why this dimension is array at k.

83
00:05:32,980 --> 00:05:38,890
And this dimension is the value at the last index which is array at four.

84
00:05:38,890 --> 00:05:41,350
Or in a generalized manner I can say array at j.

85
00:05:41,470 --> 00:05:47,950
So what you discussed so far is this side over here reduces to array at I minus one into array at k.

86
00:05:47,950 --> 00:05:52,060
And this side over here reduces to array at k into array at j.

87
00:05:52,120 --> 00:05:58,990
And when we are trying to multiply these two matrices we know that the cost involved is array at I minus

88
00:05:58,990 --> 00:06:02,020
one into array at k into array j.

89
00:06:02,020 --> 00:06:04,120
And that's what we have seen over here as well.

90
00:06:04,120 --> 00:06:04,510
Right.

91
00:06:04,510 --> 00:06:06,940
And we have discussed this in a previous video also.

92
00:06:06,940 --> 00:06:13,960
So when we multiply two matrices which have these dimensions the cost involved is array at I minus one

93
00:06:13,960 --> 00:06:16,360
into array at k into array at j.

94
00:06:16,360 --> 00:06:19,450
So that's this aspect in this equation.

95
00:06:19,450 --> 00:06:24,130
So we have discussed in detail the recursive approach for solving this question.

96
00:06:24,130 --> 00:06:27,250
And we have also come up with the pseudocode for solving this.

97
00:06:27,280 --> 00:06:33,310
In the next video let's discuss the space and time complexity for the recursive approach for solving

98
00:06:33,310 --> 00:06:34,600
the matrix chain multiplication.