1 00:00:03,720 --> 00:00:09,356 Next, we're going to take a moment to describe in detail the scientific 2 00:00:09,356 --> 00:00:14,081 approach that we use in modern analysis of algorithms. 3 00:00:14,081 --> 00:00:20,814 so again, just a note about notation. in the theory of algorithms, when they're 4 00:00:20,814 --> 00:00:27,120 looking at upper bounds on worst case performance they use these notations big 5 00:00:27,120 --> 00:00:32,685 O, big omega, and big theta to try to capture the order of growth, and that's 6 00:00:32,685 --> 00:00:38,769 what they use for classifying algorithms. if g of N is big O of f of N, it means 7 00:00:38,769 --> 00:00:44,852 that the ratio of g of N to f of N is bounded from above as N goes to infinity. 8 00:00:44,852 --> 00:00:48,340 If it's omega, it means it's bounded from below. 9 00:00:48,340 --> 00:00:53,341 and if it's theta, it means that it's bounded from both above and below. 10 00:00:53,341 --> 00:00:58,407 so there's, so this one says, there's a constant such that g of N is less than 11 00:00:58,407 --> 00:01:02,369 that constant of f f of N. this one says, there's two constants 12 00:01:02,369 --> 00:01:06,916 that's it's in between. so that allows classification according 13 00:01:06,916 --> 00:01:11,955 to functional growth. as I mentioned mergesort is N log N and 14 00:01:11,955 --> 00:01:16,803 quicksort is N squared. so that's the, the notation that you 15 00:01:16,803 --> 00:01:23,293 often see throughout the literature describing the performance of algorithms. 16 00:01:23,293 --> 00:01:27,437 But as I mentioned, big O notation is dangerous. 17 00:01:27,437 --> 00:01:31,660 And I'll have more to say about that in just a minute. 18 00:01:31,660 --> 00:01:36,738 so, you can't, it's not scientific to use the big O notation to try to compare 19 00:01:36,738 --> 00:01:40,102 algorithms. you can't say, if you say the running 20 00:01:40,102 --> 00:01:45,379 time is big O of N to the c, that's not of any use for predicting performance. 21 00:01:45,379 --> 00:01:51,249 It's an upper bound on the worst case. the actual performance may be much better 22 00:01:51,249 --> 00:01:55,470 than the worst case. and it could be that the even the actual 23 00:01:55,470 --> 00:01:59,230 bound is less than what's given by the big O notation. 24 00:01:59,230 --> 00:02:04,876 It's fine for a first cut of classifying algorithms, but not useful for comparing. 25 00:02:04,876 --> 00:02:08,990 what we use instead is what's called the tilde notation. 26 00:02:08,990 --> 00:02:15,171 and so what we'll typically say is that the running time of an algorithm is 27 00:02:15,171 --> 00:02:20,298 tilde, a constant times say some function of N where N is the input size. 28 00:02:20,298 --> 00:02:25,047 That does provide an effective path for prediction performance. 29 00:02:25,047 --> 00:02:28,666 And I'll show some examples of that later on. 30 00:02:28,666 --> 00:02:34,998 So, we don't use the common big O, big theta omega notation very much except in 31 00:02:34,998 --> 00:02:41,180 a specific technical sense that I'll talk about later on when we talk about 32 00:02:41,180 --> 00:02:45,792 asymptotic approximations. So, [COUGH] big O notation is useful for 33 00:02:45,792 --> 00:02:51,115 a lot of reasons and it dates back a few centuries and, and we do use it in math. 34 00:02:51,115 --> 00:02:56,579 But it's a common error to think that big O notation is useful for predicting 35 00:02:56,579 --> 00:03:00,502 performance. and I just want to make sure to nip that 36 00:03:00,502 --> 00:03:05,406 problem in the bag right away. This is what often happens to me when I 37 00:03:05,406 --> 00:03:10,575 give talks around the world on this topic, typical exchange and say that Q 38 00:03:10,575 --> 00:03:14,111 and A for my talk, depending on how formal it is to 39 00:03:14,111 --> 00:03:16,839 somebody. I'll, I'll say, okay, big O notation is 40 00:03:16,839 --> 00:03:19,971 dangerous. You can't use it to predict performance. 41 00:03:19,971 --> 00:03:26,072 and somebody will ask or shout out but an algorithm that is big O of N log N 42 00:03:26,072 --> 00:03:28,239 surely beats one that's big O of N2. squared. 43 00:03:28,239 --> 00:03:33,256 And then, I trot out, say, the quicksort, mergesort example and say, well, not by 44 00:03:33,256 --> 00:03:37,096 the definition, big O is just an upper bound on the worst case. 45 00:03:37,096 --> 00:03:41,988 And they'll say, well, so use the theta notation which says that it's in between. 46 00:03:41,988 --> 00:03:45,518 and I say well, that maybe gets rid of the upper bound. 47 00:03:45,518 --> 00:03:48,677 But you're still typically bounding the worst case. 48 00:03:48,677 --> 00:03:53,136 is your input a worst case? and even with that logic, and with a 49 00:03:53,136 --> 00:03:56,418 compelling example like quicksort versus mergesort, 50 00:03:56,418 --> 00:04:01,473 usually what happens is the questioner whispers to one of his colleagues. 51 00:04:01,473 --> 00:04:04,758 Well, I'd still use the N log N algorithm, wouldn't you? 52 00:04:04,758 --> 00:04:08,956 [LAUGH] and actually such people usually don't program much. 53 00:04:08,956 --> 00:04:12,666 and shouldn't be recommending what practitioners do. 54 00:04:12,666 --> 00:04:17,753 but surely, we can do better than this. that's part of what analytic 55 00:04:17,753 --> 00:04:23,083 combinatorics is all about. There's another idea that's out there as 56 00:04:23,083 --> 00:04:26,817 well, and that's the concept of a galactic algorithm. 57 00:04:26,817 --> 00:04:33,207 and this, I found this on a friend's blog Dick Lipton, who said let's define a 58 00:04:33,207 --> 00:04:39,167 algorithm that will never be used as being galactic and why will it never be 59 00:04:39,167 --> 00:04:42,182 used? Because no one would ever notice any 60 00:04:42,182 --> 00:04:45,270 affect about this algorithm in this galaxy. 61 00:04:45,270 --> 00:04:51,624 because any savings is going to happen for input size so large that it couldn't, 62 00:04:51,624 --> 00:04:56,943 it couldn't happen in this galaxy. So, an example of galactic algorithm and 63 00:04:56,943 --> 00:05:02,603 this one is actually maybe planetary or something, it's actually close to the 64 00:05:02,603 --> 00:05:06,424 real world, is Chazelle's linear time triangulation 65 00:05:06,424 --> 00:05:09,820 algorithm. So, the problem is to find a way to 66 00:05:09,820 --> 00:05:15,319 triangulate a polygon in linear time. it was a surprising result and a 67 00:05:15,319 --> 00:05:21,771 theoretical tour de force to prove that it was possible to solve this problem in 68 00:05:21,771 --> 00:05:25,776 linear time. But the method is much too complicated 69 00:05:25,776 --> 00:05:31,338 for anyone to implement. And if anyone did implement it, the, the 70 00:05:31,338 --> 00:05:37,938 cost of the implementation would definitely exceed any savings until N is 71 00:05:37,938 --> 00:05:43,130 so hard, large that it would take another galaxy to deal with it. 72 00:05:43,130 --> 00:05:47,879 And [COUGH] this is you know, an interesting 73 00:05:47,879 --> 00:05:51,548 situation. I think one of the problems is that so 74 00:05:51,548 --> 00:05:57,263 many algorithms that are out there, that are being published in the literature, in 75 00:05:57,263 --> 00:06:04,248 this category after Lipton introduced the concept one of the contributors to his 76 00:06:04,248 --> 00:06:09,681 blog estimated that something like 75 to 95% of the papers in the theoretical 77 00:06:09,681 --> 00:06:12,856 Computer Science conferences are galactic. 78 00:06:12,856 --> 00:06:18,473 and I think the problem is that practitioners aren't necessarily aware 79 00:06:18,473 --> 00:06:21,716 that they're galactic, and they maybe try to use them. 80 00:06:21,716 --> 00:06:27,285 when a relatively simple analysis would say there's no point in a practitioner 81 00:06:27,285 --> 00:06:32,120 taking a look at this the papers should have asterisks on them or something. 82 00:06:32,120 --> 00:06:36,489 So, I, I think it's okay for basic research to drive the agenda and there's 83 00:06:36,489 --> 00:06:41,271 nothing wrong with trying to find the algorithm with the best upper bound and 84 00:06:41,271 --> 00:06:46,104 worst case performance but we have to do something about the common error where 85 00:06:46,104 --> 00:06:50,615 people think that a galactic algorithm is actually useful in practice. 86 00:06:50,615 --> 00:06:55,065 There's a lot of denial out there. Now, here's another thing that often 87 00:06:55,065 --> 00:06:58,356 happens to me. This was an actual exchange with a very 88 00:06:58,356 --> 00:07:01,831 prominent theoretical computer scientist a few years ago. 89 00:07:01,831 --> 00:07:06,581 and he said in a talk, well the algorithm A, that actually is a pretty 90 00:07:06,581 --> 00:07:11,774 straightforward algorithm that's in widespread use, is a bad algorithm. 91 00:07:11,774 --> 00:07:17,161 Google and other internet providers should be interested in my new algorithm, 92 00:07:17,161 --> 00:07:19,380 algorithm B. [COUGH] 93 00:07:19,380 --> 00:07:24,426 and so, in the question and answer I said, well, what's the matter with 94 00:07:24,426 --> 00:07:27,644 algorithm A? and, and, and he responded, it's not 95 00:07:27,644 --> 00:07:31,960 optimal. it's running time has an extra log log N factor. 96 00:07:31,960 --> 00:07:38,047 and that's always a tip off for me. I say, well, but your algorithm is very 97 00:07:38,047 --> 00:07:44,057 complicated, it takes ten pages to describe. by the way we all know that log 98 00:07:44,057 --> 00:07:48,911 log N is less than six in this universe, that's two to the 64th. 99 00:07:48,911 --> 00:07:53,361 and, and so if N is to the 64th, it's less than six. 100 00:07:53,361 --> 00:07:57,616 And, and so, not only that it's just an upper bound. 101 00:07:57,616 --> 00:08:00,893 Not only that your algorithm is so complicated. 102 00:08:00,893 --> 00:08:05,140 It's certain to run ten to a hundred times faster in any conceivable real 103 00:08:05,140 --> 00:08:08,550 world situation. Why should Google care about algorithm B, 104 00:08:08,550 --> 00:08:11,720 as you said? and then the response was, well, I like 105 00:08:11,720 --> 00:08:14,173 algorithm B. I don't care about Google. 106 00:08:14,173 --> 00:08:18,420 and again, that's fine to do research for the intellectual challenge. 107 00:08:18,420 --> 00:08:22,846 just don't say that some practitioner should be interested in it. 108 00:08:22,846 --> 00:08:27,121 Surely we can do better than that. So, what I want to talk about 109 00:08:27,121 --> 00:08:32,549 specifically is the scientific approach, say, the modern rendition of what Knuth 110 00:08:32,549 --> 00:08:38,389 taught us that is used for many, many algorithms in the fourth edition of my 111 00:08:38,389 --> 00:08:42,100 algorithms book which is co-authored with Kevin Wayne. 112 00:08:42,100 --> 00:08:47,310 so, this is described in a lot of detail with examples in Section 1.4 of the book. 113 00:08:47,310 --> 00:08:52,457 Again, as Knuth said we start with a complete implementation that we can test. 114 00:08:52,457 --> 00:08:57,915 and then therefore we'll be able to make hypotheses about the performance of that 115 00:08:57,915 --> 00:09:02,687 implementation and test them. And then, what we're going to do is maybe 116 00:09:02,687 --> 00:09:08,330 try to avoid some of the detail in Knuth. And we're going to analyze the algorithm 117 00:09:08,330 --> 00:09:12,749 by trying to find an abstract operation that's in the inner loop. 118 00:09:12,749 --> 00:09:17,032 That is, it's get executed more times than any other operations. 119 00:09:17,032 --> 00:09:22,335 and then, we'll also need to develop some realistic model for the input to the 120 00:09:22,335 --> 00:09:24,919 program. That's still a sticking point. 121 00:09:24,919 --> 00:09:29,474 and then, we'll just analyze the frequency of execution of that one 122 00:09:29,474 --> 00:09:34,654 operation for input size N. and our hypothesis will be that the 123 00:09:34,654 --> 00:09:41,000 actual running time is proportional to a constant times that frequency. 124 00:09:41,000 --> 00:09:45,775 That's it. so the hypothesis might be wrong but we 125 00:09:45,775 --> 00:09:49,992 can test it. and we have the tilde operation and I'll 126 00:09:49,992 --> 00:09:56,281 show you specifically how we can go ahead and test it and actually the unknown 127 00:09:56,281 --> 00:10:02,348 constant is an annoying thing care around, carry around but not actually too 128 00:10:02,348 --> 00:10:07,898 bad because it does allow us to make specific mathematical calculations. 129 00:10:07,898 --> 00:10:11,136 So, what we'll do then is once we have the 130 00:10:11,136 --> 00:10:17,170 hypothesis, we're going to validate the hypothesis by, first of all, we want to 131 00:10:17,170 --> 00:10:20,170 generate some large inputs according to the model. 132 00:10:20,170 --> 00:10:24,730 So, for example, we'll look at sorting algorithms where the model is that the 133 00:10:24,730 --> 00:10:29,650 things are randomly ordered and distinct. And so, it's easy to write a program to 134 00:10:29,650 --> 00:10:32,470 generate large randomly ordered distinct files. 135 00:10:32,470 --> 00:10:36,730 and then, we can just run the program for large input to calculate A. 136 00:10:36,730 --> 00:10:39,850 And actually, we don't, we can even skip that step. 137 00:10:39,850 --> 00:10:44,858 I'll show you that in a minute. But we definitely can get A that way an 138 00:10:44,858 --> 00:10:48,542 estimate of A. And then that give us a model that we can 139 00:10:48,542 --> 00:10:53,674 use to predict performance for even larger inputs and check our hypothesis. 140 00:10:53,674 --> 00:10:58,082 that's the scientific approach to the analysis of algorithms. 141 00:10:58,082 --> 00:11:04,010 So really, then, later, what we need to do also is find an application that 142 00:11:04,010 --> 00:11:10,720 actually uses real world data in testing application context to validate the model 143 00:11:10,720 --> 00:11:15,018 as well. that's actually the hardest part that's 144 00:11:15,018 --> 00:11:19,768 often overlooked nowadays. and then, as in any application 145 00:11:19,768 --> 00:11:26,554 scientific method we'll refine and repeat and revise of the model and the algorithm 146 00:11:26,554 --> 00:11:30,400 as necessary or as we learn much about the problem. 147 00:11:30,400 --> 00:11:35,586 As I mentioned earlier, one of the great things that happens with this process is 148 00:11:35,586 --> 00:11:40,324 that often we learn things about the algorithm that allow us, enable us, to 149 00:11:40,324 --> 00:11:45,383 develop improved versions by doing this. And we have many, many examples of this 150 00:11:45,383 --> 00:11:50,505 for sorting and searching algorithms, and graph algorithms, and string processing 151 00:11:50,505 --> 00:11:55,755 and data compression and many, many other applications where we successfully apply 152 00:11:55,755 --> 00:12:00,045 this approach to develop good implementations and understand their 153 00:12:00,045 --> 00:12:03,375 performance. so that's now, what this course is going 154 00:12:03,375 --> 00:12:07,397 to be all about is this analysis of the frequency execution. 155 00:12:07,397 --> 00:12:11,113 That's where the math is. and so, but I want to give this full 156 00:12:11,113 --> 00:12:15,550 context so people can understand why we're going to this trouble. 157 00:12:15,550 --> 00:12:21,372 So as I mentioned, we don't use the, the big O notation, or omega or theta that 158 00:12:21,372 --> 00:12:21,933 much. In, 159 00:12:21,933 --> 00:12:25,020 instead that's for the theory of algorithms. 160 00:12:25,020 --> 00:12:30,562 Instead we're going to use the tilde notation and all the tilde notation means 161 00:12:30,562 --> 00:12:36,384 is that two functions g of N is tilde f of N if their ratio approaches one as N 162 00:12:36,384 --> 00:12:42,487 approaches infinity. And usually we have f of N is a constant times A standard 163 00:12:42,487 --> 00:12:45,547 function of N. so that's the notation. 164 00:12:45,547 --> 00:12:48,772 So we're just using tilde and that's good. 165 00:12:48,772 --> 00:12:53,859 that simplifies things a bit. and then, we're just left with these 166 00:12:53,859 --> 00:12:57,514 basic components. So, one of the basic components of 167 00:12:57,514 --> 00:13:01,240 algorithm analysis involves programming. So 168 00:13:01,240 --> 00:13:06,637 people who do analysis with algorithms need to be comfortable with implementing 169 00:13:06,637 --> 00:13:11,384 algorithms, running them and, and be able to at least count operations. 170 00:13:11,384 --> 00:13:15,676 so you need a good implementation. Now, maybe someone did, did the 171 00:13:15,676 --> 00:13:21,983 implementation but still you want to have experience with it on your own computer 172 00:13:21,983 --> 00:13:25,040 to test various hypotheses that you might have. 173 00:13:25,040 --> 00:13:29,653 then we got the mathematical challenge and that's again going to be most of our 174 00:13:29,653 --> 00:13:33,838 emphasis in this course where we develop a model, analyze the algorithm in the 175 00:13:33,838 --> 00:13:36,359 model. and what we're going to talk about in 176 00:13:36,359 --> 00:13:39,041 this course, is that really, we need to do the math. 177 00:13:39,041 --> 00:13:43,118 And that's the kind of math that I'm going to be talking about very soon in 178 00:13:43,118 --> 00:13:46,541 just a minute. and then, there's a scientific process of 179 00:13:46,541 --> 00:13:51,278 running the algorithm to solve a real problem and checking for agreement with 180 00:13:51,278 --> 00:13:54,193 the model. and so, you can't do that, you can't 181 00:13:54,193 --> 00:13:58,565 really compare two algorithms until you've done all the rest of this. 182 00:13:58,565 --> 00:14:01,420 so, it's very important to have that concept, 183 00:14:01,420 --> 00:14:07,674 context to understand why we're so interested in getting this math done 184 00:14:07,674 --> 00:14:12,914 right without excessive detail. Now there's definitely potential 185 00:14:12,914 --> 00:14:16,545 drawbacks still. And [COUGH] you, you know, 186 00:14:16,545 --> 00:14:21,919 the the theory of algorithms still it goes to places where we can't go. 187 00:14:21,919 --> 00:14:26,713 number one is, the model might not be, might not have a realistic model. 188 00:14:26,713 --> 00:14:31,288 And that's actually a challenge in every scientific discipline. 189 00:14:31,288 --> 00:14:37,243 Now, we do have a big advantage in Computer Science because we can randomize 190 00:14:37,243 --> 00:14:40,511 to make, make the model actually totally valid. 191 00:14:40,511 --> 00:14:43,780 And I'll show an example in just a minute. 192 00:14:43,780 --> 00:14:48,530 so, if we don't have a realistic model, maybe we can get a realistic model by 193 00:14:48,530 --> 00:14:51,380 randomizing. That's a very powerful concept that if 194 00:14:51,380 --> 00:14:55,459 you don't get, if you're doing science that involves going to the moon or 195 00:14:55,459 --> 00:14:59,925 killing monkeys or something. second thing is, the math might be too 196 00:14:59,925 --> 00:15:03,134 difficult. that's also a big challenge in any 197 00:15:03,134 --> 00:15:07,501 scientific discipline. statistical physics and many other areas. 198 00:15:07,501 --> 00:15:12,530 New developments in mathematics were involved in order to do the science. 199 00:15:12,530 --> 00:15:17,361 And that's certainly going to be it here. And really, that's what analytic 200 00:15:17,361 --> 00:15:21,199 combinatorics is. A calculus for analysis of algorithms is 201 00:15:21,199 --> 00:15:26,085 the true motivation for this course. and thirdly, it might be that the 202 00:15:26,085 --> 00:15:29,862 experiments are too difficult to really validate the model. 203 00:15:29,862 --> 00:15:34,921 and again that's not much of a point compared to any other scientific 204 00:15:34,921 --> 00:15:38,442 discipline. no problem for us to run an algorithm a 205 00:15:38,442 --> 00:15:42,348 million times. And we do it we do it a lot whereas, if 206 00:15:42,348 --> 00:15:47,983 you had to feed a million mice you might have some restrictions or or go to a 207 00:15:47,983 --> 00:15:53,041 million planets or whatever else. and, but it's a roadblock for a lot of 208 00:15:53,041 --> 00:15:58,560 people trying to study algorithms because actually they're trying to study galactic 209 00:15:58,560 --> 00:16:01,381 algorithms. It might be way too difficult to 210 00:16:01,381 --> 00:16:05,703 implement and if you can't implement it why, why try to analyze it? 211 00:16:05,703 --> 00:16:10,625 And it's fine for the intellectual challenge but again there are people out 212 00:16:10,625 --> 00:16:14,886 there that are thinking that the algorithms that you're developing are 213 00:16:14,886 --> 00:16:20,588 useful in practice and really they should be validated scientifically before the 214 00:16:20,588 --> 00:16:23,350 poor working programmer is faced with them. 215 00:16:23,350 --> 00:16:29,460 so that's an outline of our approach to the analysis of algorithms.