So now, just a, a little bit, continuing 
the historical context before we get into 
Analytic Combinatorics. 
so we started thinking about, Phillipe 
and I met, and wondered about how we were 
going to approach this problem of 
teaching algorithms. 
in the early 80s, or just before it, I 
spent a year's sabbatical in Paris. 
and, so as I mentioned, what is 
certainly, one part of the story was 
that, there was a lot of opportunity and 
optimism, to be successful, in all sorts 
of, venues, with computation. 
everybody knew that, we were going to be 
completely transforming, the world, with, 
our understanding of how to use 
computation, effectively. 
and we had a basis Knuth's volumes one 
one to three, where each 1000 pages, just 
completely filled with wonderful 
information about both efficient and 
effective algorithms, and methods for 
studying and understanding them. 
and we were looking for, of course 
general themes in theorems that could be, 
somehow explained, in the fact that we 
came up with the same formula. 
and at the same time I realized that 
there were lots and lots of easy, easy to 
learn, effective algorithms that many, 
many people needed to know. 
and I started my series of books on, on 
algorithms, that many of which were not 
yet in canuse/g volumes, but still people 
needed to know and understand. 
So we had a big laboratory of possible 
things to study, and we're working for a 
living doing teaching and research, and 
we needed to educate our students. 
so so that's where we kind of embarked on 
the project or the idea of that 
eventually led to analytic combinatorics. 
We didn't know that it would take 30 
years. 
As I said, in around 1980 we decided we 
should write should write a book. 
Well, by the way, everyone in computer 
science was deciding to write a book, 
because there were no books. 
it's not like teaching math, or 
economics, or physics where there's 
plenty of books and you choose one. 
Computer science, there were no books, so 
you, everybody, in their area in the 90s 
had to write a book. 
And we were we were no different. 
and around 1986 I came to, I came to 
Princeton in '85, and a year after, 
Phillipe came. 
and we we taught a course on Analysis of 
Algorithms and we had done some 
preliminary work on what we wanted to 
have in the book, but But that's where 
I'm at least in Philippe's mind, for 
sure, it really crystallized that there 
was going to be something worth doing 
here. 
and we worked for quite a while. 
We had all, both of us had many other 
endeavors, that we're involved in, and 
around 1992 it became clear that we had 
so much stuff that, we were really going 
to have to do 2 books. 
one of them was going to have to cover 
the basics of analysis of algorithms, 
like, deriving Catalon numbers that I, 
that i just explained. 
but the other one, was going to involve 
some. 
Doing some math. 
That is, there was a lot of research 
needed to really back up what was, at the 
time, some folk theorems or loose 
understanding of what goes on. 
But actually prove facts was going to 
require some serious research in that 
Matics. 
And Philippe wrote a series of tech 
reports over the next fifteen, twenty 
years, that really enbodied a lot of that 
math, not to mention, 100s of,. 
of research papers. 
it wasn't until 2009 that the second 
book, Analytic Combinatorics was finally 
published so, around 1995 the first book 
came out. 
That's our Introduction to Analysis of 
Algorithms book. 
in it, was a fine coverage of many of the 
things that we felt were important for 
people working in analysis of algorithms 
The, covering the, the basics for the 
kind of [UNKNOWN] that I just gave as an 
example in preparing people say to really 
get the most out of Knuth books and other 
research papers. 
So it covers recurrences and generating 
functions and asymptotics. 
And it talks about basic combinatorial 
structures like trees and permutations 
and tries, now words and mappings and, 
all the basic things you need for, 
algorithms for sorting and searching. 
But other things like, like factoring 
and, various, string processing 
algorithms. 
So a fine way we felt, to teach the 
mathematics needed to really do good 
scientific studies of the performance of 
computer programs. 
And so the question is, okay that's a 
book, that's what we set out to do in 
1980, are we done? but, of course, as I 
just alluded what Philippe was seeing 
particularly Philippe in the 1980s, that 
we can get really although the classical 
methods can give us everything that we 
need in principle in practice we can even 
do better because there are general laws. 
they're, in, and it's actually possible 
to in many cases, we skip the details. 
and in fact the feeling was, was so 
strong that it, it really seemed like. 
We should work towards the goal of 
automatically analyzing algorithms. 
Thinking about some kind of black box 
that you just put in your algorithm and 
your input model and you get out an 
estimate of the running time and have the 
rest of it done automatically. 
Of course that's unattainable because of 
the halting problem, but it's amazing how 
close Philippe came to to this this goal 
in his research. 
[INAUDIBLE]. 
so just a little bit more detail on, on 
what Knuth was saying about the analysis 
of algorithms. 
so in his, in his books in, in the 60's. 
So what he said was that you should have 
a Good implementation that you understand 
and should have a realistic input model, 
so that you can run experiments and you 
can go ahead and find, figure out the 
cost at execution frequency of each 
operation. 
In the program and then you can calculate 
the total running time by multiplying the 
frequency and the costs. 
Now these things might involve some work. 
and they definitely would but certainly 
in principle you can go ahead and do 
that. 
And then you can run experiments to 
validate that your mathematical model of 
the input and the frequencies are valid, 
and that, that your analysis works. 
And believe me, we did this in many, many 
situations for both Felipe and I, 
consulted for, companies and government, 
and our jobs were to go ahead and, figure 
out how long a certain computation would 
take on a massive supercomputer, say, 
like a Cray 1 or not various other 
computers the time that I could name, and 
we could do it, it was very exciting it 
was very surprising that, that we could 
do it. 
we could say if you are going to do that 
it's going to take this amount of time 
and then they would do it and that's how 
much time it would take. 
we could be very very accurate about it 
really, this is nothign mjore than the 
scientific methiod, applied to the study 
of computer programs. 
And as I said, it's got the great benefit 
that, it gives a scientific foundation 
for analysis of algorithms. 
in that we can go ahead and predict 
performance and compare algorithms and 
decide which ones to use and what kind of 
resources they're going to consume. 
We have many, many Documented success 
stories along this lines. 
But there's drawbacks too. 
so the first drawback is that getting a 
realistic input model is, is often, very 
often the hard part and the other one is 
that. 
there is really a lot of detail in these 
kinds of analysis. 
so you did need experience and skill to 
get through these detailed analyses with 
generating functions n with f and 
[INAUDIBLE]. 
And so but, but the world is moving on 
There's all kinds of innovation, 
possible. 
So people were looking at other 
approaches. 
and, 1 that has been extremely successful 
is, what I refer to as the Theory of 
Algorithms, it was started out by Aho, 
Hopcroft, and Ullman in the '70s. 
High and is widely followed textbook by 
Cormen, Leiserson, Rivest, and Stein 
today that address the drawbacks in 
Knuth's approach in two ways. 
First thing was, analyze the worst-case 
cost of the algorithm. 
so provide guarantees on the running time 
no matter what the input is. 
That has the big benefit of taking the 
model out of the picture. 
you can, if you can guarantee that the 
running time is low, you're in good 
shape. 
and the other thing to do, is just do 
approximate analyses, and really, just 
use o notation, and get an upper bound on 
the running time. 
That still provides a guarantee. 
And if that guarantee's low, you're in 
good shape. 
And that has the big benefit of taking a 
lot of the detail out of the analysis. 
and then, go ahead and classify 
algorithms by these costs, the guaranteed 
worst-case running time. 
and that was very successful. 
I'd enabled what one blogger called, a 
new age of algorithm design. 
and there's literally [COUGH] hundreds, 
thousands a huge fraction of our 
computational infrastructure started with 
studies like this. 
This. 
but there is a big drawback, and the 
drawback is that this analysis is 
usually, or often, at least, not suitable 
for scientific studies. 
you can't really, predict performance or 
compare algorithms. 
If all you have is an upper-bound and the 
worst-case cause. 
It might be much to high, or might be a 
worst case that's not realized in 
practical situations, and many other 
problems It's not what, Oyler or Poinker 
Ray, or Strolling, were, trying to do to 
come up with, precise predictions. 
so that's the context for, really 
thinking about, analytic combinatorics. 
Knuth was very successful, but kind of 
stuck with the model, and there's detail 
excessive detail, in the analysis. 
In AHU and CLRS they're working on 
worst-case. 
It might not be relevant, and the And the 
O bounds, worst case upper bounds are too 
loose to be useful in lots of situations. 
But what analytic combinatorics can 
provide is really a basis for scientific 
studies. 
It does it in two ways. 
provides a calculus for developing 
models, or input models that is very very 
broad and extensible. 
that's number one. 
And number two a lot of the detail can be 
encompassed in universal laws that are 
proven mathematical facts. 
but, really, take care of all the detail 
in the analysis. 
So that's the context, where we're going 
to start talking about really what 
analytic combinatorics is.