0:15

The first things is books.

Now, this is not going to be a lecture on ebooks or

modern technologies for disseminating knowledge.

Well actually it is going to be a lecture for modern technologies for

disseminating knowledge.

Cause you're going to see way more of those in this course than you will in

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 a second edition of a book that we wrote in the 1990s.

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 The story on that, and I'm trying to present here.

So certainly the book is a very important resource.

1:57

I already mentioned for algorithms, for studying algorithms, you can

look at our book Algorithm's fourth edition and again there's a great

amount of information here, and this is the most efficient way to get at it.

For double programming these are, I didn't show this,

these are earlier editions of algorithms that people might be familiar with.

[LAUGH] And for Java programming

this is earlier introductory book on Java by Kevin Wayne and

myself and again all of their references I'll have as saw I'll have

material that assumes understanding a lot of 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 second.

But still the best thing is to be involved with the textbooks.

I think that textbooks are here to stay, and have worked very hard on these.

And so I hope people don't take them lightly.

But we do have web resources as well that we call Booksites,

and there's a web resource associated with this course.

That's the url aoto.cs.princeton.edu.

There's a lot of information on the book's site.

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 to In a foundation

we usually have contends version of the text and

the book that describe the highlight 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.

And 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, maybe a little less than that and

it's proven very successful way to get the benefits of

both the traditional book and the flexibility of the web.

So we expect to see a lot more development around these web resources.

And certainly,

if you can't get to the book you can get a lot of information out of the book site.

So often I'll refer to that as well.

5:15

And there's a lot of other information out there so

I hope that people will get involved with the booksites.

As a part of taking this course as well.

The other thing is there is a lot of original research that's the basis for

the material in this course.

For example, the real foundation is Knuth's work.

And Knuth's work is available in his collected works, which is his four volume

on the art of computer program and also a number of books with selected papers.

And these are some of them, but not all of them.

But, again, these have a wealth of information.

Each one of them is 1000 pages.

And every page has a great amount of interesting information on them.

There is also Flajolet's collected works.

This is, in addition to the two books this is hundreds of research papers.

And we are working hard on having this published by 2014 by

Cambridge University Press in seven volumes or so.

6:22

Many of the papers are available on the web as well.

And then there's research papers and

books by literally hundreds of other researchers that we draw on.

I'll call attention to papers and books now and then, but

there's quite a bit out there, and I just want to make the 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 intents, 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 material out there, if not more.

So, obviously I 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 there that I don't have time to talk about in

detail, but I'm sure will get covered in discussion groups and

various other things.

I think many people,

by the time they get to a course like this will know about math type setting, and

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 side.

So nowadays, I don't do math on the blackboard or pencil and paper anymore.

I find it kind of strange to say that, but

8:00

the digital resources are so good that we can

create the math in the way that it used to take a year to get it published.

And that's a big, big benefit.

As maybe you can see by the kinds of lecture slides that I'm preparing,

a lot of which that 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,

8:38

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.

We will be using these kinds of packages to help them through

some difficult calculations.

I can't just take the time to go into how to use

these packages to do the kinds of things we do, but it is an important topic.

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 and

the way I'm teaching them 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 is the online encyclopedia of integer sequences.

And I'll refer to that on several occasions, I'm sure.

Wikipedia is 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.

10:42

What I want to do is basically introduce topics in lecture,

usually they're things that people maybe haven't seen or thought about.

But there is much more depth in the book or on the book site.

And then a few assignments that exercise the ideas

that I've talked about or taketh in a direction I didn't have time to cover.

So I think most students will, after the lecture, read the relevant materials

in the book and try to do some of the assignments before the next lecture.

So for example here's exercise

1.14 which is solving a recurrence kind of like the quicksword occurrence 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 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

persons solution and there's many, many exercises in the book and on the web.

They are not assigned that you can use to test it.

The main resource in this class is you.

You will get out of it, as with many good courses,

you will 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.

I think There's a lot of interesting material here that will engage a lot of

people, and tha's really the goal, and not deciding who's better at it.

So here's a couple of exercising that I think

will help cement understanding of the material I've talked about today.

So we just talked about compare.

How about a number of recursive calls in Quicksort?

Or how about how many data moves, how many exchanges?

12:39

So here's two exercises.

So this first one that I just showed is the number of recursive calls in

Quicksort, and the other one is average number of exchanges.

And it shows a little facility in

dealing with the recurrences of the way that I talked about, by following

through the way that I did other things people can get this exercise solved.

And in the next one, it's about this idea of a parameter that I talked about.

In practice what we do is recognise the quick sort is not going to be first with

small range, so we should switch to a method even simpler for

penal rays than that insertion sort.

So what threshold value we going to use, are we going to use different a different

sorting method when file gets less than 100 or less than five or what .And so

what this exercise shows is a way to parameterize 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 poster child for

this concept that comes up often in the analysis of algorithm.

We have some degree of freedom.

And we capture that in the math and

with the math model we can figure out the optimal value and

that translates right back to practice so that's those two exercises.

So in summary if for the next lecture if people would take a look at the book

cites to just become familiar with what's in there and bookmark them so

you can get back to them and then start learning to use some of the software.

If you are not to comfortable with your programming environment.

We have imputed a few some familiarity.

We have prettY simple programming model.

And I'll be describing codes in terms of those models.

It's not an absolute requirement, but a lot of people might find it interesting

to, when working with the code that I'm presenting, to run experiments and

do other things.

So that's all described in the algorithm fourth edition books.

And it's pretty easy to download our model.

And to be using our code.

We have hundreds and hundreds of students do it every year here at Princeton.

Most of them are only 19 or 20.

So I think a lot of the people taking this course have the experience maturity to

be able to run programs this way.

Another thing is tech, as I said nowadays the best way to communicate mathematics,

it turns out to be is using tech and there is 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 for the books.

It was less than a year ago I set on this project, I never imagined I'd be able to

get the math in the books as easily so people can do assignments that way too.

And maybe the discussion groups will tell us.

I'm sure there'll be a great amount of discussion about the best way to do this.

15:58

If you're interested, I'd download Quicksort and

use it to predict performance the way that I said and

see if you believe the idea of Increase the problem size

by a factor of 10 many times, increase by about a factor of 10.

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 I hope people that have the book will have the opportunity to go ahead and

read those pages.

And do all that and we'll be ready to go on the next lecture.

[COUGH] And of course, writing up the solutions,

even if you think you can do them, actually doing them is a different thing.

And most students find that, whether or not somebody's going to grade them, it's

a good idea to actually write up the proof and see if you can solve those exercises.

And that's an introduction to the analysis of algorithms, which, as I mentioned,

is one of the main motivations for the development and

emergence of the field of analytic combinatorics.