1
00:00:00,012 --> 00:00:07,092
And next it will be worthwhile to 
consider a detailed example to set the 

2
00:00:07,092 --> 00:00:14,784
stage by illustrating the kinds of 
mathematical techniques that, that we 

3
00:00:14,784 --> 00:00:19,674
were using. 
So let's use a classic application for 

4
00:00:19,674 --> 00:00:25,517
the analysis of algorithms. 
and a very ubiquitous, structure in 

5
00:00:25,517 --> 00:00:29,742
computer algorithms and implementations 
is a binary tree. 

6
00:00:29,742 --> 00:00:35,442
And so, one question that arises is, how 
many bits do you need to represent a 

7
00:00:35,442 --> 00:00:40,561
binary tree with N internal node? And 
there's many applications of this for 

8
00:00:40,561 --> 00:00:45,019
example there's data compression 
algorithms that involve building a code 

9
00:00:45,019 --> 00:00:49,439
that's represented with a binary tree and 
then transmitting the binary tree. 

10
00:00:49,439 --> 00:00:52,675
And you want to do it with the least 
number Bits 

11
00:00:52,675 --> 00:00:59,874
So the answer which is kind of direct 
from information theory is that if you 

12
00:00:59,874 --> 00:01:06,547
know the number of different binary trees 
with N internal nodes then you need log 

13
00:01:06,547 --> 00:01:10,215
base 2 of that many bits. 
because otherwise, you couldn't 

14
00:01:10,215 --> 00:01:14,607
distinguish between, there'd be two trees 
you couldn't distinguish between. 

15
00:01:14,607 --> 00:01:18,889
So, you need at least log base to TN, 
where TN is the number of binary trees, 

16
00:01:18,889 --> 00:01:23,387
with N internal nodes. 
so then the question returns the reduces 

17
00:01:23,387 --> 00:01:28,360
immediately to accounting question. 
How many binary trees are there within 

18
00:01:28,360 --> 00:01:33,615
internal nodes? so that's a classic 
application of analysis of algorithms. 

19
00:01:33,615 --> 00:01:38,525
We have this practical problem and we, 
and we want to solve this accounting 

20
00:01:38,525 --> 00:01:41,353
problem. 
So the first step in, in the classic 

21
00:01:41,353 --> 00:01:46,682
analysis of algorithms is to go ahead and 
develop a recurrence relation. 

22
00:01:46,682 --> 00:01:53,765
A binary tree is a recursive structure 
where you have a node that has exactly 2 

23
00:01:53,765 --> 00:01:58,496
sub trees, 
a left sub tree and a right sub tree and 

24
00:01:58,496 --> 00:02:04,316
if there's k nodes on the left then 
there's n-1k nodes on the right. 

25
00:02:04,316 --> 00:02:11,342
So we can write down this mathematical 
recurrence relation on the bottom left. 

26
00:02:11,342 --> 00:02:13,911
There. 
T sub N is equal to the sum for all K 

27
00:02:13,911 --> 00:02:16,752
between 0 and N-1 of the product of these 
two. 

28
00:02:16,752 --> 00:02:20,416
You can have any tree on the left, and 
any tree on the right. 

29
00:02:20,416 --> 00:02:25,794
and then we add a chronic of delta, for 
zero, because we say there's exactly one 

30
00:02:25,794 --> 00:02:29,702
binary tree with zero nodes to make the 
recurrence work. 

31
00:02:29,702 --> 00:02:34,863
And over in the right here is this small 
case, is it's showing there's one tree 

32
00:02:34,863 --> 00:02:40,049
with one node, two trees with two nodes, 
three trees with five nodes, 14 trees 

33
00:02:40,049 --> 00:02:44,544
with four nodes and so forth. 
So that's the first step, develop a, a 

34
00:02:44,544 --> 00:02:49,211
recurrence relation. 
Now the next step is to introduce what's 

35
00:02:49,211 --> 00:02:54,297
called a generating function to try and 
solve that recurrence relation. 

36
00:02:54,297 --> 00:03:00,143
Use that mathematical relationship to try 
to get an explicit expression for the 

37
00:03:00,143 --> 00:03:05,944
number of binary trees of n nodes. 
and the generating function is just sum 

38
00:03:05,944 --> 00:03:09,595
for all n. 
the number of trees with n nodes times z 

39
00:03:09,595 --> 00:03:12,499
to the n, 
Where z's a, a free variable. 

