1 00:00:03,700 --> 00:00:10,470 I want to finish by talking about various resources that will be useful to people 2 00:00:10,470 --> 00:00:16,002 in studying the Analysis of Algorithms and analytic combinatorics. 3 00:00:16,002 --> 00:00:21,362 the first thing is books now. This is not going to be a lecture on, 4 00:00:21,362 --> 00:00:25,026 eBooks or on modern technologies for disseminating knowledge. 5 00:00:25,026 --> 00:00:29,231 Well, actually it is going to be a lecture on, [LAUGH], modern technologies 6 00:00:29,231 --> 00:00:34,037 for disseminating knowledge cause you're going to see way more of those, in this 7 00:00:34,037 --> 00:00:38,422 course, than you will in, any, any other thing, that's out there. 8 00:00:38,422 --> 00:00:43,108 So I want to take a little time to talk about, various resources that we're going 9 00:00:43,108 --> 00:00:45,811 to use. But first of all, I just want to 10 00:00:45,811 --> 00:00:50,797 emphasize that particularly, for these kinds of fields of mathematics, I think 11 00:00:50,797 --> 00:00:55,677 books are here to stay for a long time. So that's why we have a textbook 12 00:00:55,677 --> 00:01:01,445 associated with the course. this is the second edition of a book that 13 00:01:01,445 --> 00:01:06,520 we wrote in the 1990's. And the new edition is just out in 2013. 14 00:01:06,520 --> 00:01:13,365 Phillipe and I put a lot of effort into this book and it really tells the story 15 00:01:13,365 --> 00:01:19,517 that I'm trying to present here. So certainly the book is a very important 16 00:01:19,517 --> 00:01:23,245 resource. [COUGH], this is the first edition of the 17 00:01:23,245 --> 00:01:29,304 book that maybe many people have seen. so but second edition has quite a bit new 18 00:01:29,304 --> 00:01:31,600 material. and I'll talk about why. 19 00:01:31,600 --> 00:01:38,115 and the second part of the course is about analytic combinatorics and this is 20 00:01:38,115 --> 00:01:44,210 something that Philippe put 25 years into and I put a great, great amount of time 21 00:01:44,210 --> 00:01:49,043 into it as well. And again this is what defines the field 22 00:01:49,043 --> 00:01:54,788 and has, tells the story, and has all the information that you need to really 23 00:01:54,788 --> 00:02:00,047 understand what's going on. I already mentioned for algorithms, for 24 00:02:00,047 --> 00:02:06,035 studying algorithms, you can look at our book Algorithms Fourth Edition. 25 00:02:06,035 --> 00:02:12,022 And again, there's a great amount of information here and this is the most 26 00:02:12,022 --> 00:02:15,840 efficient way to get at it. for Java programming. 27 00:02:15,840 --> 00:02:20,174 These are I didn't show this, these are earlier editions of algorithms that 28 00:02:20,174 --> 00:02:24,694 people might be familiar with. and for Java programming this is an 29 00:02:24,694 --> 00:02:29,273 earlier introductory book on Java by Kevin Wayne and myself. 30 00:02:29,273 --> 00:02:35,241 And again all of these references all have as you saw, all have material that 31 00:02:35,241 --> 00:02:41,208 assumes understanding a lot of of a lot of the material in these books or at 32 00:02:41,208 --> 00:02:46,967 least the best way to really cement your understanding of what's going on is 33 00:02:46,967 --> 00:02:51,131 through the books. It's possible to follow quite a bit of 34 00:02:51,131 --> 00:02:55,780 what I'm saying without them, and I'll get into that in a sec. 35 00:02:55,780 --> 00:02:59,218 [INAUDIBLE]. but still, the best thing, is to be 36 00:02:59,218 --> 00:03:03,847 involved with, the textbooks. I think that textbooks are, are here to 37 00:03:03,847 --> 00:03:04,838 stay. and 38 00:03:04,838 --> 00:03:09,930 So, and I've worked very hard on these. And so, I hope people, don't, not take 39 00:03:09,930 --> 00:03:14,753 them lightly. but we do we have web root sources, that 40 00:03:14,753 --> 00:03:19,477 we call book sites. and there's a web resource associated 41 00:03:19,477 --> 00:03:23,920 with this course. that's the URL a of a.cs.princeton.edu. 42 00:03:23,920 --> 00:03:28,137 and there's a lot of information on the book site. 43 00:03:28,137 --> 00:03:33,032 but it's not intended to be an electronic version of the book. 44 00:03:33,032 --> 00:03:39,282 It's intended to be a resource, for use while on the web, to provide the kinds of 45 00:03:39,282 --> 00:03:45,081 things that we can't put into a book. Now to provide some guidance and, and 46 00:03:45,081 --> 00:03:48,931 some into. In a foundation, we usually have, 47 00:03:48,931 --> 00:03:54,975 condensed versions of the text in the book, that describes the highlights but 48 00:03:54,975 --> 00:04:00,415 doesn't, go into depth. so there's text that keeps it associated, 49 00:04:00,415 --> 00:04:05,024 with the book. but there's also, many other resources, 50 00:04:05,024 --> 00:04:10,917 like data or programs or, simulations. or, links to other web resources. 51 00:04:10,917 --> 00:04:17,037 these things are alive and they change, the books, they change frequently. 52 00:04:17,037 --> 00:04:22,550 The books, don't change that often. There's a book site for each of the 53 00:04:22,550 --> 00:04:28,107 books, that I showed you, and if you go to any one of them, there's direct links 54 00:04:28,107 --> 00:04:32,258 to get to any of the others. this is something that we've been 55 00:04:32,258 --> 00:04:35,068 experimenting with for almost ten years now. 56 00:04:35,068 --> 00:04:41,441 May be a little less than that and its proven very successful way to get the 57 00:04:41,441 --> 00:04:48,266 benefits of both the traditional book and the flexibility of the web and so we 58 00:04:48,266 --> 00:04:54,929 expect to see a lot more development around these these web resources and 59 00:04:54,929 --> 00:05:01,593 certainly if we can get to the book you can get really a lot of information out 60 00:05:01,593 --> 00:05:06,330 of the book side so often I refer to that as well so. 61 00:05:06,330 --> 00:05:11,251 if we want something like download a program, go to the books that you can 62 00:05:11,251 --> 00:05:15,213 download the program. You don't have to type in the one that's 63 00:05:15,213 --> 00:05:18,984 in the book. and there's lot of information out there. 64 00:05:18,984 --> 00:05:24,544 So, I hope that people will get involved with the book-sites, as a part of talking 65 00:05:24,544 --> 00:05:28,506 this course, as well. the other thing is, there's a lot of 66 00:05:28,506 --> 00:05:32,788 regional resource, that's the basis for the material in this course. 67 00:05:32,788 --> 00:05:36,175 for example, the real foundation is, Kanooz work. 68 00:05:36,175 --> 00:05:40,330 And Kanooz, work is available in his collective works which is. 69 00:05:40,330 --> 00:05:45,687 Is four volume treatisim the art of computer programming, and also a number 70 00:05:45,687 --> 00:05:51,388 of books with selected papers, and these are, some of them, but not all of them, 71 00:05:51,388 --> 00:05:56,952 but, again these are, [COUGH], have a wealf of information, each one of them's 72 00:05:56,952 --> 00:06:02,653 a 1000 pages, and, every page has, a great amount of interesting information 73 00:06:02,653 --> 00:06:06,018 on 'em. there's also Flash and Lays collective 74 00:06:06,018 --> 00:06:11,857 works, and this is, in addition to the new books, this is hundreds of research 75 00:06:11,857 --> 00:06:16,853 papers and we're working hard on, This published by 2014 by Cambridge 76 00:06:16,853 --> 00:06:22,882 University Press, in seven volumes or so. many of the papers are available on the 77 00:06:22,882 --> 00:06:26,387 web, as well. And then, there is research papers and 78 00:06:26,387 --> 00:06:31,224 books by literally hundreds of others of researchers that we draw on. 79 00:06:31,224 --> 00:06:37,113 I'll call attention to papers and books on now and then, but there is quite a bit 80 00:06:37,113 --> 00:06:42,791 out there and I want to make a point that it's not just what's in our books that 81 00:06:42,791 --> 00:06:47,699 matters, it's what's in all of this material and really one of my main 82 00:06:47,699 --> 00:06:50,843 intent... Main goals for this course is to make 83 00:06:50,843 --> 00:06:54,217 this work accessible to as many people as possible. 84 00:06:54,217 --> 00:06:59,839 I'm trying to provide the basics and tell the story, so that, people can see the 85 00:06:59,839 --> 00:07:04,536 value, in all this other work. there's at least 20,000 pages of, of 86 00:07:04,536 --> 00:07:09,232 material out there, if not more. and so, I can't, obviously can't cover 87 00:07:09,232 --> 00:07:13,003 everything. but I can make it so that, people can, 88 00:07:13,003 --> 00:07:18,361 understand, what they can get to. that's a very important feature of, what 89 00:07:18,361 --> 00:07:22,330 goes on in this course. There's a lot of other resources out. 90 00:07:22,330 --> 00:07:27,506 Up there that I don't have time to talk about in detail but I'm sure will get 91 00:07:27,506 --> 00:07:31,341 covered in disscusion groups and various other things. 92 00:07:31,341 --> 00:07:36,901 I think that many people by the time they get to a course like this will know about 93 00:07:36,901 --> 00:07:40,416 math type setting. and there's various, these are the 94 00:07:40,416 --> 00:07:44,251 resources that I use to prepare these types of materials. 95 00:07:44,251 --> 00:07:49,747 and there's a couple of links to useful resources out on the book site. 96 00:07:49,747 --> 00:07:54,604 so nowadays I don't do math on the blackboard or the pencil and paper 97 00:07:54,604 --> 00:07:57,664 anymore. I find it kind of strange to, to say 98 00:07:57,664 --> 00:08:01,520 that. but, of the digital resources are so good 99 00:08:01,520 --> 00:08:07,601 that, we can create the math in the way that, it use to take a year to get it 100 00:08:07,601 --> 00:08:11,086 published. and that's a, a big, big benefit, as 101 00:08:11,086 --> 00:08:16,351 maybe you can see by the kinds of lecture slides that I'm preparing. 102 00:08:16,351 --> 00:08:19,762 A lot of which I never did pencil to paper. 103 00:08:19,762 --> 00:08:24,953 It was all done using modern resources. Another thing is symbolic math. 104 00:08:24,953 --> 00:08:29,180 This is not a course about symbolic math manipulation, 105 00:08:29,180 --> 00:08:32,418 [COUGH]. Although they were powerful packages, 106 00:08:32,418 --> 00:08:38,152 very powerful packages that practicing mathematicians use regularly every once 107 00:08:38,152 --> 00:08:43,751 in a while, if I'm checking a calculation I might use one of these but I suspect 108 00:08:43,751 --> 00:08:49,553 that a lot of people will be using these kinds of packages to help them through 109 00:08:49,553 --> 00:08:55,826 some difficult calculations and I just can't take the time to go in to how to 110 00:08:55,826 --> 00:09:01,156 use these packages to do the kinds of things we do but it, it is in an 111 00:09:01,156 --> 00:09:05,598 important topic and certainly. the way that many people work. 112 00:09:05,598 --> 00:09:09,764 So occasionally I do go into these kinds of ideas. 113 00:09:09,764 --> 00:09:15,342 You have to understand the fundamental theorems and the basic calculations in a 114 00:09:15,342 --> 00:09:20,784 way I'm teaching you before you can effectively use these things but still 115 00:09:20,784 --> 00:09:25,017 it's an important resource. And then there's a lot of other web 116 00:09:25,017 --> 00:09:30,259 resources out there that practicing mathematicians and students in this 117 00:09:30,259 --> 00:09:35,567 course certainly will use regularly. one of the online encyclopedia of 118 00:09:35,567 --> 00:09:40,147 integers sequence of. and I'll refer to that and on, on several 119 00:09:40,147 --> 00:09:43,999 occasions I'm sure. wikipedia's a pretty good resource for 120 00:09:43,999 --> 00:09:47,536 math nowadays. And again the kind of math we're doing 121 00:09:47,536 --> 00:09:52,840 even if you think that the information on the web is wrong usually you can check 122 00:09:52,840 --> 00:09:56,571 it. there's a math world which is associated 123 00:09:56,571 --> 00:10:01,105 with mathematica. and then there's the Nift Handbook of 124 00:10:01,105 --> 00:10:07,055 Mathematical Functions, which replaces the old Bronas and Stagen that is a big 125 00:10:07,055 --> 00:10:12,863 resource for the study of many of the kinds of special functions that arise in 126 00:10:12,863 --> 00:10:17,325 the analysis of algorithms. Again, these are just ideas I'm just 127 00:10:17,325 --> 00:10:21,434 trying to lay out. the kinds of resources that I use in 128 00:10:21,434 --> 00:10:27,030 preparing materials for this course, and to make people aware of that and 129 00:10:27,030 --> 00:10:35,032 Everything's, fair nowadays, on the web and in mathematics, now how's the course 130 00:10:35,032 --> 00:10:41,770 going to work, I'm going to not have, too much of emphasis on assessment. 131 00:10:41,770 --> 00:10:45,964 what I want to do is basically introduce topics and lecture. 132 00:10:45,964 --> 00:10:50,667 usually they're things that people, maybe, haven't seen or thought about. 133 00:10:50,667 --> 00:10:54,925 but there's much more depth in the book around the book site. 134 00:10:54,925 --> 00:11:00,708 and then, a few assignments that exercise the ideas that I've talked about, or take 135 00:11:00,708 --> 00:11:03,949 us in a direction that I didn't have time to cover. 136 00:11:03,949 --> 00:11:09,669 so I think most students will after the lecture will read the relevant materials 137 00:11:09,669 --> 00:11:14,562 in the book and try to do some of the assignments before the next lecture. 138 00:11:14,562 --> 00:11:18,761 so that, so that. And so for example here's exercise 1.14, 139 00:11:18,761 --> 00:11:24,117 which is solving a recurrence, kind of like the quick sort recurrence, but not 140 00:11:24,117 --> 00:11:27,790 exactly like it. and then I'm sure in the discussion 141 00:11:27,790 --> 00:11:33,703 groups there'll be plenty of discussion of the assignments and the reading online 142 00:11:33,703 --> 00:11:38,275 but we're going to, not going to have assessments at this level you know, if 143 00:11:38,275 --> 00:11:43,334 you understand it well enough to be able to do the exercise or understand the next 144 00:11:43,334 --> 00:11:48,515 person's solution, and there's many, many exercises in the book and on the web that 145 00:11:48,515 --> 00:11:53,697 are not assigned that you can use to test that the main resource in this class is 146 00:11:53,697 --> 00:11:55,770 you. you'll get a lot out of it. 147 00:11:55,770 --> 00:11:59,770 as with many good courses you get out of it what you put in to it. 148 00:11:59,770 --> 00:12:05,968 the goal is for you to learn quite a few things that you don't now know. 149 00:12:05,968 --> 00:12:13,084 and I think there's a lot of interesting material here that will engage a lot of 150 00:12:13,084 --> 00:12:16,757 people. and that's really the goal and not 151 00:12:16,757 --> 00:12:22,101 deciding who's better at it. so, here's a couple of exercise that 152 00:12:22,101 --> 00:12:27,901 exercises that I think will help cement understanding of the material I've talked 153 00:12:27,901 --> 00:12:31,297 about today. so, we just talked about compares, 154 00:12:31,297 --> 00:12:35,117 how'bout a number of recursive calls in quick sort? 155 00:12:35,117 --> 00:12:39,715 Or, how'bout how much time, how many data moves, how many exchanges? 156 00:12:39,715 --> 00:12:42,755 so. here's two excercises, so this first one 157 00:12:42,755 --> 00:12:47,621 that I just showed, is, the number of recursive calls in quick sort, and the 158 00:12:47,621 --> 00:12:52,730 other one is, average number of exchanges and it shows, a little, facility in, 159 00:12:52,730 --> 00:12:57,778 dealing with the, reccurences of the way that I talk about, but following through 160 00:12:57,778 --> 00:13:02,097 the way I did other things, people can get, this extra size solved. 161 00:13:02,097 --> 00:13:07,145 And then the next one is about this ideal of a parameter that I talked about, in 162 00:13:07,145 --> 00:13:11,707 practice what we do is recognize that quick sorts not going to be fast for 163 00:13:11,707 --> 00:13:17,043 really small arrays so we should switch. To a method that's even simpler for tiny 164 00:13:17,043 --> 00:13:22,212 arrays, and that's insertion sort. so what threshold value are we going to 165 00:13:22,212 --> 00:13:25,115 use? Are we going to use a different sorting 166 00:13:25,115 --> 00:13:29,647 method when the fog is to be less than 100 or less five, or what? 167 00:13:29,647 --> 00:13:35,665 and so, what this exercise shows is a way to parameritize that threshold, do the 168 00:13:35,665 --> 00:13:38,927 math. And then figure out the best value of the 169 00:13:38,927 --> 00:13:41,748 parameter. And again, that's the importance of 170 00:13:41,748 --> 00:13:45,945 having a mathematical model. and it's a a poster child for this 171 00:13:45,945 --> 00:13:49,655 concept, that comes up often in the analysis of algorithms. 172 00:13:49,655 --> 00:13:54,521 We have some degree of freedom and we capture that in the math and then with 173 00:13:54,521 --> 00:13:57,684 the math model, we can figure out the outcomal value. 174 00:13:57,684 --> 00:14:01,272 and then that just translates right back to practice. 175 00:14:01,272 --> 00:14:06,503 so that's those those two exercises. So in summary if for the next lecture 176 00:14:06,503 --> 00:14:10,882 people would take a look at the book sites, to just become familiar with 177 00:14:10,882 --> 00:14:13,620 what's in there and bookmark them so you can. 178 00:14:13,620 --> 00:14:22,106 And get back to'em, and then, start learning to use some of the software, if 179 00:14:22,106 --> 00:14:26,045 you, are not. [COUGH], too comfortable with your 180 00:14:26,045 --> 00:14:29,815 programming environment. we have input if you have some 181 00:14:29,815 --> 00:14:34,756 familiarity we have a pretty simple to use programming model and I'll be 182 00:14:34,756 --> 00:14:40,022 describing code in terms of that model. It's not an absolute requirement but a 183 00:14:40,022 --> 00:14:45,808 lot of people might find it interesting to be working with the code that I'm 184 00:14:45,808 --> 00:14:49,253 presenting to run experiments and do other things. 185 00:14:49,253 --> 00:14:55,039 So that's all described in the algorithms fourth edition book site and it's pretty 186 00:14:55,039 --> 00:14:58,933 easy to download our model and to Using our code 187 00:14:58,933 --> 00:15:04,662 we have hundreds and hundreds of students do it every year here at Princeton and 188 00:15:04,662 --> 00:15:09,775 most of them here are only nineteen or twenty, so I think a lot of people taking 189 00:15:09,775 --> 00:15:14,518 this course have the experience and maturity to be able to run programs this 190 00:15:14,518 --> 00:15:16,490 way. another thing is tech 191 00:15:16,490 --> 00:15:22,539 as, as I said nowadays the best way to communicate in mathematics turns out to 192 00:15:22,539 --> 00:15:27,892 be using tech, and there's plenty of tools available, so, that you can write 193 00:15:27,892 --> 00:15:33,733 up assignments either in tech using tech shop or some similar tool or you can 194 00:15:33,733 --> 00:15:38,183 actually do it in HTML the way I did it for the book signing. 195 00:15:38,183 --> 00:15:43,606 I never, it was less than a year ago that I sat on this project and I never 196 00:15:43,606 --> 00:15:48,751 imagined I'd get the math in the book site as easily, and people can do 197 00:15:48,751 --> 00:15:52,845 assignments that way too. Maybe the discussion groups would tell 198 00:15:52,845 --> 00:15:57,676 us, I'm sure there will be a great amount of discussion about the best way to do 199 00:15:57,676 --> 00:16:00,814 this. If your interested download quick sort 200 00:16:00,814 --> 00:16:04,606 and use it to predict performance the way that I said. 201 00:16:04,606 --> 00:16:09,851 And see if you believe the idea of increasing problem size by a factor of 202 00:16:09,851 --> 00:16:13,959 ten in the running time, increases by about a factor of ten. 203 00:16:13,959 --> 00:16:19,583 you really, sometimes have to experience this kind of thing to really believe it. 204 00:16:19,583 --> 00:16:25,271 and then everything that I've talked about is in the first 40 pages of the 205 00:16:25,271 --> 00:16:28,431 text. So there are people that have the book 206 00:16:28,431 --> 00:16:32,160 will have the opportunity to go ahead and read those pages. 207 00:16:32,160 --> 00:16:36,230 And do all that and I'll be ready to go on the next lecture. 208 00:16:36,230 --> 00:16:39,012 [COUGH]. in, oh, of course. 209 00:16:39,012 --> 00:16:42,984 writing up the solutions. even if you think you can do'em. 210 00:16:42,984 --> 00:16:48,848 actually doing'em is, a different thing. and most students, find that, whether or 211 00:16:48,848 --> 00:16:53,514 not someone is going to grade'em. it's a good idea to actually, write up 212 00:16:53,514 --> 00:16:56,981 the proof. And and, and see if you can, solve those 213 00:16:56,981 --> 00:16:59,756 exercises. And that's an introduction to the 214 00:16:59,756 --> 00:17:03,665 analysis of algorithms. Which, as I mentioned, is the, one of the 215 00:17:03,665 --> 00:17:08,457 main motivations for the development and emergence of the field of analytic 216 00:17:08,457 --> 00:17:12,749 combinatorics. in the next lecture we'll begin on the 217 00:17:12,749 --> 00:17:17,598 journey of really trying to understand. And that pipes of mathematical 218 00:17:17,598 --> 00:17:23,498 manipulations that I was doing in class today to be able to use them on a broader 219 00:17:23,498 --> 00:17:28,526 class of problems and that will eventually evolve into the modern tools 220 00:17:28,526 --> 00:17:30,940 that we call analytic combinatorics.