Welcome to this first course in the design and analysis of algorithms. I imagine many of you are already clear on your reasons for taking this course, but let me begin by justifying the course's existence. I'm giving you several different motivations for learning about algorithms. So, what is an algorithm? Well, we're not going to be needing a precise definition in this course, but essentially, an algorithm is a well-defined set of rules. A recipe in effect for solving some kind of computational problem. So, for example, maybe you're given a bunch of numbers and you want to rearrange them into sorted order. Maybe you're given a road network with an origin and a destination, and you want to compute the shortest path from point a to point b. Maybe you're given a bunch of tasks with deadlines and you want to know weather or not it's feasible to accomplish all of those tasks by their respective deadlines. So, why study algorithms? Well, first of all, understanding the field of algorithms, and also the related field of data structures, is crucial for doing serious work in pretty much any other branch of Computer Science. That's the precise reason why here at Stanford University, this is the course that's required for all of the degrees that the Computer Science Department grants, be it a Bachelors, a Masters, or a PhD degree, we insist that you have mastery of the field of algorithms. So, what are some examples of uses in the rest of Computer Science? Well, if you're doing routing and communication network, that piggybacks on classical shortest path algorithms. the effectiveness of public key cryptography really rests on that, of number theoretic algorithms. In, say, computer graphics, you need the computational primitives that are supplied by the study of geometric algorithms. Database indices rely on balance search tree data structures, as covered in this course. and computational biology uses dynamic programming algorithms to measure similarity among genomes. And the list goes on and on. A second reason to study algorithms is that they play a key role in modern technological innovation. Obviously, I could give any number of examples here. Let me just state one super obvious one. which is that search engines use a tapestry of algorithms to efficiently compute the relevance of various web pages. The most famous search algorithm which you may have heard of is the page rank algorithm in use by Google. Indeed, in a December 2010 report to the United States Whitehouse, the President's Counsel of Advisers on Science and Technology argued that in many areas, performance gains due to improvements in algorithms, have vastly exceeded even the dramatic performance gains due to increased processor speed, as you'd be familiar with in the form of Moore's Law. Third, although this is getting significantly outside the scope of this course, algorithms are increasingly being used to provide a novel lens on processes outside of Computer Science and Technology. For example, the set of quantum computation has provided a new and computational viewpoint on quantum mechanics, price fluctuations in economic markets can be fruitfully viewed as an algorithmic process, and even evolution can be usefully thought of as, as a surprisingly search algorithm. The last two reasons I'm going to give you might sound a little flipping but, you know, I, I think there is more than a grain of truth to both of them. Now, I don't know about you but back when I was a student my favorite classes were always challenging classes but after I struggled through them, I somehow felt I had a few more IQ points than when I started. So, I hope this course provides a similar experience for many of you that one the one hand it's a bit of a struggle. You find the, the concepts challenging but perhaps you feel just a tinge smarter after we're done. Finally, I hope that by the end of the course, a constant fraction of you will agree with me that designing and analyzing algorithms is simply fun. It's an endeavor that requires a rare blend of creativity and precision and it can certainly be frustrating at times, but even more than that, it is addictive. So, let's now descend from these lofty generalities and get much more concrete. And also, let's remember that we've all been learning and using algorithms since we were little kids. So, once upon a time, in roughly third grade or so, you learned how to multiply two numbers. Now, you probably weren't thinking in these terms at the time, but multiplying two numbers is certainly a well-defined computational problem and that procedure you learned back in third grade or so, is indeed an algorithm. So, let's just make that a little bit more precise. In this computational problem, we're given as input, two numbers, let's say with n digits. And to make things interesting, why don't you think about n as being really quite large, say in the thousands? Maybe we're implementing an algorithm that's going to be used in a cryptography application where you need to keep track of really quite large numbers. So, if we call the two input numbers x and y, the problem is simply to compute their product, xy. times y. So, a quick digression. I'll certainly be the first to admit that my handwriting is not the greatest. I got a C in penmanship back in elementary school, and I think the teacher was being a little generous but, you know, it's got an acquired taste, but trust me, you will get used to it. Okay, back to integer multiplication. Now, when we talk about procedures for multiplying two numbers, we're going to be interested in counting how many steps are required, in order to execute the multiplication. So, how do we count a step? We'll talk more about this more later, but for multiplying two numbers, let's just call a step, the addition or multiplication of two single digit numbers. So, let's review the integer multiplication algorithm that we learned back in grade school, just by working through a concrete example. Specifically, let's think of n equals 4. So, let's look at two four-digit numbers let's say, five, six, seven, eight, and one, two, three, four. Now, as you'll recall, the procedure we learned way back when was just to take each digit of the bottom number and multiply it by each of the top numbers. And then to take each of those n partial products, and add them up. So, for example, you start with the four. You multiply it by eight, so you get 32. Carry the three. 4 times 7 is 28, add the three, you get one, carry the three, and so on. So, that gives you this first partial product. 22, 7, 12. Then, you do a shift, so you effectively put a zero in this final digit, and you repeat that procedure using the next digit, the three. So again, three times eight is four, carry the two, and so on. And you compute the final two partial products using the two and the one. And having computed all of the partial products, you just add them up to get the final product. Now, the question I'm interested in is, how much work, how many primitive operations did we do to multiply these two numbers. And more generally, how many does it require to multiply two n digit numbers as a function of n. Well, just to get sort of a ballpark view for what's going on, we started with two n digit numbers. And at the end of the day, we basically filled out a grid of size roughly n by n, give or take a little bit. So, just in ballpark terms, it seems that multiplying two n digit numbers required essentially a quadratic number of operations, a small number of operations to fill in each entry in this grid. The grid is n by n roughly so that is roughly n squared operations. In a little more detail, we could look at each of the partial products separately. So, to compute, say, this first partial product, what do we do? We take the four we multiplied it by each of the n digits on top. We also did some carries, so that effects things a little bit. But, in the end, we did somewhere between, say, n and the 2n, primitive operations to compute this first partial product. And that's true, of course, for each of the n partial products. So, that's roughly n operations for each of the n partial products. So, that's roughly n squared operations. It could be all of the partial products. Then, we have to add it all up at the end. But that takes just an extra number of constant times n primitive operations to do all of those additions. So summarizing, overall, the number of primitive operations required to multiply to n digit numbers using this procedure grows quadratically with the length N. So, for example, if you double the length of two numbers, you expect to do roughly four times as many primitive operations if you use this iterative algorithm for multiplying two numbers. Now, depending on what type of third grader you were, you might well have accepted this procedure as being the unique or at least the optimal way of multiplying two n digit numbers together. And if you want to be an expert algorithm designer, that kind of obedient attitude is something you're going to have to learn to discard. Here's a favorite quote of mine. It's from a quite early textbook in the field The Design and Analysis of Computer Algorithms by Aho, Hopcroft, and Ullman, and after highlighting a number of algorithmic design techniques, they conclude by saying, perhaps the most important principle for the good algorithm designer is to refuse to be content." So, that's a beautifully accurate quote. I might rephrase it more succinctly by just saying, if you're, want to be a good algorithm designer, you should adopt the following mantra. You should always be asking, can we do better? This is particularly appropriate question to ask when you're faced with some kind of naive or obvious algorithm for solving a problem, like the third grade algorithm for energy multiplication. So, this will come up over and over again. We'll see an algorithm. There'll be an obvious solution but with some extra algorithmic ingenuity by detecting subtle structure in the problem, we'll be able to do signifigantly, qualitatively better than the naive or the obvious solution to the problem. So, let's apply this cocky attitude to the problem of multiplying two integers. Let's just take, suppose as a working hypothesis that there is some procedure which is better than what we learned back in elementary school. What could it possibly look like? So, as someone with some programming experience, you know that they are not only iterative algorithms, iterative programs, like the one we just outlined for multiplying two integers. But they're also recursive programs. These are programs that call themselves, typically, on an input of a similar form, but with smaller size. So, as a working hypothesis, let's imagine that there's some interesting recursive approach to multiplying two integers. What must such an algorithm look like? Well, it must somehow fundamentally involve calling itself on smaller problems. That is, on smaller numbers, numbers with fewer digits. So, what kind of decomposition on numbers could be used to enable this kind of recursive approach? Well, if you think about it, there's a pretty natural way to break a number with a bunch of digits into a couple numbers with fewer digits. Namely, just take the first half of the digits, the first n over two digits, regard that as a number in its own right. And the second half of the digits, regard that as a number in its own right. So, perhaps this decomposition will have some use, in enabling a recursive attack on how to multiply two images. So, we're going to investigate that in more detail on this next slide. Given x and y, each with n over two digits, we're going to represent x as terms of its first half of the digits a and its second half of the digit to b. Similarly, we will write y, the second input in terms of its first half and second half of digits, c and d. And in this expansion, a and b, c and d are all n over two digit numbers. I'm assuming for convenience here, that n is even. This will extend to the case where n is odd in the natural way, where you break it into n over two rounded up and n over two rounded down. So, in our previous example, where x was 5,678 and y was 1,234, we would have a being equal to 56. The first two digits of the four in x. And then b would be the other two digits. And then similarly for c and d. They have decomposition of y. So now, in a purely mechanical way, we can expand the product of x times y in terms of this representation. In terms of these smaller numbers, a, b, c, and d. So, x times y, by a representation, is just the same thing as ten n over two times a plus b times quantity ten to the n over two c plus d. And now, if we expand this in grouplike terms, we get a ten to the n times ac plus ten to the n over two times ad plus bc. So, that's combining two terms from the expansion, plus bd. And I'm going to call this expression circled in green, star. Now, what I want you to think about and make sure you understand is that, this expansion that I've circled and called star, immediately suggests a recursive algorithm for multiplying two integers. Now, it's not clear whether that algorithm is going to be fast or slow, whether this is a good idea or a crackpot idea. But certainly, it's a legitimate recursive approach to multiplying two integers. Specifically, the relevant product in star namely ac, ad, bc, and bd all involve smaller numbers than what we stared with. Those are all n over two digit numbers. Those all original inputs at n digits so we can legitimately solve those recursively. We can invoke our same algorithm to compute those in a recursive way. Now, once we've invoked our multiplication algorithm recursively four times to compute these four relevant products, now we can just compute the expression in star in the obvious way. We take ad and bc. We add them together, using the just, standard first grade iterative addition algorithm. Then, we add both ac and the result of that addition by a bunch of zeros, n over 2 zeros or n zeros as appropriate. Now, we have these three constituent terms and we just add them up again using the grade school algorithms to compute the overall expression. So, to keep this intro lecture brisk, I haven't discussed the base case of this recursive algorithm. As, hopefully, you all know, recursive algorithms do need base cases. At some point, the recursion has got to stop. Otherwise, your algorithm is never going to terminate. So, in multiplication, all you'd do is, if your past as input two single digit numbers, you'd multiply them in one primitive operation, and return the result. If the numbers have two or more digits, you would recurse in the way we have described here. If there's one digit, you just compute them and you're done. So, who knows whether this recursive algorithm is a good idea or not, it's totally not obvious, you should not even necessarily have any intuition about how this compares to the iterative algorithm you learned back in elementary school. So, in lieu of answering that question, although we will answer it several lectures hence, I want to show you a second, still more clever, recursive algorithm, for integer multiplication, so this goes by the name of Karatsuba multiplication after the founder, although really it's sort of the key point, there's a trick pointed out by the mathematician, Gauss, in the early 19th century. So, to explain this algorithm, let me write once again our expansion in terms of the n over two digit numbers. So, we have the product x times y, which we wrote as 10 to the n ac plus 10 to the n over two ad plus bc plus bd. Now, the previous approach was in recognition of the four products that we see in this expression. We made four recursive calls. So, here's the trick, and this is really what Gauss figured out over 200 years ago which is that it seems there are four products. But fundamentally, in this expression, there's really only three quantities that we care about. There's the ac, the coefficient of this first term. There's ad plus bc, the coefficient of this middle term, and there's bd. So, we care about ad and bc as quantities individually, only in as much as we care about their sum. We really don't care about them individually. So, that motivates the question, perhaps we can somehow uncover these three different quantities using only three recursive calls rather than four. In fact, we can't, and that's Karatsuba multiplication. So, to be more specific, our first two recursive calls are shared with the previous recursive algorithm. We go ahead and compute ac and bd recursively. The third step is the, is the clever one where we recursively compute the product of quantity a plus b with c plus d. Now, expanding what are we going to get when we recursively compute this product, we're going to get ac plus bd plus ad plus bc. And here is Gauss's trick for observation which is that the result of the third recursive call minus each of the first two, what happens? Well, the ac is going to cancel the ac, the bd is going to cancel the bd and we will be left with ad + bc, which is exactly that middle coefficience that we cared about. So, we can indeed compute the sum of ad and bc without separately computing each of them, and that's exactly what we wanted. So, what is this bias? This gives us another second recursive algorithm from multiplying two integers that makes use of fewer recursive calls. Only three recursive calls rather than four. And as before, there's a little bit of work to do beyond the recursive calls but not much. You just have to do some padding by zeroes and adding up the results. So, there is two points I want you to appreciate about all these energy multiplication algorithms. The first point is that the algorithm design space is incredibly rich. Much richer than you might have had initially had intuition for. Multiply two integers. What else could you do with the elementary algorithm? Well, what have we seen? You can do a lot of other things. In particular the second recursive algorithm looks nothing like what we learned back in grade school. We will see this over and over again, that with sufficient ingenuity, sufficient cleverness you can solve problems in ways much differently and sometimes much better than using the naive straightforward algorithm. The second takeaway point from this discussion of integer multiplication algorithms is that sometimes you have interesting algorithmic ideas for which it's totally not obvious what kinds of properties or what kinds of performance guarantees those algorithms enjoy. So, in particular, confronted with these three different integer multiplication algorithms, how could we not wonder which of the three is the best? Which of these three requires the fewest number of cumulative operations to multiply two integers? In particular, does one of these novel recursive approaches do better than the algorithm we learned back in elementary school? The answer to that question is totally not obvious and it requires nontrivial mathematical analysis to answer. In the upcoming lectures, I will provide you with the tools to not only precisely understand and answer this question but more generally, to predict the running times of an entire genre of divide and conquer algorithms like Karatsuba multiplication. So, stay tuned.