40
00:03:12,499 --> 00:03:16,779
T of z is defined to be the sum for all n 
of t sub nz to the n. 

41
00:03:16,779 --> 00:03:22,042
and, so, on the right hand side. 
we have a double sum. 

42
00:03:22,042 --> 00:03:28,195
Sum for N greater or equal 0 and then the 
recurrence, TKTN minus k, sub [INAUDIBLE] 

43
00:03:28,195 --> 00:03:31,871
k times Z of N. 
and then the delta N0 just reduces to a 

44
00:03:31,871 --> 00:03:35,354
1. 
so we, now we have an expression for T of 

45
00:03:35,354 --> 00:03:38,603
Z. 
And what we're going to do is manipulate 

46
00:03:38,603 --> 00:03:44,072
the sums on the right hand side, to 
express them, in terms of T of Z. 

47
00:03:44,072 --> 00:03:51,052
And the way to do that, is to switch the 
order of summation, put the sum on n 

48
00:03:51,052 --> 00:03:57,816
inside the sum of k outside. 
So, it's the sum all positive k, sum and 

49
00:03:57,816 --> 00:04:02,902
bigger than k, tn minus k, tn, tk, tn 
minus 1, minus k, z to n. 

50
00:04:02,902 --> 00:04:08,522
And then the next thing you can do is 
change n to n plus k plus 1. 

51
00:04:08,522 --> 00:04:13,190
and that will allow us to separate the 
sums. 

52
00:04:13,190 --> 00:04:19,390
so TN minus 1 minus K becomes t sub n, z 
to the n, becomes, Zn plus k plus 1. 

53
00:04:19,390 --> 00:04:25,178
And now that allows us to distribute and 
separate the sums. 

54
00:04:25,178 --> 00:04:29,854
So t of z equals 1 plus z, 
Sum on k, TkZ to the K, sum on N, TNZ ^ 

55
00:04:29,854 --> 00:04:38,099
N, and both of those are nothing more 
than T of Z so we have a, an explicit 

56
00:04:38,099 --> 00:04:44,522
relationship on the generating function. 
T of Z equals 1 + ZT of Z squared. 

57
00:04:44,522 --> 00:04:49,707
So starting with the recurrence, we end 
up with a functional equation that the 

58
00:04:49,707 --> 00:04:54,274
generating function must satisfy. 
That's the second step in classic 

59
00:04:54,274 --> 00:04:58,225
analysis of algorithms. 
Now, the third step is to take that 

60
00:04:58,225 --> 00:05:03,954
functional equation and use it to extract 
the coefficients, to tell us what TN is. 

61
00:05:03,954 --> 00:05:09,484
That's what we're after. 
So the functional equation is from the 

62
00:05:09,484 --> 00:05:12,892
last slide, T of Z is 1 plus ZT of Z 
squared. 

63
00:05:12,892 --> 00:05:18,015
we can use a quadratic formula to solve 
that. 

64
00:05:18,015 --> 00:05:22,941
and so just, it's just a quadratic in T 
of Z. 

65
00:05:22,941 --> 00:05:30,352
so just manipulating the algebra. It 
turns out to be 1/2, 1 plus or minus 

66
00:05:30,352 --> 00:05:35,612
square root of 1 minus 4z. 
has to be minus, out of the 2 choices for 

67
00:05:35,612 --> 00:05:41,942
it to come out right for, and equal 0. 
and then, 1 minus 4z, that's 1 minus 4z 

68
00:05:41,942 --> 00:05:45,949
to the half power. 
So we can use the binomial theorem, or 

69
00:05:45,949 --> 00:05:51,486
the generalized version of the binomial 
theorem, due to Newton to express that as 

70
00:05:51,486 --> 00:05:55,677
1/2 choose N, a generalized binomial 
coefficient, minus 4Z to the N, sum, 

71
00:05:55,677 --> 00:06:00,207
summed over all N. 
So that's direct from the, generalized 

72
00:06:00,207 --> 00:06:05,427
binomial theorem. 
now, there, on the left hand side, our 

73
00:06:05,427 --> 00:06:09,672
coefficient is t to the n. 
On the right hand side, 

74
00:06:09,672 --> 00:06:13,737
Well, we have to make a variable change 
to n to n plus 1. 

75
00:06:13,737 --> 00:06:20,577
but setting coefficients equal, now we 
have this explicit expression for t sub n 

76
00:06:20,577 --> 00:06:23,515
minus 1/2. 
1/2 choose N plus 1 minus 4 to the n plus 

