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.

Â