1
00:00:03,360 --> 00:00:07,717
Next, to finish off our study of 
recurrence relations, we'll talk about 

2
00:00:07,717 --> 00:00:11,079
the master theorem for divide and conquer 
recurrences. 

3
00:00:11,079 --> 00:00:14,877
and this is very important in the theory 
of algorithms. 

4
00:00:14,877 --> 00:00:18,549
And it's all about. 
Divide and conquer algorithms. 

5
00:00:18,549 --> 00:00:24,689
So many algorithms gained their 
efficiency by attacking a problem of size 

6
00:00:24,689 --> 00:00:30,332
n by, with the following steps. 
first divide it into smaller parts. 

7
00:00:30,332 --> 00:00:36,140
So, in the case of merge sorter was 
divided into two parts of size n/2. 

8
00:00:36,140 --> 00:00:41,726
more generally it might be 
parts of maybe different size. 

9
00:00:41,726 --> 00:00:47,173
So we'll pick a factor beta, so it could 
be n over three or n over four, whatever. 

10
00:00:47,173 --> 00:00:50,347
and. 
Not only that, it might not add up to n. 

11
00:00:50,347 --> 00:00:55,810
So, there might be multiple parts, say 
three parts of size n/2 or seven parts of 

12
00:00:55,810 --> 00:01:00,028
size n/8, or whatever. 
So, parametrize both the number of parts 

13
00:01:00,028 --> 00:01:04,454
and the size of each part. 
Usually they try to do equal sizes, if 

14
00:01:04,454 --> 00:01:08,950
you don't have equal sizes then you have 
even more complications. 

15
00:01:08,950 --> 00:01:13,652
so that's the first thing, divide into 
alpha parts of size n/beta. 

16
00:01:13,652 --> 00:01:19,556
And then solve recursively 
and then put the solution together some 

17
00:01:19,556 --> 00:01:24,351
how with extra cost that is described by 
a standard function. 

18
00:01:24,351 --> 00:01:30,648
and in the theory of algorithms remember 
we don't care about the constant, we just 

19
00:01:30,648 --> 00:01:36,086
want to get the order of growth. 
so, we'll say theta of N to the gamma log 

20
00:01:36,086 --> 00:01:40,301
N to the delta. 
So there's a lot of problems that fall, 

21
00:01:40,301 --> 00:01:45,164
within, this paradigm. 
and again, it's easy to write computer 

22
00:01:45,164 --> 00:01:51,298
programs that have this kind of behavior. 
Just write a recursive program that does 

23
00:01:51,298 --> 00:01:55,337
the things. 
And so, for the theory of algorithms, for 

24
00:01:55,337 --> 00:01:59,751
decades, people have been developing 
computer programs that. 

25
00:01:59,751 --> 00:02:02,836
that. 
Are gain their efficiency by this 

26
00:02:02,836 --> 00:02:06,346
strategy and what we want is to analyze 
them. 

27
00:02:06,346 --> 00:02:12,855
So very early on people started studying, 
general models for computer programs like 

28
00:02:12,855 --> 00:02:18,778
this and that's why, what's called the 
master theorem that we'll talk about 

29
00:02:18,778 --> 00:02:21,338
next. 
So, first, here's some examples. 

30
00:02:21,338 --> 00:02:26,446
So, we did merge sort. 
So for merge sort problem size is n/2 so 

31
00:02:26,446 --> 00:02:31,197
that's beta two. 
two problems of size n/2 two, so that's 

32
00:02:31,197 --> 00:02:34,863
alpha is two. 
and the extra cost is n, so there's no 

33
00:02:34,863 --> 00:02:37,850
log n so delta equals zero, gamma equals 
one. 

34
00:02:37,850 --> 00:02:42,511
So that's merge sort. 
here's another example that's similar, 

35
00:02:42,511 --> 00:02:48,324
So that's Batcher's network for, sorting. 
so that's a different approach to, 

36
00:02:48,324 --> 00:02:51,616
sorting. 
Where we don't do it with programs, but 

37
00:02:51,616 --> 00:02:56,238
we do it with hardware. 
and Batcher's is like Merge Sort, except 

38
00:02:56,238 --> 00:02:59,179
the extra cost has a log n factor. 
So this delta1. 

39
00:02:59,179 --> 00:03:03,996
= 1, that's batcher's network. 
So, now I'm going to only write the ones 

40
00:03:03,996 --> 00:03:09,407
that are valid when N is the power of 
two, taking into account the floors and 