77
00:06:23,515 --> 00:06:27,366
1. 
That's the an explicit expression for the 

78
00:06:27,366 --> 00:06:33,769
number of binary trees with N nodes. 
Now we can simplify that using the 

79
00:06:33,769 --> 00:06:41,041
definition of the generalized binomial 
coefficient so, on the bottom you have 

80
00:06:41,041 --> 00:06:47,672
the n+1 factorial and on the top, you 
subtract, 1, 2, up to n+1 from the 1/2 

81
00:06:47,672 --> 00:06:54,848
and so we get this expression here, which 
looks a little bit, unwieldly, but You 

82
00:06:54,848 --> 00:07:00,172
know, it's not, not too difficult. 
the next thing we can do is, out of the 

83
00:07:00,172 --> 00:07:03,804
minus 4 to the N plus 1, you take minus 2 
to the N, and put them into those 

84
00:07:03,804 --> 00:07:09,667
factors, and you get the odd numbers. 
and then there's a 2 to the n left over. 

85
00:07:09,667 --> 00:07:12,817
and another one goes to cancel out the 
1/2. 

86
00:07:12,817 --> 00:07:17,017
so you can check that. 
That's, just, arithmetic. 

87
00:07:17,017 --> 00:07:22,092
and now, we're getting close to a, pretty 
simple, expression. 

88
00:07:22,092 --> 00:07:27,692
because what you can do is write the 2 to 
the n as 2 over 1, 4 over 2, 6 over 3, 

89
00:07:27,692 --> 00:07:32,526
and like that. 
and now, on the top, we're going to have 

90
00:07:32,526 --> 00:07:36,044
2N factorial. 
On the bottom, we're going to have 

91
00:07:36,044 --> 00:07:41,654
another, N factorial factor. 
and that gets us down to an explicit 

92
00:07:41,654 --> 00:07:44,812
solution, T sub N equal 1/N plus 1, 2N 
choose N. 

93
00:07:44,812 --> 00:07:49,018
These are famous numbers known as the 
Catalan numbers. 

94
00:07:49,018 --> 00:07:52,683
This solution's been known for a few 
centuries. 

95
00:07:52,683 --> 00:07:57,061
That's the third step in classic analysis 
of algorithms. 

96
00:07:57,061 --> 00:08:02,843
So now, our question was, how many bits 
do we need to represent a binary tree 

97
00:08:02,843 --> 00:08:08,625
with n internal nodes? And our answer is, 
you need a least log of the Catalan 

98
00:08:08,625 --> 00:08:09,882
numbers' 
bits. 

99
00:08:09,882 --> 00:08:13,450
but that's not quite a satisfactory 
answer. 

100
00:08:13,450 --> 00:08:19,396
if you've got a program that's trying to 
figure out how to do it for a 1,000 nodes 

101
00:08:19,396 --> 00:08:25,419
you've got to figure out how to calculate 
the number of bits from that expression 

102
00:08:25,419 --> 00:08:30,125
or it's for a million nodes. 
it's not so clear maybe need some 

103
00:08:30,125 --> 00:08:35,212
expertise in numerical analysis. 
and when you think about this sort of 

104
00:08:35,212 --> 00:08:40,341
problem people today think, well, once I 
have a mathematical expression. 

105
00:08:40,341 --> 00:08:44,123
I can just, call a math package, and, and 
get the answer. 

106
00:08:44,123 --> 00:08:49,111
And that's, maybe, sort of the case of 
having a computer or calculator do it. 

107
00:08:49,111 --> 00:08:53,862
But think back to the classical, 
mathematicians in the 18th and 19th, 

108
00:08:53,862 --> 00:08:59,176
17th, 18th, and 19th centuries. 
They did all these calculations by hand, 

109
00:08:59,176 --> 00:09:05,249
and so they're looking for, really 
efficient ways to, calculate things, not 

110
00:09:05,249 --> 00:09:10,009
using a computer at all. 
And in fact, what's called asymptotics, 

111
00:09:10,009 --> 00:09:15,614
or asymptotic estimates, has been really 
a, played a central role in scientific 

112
00:09:15,614 --> 00:09:20,702
calculations for, for centuries. 
and so, there's a, a vast array of 

113
00:09:20,702 --> 00:09:26,629
techniques available to us to so a little 
bit better job than giving a complex 

114
00:09:26,629 --> 00:09:32,027
mathematical expression. 
and perhaps the most famous example of 

