1 00:00:00,012 --> 00:00:06,852 So now, just a, a little bit, continuing the historical context before we get into 2 00:00:06,852 --> 00:00:12,082 Analytic Combinatorics. so we started thinking about, Phillipe 3 00:00:12,082 --> 00:00:18,387 and I met, and wondered about how we were going to approach this problem of 4 00:00:18,387 --> 00:00:23,512 teaching algorithms. in the early 80s, or just before it, I 5 00:00:23,512 --> 00:00:29,121 spent a year's sabbatical in Paris. and, so as I mentioned, what is 6 00:00:29,121 --> 00:00:34,683 certainly, one part of the story was that, there was a lot of opportunity and 7 00:00:34,683 --> 00:00:40,539 optimism, to be successful, in all sorts of, venues, with computation. 8 00:00:40,539 --> 00:00:47,419 everybody knew that, we were going to be completely transforming, the world, with, 9 00:00:47,419 --> 00:00:51,832 our understanding of how to use computation, effectively. 10 00:00:51,832 --> 00:00:58,932 and we had a basis Knuth's volumes one one to three, where each 1000 pages, just 11 00:00:58,932 --> 00:01:05,197 completely filled with wonderful information about both efficient and 12 00:01:05,197 --> 00:01:10,432 effective algorithms, and methods for studying and understanding them. 13 00:01:10,432 --> 00:01:17,777 and we were looking for, of course general themes in theorems that could be, 14 00:01:17,777 --> 00:01:23,922 somehow explained, in the fact that we came up with the same formula. 15 00:01:23,922 --> 00:01:31,872 and at the same time I realized that there were lots and lots of easy, easy to 16 00:01:31,872 --> 00:01:37,647 learn, effective algorithms that many, many people needed to know. 17 00:01:37,647 --> 00:01:44,856 and I started my series of books on, on algorithms, that many of which were not 18 00:01:44,856 --> 00:01:50,635 yet in canuse/g volumes, but still people needed to know and understand. 19 00:01:50,635 --> 00:01:57,390 So we had a big laboratory of possible things to study, and we're working for a 20 00:01:57,390 --> 00:02:03,842 living doing teaching and research, and we needed to educate our students. 21 00:02:03,842 --> 00:02:10,812 so so that's where we kind of embarked on the project or the idea of that 22 00:02:10,812 --> 00:02:17,168 eventually led to analytic combinatorics. We didn't know that it would take 30 23 00:02:17,168 --> 00:02:20,739 years. As I said, in around 1980 we decided we 24 00:02:20,739 --> 00:02:24,799 should write should write a book. Well, by the way, everyone in computer 25 00:02:24,799 --> 00:02:28,260 science was deciding to write a book, because there were no books. 26 00:02:28,260 --> 00:02:32,295 it's not like teaching math, or economics, or physics where there's 27 00:02:32,295 --> 00:02:37,537 plenty of books and you choose one. Computer science, there were no books, so 28 00:02:37,537 --> 00:02:42,162 you, everybody, in their area in the 90s had to write a book. 29 00:02:42,162 --> 00:02:47,562 And we were we were no different. and around 1986 I came to, I came to 30 00:02:47,562 --> 00:02:51,012 Princeton in '85, and a year after, Phillipe came. 31 00:02:51,012 --> 00:02:57,387 and we we taught a course on Analysis of Algorithms and we had done some 32 00:02:57,387 --> 00:03:02,839 preliminary work on what we wanted to have in the book, but But that's where 33 00:03:02,839 --> 00:03:07,934 I'm at least in Philippe's mind, for sure, it really crystallized that there 34 00:03:07,934 --> 00:03:11,031 was going to be something worth doing here. 35 00:03:11,031 --> 00:03:16,573 and we worked for quite a while. We had all, both of us had many other 36 00:03:16,573 --> 00:03:22,540 endeavors, that we're involved in, and around 1992 it became clear that we had 37 00:03:22,540 --> 00:03:27,071 so much stuff that, we were really going to have to do 2 books. 38 00:03:27,071 --> 00:03:33,088 one of them was going to have to cover the basics of analysis of algorithms, 39 00:03:33,088 --> 00:03:37,698 like, deriving Catalon numbers that I, that i just explained. 40 00:03:37,698 --> 00:03:41,522 but the other one, was going to involve some. 41 00:03:41,522 --> 00:03:45,760 Doing some math. That is, there was a lot of research 42 00:03:45,760 --> 00:03:51,736 needed to really back up what was, at the time, some folk theorems or loose 43 00:03:51,736 --> 00:03:57,248 understanding of what goes on. But actually prove facts was going to 44 00:03:57,248 --> 00:04:01,103 require some serious research in that Matics. 45 00:04:01,103 --> 00:04:07,712 And Philippe wrote a series of tech reports over the next fifteen, twenty 46 00:04:07,712 --> 00:04:13,740 years, that really enbodied a lot of that math, not to mention, 100s of,. 47 00:04:13,740 --> 00:04:18,514 of research papers. it wasn't until 2009 that the second 48 00:04:18,514 --> 00:04:27,396 book, Analytic Combinatorics was finally published so, around 1995 the first book 49 00:04:27,396 --> 00:04:32,049 came out. That's our Introduction to Analysis of 50 00:04:32,049 --> 00:04:38,223 Algorithms book. in it, was a fine coverage of many of the 51 00:04:38,223 --> 00:04:46,352 things that we felt were important for people working in analysis of algorithms 52 00:04:46,352 --> 00:04:51,406 The, covering the, the basics for the kind of [UNKNOWN] that I just gave as an 53 00:04:51,406 --> 00:04:57,526 example in preparing people say to really get the most out of Knuth books and other 54 00:04:57,526 --> 00:05:01,132 research papers. So it covers recurrences and generating 55 00:05:01,132 --> 00:05:05,462 functions and asymptotics. And it talks about basic combinatorial 56 00:05:05,462 --> 00:05:10,692 structures like trees and permutations and tries, now words and mappings and, 57 00:05:10,692 --> 00:05:15,572 all the basic things you need for, algorithms for sorting and searching. 58 00:05:15,572 --> 00:05:20,877 But other things like, like factoring and, various, string processing 59 00:05:20,877 --> 00:05:24,788 algorithms. So a fine way we felt, to teach the 60 00:05:24,788 --> 00:05:31,556 mathematics needed to really do good scientific studies of the performance of 61 00:05:31,556 --> 00:05:36,462 computer programs. And so the question is, okay that's a 62 00:05:36,462 --> 00:05:43,051 book, that's what we set out to do in 1980, are we done? but, of course, as I 63 00:05:43,051 --> 00:05:50,370 just alluded what Philippe was seeing particularly Philippe in the 1980s, that 64 00:05:50,370 --> 00:05:56,682 we can get really although the classical methods can give us everything that we 65 00:05:56,682 --> 00:06:02,732 need in principle in practice we can even do better because there are general laws. 66 00:06:02,732 --> 00:06:08,536 they're, in, and it's actually possible to in many cases, we skip the details. 67 00:06:08,536 --> 00:06:14,152 and in fact the feeling was, was so strong that it, it really seemed like. 68 00:06:14,152 --> 00:06:18,087 We should work towards the goal of automatically analyzing algorithms. 69 00:06:18,087 --> 00:06:22,472 Thinking about some kind of black box that you just put in your algorithm and 70 00:06:22,472 --> 00:06:27,052 your input model and you get out an estimate of the running time and have the 71 00:06:27,052 --> 00:06:32,598 rest of it done automatically. Of course that's unattainable because of 72 00:06:32,598 --> 00:06:41,002 the halting problem, but it's amazing how close Philippe came to to this this goal 73 00:06:41,002 --> 00:06:43,476 in his research. [INAUDIBLE]. 74 00:06:43,476 --> 00:06:50,178 so just a little bit more detail on, on what Knuth was saying about the analysis 75 00:06:50,178 --> 00:06:55,028 of algorithms. so in his, in his books in, in the 60's. 76 00:06:55,028 --> 00:07:00,867 So what he said was that you should have a Good implementation that you understand 77 00:07:00,867 --> 00:07:06,695 and should have a realistic input model, so that you can run experiments and you 78 00:07:06,695 --> 00:07:11,510 can go ahead and find, figure out the cost at execution frequency of each 79 00:07:11,510 --> 00:07:14,770 operation. In the program and then you can calculate 80 00:07:14,770 --> 00:07:18,542 the total running time by multiplying the frequency and the costs. 81 00:07:18,542 --> 00:07:23,878 Now these things might involve some work. and they definitely would but certainly 82 00:07:23,878 --> 00:07:26,472 in principle you can go ahead and do that. 83 00:07:26,472 --> 00:07:31,705 And then you can run experiments to validate that your mathematical model of 84 00:07:31,705 --> 00:07:37,247 the input and the frequencies are valid, and that, that your analysis works. 85 00:07:37,247 --> 00:07:43,450 And believe me, we did this in many, many situations for both Felipe and I, 86 00:07:43,450 --> 00:07:50,811 consulted for, companies and government, and our jobs were to go ahead and, figure 87 00:07:50,811 --> 00:07:56,928 out how long a certain computation would take on a massive supercomputer, say, 88 00:07:56,928 --> 00:08:01,395 like a Cray 1 or not various other computers the time that I could name, and 89 00:08:01,395 --> 00:08:05,771 we could do it, it was very exciting it was very surprising that, that we could 90 00:08:05,771 --> 00:08:08,148 do it. we could say if you are going to do that 91 00:08:08,148 --> 00:08:12,385 it's going to take this amount of time and then they would do it and that's how 92 00:08:12,385 --> 00:08:16,581 much time it would take. we could be very very accurate about it 93 00:08:16,581 --> 00:08:21,847 really, this is nothign mjore than the scientific methiod, applied to the study 94 00:08:21,847 --> 00:08:25,993 of computer programs. And as I said, it's got the great benefit 95 00:08:25,993 --> 00:08:30,572 that, it gives a scientific foundation for analysis of algorithms. 96 00:08:30,572 --> 00:08:35,887 in that we can go ahead and predict performance and compare algorithms and 97 00:08:35,887 --> 00:08:41,126 decide which ones to use and what kind of resources they're going to consume. 98 00:08:41,126 --> 00:08:46,816 We have many, many Documented success stories along this lines. 99 00:08:46,816 --> 00:08:52,487 But there's drawbacks too. so the first drawback is that getting a 100 00:08:52,487 --> 00:08:59,845 realistic input model is, is often, very often the hard part and the other one is 101 00:08:59,845 --> 00:09:03,656 that. there is really a lot of detail in these 102 00:09:03,656 --> 00:09:08,392 kinds of analysis. so you did need experience and skill to 103 00:09:08,392 --> 00:09:14,418 get through these detailed analyses with generating functions n with f and 104 00:09:14,418 --> 00:09:18,572 [INAUDIBLE]. And so but, but the world is moving on 105 00:09:18,572 --> 00:09:21,622 There's all kinds of innovation, possible. 106 00:09:21,622 --> 00:09:24,412 So people were looking at other approaches. 107 00:09:24,412 --> 00:09:30,052 and, 1 that has been extremely successful is, what I refer to as the Theory of 108 00:09:30,052 --> 00:09:34,937 Algorithms, it was started out by Aho, Hopcroft, and Ullman in the '70s. 109 00:09:34,937 --> 00:09:41,855 High and is widely followed textbook by Cormen, Leiserson, Rivest, and Stein 110 00:09:41,855 --> 00:09:47,553 today that address the drawbacks in Knuth's approach in two ways. 111 00:09:47,553 --> 00:09:52,199 First thing was, analyze the worst-case cost of the algorithm. 112 00:09:52,199 --> 00:09:57,601 so provide guarantees on the running time no matter what the input is. 113 00:09:57,601 --> 00:10:02,292 That has the big benefit of taking the model out of the picture. 114 00:10:02,292 --> 00:10:06,988 you can, if you can guarantee that the running time is low, you're in good 115 00:10:06,988 --> 00:10:09,884 shape. and the other thing to do, is just do 116 00:10:09,884 --> 00:10:14,798 approximate analyses, and really, just use o notation, and get an upper bound on 117 00:10:14,798 --> 00:10:17,929 the running time. That still provides a guarantee. 118 00:10:17,929 --> 00:10:21,018 And if that guarantee's low, you're in good shape. 119 00:10:21,018 --> 00:10:25,712 And that has the big benefit of taking a lot of the detail out of the analysis. 120 00:10:25,712 --> 00:10:31,052 and then, go ahead and classify algorithms by these costs, the guaranteed 121 00:10:31,052 --> 00:10:35,152 worst-case running time. and that was very successful. 122 00:10:35,152 --> 00:10:40,314 I'd enabled what one blogger called, a new age of algorithm design. 123 00:10:40,314 --> 00:10:46,438 and there's literally [COUGH] hundreds, thousands a huge fraction of our 124 00:10:46,438 --> 00:10:52,032 computational infrastructure started with studies like this. 125 00:10:52,032 --> 00:10:55,391 This. but there is a big drawback, and the 126 00:10:55,391 --> 00:11:00,957 drawback is that this analysis is usually, or often, at least, not suitable 127 00:11:00,957 --> 00:11:06,262 for scientific studies. you can't really, predict performance or 128 00:11:06,262 --> 00:11:10,540 compare algorithms. If all you have is an upper-bound and the 129 00:11:10,540 --> 00:11:15,330 worst-case cause. It might be much to high, or might be a 130 00:11:15,330 --> 00:11:20,878 worst case that's not realized in practical situations, and many other 131 00:11:20,878 --> 00:11:28,685 problems It's not what, Oyler or Poinker Ray, or Strolling, were, trying to do to 132 00:11:28,685 --> 00:11:34,947 come up with, precise predictions. so that's the context for, really 133 00:11:34,947 --> 00:11:41,800 thinking about, analytic combinatorics. Knuth was very successful, but kind of 134 00:11:41,800 --> 00:11:47,595 stuck with the model, and there's detail excessive detail, in the analysis. 135 00:11:47,595 --> 00:11:51,062 In AHU and CLRS they're working on worst-case. 136 00:11:51,062 --> 00:11:57,729 It might not be relevant, and the And the O bounds, worst case upper bounds are too 137 00:11:57,729 --> 00:12:03,717 loose to be useful in lots of situations. But what analytic combinatorics can 138 00:12:03,717 --> 00:12:07,218 provide is really a basis for scientific studies. 139 00:12:07,218 --> 00:12:11,855 It does it in two ways. provides a calculus for developing 140 00:12:11,855 --> 00:12:17,970 models, or input models that is very very broad and extensible. 141 00:12:17,970 --> 00:12:23,064 that's number one. And number two a lot of the detail can be 142 00:12:23,064 --> 00:12:28,332 encompassed in universal laws that are proven mathematical facts. 143 00:12:28,332 --> 00:12:33,156 but, really, take care of all the detail in the analysis. 144 00:12:33,156 --> 00:12:38,902 So that's the context, where we're going to start talking about really what 145 00:12:38,902 --> 00:12:40,828 analytic combinatorics is.