41
00:03:09,407 --> 00:03:15,766
ceilings that are needed for, general N. 
takes us, to another level, that we don't 

42
00:03:15,766 --> 00:03:20,906
necessarily need to worry about, in many 
cases, with the theory of algorithms. 

43
00:03:20,906 --> 00:03:25,980
and so, we'll try not to worry about that 
in this cut at the analysis. 

44
00:03:25,980 --> 00:03:33,188
a famous algorithm that got people 
interested in this was multiplication at 

45
00:03:33,188 --> 00:03:38,180
the beginning people were wondering how. 
[COUGH]. 

46
00:03:38,180 --> 00:03:42,226
Difficult is the problem of multiplying 
two N bit integers. 

47
00:03:42,226 --> 00:03:47,232
It seemed like the best you could do 
would be the grade school method of 

48
00:03:47,232 --> 00:03:53,199
multiplying two N bit integers by taking 
each bit multiply by all the other bits, 

49
00:03:53,199 --> 00:03:57,999
moving over one and then adding up. 
Little N by N table of bits that's going 

50
00:03:57,999 --> 00:04:04,137
to take time proportional to N squared. 
and then the suitable multiplication 

51
00:04:04,137 --> 00:04:10,571
algorithm came along where they showed 
how to multiply input integers by 

52
00:04:10,571 --> 00:04:14,480
dividing into three problems of sizing 
over two. 

53
00:04:14,480 --> 00:04:20,942
and then combining with an extra cost of 
N and so that's the number of steps 

54
00:04:20,942 --> 00:04:24,736
required for that particular 
multiplication algorithm. 

55
00:04:24,736 --> 00:04:30,356
And a related one that's also very famous 
is the Strassen Matrix Multiplication 

56
00:04:30,356 --> 00:04:33,868
Algorithm. 
it seemed that matrix multiplication 

57
00:04:33,868 --> 00:04:38,926
algorithm where you have two N by N 
matrices that you want to multiply 

58
00:04:38,926 --> 00:04:44,124
together to get an N by N result. 
it seemed that for every entry in the 

59
00:04:44,124 --> 00:04:48,480
result you needed to have a dot product 
of a row and a column. 

60
00:04:48,480 --> 00:04:54,412
which is going to require N 
multiplications for each of the n squared 

61
00:04:54,412 --> 00:05:01,135
entry's in the result which would be n 
cubed and but Strassen showed you could 

62
00:05:01,135 --> 00:05:06,909
solve it with a divide and conquer 
algorithm where you divide into seven 

63
00:05:06,909 --> 00:05:14,651
problems besides n/2 and then get the 
final solution with extra N, so, it's an 

64
00:05:14,651 --> 00:05:19,294
algortithm that did metric 
smallification, and a number of 

65
00:05:19,294 --> 00:05:25,459
operations discredit by this reccurence, 
so these are three example of divide and 

66
00:05:25,459 --> 00:05:31,699
conquer algorithms that, all have the 
same general character, and so what the 

67
00:05:31,699 --> 00:05:38,371
master theorm says, is that, it, that 
gives, a, under the supposition that you 

68
00:05:38,371 --> 00:05:42,344
have a problem. 
Size, alpha parts of size n over beta 

69
00:05:42,344 --> 00:05:47,695
with an extra crossed n to the gamma log 
n to the delta, that that's going to lead 

70
00:05:47,695 --> 00:05:52,060
to a recurrence. 
And the recurrence is going to look a lot 

71
00:05:52,060 --> 00:05:57,121
like our merge sort recurrence. 
Except instead of the floors and 

72
00:05:57,121 --> 00:06:03,130
ceilings, we add little tiny constants to 
each one of the problem part sizes. 

73
00:06:03,130 --> 00:06:08,823
because n/beta, when, it has to be an 
integer, so you have to have some floors 

74
00:06:08,823 --> 00:06:14,912
and ceilings in there somewhere or maybe 
the problem size is throw out a few 

75
00:06:14,912 --> 00:06:18,312
terms. 
So, as general as we can do is to get 

76
00:06:18,312 --> 00:06:22,740
alpha terms of the form n/beta+O(1), + 
O(1) and then we add on the X, 

77
00:06:22,740 --> 00:06:29,480
cost, and the master theorem, gives the 
order of growth of the solution. 

78
00:06:29,480 --> 00:06:36,026
and it all has to do with the 
relationship between this extra power 

79
00:06:36,026 --> 00:06:43,678
gamma in the extra cost term and the log 
to the base beta of alpha were alpha is 

