I want to finish by talking about various resources that will be useful to people in studying the analysis of algorithms. Analytic Combinatorics. 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. This is the first edition of the book that maybe many people have seen, so but, our second edition has quite a bit of new material, and I'll talk about why. In a second part of the class is about analytic combinatorics. And this is something that Philippe put 25 years into. And I put a great amount of time into it as well, and again, this is what defines the field and 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 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. So when it's something like download a program, go to the booksite, you can download the program. You don't have to type in the one that's in the book. 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. 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 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, although there are 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. 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. There's MathWorld, which is associated with Mathematica, and then there's the NIST handbook of mathematical functions which replaces the old Abramowitz and Stegun's. That is a big resource for the study of many 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 when preparing materials for this course and to make people aware that 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 an emphasis on assessment. 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? 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. 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. In the next lecture, we'll begin on a journey of really trying to understand the types of mathematical manipulations that I was doing in class today, to be able to use them on a broader class of problems. That will eventually evolve into the modern tools that we call analytic combinatorics.