115
00:09:32,027 --> 00:09:37,454
that is Stirling's approximation, 
developed in the 18th century. 

116
00:09:37,454 --> 00:09:43,850
And it says that log of N factorial, is 
about N log N - N + log square root of 2 

117
00:09:43,850 --> 00:09:47,429
pi N. 
And actually that squared of 2 pi, was 

118
00:09:47,429 --> 00:09:53,324
not known, for, quite awhile. 
That was Stirling's, contribution. 

119
00:09:53,324 --> 00:09:59,805
and it's a very accurate approximation 
and a lot easier to compute than log of N 

120
00:09:59,805 --> 00:10:04,830
factorial. 
even for 100, so this table just gives 

121
00:10:04,830 --> 00:10:11,151
what the, 460 is N log N, the 360.52 is 
what you get when you subtract N, 363.74 

122
00:10:11,151 --> 00:10:15,624
is what you get when add N log, the 
square root of 2 pi N. 

123
00:10:15,624 --> 00:10:22,332
So it's very close even for 100. 
And for large It remains, very close. 

124
00:10:22,332 --> 00:10:29,157
For a thousand, it's accurate to within 
2, and for 10,000, it's still very close. 

125
00:10:29,157 --> 00:10:33,762
Extremely, accurate, approximation, to ln 
n. 

126
00:10:33,762 --> 00:10:40,201
and the rationale for using 
approximations of this sort is that we 

127
00:10:40,201 --> 00:10:47,259
can get very precise numbers which is 
really what the scientist wants for 

128
00:10:47,259 --> 00:10:51,665
specific values. 
not only that, we get, using just a few 

129
00:10:51,665 --> 00:10:56,573
standard functions, we get concise 
representations of the functions that, 

130
00:10:56,573 --> 00:11:01,537
that we care about that are in a 
canonical form that, that we can work 

131
00:11:01,537 --> 00:11:05,008
with. 
and not only that by adding more terms, 

132
00:11:05,008 --> 00:11:10,110
we can have what's called asymptotic 
expansions, where we can get the accuracy 

133
00:11:10,110 --> 00:11:13,117
we want. 
just by adding more terms. 

134
00:11:13,117 --> 00:11:19,272
In all the methods that we consider have 
that property and this was developed over 

135
00:11:19,272 --> 00:11:25,462
and used and successfully over many years 
by many scientists and mathematicians. 

136
00:11:25,462 --> 00:11:31,567
Just mentioned a few Euler and Poincare 
and Bruijn just from different centuries 

137
00:11:31,567 --> 00:11:37,980
but there's many many others. 
that, have developed and work with, 

138
00:11:37,980 --> 00:11:44,310
asymptotic expansions and they play a key 
role in the analysis of algorithms. 

139
00:11:44,310 --> 00:11:49,310
For example, for our problem, we have 
this solution, 

140
00:11:49,310 --> 00:11:55,572
1/N + 1, 2N choose, N. 
and actually, to put it in a convenient 

141
00:11:55,572 --> 00:12:01,791
form for applying Stirling's 
approximation, we just write that as e to 

142
00:12:01,791 --> 00:12:07,646
the log of it, and so the log of 2n 
choose n, is log of 2n factorial -2 log 

143
00:12:07,646 --> 00:12:12,872
of n factorial, and then there's a -log 
of n + 1, for the 1 over n + 1. 

144
00:12:12,872 --> 00:12:18,859
And now we can apply Stirling's 
approximation to the first two terms. 

145
00:12:18,859 --> 00:12:23,817
in the second term is very close to log 
in, of course. 

146
00:12:23,817 --> 00:12:29,770
so just substituting that in, we get a a 
long expression. 

147
00:12:29,770 --> 00:12:37,038
log of 2n factorial just using Sterling's 
approximation is about 2n, log 2n minus 

148
00:12:37,038 --> 00:12:42,883
2n and plus log squared of 4n. 
and then the next 2 log n factorial, 

149
00:12:42,883 --> 00:12:49,963
that's the next term 2 n log N minus n 
plus log squared to pan, and then there's 

150
00:12:49,963 --> 00:12:54,057
a minus log N. 
And now it's just a little bit of algebra 

151
00:12:54,057 --> 00:12:59,807
just to practice your algebraic ability 
just to check that this is true. 

152
00:12:59,807 --> 00:13:05,912
So log of square root 4 pi n minus 2 log 
of square root of 2 pi n equals minus log 