80
00:06:43,678 --> 00:06:51,244
the number of part, parts in beta is the 
amount the, the fraction that you divide 

81
00:06:51,244 --> 00:06:56,811
n by. 
so, in what the solution is, is three 

82
00:06:56,811 --> 00:07:02,497
different cases if gamma is small 
compared to log beta of alpha. 

83
00:07:02,497 --> 00:07:09,007
It's n to the gamma log n to the delta. 
if it's equal then there's an extra 

84
00:07:09,007 --> 00:07:13,155
factor of log n. 
and then if gamma is big, so that means 

85
00:07:13,155 --> 00:07:16,600
the extra cost is big. 
Then that's going to dominate. 

86
00:07:16,600 --> 00:07:20,344
and it's n to that power. 
and so, here's a 

87
00:07:20,344 --> 00:07:26,635
In, in the book, it's a little graphic 
way of seeing how these three cases have 

88
00:07:26,635 --> 00:07:31,353
to be different. 
so this is the case that alpha = 3 so we 

89
00:07:31,353 --> 00:07:36,221
have three parts. 
and so it has to do with the relationship 

90
00:07:36,221 --> 00:07:40,714
between our number of parts. 
and the size of each part. 

91
00:07:40,714 --> 00:07:45,357
And the one in the middle is like what we 
did with merge sort. 

92
00:07:45,357 --> 00:07:48,727
If you have three parts of size n over 
three. 

93
00:07:48,727 --> 00:07:54,070
Then the total number of problems that 
you analyze at every case. 

94
00:07:54,070 --> 00:07:59,074
The size of them is going to about add up 
to n at every stage. 

95
00:07:59,074 --> 00:08:02,464
As you see, you divide by three every 
time. 

96
00:08:02,464 --> 00:08:08,517
And then every time you divide by beta, 
you keep going until you get to one. 

97
00:08:08,517 --> 00:08:12,149
So that's the logbeta(n)). 
beta of n, this should say, n at alpha. 

98
00:08:12,149 --> 00:08:19,647
So that gets you down to a problem size 
of with log N steps. you get down to the 

99
00:08:19,647 --> 00:08:26,040
problem size of one, so that's where you 
get the extra log N factor. 

100
00:08:26,040 --> 00:08:35,923
if on the other hand you're dividing into 
so three parts but they're small then 

101
00:08:35,923 --> 00:08:43,890
what's going to happen is that really all 
that matters is the first cost. 

102
00:08:43,890 --> 00:08:47,250
And the rest of them become not so 
significant. 

103
00:08:47,250 --> 00:08:51,730
So, really, the cost of doing it the 
first time is what counts. 

104
00:08:51,730 --> 00:08:56,910
but if your problem sizes are bigger, 
then it's all about the number of 

105
00:08:56,910 --> 00:09:02,230
problems that you get at the end. 
and that's what, n to the log beta of 

106
00:09:02,230 --> 00:09:07,421
alpha comes up. 
So that's the master theorem for Divide 

107
00:09:07,421 --> 00:09:14,693
and Conquer algorithms. 
and, so here's the typical applications, 

108
00:09:14,693 --> 00:09:19,508
so, 
This is for mergesort you get n log n for 

109
00:09:19,508 --> 00:09:23,717
batchers network you get the extra factor 
of log n. 

110
00:09:23,717 --> 00:09:31,227
for karatsuba multiplication you get this 
case here so it's n to the log base two 

111
00:09:31,227 --> 00:09:36,274
of three. 
which is about 1.585 not N squared. 

112
00:09:36,274 --> 00:09:44,882
it's less than N squared and for Strassen 
you get N to the 2.8, it's less than N 

113
00:09:44,882 --> 00:09:49,132
cubed so 
the basic ideal of a master theorm is 

114
00:09:49,132 --> 00:09:54,844
that it gives us good asontotic growth 
rates, as very important for the theory 

115
00:09:54,844 --> 00:10:01,142
of algorithms to help us understand the 
what, we can do in terms of asontotic 

116
00:10:01,142 --> 00:10:05,683
growth rates. 
now there's a lot of versions, that have 

117
00:10:05,683 --> 00:10:11,615
been study, about the master theorm 
there's some cases where you can get 

118
00:10:11,615 --> 00:10:15,350
precise results, like, like we did for 
merge sort. 

119
00:10:15,350 --> 00:10:20,074
and for the most important algorithms 
that people use in practice, and we want 

120
00:10:20,074 --> 00:10:24,740
to predict performance and compare 
algorithms, we have no choice but to go 

