1 00:00:00,000 --> 00:00:03,031 Welcome to this first course in the design and analysis of algorithms. 2 00:00:03,031 --> 00:00:06,453 I imagine many of you are already clear on your reasons for taking this course, 3 00:00:06,453 --> 00:00:08,792 but let me begin by justifying the course's existence. 4 00:00:08,792 --> 00:00:11,564 I'm giving you several different motivations for learning about 5 00:00:11,564 --> 00:00:13,080 algorithms. So, what is an algorithm? 6 00:00:13,080 --> 00:00:16,328 Well, we're not going to be needing a precise definition in this course, but 7 00:00:16,328 --> 00:00:18,754 essentially, an algorithm is a well-defined set of rules. 8 00:00:18,754 --> 00:00:21,612 A recipe in effect for solving some kind of computational problem. 9 00:00:21,612 --> 00:00:24,601 So, for example, maybe you're given a bunch of numbers and you want to 10 00:00:24,601 --> 00:00:27,849 rearrange them into sorted order. Maybe you're given a road network with an 11 00:00:27,849 --> 00:00:31,444 origin and a destination, and you want to compute the shortest path from point a to 12 00:00:31,444 --> 00:00:33,566 point b. Maybe you're given a bunch of tasks with 13 00:00:33,566 --> 00:00:37,878 deadlines and you want to know weather or not it's feasible to accomplish all of 14 00:00:37,878 --> 00:00:40,050 those tasks by their respective deadlines. 15 00:00:40,050 --> 00:00:43,094 So, why study algorithms? Well, first of all, understanding the 16 00:00:43,094 --> 00:00:47,205 field of algorithms, and also the related field of data structures, is crucial for 17 00:00:47,205 --> 00:00:50,808 doing serious work in pretty much any other branch of Computer Science. 18 00:00:50,808 --> 00:00:54,715 That's the precise reason why here at Stanford University, this is the course 19 00:00:54,715 --> 00:00:58,724 that's required for all of the degrees that the Computer Science Department 20 00:00:58,724 --> 00:01:02,682 grants, be it a Bachelors, a Masters, or a PhD degree, we insist that you have 21 00:01:02,682 --> 00:01:06,539 mastery of the field of algorithms. So, what are some examples of uses in the 22 00:01:06,539 --> 00:01:09,482 rest of Computer Science? Well, if you're doing routing and 23 00:01:09,482 --> 00:01:13,339 communication network, that piggybacks on classical shortest path algorithms. 24 00:01:13,339 --> 00:01:17,219 the effectiveness of public key cryptography really rests on that, 25 00:01:17,219 --> 00:01:20,864 of number theoretic algorithms. In, say, computer graphics, you need the 26 00:01:20,864 --> 00:01:24,509 computational primitives that are supplied by the study of geometric 27 00:01:24,509 --> 00:01:27,203 algorithms. Database indices rely on balance search 28 00:01:27,203 --> 00:01:29,685 tree data structures, as covered in this course. 29 00:01:29,685 --> 00:01:33,700 and computational biology uses dynamic programming algorithms to measure 30 00:01:33,700 --> 00:01:37,020 similarity among genomes. And the list goes on and on. 31 00:01:37,020 --> 00:01:40,796 A second reason to study algorithms is that they play a key role in modern 32 00:01:40,796 --> 00:01:43,918 technological innovation. Obviously, I could give any number of 33 00:01:43,918 --> 00:01:46,637 examples here. Let me just state one super obvious one. 34 00:01:46,637 --> 00:01:50,464 which is that search engines use a tapestry of algorithms to efficiently 35 00:01:50,464 --> 00:01:52,629 compute the relevance of various web pages. 36 00:01:52,629 --> 00:01:56,456 The most famous search algorithm which you may have heard of is the page rank 37 00:01:56,456 --> 00:01:58,320 algorithm in use by Google. Indeed, 38 00:01:58,320 --> 00:02:02,149 in a December 2010 report to the United States Whitehouse, the President's 39 00:02:02,149 --> 00:02:05,927 Counsel of Advisers on Science and Technology argued that in many areas, 40 00:02:05,927 --> 00:02:10,176 performance gains due to improvements in algorithms, have vastly exceeded even the 41 00:02:10,176 --> 00:02:13,953 dramatic performance gains due to increased processor speed, as you'd be 42 00:02:13,953 --> 00:02:17,492 familiar with in the form of Moore's Law. Third, although this is getting 43 00:02:17,492 --> 00:02:21,391 significantly outside the scope of this course, algorithms are increasingly being 44 00:02:21,391 --> 00:02:24,954 used to provide a novel lens on processes outside of Computer Science and 45 00:02:24,954 --> 00:02:27,216 Technology. For example, the set of quantum 46 00:02:27,216 --> 00:02:30,586 computation has provided a new and computational viewpoint on quantum 47 00:02:30,586 --> 00:02:34,437 mechanics, price fluctuations in economic markets can be fruitfully viewed as an 48 00:02:34,437 --> 00:02:37,855 algorithmic process, and even evolution can be usefully thought of as, as a 49 00:02:37,855 --> 00:02:41,902 surprisingly search algorithm. The last two reasons I'm going to give 50 00:02:41,902 --> 00:02:45,827 you might sound a little flipping but, you know, I, I think there is more than a 51 00:02:45,827 --> 00:02:49,450 grain of truth to both of them. Now, I don't know about you but back when 52 00:02:49,450 --> 00:02:53,476 I was a student my favorite classes were always challenging classes but after I 53 00:02:53,476 --> 00:02:57,350 struggled through them, I somehow felt I had a few more IQ points than when I 54 00:02:57,350 --> 00:02:59,816 started. So, I hope this course provides a similar 55 00:02:59,816 --> 00:03:03,540 experience for many of you that one the one hand it's a bit of a struggle. 56 00:03:03,540 --> 00:03:07,364 You find the, the concepts challenging but perhaps you feel just a tinge smarter 57 00:03:07,364 --> 00:03:10,145 after we're done. Finally, I hope that by the end of the 58 00:03:10,145 --> 00:03:13,793 course, a constant fraction of you will agree with me that designing and 59 00:03:13,793 --> 00:03:17,492 analyzing algorithms is simply fun. It's an endeavor that requires a rare 60 00:03:17,492 --> 00:03:21,494 blend of creativity and precision and it can certainly be frustrating at times, 61 00:03:21,494 --> 00:03:25,446 but even more than that, it is addictive. So, let's now descend from these lofty 62 00:03:25,446 --> 00:03:29,449 generalities and get much more concrete. And also, let's remember that we've all 63 00:03:29,449 --> 00:03:32,540 been learning and using algorithms since we were little kids. 64 00:03:33,960 --> 00:03:38,078 So, once upon a time, in roughly third grade or so, you learned how to multiply 65 00:03:38,078 --> 00:03:40,698 two numbers. Now, you probably weren't thinking in 66 00:03:40,698 --> 00:03:44,977 these terms at the time, but multiplying two numbers is certainly a well-defined 67 00:03:44,977 --> 00:03:49,363 computational problem and that procedure you learned back in third grade or so, is 68 00:03:49,363 --> 00:03:52,411 indeed an algorithm. So, let's just make that a little bit 69 00:03:52,411 --> 00:03:55,032 more precise. In this computational problem, we're 70 00:03:55,032 --> 00:03:57,760 given as input, two numbers, let's say with n digits. 71 00:03:57,760 --> 00:04:02,866 And to make things interesting, why don't you think about n as being really quite 72 00:04:02,866 --> 00:04:06,965 large, say in the thousands? Maybe we're implementing an algorithm 73 00:04:06,965 --> 00:04:12,135 that's going to be used in a cryptography application where you need to keep track 74 00:04:12,135 --> 00:04:16,422 of really quite large numbers. So, if we call the two input numbers x 75 00:04:16,422 --> 00:04:19,763 and y, the problem is simply to compute their product, xy. 76 00:04:19,763 --> 00:04:21,058 times y. So, a quick digression. 77 00:04:21,058 --> 00:04:25,147 I'll certainly be the first to admit that my handwriting is not the greatest. 78 00:04:25,147 --> 00:04:28,812 I got a C in penmanship back in elementary school, and I think the 79 00:04:28,812 --> 00:04:33,007 teacher was being a little generous but, you know, it's got an acquired taste, but 80 00:04:33,007 --> 00:04:36,710 trust me, you will get used to it. Okay, back to integer multiplication. 81 00:04:36,710 --> 00:04:40,883 Now, when we talk about procedures for multiplying two numbers, we're going to 82 00:04:40,883 --> 00:04:45,272 be interested in counting how many steps are required, in order to execute the 83 00:04:45,272 --> 00:04:47,494 multiplication. So, how do we count a step? 84 00:04:47,494 --> 00:04:51,341 We'll talk more about this more later, but for multiplying two numbers, let's 85 00:04:51,341 --> 00:04:55,026 just call a step, the addition or multiplication of two single digit 86 00:04:55,026 --> 00:04:57,063 numbers. So, let's review the integer 87 00:04:57,063 --> 00:05:01,376 multiplication algorithm that we learned back in grade school, just by working 88 00:05:01,376 --> 00:05:05,339 through a concrete example. Specifically, let's think of n equals 4. 89 00:05:05,339 --> 00:05:09,449 So, let's look at two four-digit numbers let's say, five, six, seven, eight, and 90 00:05:09,449 --> 00:05:13,251 one, two, three, four. Now, as you'll recall, the procedure we 91 00:05:13,251 --> 00:05:17,738 learned way back when was just to take each digit of the bottom number and 92 00:05:17,738 --> 00:05:22,703 multiply it by each of the top numbers. And then to take each of those n partial 93 00:05:22,703 --> 00:05:26,532 products, and add them up. So, for example, you start with the four. 94 00:05:26,532 --> 00:05:29,822 You multiply it by eight, so you get 32. Carry the three. 95 00:05:29,822 --> 00:05:32,454 4 times 7 is 28, add the three, you get one, 96 00:05:32,454 --> 00:05:36,304 carry the three, and so on. So, that gives you this first partial 97 00:05:36,304 --> 00:05:38,455 product. 22, 7, 12. 98 00:05:38,455 --> 00:05:43,835 Then, you do a shift, so you effectively put a zero in this final digit, and you 99 00:05:43,835 --> 00:05:47,490 repeat that procedure using the next digit, the three. 100 00:05:47,490 --> 00:05:52,480 So again, three times eight is four, carry the two, and so on. 101 00:05:52,480 --> 00:05:56,980 And you compute the final two partial products using the two and the one. 102 00:05:58,320 --> 00:06:02,490 And having computed all of the partial products, you just add them up to get the 103 00:06:02,490 --> 00:06:06,035 final product. Now, the question I'm interested in is, 104 00:06:06,035 --> 00:06:10,269 how much work, how many primitive operations did we do to multiply these 105 00:06:10,269 --> 00:06:13,093 two numbers. And more generally, how many does it 106 00:06:13,093 --> 00:06:16,563 require to multiply two n digit numbers as a function of n. 107 00:06:16,563 --> 00:06:20,210 Well, just to get sort of a ballpark view for what's going on, 108 00:06:20,210 --> 00:06:24,621 we started with two n digit numbers. And at the end of the day, we basically 109 00:06:24,621 --> 00:06:28,351 filled out a grid of size roughly n by n, give or take a little bit. 110 00:06:28,351 --> 00:06:32,767 So, just in ballpark terms, it seems that multiplying two n digit numbers required 111 00:06:32,767 --> 00:06:36,802 essentially a quadratic number of operations, a small number of operations 112 00:06:36,802 --> 00:06:40,782 to fill in each entry in this grid. The grid is n by n roughly so that is 113 00:06:40,782 --> 00:06:44,599 roughly n squared operations. In a little more detail, we could look at 114 00:06:44,599 --> 00:06:48,989 each of the partial products separately. So, to compute, say, this first partial 115 00:06:48,989 --> 00:06:52,812 product, what do we do? We take the four we multiplied it by each 116 00:06:52,812 --> 00:06:56,634 of the n digits on top. We also did some carries, so that effects 117 00:06:56,634 --> 00:06:59,740 things a little bit. But, in the end, we did somewhere 118 00:06:59,740 --> 00:07:04,279 between, say, n and the 2n, primitive operations to compute this first partial 119 00:07:04,279 --> 00:07:07,026 product. And that's true, of course, for each of 120 00:07:07,026 --> 00:07:11,387 the n partial products. So, that's roughly n operations for each 121 00:07:11,387 --> 00:07:15,889 of the n partial products. So, that's roughly n squared operations. 122 00:07:15,889 --> 00:07:20,935 It could be all of the partial products. Then, we have to add it all up at the 123 00:07:20,935 --> 00:07:23,868 end. But that takes just an extra number of 124 00:07:23,868 --> 00:07:28,232 constant times n primitive operations to do all of those additions. 125 00:07:28,232 --> 00:07:33,620 So summarizing, overall, the number of primitive operations required to multiply 126 00:07:33,620 --> 00:07:38,940 to n digit numbers using this procedure grows quadratically with the length N. 127 00:07:40,720 --> 00:07:45,321 So, for example, if you double the length of two numbers, you expect to do roughly 128 00:07:45,321 --> 00:07:49,979 four times as many primitive operations if you use this iterative algorithm for 129 00:07:49,979 --> 00:07:54,129 multiplying two numbers. Now, depending on what type of third 130 00:07:54,129 --> 00:07:56,586 grader you were, you might well have accepted this 131 00:07:56,586 --> 00:08:00,566 procedure as being the unique or at least the optimal way of multiplying two n 132 00:08:00,566 --> 00:08:03,760 digit numbers together. And if you want to be an expert algorithm 133 00:08:03,760 --> 00:08:07,544 designer, that kind of obedient attitude is something you're going to have to 134 00:08:07,544 --> 00:08:10,975 learn to discard. Here's a favorite quote of mine. 135 00:08:10,975 --> 00:08:15,957 It's from a quite early textbook in the field The Design and Analysis of Computer 136 00:08:15,957 --> 00:08:20,235 Algorithms by Aho, Hopcroft, and Ullman, and after highlighting a number of 137 00:08:20,235 --> 00:08:24,396 algorithmic design techniques, they conclude by saying, perhaps the most 138 00:08:24,396 --> 00:08:28,557 important principle for the good algorithm designer is to refuse to be 139 00:08:28,557 --> 00:08:31,312 content." So, that's a beautifully accurate quote. 140 00:08:31,312 --> 00:08:35,942 I might rephrase it more succinctly by just saying, if you're, want to be a good 141 00:08:35,942 --> 00:08:39,282 algorithm designer, you should adopt the following mantra. 142 00:08:39,282 --> 00:08:41,920 You should always be asking, can we do better? 143 00:08:41,920 --> 00:08:46,402 This is particularly appropriate question to ask when you're faced with some kind 144 00:08:46,402 --> 00:08:50,831 of naive or obvious algorithm for solving a problem, like the third grade algorithm 145 00:08:50,831 --> 00:08:54,086 for energy multiplication. So, this will come up over and over 146 00:08:54,086 --> 00:08:55,633 again. We'll see an algorithm. 147 00:08:55,633 --> 00:08:59,742 There'll be an obvious solution but with some extra algorithmic ingenuity by 148 00:08:59,742 --> 00:09:01,983 detecting subtle structure in the problem, 149 00:09:01,983 --> 00:09:05,879 we'll be able to do signifigantly, qualitatively better than the naive or 150 00:09:05,879 --> 00:09:11,031 the obvious solution to the problem. So, let's apply this cocky attitude to 151 00:09:11,031 --> 00:09:15,040 the problem of multiplying two integers. Let's just take, suppose as a working 152 00:09:15,040 --> 00:09:19,423 hypothesis that there is some procedure which is better than what we learned back 153 00:09:19,423 --> 00:09:22,310 in elementary school. What could it possibly look like? 154 00:09:22,310 --> 00:09:26,374 So, as someone with some programming experience, you know that they are not 155 00:09:26,374 --> 00:09:30,494 only iterative algorithms, iterative programs, like the one we just outlined 156 00:09:30,494 --> 00:09:34,064 for multiplying two integers. But they're also recursive programs. 157 00:09:34,064 --> 00:09:38,458 These are programs that call themselves, typically, on an input of a similar form, 158 00:09:38,458 --> 00:09:41,479 but with smaller size. So, as a working hypothesis, let's 159 00:09:41,479 --> 00:09:45,654 imagine that there's some interesting recursive approach to multiplying two 160 00:09:45,654 --> 00:09:48,235 integers. What must such an algorithm look like? 161 00:09:48,235 --> 00:09:52,025 Well, it must somehow fundamentally involve calling itself on smaller 162 00:09:52,025 --> 00:09:54,003 problems. That is, on smaller numbers, 163 00:09:54,003 --> 00:09:57,567 numbers with fewer digits. So, what kind of decomposition on numbers 164 00:09:57,567 --> 00:10:00,383 could be used to enable this kind of recursive approach? 165 00:10:00,383 --> 00:10:04,357 Well, if you think about it, there's a pretty natural way to break a number with 166 00:10:04,357 --> 00:10:07,274 a bunch of digits into a couple numbers with fewer digits. 167 00:10:07,274 --> 00:10:10,995 Namely, just take the first half of the digits, the first n over two digits, 168 00:10:10,995 --> 00:10:15,120 regard that as a number in its own right. And the second half of the digits, regard 169 00:10:15,120 --> 00:10:19,336 that as a number in its own right. So, perhaps this decomposition will have 170 00:10:19,336 --> 00:10:23,723 some use, in enabling a recursive attack on how to multiply two images. 171 00:10:23,723 --> 00:10:27,860 So, we're going to investigate that in more detail on this next slide. 172 00:10:30,860 --> 00:10:37,304 Given x and y, each with n over two digits, we're going to represent x as 173 00:10:37,304 --> 00:10:44,178 terms of its first half of the digits a and its second half of the digit to b. 174 00:10:44,178 --> 00:10:50,622 Similarly, we will write y, the second input in terms of its first half and 175 00:10:50,622 --> 00:10:55,765 second half of digits, c and d. And in this expansion, a and b, c and d 176 00:10:55,765 --> 00:11:00,827 are all n over two digit numbers. I'm assuming for convenience here, that n 177 00:11:00,827 --> 00:11:04,270 is even. This will extend to the case where n is 178 00:11:04,270 --> 00:11:09,872 odd in the natural way, where you break it into n over two rounded up and n over 179 00:11:09,872 --> 00:11:16,125 two rounded down. So, in our previous example, where x was 180 00:11:16,125 --> 00:11:21,302 5,678 and y was 1,234, we would have a being equal to 56. 181 00:11:21,302 --> 00:11:28,119 The first two digits of the four in x. And then b would be the other two digits. 182 00:11:28,119 --> 00:11:33,555 And then similarly for c and d. They have decomposition of y. 183 00:11:33,555 --> 00:11:40,113 So now, in a purely mechanical way, we can expand the product of x times y in 184 00:11:40,113 --> 00:11:45,894 terms of this representation. In terms of these smaller numbers, a, b, 185 00:11:45,894 --> 00:11:53,602 c, and d. So, x times y, by a representation, is just the same thing as 186 00:11:53,602 --> 00:12:00,028 ten n over two times a plus b times quantity ten to the n over two c plus d. 187 00:12:00,028 --> 00:12:04,280 And now, if we expand this in grouplike terms, 188 00:12:04,280 --> 00:12:09,666 we get a ten to the n times ac plus ten to the n over two times ad plus bc. 189 00:12:09,666 --> 00:12:15,220 So, that's combining two terms from the expansion, plus bd. 190 00:12:15,220 --> 00:12:20,920 And I'm going to call this expression circled in green, star. 191 00:12:20,920 --> 00:12:25,231 Now, what I want you to think about and make sure you understand is that, this 192 00:12:25,231 --> 00:12:29,542 expansion that I've circled and called star, immediately suggests a recursive 193 00:12:29,542 --> 00:12:33,517 algorithm for multiplying two integers. Now, it's not clear whether that 194 00:12:33,517 --> 00:12:37,828 algorithm is going to be fast or slow, whether this is a good idea or a crackpot 195 00:12:37,828 --> 00:12:39,900 idea. But certainly, it's a legitimate 196 00:12:39,900 --> 00:12:42,532 recursive approach to multiplying two integers. 197 00:12:42,532 --> 00:12:46,208 Specifically, the relevant product in star namely ac, 198 00:12:46,208 --> 00:12:50,250 ad, bc, and bd all involve smaller numbers than what we stared with. 199 00:12:50,250 --> 00:12:55,579 Those are all n over two digit numbers. Those all original inputs at n digits so 200 00:12:55,579 --> 00:12:58,274 we can legitimately solve those recursively. 201 00:12:58,274 --> 00:13:02,500 We can invoke our same algorithm to compute those in a recursive way. 202 00:13:04,540 --> 00:13:08,537 Now, once we've invoked our multiplication algorithm recursively four 203 00:13:08,537 --> 00:13:11,091 times to compute these four relevant products, 204 00:13:11,091 --> 00:13:14,922 now we can just compute the expression in star in the obvious way. 205 00:13:14,922 --> 00:13:17,921 We take ad and bc. We add them together, using the just, 206 00:13:17,921 --> 00:13:20,697 standard first grade iterative addition algorithm. 207 00:13:20,697 --> 00:13:24,583 Then, we add both ac and the result of that addition by a bunch of zeros, 208 00:13:24,583 --> 00:13:29,192 n over 2 zeros or n zeros as appropriate. Now, we have these three constituent 209 00:13:29,192 --> 00:13:33,522 terms and we just add them up again using the grade school algorithms to compute 210 00:13:33,522 --> 00:13:38,719 the overall expression. So, to keep this intro lecture brisk, I 211 00:13:38,719 --> 00:13:41,435 haven't discussed the base case of this recursive algorithm. 212 00:13:41,435 --> 00:13:44,422 As, hopefully, you all know, recursive algorithms do need base cases. 213 00:13:44,422 --> 00:13:46,368 At some point, the recursion has got to stop. 214 00:13:46,368 --> 00:13:48,631 Otherwise, your algorithm is never going to terminate. 215 00:13:48,631 --> 00:13:52,070 So, in multiplication, all you'd do is, if your past as input two single digit 216 00:13:52,070 --> 00:13:55,238 numbers, you'd multiply them in one primitive operation, and return the 217 00:13:55,238 --> 00:13:57,320 result. If the numbers have two or more digits, 218 00:13:57,320 --> 00:13:59,674 you would recurse in the way we have described here. 219 00:13:59,674 --> 00:14:03,420 If there's one digit, you just compute them and you're done. 220 00:14:03,420 --> 00:14:07,162 So, who knows whether this recursive algorithm is a good idea or not, it's 221 00:14:07,162 --> 00:14:11,259 totally not obvious, you should not even necessarily have any intuition about how 222 00:14:11,259 --> 00:14:15,255 this compares to the iterative algorithm you learned back in elementary school. 223 00:14:15,255 --> 00:14:19,099 So, in lieu of answering that question, although we will answer it several 224 00:14:19,099 --> 00:14:21,830 lectures hence, I want to show you a second, still more 225 00:14:21,830 --> 00:14:25,826 clever, recursive algorithm, for integer multiplication, so this goes by the name 226 00:14:25,826 --> 00:14:29,973 of Karatsuba multiplication after the founder, although really it's sort of the 227 00:14:29,973 --> 00:14:33,919 key point, there's a trick pointed out by the mathematician, Gauss, in the early 228 00:14:33,919 --> 00:14:37,410 19th century. So, to explain this algorithm, let me 229 00:14:37,410 --> 00:14:41,952 write once again our expansion in terms of the n over two digit numbers. 230 00:14:41,952 --> 00:14:48,795 So, we have the product x times y, which we wrote as 10 to the n ac plus 10 to the 231 00:14:48,795 --> 00:14:54,197 n over two ad plus bc plus bd. Now, the previous approach was in 232 00:14:54,197 --> 00:14:57,645 recognition of the four products that we see in this expression. 233 00:14:57,645 --> 00:15:01,308 We made four recursive calls. So, here's the trick, and this is really 234 00:15:01,308 --> 00:15:05,617 what Gauss figured out over 200 years ago which is that it seems there are four 235 00:15:05,617 --> 00:15:08,095 products. But fundamentally, in this expression, 236 00:15:08,095 --> 00:15:11,111 there's really only three quantities that we care about. 237 00:15:11,111 --> 00:15:13,839 There's the ac, the coefficient of this first term. 238 00:15:13,839 --> 00:15:18,173 There's ad plus bc, the coefficient of this middle term, and there's bd. 239 00:15:18,173 --> 00:15:23,064 So, we care about ad and bc as quantities individually, only in as much as we care 240 00:15:23,064 --> 00:15:26,036 about their sum. We really don't care about them 241 00:15:26,036 --> 00:15:29,256 individually. So, that motivates the question, perhaps 242 00:15:29,256 --> 00:15:33,776 we can somehow uncover these three different quantities using only three 243 00:15:33,776 --> 00:15:38,716 recursive calls rather than four. In fact, we can't, and that's Karatsuba 244 00:15:38,716 --> 00:15:41,550 multiplication. So, to be more specific, 245 00:15:41,550 --> 00:15:47,220 our first two recursive calls are shared with the previous recursive algorithm. 246 00:15:47,220 --> 00:15:52,220 We go ahead and compute ac and bd recursively. 247 00:15:53,526 --> 00:16:00,276 The third step is the, is the clever one where we recursively compute the product 248 00:16:00,276 --> 00:16:06,443 of quantity a plus b with c plus d. Now, expanding what are we going to get 249 00:16:06,443 --> 00:16:13,026 when we recursively compute this product, we're going to get ac plus bd plus ad 250 00:16:13,026 --> 00:16:18,338 plus bc. And here is Gauss's trick for observation 251 00:16:18,338 --> 00:16:25,810 which is that the result of the third recursive call minus each of the first 252 00:16:25,810 --> 00:16:30,560 two, what happens? Well, the ac is going to cancel the ac, 253 00:16:30,560 --> 00:16:35,702 the bd is going to cancel the bd and we will be left with ad + bc, which is 254 00:16:35,702 --> 00:16:39,385 exactly that middle coefficience that we cared about. 255 00:16:39,385 --> 00:16:44,945 So, we can indeed compute the sum of ad and bc without separately computing each 256 00:16:44,945 --> 00:16:47,863 of them, and that's exactly what we wanted. 257 00:16:47,863 --> 00:16:52,033 So, what is this bias? This gives us another second recursive 258 00:16:52,033 --> 00:16:57,592 algorithm from multiplying two integers that makes use of fewer recursive calls. 259 00:16:57,592 --> 00:17:01,113 Only three recursive calls rather than four. 260 00:17:01,113 --> 00:17:05,744 And as before, there's a little bit of work to do beyond the recursive calls but 261 00:17:05,744 --> 00:17:08,349 not much. You just have to do some padding by 262 00:17:08,349 --> 00:17:12,911 zeroes and adding up the results. So, there is two points I want you to 263 00:17:12,911 --> 00:17:15,947 appreciate about all these energy multiplication algorithms. 264 00:17:15,947 --> 00:17:19,488 The first point is that the algorithm design space is incredibly rich. 265 00:17:19,488 --> 00:17:22,726 Much richer than you might have had initially had intuition for. 266 00:17:22,726 --> 00:17:25,357 Multiply two integers. What else could you do with the 267 00:17:25,357 --> 00:17:27,568 elementary algorithm? Well, what have we seen? 268 00:17:27,568 --> 00:17:30,964 You can do a lot of other things. In particular the second recursive 269 00:17:30,964 --> 00:17:34,260 algorithm looks nothing like what we learned back in grade school. 270 00:17:34,260 --> 00:17:37,655 We will see this over and over again, that with sufficient ingenuity, 271 00:17:37,655 --> 00:17:41,351 sufficient cleverness you can solve problems in ways much differently and 272 00:17:41,351 --> 00:17:44,867 sometimes much better than using the naive straightforward algorithm. 273 00:17:44,867 --> 00:17:48,673 The second takeaway point from this discussion of integer multiplication 274 00:17:48,673 --> 00:17:52,686 algorithms is that sometimes you have interesting algorithmic ideas for which 275 00:17:52,686 --> 00:17:56,749 it's totally not obvious what kinds of properties or what kinds of performance 276 00:17:56,749 --> 00:18:00,504 guarantees those algorithms enjoy. So, in particular, confronted with these 277 00:18:00,504 --> 00:18:04,619 three different integer multiplication algorithms, how could we not wonder which 278 00:18:04,619 --> 00:18:08,014 of the three is the best? Which of these three requires the fewest 279 00:18:08,014 --> 00:18:10,946 number of cumulative operations to multiply two integers? 280 00:18:10,946 --> 00:18:14,958 In particular, does one of these novel recursive approaches do better than the 281 00:18:14,958 --> 00:18:17,274 algorithm we learned back in elementary school? 282 00:18:17,274 --> 00:18:20,890 The answer to that question is totally not obvious and it requires nontrivial 283 00:18:20,890 --> 00:18:24,232 mathematical analysis to answer. In the upcoming lectures, I will provide 284 00:18:24,232 --> 00:18:27,940 you with the tools to not only precisely understand and answer this question but 285 00:18:27,940 --> 00:18:31,465 more generally, to predict the running times of an entire genre of divide and 286 00:18:31,465 --> 00:18:33,846 conquer algorithms like Karatsuba multiplication. 287 00:18:33,846 --> 00:18:34,487 So, stay tuned.