1
00:00:01,196 --> 00:00:06,724
In recent years, a lot of people have 
asked me just what the phrase analytic 

2
00:00:06,724 --> 00:00:11,722
combinatorics actually means. 
In this lecture, I'm going to describe 

3
00:00:11,722 --> 00:00:16,253
what the field is and tell the story of 
how it came into being. 

4
00:00:16,253 --> 00:00:21,575
I think this context is important for 
anyone who's interested in learning 

5
00:00:21,575 --> 00:00:26,587
anything about the field. 
this lecture is dedicated to the memory 

6
00:00:26,587 --> 00:00:31,687
of my friend and colleague, Philippe 
Flajolet, who really was the driving 

7
00:00:31,687 --> 00:00:37,417
force behind the development of the field 
and who died suddenly in 2011. 

8
00:00:37,417 --> 00:00:43,672
I'll start off with a brief history to 
try to give some context for how we got 

9
00:00:43,672 --> 00:00:47,032
there. 
I first met Philippe in 1977. 

10
00:00:47,032 --> 00:00:53,947
my first research paper that I wrote 
after getting my Ph.D. was on an 

11
00:00:53,947 --> 00:01:00,517
algorithm called Odd-Even Merging and I, 
I went to a, in those days you would get 

12
00:01:00,517 --> 00:01:05,213
your paper typed by a secretary and go to 
a conference and present it. 

13
00:01:05,213 --> 00:01:10,219
and I was very proud to have developed 
this formula that involves the gamma 

14
00:01:10,219 --> 00:01:15,761
function and the zeta function, and gives 
a precise description of the performance 

15
00:01:15,761 --> 00:01:21,697
of this particular algorithm. 
and just a few months later we had a 

16
00:01:21,697 --> 00:01:27,007
conference in Providence, Rhode Island, 
where I was at the time. 

17
00:01:27,007 --> 00:01:33,196
and in, in those days you go to the 
conference and the first thing you do in 

18
00:01:33,196 --> 00:01:38,697
the proceedings is go and and look at the 
table of contents and recedings and see 

19
00:01:38,697 --> 00:01:41,827
what's there, and there was another type 
paper. 

20
00:01:41,827 --> 00:01:46,910
And I was amazed to see a formula very 
much like mine involving the zeta 

21
00:01:46,910 --> 00:01:51,555
function and the gamma function even 
though it was studying a completly 

22
00:01:51,555 --> 00:01:55,748
different problem. 
and just as I was realizing that, 

23
00:01:55,748 --> 00:02:01,122
Philippe came up to me and said, I 
believe that we have a formula in common. 

24
00:02:01,122 --> 00:02:07,020
and both of us were very surprised to see 
the similiarities among these formulas 

25
00:02:07,020 --> 00:02:13,564
and it might be said that we spent the 
rest of our careers trying to understand 

26
00:02:13,564 --> 00:02:18,985
why. 
now it's worth it to think about what the 

27
00:02:18,985 --> 00:02:24,092
world was like at the time that we 
started our research careers. 

28
00:02:24,092 --> 00:02:28,255
and we were both, at that time, in the, 
just the early part of our research 

29
00:02:28,255 --> 00:02:31,299
careers. 
and the world was changing in very 

30
00:02:31,299 --> 00:02:36,385
important ways all around us without 
going into too much detail. It really was 

31
00:02:36,385 --> 00:02:41,258
the case that when we started school 
people wore coats and ties, wear coats 

32
00:02:41,258 --> 00:02:45,702
and ties to dinner and so forth. 
But by the time we got out P.h.Ds 

33
00:02:45,702 --> 00:02:50,888
there was Woodstock and hippies and and 
so forth and, but, with respect to 

34
00:02:50,888 --> 00:02:56,116
technology, there were huge changes. 
when we started school, computers were 

35
00:02:56,116 --> 00:02:58,968
big. 
expensive rare there were physical 

36
00:02:58,968 --> 00:03:01,952
devices for every switch or for every 
bit. 

37
00:03:01,952 --> 00:03:08,792
but not that much longer when we started 
research in teaching we had integrated 

