I want to finish by talking about various 
resources that will be useful to people 
in studying the Analysis of Algorithms 
and analytic combinatorics. 
the first thing is books now. 
This is not going to be a lecture on, 
eBooks or on modern technologies for 
disseminating knowledge. 
Well, actually it is going to be a 
lecture on, [LAUGH], modern technologies 
for disseminating knowledge cause you're 
going to see way more of those, in this 
course, than you will in, any, any other 
thing, that's out there. 
So I want to take a little time to talk 
about, various resources that we're going 
to use. 
But first of all, I just want to 
emphasize that particularly, for these 
kinds of fields of mathematics, I think 
books are here to stay for a long time. 
So that's why we have a textbook 
associated with the course. 
this is the second edition of a book that 
we wrote in the 1990's. 
And the new edition is just out in 2013. 
Phillipe and I put a lot of effort into 
this book and it really tells the story 
that I'm trying to present here. 
So certainly the book is a very important 
resource. 
[COUGH], this is the first edition of the 
book that maybe many people have seen. 
so but second edition has quite a bit new 
material. 
and I'll talk about why. 
and the second part of the course is 
about analytic combinatorics and this is 
something that Philippe put 25 years into 
and I put a great, great amount of time 
into it as well. 
And again this is what defines the field 
and has, tells the story, and has all the 
information that you need to really 
understand what's going on. 
I already mentioned for algorithms, for 
studying algorithms, you can look at our 
book Algorithms Fourth Edition. 
And again, there's a great amount of 
information here and this is the most 
efficient way to get at it. 
for Java programming. 
These are I didn't show this, these are 
earlier editions of algorithms that 
people might be familiar with. 
and for Java programming this is an 
earlier introductory book on Java by 
Kevin Wayne and myself. 
And again all of these references all 
have as you saw, all have material that 
assumes understanding a lot of of a lot 
of the material in these books or at 
least the best way to really cement your 
understanding of what's going on is 
through the books. 
It's possible to follow quite a bit of 
what I'm saying without them, and I'll 
get into that in a sec. 
[INAUDIBLE]. 
but still, the best thing, is to be 
involved with, the textbooks. 
I think that textbooks are, are here to 
stay. 
and 
So, and I've worked very hard on these. 
And so, I hope people, don't, not take 
them lightly. 
but we do we have web root sources, that 
we call book sites. 
and there's a web resource associated 
with this course. 
that's the URL a of a.cs.princeton.edu. 
and there's a lot of information on the 
book site. 
but it's not intended to be an electronic 
version of the book. 
It's intended to be a resource, for use 
while on the web, to provide the kinds of 
things that we can't put into a book. 
Now to provide some guidance and, and 
some into. 
In a foundation, we usually have, 
condensed versions of the text in the 
book, that describes the highlights but 
doesn't, go into depth. 
so there's text that keeps it associated, 
with the book. 
but there's also, many other resources, 
like data or programs or, simulations. 
or, links to other web resources. 
these things are alive and they change, 
the books, they change frequently. 
The books, don't change that often. 
There's a book site for each of the 
books, that I showed you, and if you go 
to any one of them, there's direct links 
to get to any of the others. 
this is something that we've been 
experimenting with for almost ten years 
now. 
May be a little less than that and its 
proven very successful way to get the 
benefits of both the traditional book and 
the flexibility of the web and so we 
expect to see a lot more development 
around these these web resources and 
certainly if we can get to the book you 
can get really a lot of information out 
of the book side so often I refer to that 
as well so. 
if we want something like download a 
program, go to the books that you can 
download the program. 
You don't have to type in the one that's 
in the book. 
and there's lot of information out there. 
So, I hope that people will get involved 
with the book-sites, as a part of talking 
this course, as well. 
the other thing is, there's a lot of 
regional resource, that's the basis for 
the material in this course. 
for example, the real foundation is, 
Kanooz work. 
And Kanooz, work is available in his 
collective works which is. 
Is four volume treatisim the art of 
computer programming, and also a number 
of books with selected papers, and these 
are, some of them, but not all of them, 
but, again these are, [COUGH], have a 
wealf of information, each one of them's 
a 1000 pages, and, every page has, a 
great amount of interesting information 
on 'em. 
there's also Flash and Lays collective 
works, and this is, in addition to the 
new books, this is hundreds of research 
papers and we're working hard on, 
This published by 2014 by Cambridge 
University Press, in seven volumes or so. 
many of the papers are available on the 
web, as well. 
And then, there is research papers and 
books by literally hundreds of others of 
researchers that we draw on. 
I'll call attention to papers and books 
on now and then, but there is quite a bit 
out there and I want to make a point that 
it's not just what's in our books that 
matters, it's what's in all of this 
material and really one of my main 
intent... 
Main goals for this course is to make 
this work accessible to as many people as 
possible. 
I'm trying to provide the basics and tell 
the story, so that, people can see the 
value, in all this other work. 
there's at least 20,000 pages of, of 
material out there, if not more. 
and so, I can't, obviously can't cover 
everything. 
but I can make it so that, people can, 
understand, what they can get to. 
that's a very important feature of, what 
goes on in this course. 
There's a lot of other resources out. 
Up there that I don't have time to talk 
about in detail but I'm sure will get 
covered in disscusion groups and various 
other things. 
I think that many people by the time they 
get to a course like this will know about 
math type setting. 
and there's various, these are the 
resources that I use to prepare these 
types of materials. 
and there's a couple of links to useful 
resources out on the book site. 
so nowadays I don't do math on the 
blackboard or the pencil and paper 
anymore. 
I find it kind of strange to, to say 
that. 
but, of the digital resources are so good 
that, we can create the math in the way 
that, it use to take a year to get it 
published. 
and that's a, a big, big benefit, as 
maybe you can see by the kinds of lecture 
slides that I'm preparing. 
A lot of which I never did pencil to 
paper. 
It was all done using modern resources. 
Another thing is symbolic math. 
This is not a course about symbolic math 
manipulation, 
[COUGH]. 
Although they were powerful packages, 
very powerful packages that practicing 
mathematicians use regularly every once 
in a while, if I'm checking a calculation 
I might use one of these but I suspect 
that a lot of people will be using these 
kinds of packages to help them through 
some difficult calculations and I just 
can't take the time to go in to how to 
use these packages to do the kinds of 
things we do but it, it is in an 
important topic and certainly. 
the way that many people work. 
So occasionally I do go into these kinds 
of ideas. 
You have to understand the fundamental 
theorems and the basic calculations in a 
way I'm teaching you before you can 
effectively use these things but still 
it's an important resource. 
And then there's a lot of other web 
resources out there that practicing 
mathematicians and students in this 
course certainly will use regularly. 
one of the online encyclopedia of 
integers sequence of. 
and I'll refer to that and on, on several 
occasions I'm sure. 
wikipedia's a pretty good resource for 
math nowadays. 
And again the kind of math we're doing 
even if you think that the information on 
the web is wrong usually you can check 
it. 
there's a math world which is associated 
with mathematica. 
and then there's the Nift Handbook of 
Mathematical Functions, which replaces 
the old Bronas and Stagen that is a big 
resource for the study of many of the 
kinds of special functions that arise in 
the analysis of algorithms. 
Again, these are just ideas I'm just 
trying to lay out. 
the kinds of resources that I use in 
preparing materials for this course, and 
to make people aware of that and 
Everything's, fair nowadays, on the web 
and in mathematics, now how's the course 
going to work, I'm going to not have, 
too much of emphasis on assessment. 
what I want to do is basically introduce 
topics and lecture. 
usually they're things that people, 
maybe, haven't seen or thought about. 
but there's much more depth in the book 
around the book site. 
and then, a few assignments that exercise 
the ideas that I've talked about, or take 
us in a direction that I didn't have time 
to cover. 
so I think most students will after the 
lecture will read the relevant materials 
in the book and try to do some of the 
assignments before the next lecture. 
so that, so that. 
And so for example here's exercise 1.14, 
which is solving a recurrence, kind of 
like the quick sort recurrence, but not 
exactly like it. 
and then I'm sure in the discussion 
groups there'll be plenty of discussion 
of the assignments and the reading online 
but we're going to, not going to have 
assessments at this level you know, if 
you understand it well enough to be able 
to do the exercise or understand the next 
person's solution, and there's many, many 
exercises in the book and on the web that 
are not assigned that you can use to test 
that the main resource in this class is 
you. 
you'll get a lot out of it. 
as with many good courses you get out of 
it what you put in to it. 
the goal is for you to learn quite a few 
things that you don't now know. 
and I think there's a lot of interesting 
material here that will engage a lot of 
people. 
and that's really the goal and not 
deciding who's better at it. 
so, here's a couple of exercise that 
exercises that I think will help cement 
understanding of the material I've talked 
about today. 
so, we just talked about compares, 
how'bout a number of recursive calls in 
quick sort? 
Or, how'bout how much time, how many data 
moves, how many exchanges? 
so. 
here's two excercises, so this first one 
that I just showed, is, the number of 
recursive calls in quick sort, and the 
other one is, average number of exchanges 
and it shows, a little, facility in, 
dealing with the, reccurences of the way 
that I talk about, but following through 
the way I did other things, people can 
get, this extra size solved. 
And then the next one is about this ideal 
of a parameter that I talked about, in 
practice what we do is recognize that 
quick sorts not going to be fast for 
really small arrays so we should switch. 
To a method that's even simpler for tiny 
arrays, and that's insertion sort. 
so what threshold value are we going to 
use? 
Are we going to use a different sorting 
method when the fog is to be less than 
100 or less five, or what? 
and so, what this exercise shows is a way 
to parameritize that threshold, do the 
math. 
And then figure out the best value of the 
parameter. 
And again, that's the importance of 
having a mathematical model. 
and it's a a poster child for this 
concept, that comes up often in the 
analysis of algorithms. 
We have some degree of freedom and we 
capture that in the math and then with 
the math model, we can figure out the 
outcomal value. 
and then that just translates right back 
to practice. 
so that's those those two exercises. 
So in summary if for the next lecture 
people would take a look at the book 
sites, to just become familiar with 
what's in there and bookmark them so you 
can. 
And get back to'em, and then, start 
learning to use some of the software, if 
you, are not. 
[COUGH], too comfortable with your 
programming environment. 
we have input if you have some 
familiarity we have a pretty simple to 
use programming model and I'll be 
describing code in terms of that model. 
It's not an absolute requirement but a 
lot of people might find it interesting 
to be working with the code that I'm 
presenting to run experiments and do 
other things. 
So that's all described in the algorithms 
fourth edition book site and it's pretty 
easy to download our model and to 
Using our code 
we have hundreds and hundreds of students 
do it every year here at Princeton and 
most of them here are only nineteen or 
twenty, so I think a lot of people taking 
this course have the experience and 
maturity to be able to run programs this 
way. 
another thing is tech 
as, as I said nowadays the best way to 
communicate in mathematics turns out to 
be using tech, and there's plenty of 
tools available, so, that you can write 
up assignments either in tech using tech 
shop or some similar tool or you can 
actually do it in HTML the way I did it 
for the book signing. 
I never, it was less than a year ago that 
I sat on this project and I never 
imagined I'd get the math in the book 
site as easily, and people can do 
assignments that way too. 
Maybe the discussion groups would tell 
us, I'm sure there will be a great amount 
of discussion about the best way to do 
this. 
If your interested download quick sort 
and use it to predict performance the way 
that I said. 
And see if you believe the idea of 
increasing problem size by a factor of 
ten in the running time, increases by 
about a factor of ten. 
you really, sometimes have to experience 
this kind of thing to really believe it. 
and then everything that I've talked 
about is in the first 40 pages of the 
text. 
So there are people that have the book 
will have the opportunity to go ahead and 
read those pages. 
And do all that and I'll be ready to go 
on the next lecture. 
[COUGH]. 
in, oh, of course. 
writing up the solutions. 
even if you think you can do'em. 
actually doing'em is, a different thing. 
and most students, find that, whether or 
not someone is going to grade'em. 
it's a good idea to actually, write up 
the proof. 
And and, and see if you can, solve those 
exercises. 
And that's an introduction to the 
analysis of algorithms. 
Which, as I mentioned, is the, one of the 
main motivations for the development and 
emergence of the field of analytic 
combinatorics. 
in the next lecture we'll begin on the 
journey of really trying to understand. 
And that pipes of mathematical 
manipulations that I was doing in class 
today to be able to use them on a broader 
class of problems and that will 
eventually evolve into the modern tools 
that we call analytic combinatorics.