153
00:13:05,912 --> 00:13:10,836
of square root of pi n. 
so with a pencil and paper, you can 

154
00:13:10,836 --> 00:13:16,142
figure that out. 
and then the 2 log 2N most of it cancels 

155
00:13:16,142 --> 00:13:21,562
and all that's left is 2N log 2 minus the 
square root of log pi N minus the log N. 

156
00:13:21,562 --> 00:13:27,749
And then if we undo the exp-log we get 
that asymptotic estimate for the number 

157
00:13:27,749 --> 00:13:32,778
of binary trees with n nodes. 
And that's a very accurate asymptotic 

158
00:13:32,778 --> 00:13:37,952
estimate, it's very close to, very, very 
close to 1/N plus 1 2N choose N. 

159
00:13:37,952 --> 00:13:43,349
But it's much more useful. 
we can, and if we want more accuracy we 

160
00:13:43,349 --> 00:13:47,675
could get it. 
but that's in, in a standard form and 

161
00:13:47,675 --> 00:13:54,364
even by hand you can compute values or if 
you want to answer our question, how many 

162
00:13:54,364 --> 00:13:59,037
bits do you need for binary tree of 
internal nodes? you can answer it 

163
00:13:59,037 --> 00:14:02,242
directly, it's about 2N minus 1.5 log 
base 2 of N. 

164
00:14:02,242 --> 00:14:07,419
And even a working programmer is going to 
say, oh that's a little less than 2,000 

165
00:14:07,419 --> 00:14:12,078
bits for N equals 1,000. 
And by the way, it's actually easy to 

166
00:14:12,078 --> 00:14:17,508
represent a binary tree with 2 end bits. 
You just do a preordered traversal, an 

167
00:14:17,508 --> 00:14:22,834
output of 0 when you hit an internal node 
and a 1 when you hit an external node. 

168
00:14:22,834 --> 00:14:28,110
So that kind of answer is very satisfying 
to programmers, you can do it with a 

169
00:14:28,110 --> 00:14:33,906
little less than 2 N bits, you can do it 
2N bits and the best you could possibly 

170
00:14:33,906 --> 00:14:39,216
do is a little less than 2N bits and 
that's the kind of answer that, that we 

171
00:14:39,216 --> 00:14:42,974
want to see. 
So that's a very classic application of 

172
00:14:42,974 --> 00:14:47,567
analysis of algorithms. 
And particularly, in the 60s' and 70s' 

173
00:14:47,567 --> 00:14:52,908
and even 80s' there were a wide, wide 
variety of problems that needed to be 

174
00:14:52,908 --> 00:14:57,571
studied in this way. 
So, so, that's the basic summary. 

175
00:14:57,571 --> 00:15:02,718
Develop a recurrence relation. 
Derive an equation of the generating 

176
00:15:02,718 --> 00:15:05,556
function. 
Extract the coefficients. 

177
00:15:05,556 --> 00:15:11,051
Do an asymptotic approximation. 
classic techniques in analysis of 

178
00:15:11,051 --> 00:15:15,039
algorithms. 
And so when Philippe and I started our 

179
00:15:15,039 --> 00:15:21,160
careers we had learned this, we knew the 
math and well we learned more math and 

180
00:15:21,160 --> 00:15:25,872
are able to do this and able to attack 
many, many problems. 

181
00:15:25,872 --> 00:15:32,092
but our challenge was that we had to face 
the idea of teaching this stuff to 

182
00:15:32,092 --> 00:15:37,601
computer science students and 
particularly as the years started to wear 

183
00:15:37,601 --> 00:15:43,210
on we got into maybe 1980, the students 
had lots of computer science but not so 

184
00:15:43,210 --> 00:15:46,694
much math. 
So a, a challenge that, that we faced 

185
00:15:46,694 --> 00:15:52,811
just in furthering our, our, being 
successful as teachers and researchers is 

186
00:15:52,811 --> 00:15:57,556
how we're going to efficiently teach this 
stuff to CS students. 

187
00:15:57,556 --> 00:16:02,661
This is a type of thing that anybody who 
wants to use a computer effectively 

188
00:16:02,661 --> 00:16:08,547
really needs to know how we're going to 
teach it To CS students, so that's the 

189
00:16:08,547 --> 00:16:14,512
first major theme in the story. 
we knew the math, we knew how to analyse 

190
00:16:14,512 --> 00:16:19,120
the algorithm, how we're going to teach 
other people to do it.