38
00:03:08,792 --> 00:03:14,403
circuits and computers were becoming 
ubiquitous and fast and cheap. 

39
00:03:14,403 --> 00:03:18,425
another big thing was the access to 
computers. 

40
00:03:18,425 --> 00:03:25,617
most of the time that we were in college 
and in graduate school you would get to 

41
00:03:25,617 --> 00:03:30,291
develop a program you had to put each 
line of the program on a punched card and 

42
00:03:30,291 --> 00:03:35,122
you had to give a box of punched cards to 
a computer operator and you would get to 

43
00:03:35,122 --> 00:03:39,805
run your program once a day. 
not that much longer, we had later when 

44
00:03:39,805 --> 00:03:44,957
we started research in teaching we had 
timeshared terminals and we're always 

45
00:03:44,957 --> 00:03:47,731
connected and have been connected ever 
since. 

46
00:03:47,731 --> 00:03:52,630
And as I mentioned, when we started 
school my thesis was typed by a 

47
00:03:52,630 --> 00:03:55,922
secretary. 
so you present the result and 6 months 

48
00:03:55,922 --> 00:04:01,053
later, you sort of see what it looked 
like and submitted it. It might be it 

49
00:04:01,053 --> 00:04:06,464
might be a year between the time that you 
get the results and somebody sees it but 

50
00:04:06,464 --> 00:04:11,759
not that much longer, we had word 
processing and and mathematical type 

51
00:04:11,759 --> 00:04:18,106
setting and we can have a much quicker, 
and much broader communication of our, of 

52
00:04:18,106 --> 00:04:22,727
our research results. 
And another important thing is that when 

53
00:04:22,727 --> 00:04:28,752
we were in school and graduate school the 
curriculum was about math everybody 

54
00:04:28,752 --> 00:04:33,920
learned lots of math and I learned PDEs, 
and abstract alegebra, and probability, 

55
00:04:33,920 --> 00:04:38,091
and topology. 
that's what that's what people with an 

56
00:04:38,091 --> 00:04:41,082
interest in working in technical fields 
did. 

57
00:04:41,082 --> 00:04:45,625
but by the time we started researching 
teaching, there was computer science and 

58
00:04:45,625 --> 00:04:49,828
people had to learn about compilers, and 
algorithms, and data structures, and 

59
00:04:49,828 --> 00:04:53,724
graphics, and operating systems and 
programming languages, numerical 

60
00:04:53,724 --> 00:04:58,162
analysis, and all kinds of fields related 
to computer science. 

61
00:04:58,162 --> 00:05:03,067
So these are huge differences in a 
relatively short amount of time and in 

62
00:05:03,067 --> 00:05:08,087
thinking about it when preparing this 
talk, I really came to understand and 

63
00:05:08,087 --> 00:05:13,972
believe that this was a really profound 
change in the way the world worked. 

64
00:05:13,972 --> 00:05:22,017
maybe even more profound than the [COUGH] 
evolution of PCs, personal computing or, 

65
00:05:22,017 --> 00:05:27,159
or even the Internet. 
the world was a vastly different place 

66
00:05:27,159 --> 00:05:33,289
when we started to get to work. 
so that's the context where, where this 

67
00:05:33,289 --> 00:05:36,724
story starts. 
now, analysis of algorithms. 

68
00:05:36,724 --> 00:05:43,640
So that's the field of study that both 
Philippe and I were engaged in and it's 

69
00:05:43,640 --> 00:05:50,362
actually natural in each, in questions 
and it actually started with Babbage. 

70
00:05:50,362 --> 00:05:56,330
so this is a quote from from Babbage 
whose widely attributed to have one of, 

71
00:05:56,330 --> 00:06:01,144
maybe the first comp, designed the first 
computational engine, it was a mechanical 

72
00:06:01,144 --> 00:06:04,250
device that could do arithmetic 
computations. 

73
00:06:04,250 --> 00:06:09,189
and what he said even before building the 
thing as soon as an analytic engine 

74
00:06:09,189 --> 00:06:13,241
exists, it will necessarily guide the 
future course of the science, 