121
00:10:24,740 --> 00:10:29,074
there. 
the more general results in the theory of 

122
00:10:29,074 --> 00:10:36,866
algorithms and go even more general than 
where we went in terms of the extra cost 

123
00:10:36,866 --> 00:10:43,152
of doing the combination and those are 
certainly available. 

124
00:10:43,152 --> 00:10:51,032
and then actually very recently a full 
solution, using analytic combinatorics 

125
00:10:51,032 --> 00:10:59,090
was developed by Szpankowski and Dramoda 
that actually captures in general all the 

126
00:10:59,090 --> 00:11:03,470
kinds of oscilations as we determine for 
merge sort. 

127
00:11:03,470 --> 00:11:09,996
Now really appreciating how and why this 
solution works in the way that it does, 

128
00:11:09,996 --> 00:11:16,371
is going be something that's, going to 
require everything that we cover, in the 

129
00:11:16,371 --> 00:11:22,670
analytic commitorics, including part two, 
but people will have some ideal for how 

130
00:11:22,670 --> 00:11:28,286
the mathematics manages to model what 
actually happens in the computer 

131
00:11:28,286 --> 00:11:35,420
algorithm and this is really an important 
contribution of analytic commitorics in 

132
00:11:35,420 --> 00:11:39,542
this case. 
So that's the master theorem for studying 

133
00:11:39,542 --> 00:11:44,565
divide and conquer algorithms and that 
will complete our study of recurrence 

134
00:11:44,565 --> 00:11:47,642
relations. 
Next time I will move on to generating 

135
00:11:47,642 --> 00:11:51,540
functions. 
So here are a few exercises that would be 

136
00:11:51,540 --> 00:11:57,535
worthwhile for you to take a look at to 
cement your understanding of this 

137
00:11:57,535 --> 00:12:01,739
material in order to be ready for the 
next lecture. 

138
00:12:01,739 --> 00:12:07,931
the first one is exercise 2.17. 
there's a particular data structure 

139
00:12:07,931 --> 00:12:14,044
called a two three tree. 
it doesn't matter too much now what it 

140
00:12:14,044 --> 00:12:18,543
is. 
but there was a paper by Yao that proved 

141
00:12:18,543 --> 00:12:25,459
that a certain property of this tree. 
which is described here is described by 

142
00:12:25,459 --> 00:12:32,650
this second order first order recurrence. 
and so it's a complicated first order 

143
00:12:32,650 --> 00:12:36,858
recurrence. 
And so the, the problem is to go ahead 

144
00:12:36,858 --> 00:12:42,290
and solve this recurrence. 
And it's an interesting random process 

145
00:12:42,290 --> 00:12:49,023
and it leads to interesting recurrence 
that's got a solution that's definitely 

146
00:12:49,023 --> 00:12:53,938
of practical interesting. 
[COUGH] here's another one, is to go 

147
00:12:53,938 --> 00:12:57,670
ahead and try divide by three and 
conquer. 

148
00:12:57,670 --> 00:13:01,982
so a sub n = 3 A of floor event over 
three + N. 

149
00:13:01,982 --> 00:13:08,285
So maybe merge sort, by dividing into 
three parts and then doing a three way 

150
00:13:08,285 --> 00:13:12,514
merge. 
and so what is the periodicity in that 

151
00:13:12,514 --> 00:13:17,233
thing look like? 
so again using the same methodology that 

152
00:13:17,233 --> 00:13:23,377
I used for divide by two do this one and 
try to discover the, the interesting 

153
00:13:23,377 --> 00:13:29,163
performance behavior of something like 
this and think about how we might compare 

154
00:13:29,163 --> 00:13:35,044
two algorithms like that. 
now in order to address those you're 

155
00:13:35,044 --> 00:13:40,934
going to again, want to read the chapter 
on recurrences in the book. 

156
00:13:40,934 --> 00:13:45,901
and write up the solution to the 2-3 
trees exercise. 

157
00:13:45,901 --> 00:13:52,660
And then, set up standard draw or come up 
with your own way to plot the value of 

158
00:13:52,660 --> 00:13:57,139
sequences. 
and then go ahead and do, that exercise 

159
00:13:57,139 --> 00:14:00,722
for, plotting divide by three and 
conquer. 

160
00:14:00,722 --> 00:14:07,807
I think doing that work well help you, 
make sure that you understand the 

161
00:14:07,807 --> 00:14:12,540
material that we've done so far and set 
you up for the next lecture.