75
00:06:13,241 --> 00:06:18,657
because you'd be able to do computations. 
but he said whenever any result is 

76
00:06:18,657 --> 00:06:24,132
sought, the question will arise by what 
course of calculation can these results 

77
00:06:24,132 --> 00:06:29,307
be arrived at by the machine in the 
shortest time? That's in 1864 and you can 

78
00:06:29,307 --> 00:06:34,457
see why it was important to Babbage. 
This thing actually had a crank and the 

79
00:06:34,457 --> 00:06:39,412
only way that it could compute things was 
by somebody turning the crank. 

80
00:06:39,412 --> 00:06:46,609
Obviously you want to minimize the number 
of times that you need to turn the crank. 

81
00:06:46,609 --> 00:06:53,942
The computers were expensive and slow and 
and used energy and so forth, and so 

82
00:06:53,942 --> 00:06:59,058
minimizing the cost of computation was 
always very important. 

83
00:06:59,058 --> 00:07:06,047
even Turing who many who, who is, is 
[COUGH] the founder of theoretical 

84
00:07:06,047 --> 00:07:11,557
computer science could see the importance 
of these kinds of practical questions. 

85
00:07:11,557 --> 00:07:16,316
we want to have a measure of the amount 
of work involved in a computing process, 

86
00:07:16,316 --> 00:07:20,395
even though, it might be a crude one. 
We count up the number of times that 

87
00:07:20,395 --> 00:07:26,334
elementary operations are applied in the 
whole process and, and, in order to 

88
00:07:26,334 --> 00:07:32,596
figure out how much work it's going to 
take before to help in designing 

89
00:07:32,596 --> 00:07:37,490
efficient computation. 
But the field of analysis of algorithms 

90
00:07:37,490 --> 00:07:41,205
was really initiated by Knuth in the 
1960s. 

91
00:07:41,205 --> 00:07:48,280
and what Knuth told the world, and there 
was some debate about it at the time, was 

92
00:07:48,280 --> 00:07:53,447
that classical mathematics, as we got the 
necessary tools that we need for 

93
00:07:53,447 --> 00:07:56,197
understanding the performance of 
algorithms. 

94
00:07:56,197 --> 00:08:01,487
there's things like recurrence relations, 
and generating functions, and asymptotic 

95
00:08:01,487 --> 00:08:07,853
analysis that has the benefit of giving a 
scientific foundation for the analysis of 

96
00:08:07,853 --> 00:08:11,981
algorithms and Knuth wrote a series of 
four books so far. 

97
00:08:11,981 --> 00:08:17,788
First one came out in, in the late 60s 
and two more came out in the early 70s. 

98
00:08:17,788 --> 00:08:21,294
We really set up this scientific 
foundation. 

99
00:08:21,294 --> 00:08:28,628
We really can use classic mathematic to 
understand the performance of algorithms 

100
00:08:28,628 --> 00:08:35,562
in, with those mathematical models we 
could go ahead and accurately predict 

101
00:08:35,562 --> 00:08:40,121
performance and compare the efficiency of 
algorithms. 

102
00:08:40,121 --> 00:08:48,312
in that's what we found exciting we could 
use classical mathematics to understand. 

103
00:08:48,312 --> 00:08:53,434
Now, the cost of a computation and then 
test up those results in [COUGH] 

104
00:08:53,434 --> 00:08:58,504
formulate hypothesis about how long we 
take to do something, and then validate 

105
00:08:58,504 --> 00:09:03,305
those hypothesis by actually 
implementing, and running a program, and 

106
00:09:03,305 --> 00:09:07,841
checking them against the math. 
There are many many practical 

107
00:09:07,841 --> 00:09:13,795
applications where people needed the have 
these kinds of accurate math, math, math 

108
00:09:13,795 --> 00:09:19,788
models and, and predictions. 
and in Knuth's books we're very densely 

109
00:09:19,788 --> 00:09:25,868
filled with this information that helped 
us advance this science. 

110
00:09:25,868 --> 00:09:31,911
So that's a brief history of where we got 
started with analysis of algorthm.