0:01

Sometime when you were a kid, maybe say third grade or so, you learned an

Â Algorithm for multiplying two numbers. Maybe your third grade teacher didn't

Â call it that, maybe that's not how you thought about it.

Â But you learned a well defined set of rules for transforming input, namely two

Â numbers into an output, namely their product.

Â So, that is an algorithm for solving a computational problem.

Â Let's pause and be precise about it. Many of the lectures in this course will

Â follow a pattern. We'll define a computational problem.

Â We'll say what the input is, and then we'll say what the desired output is.

Â Then we will proceed to giving a solution, to giving an algorithm that

Â transforms the input to the output. When the integer multiplication problem,

Â the input is just two, n-digit numbers. So the length, n, of the two input

Â integers x and y could be anything, but for motivation you might want to think of

Â n as large, in the thousands or even more, perhaps we're implementing some

Â kind of cryptographic application which has to manipulate very large numbers.

Â 1:12

We also need to explain what is desired output in this simple problem it's simply

Â the product x times y. So a quick digression so back in 3rd

Â grade around the same I was learning the Integer Multiplication Algorithm.

Â I got a C in penmanship and I don't think my handwriting has improved much since.

Â Many people tell me by the end of the course.

Â They think of it fondly as a sort of acquired taste, but if you're feeling

Â impatient, please note there are typed versions of these slides.

Â Which I encourage you to use as you go through the lectures, if you don't want

Â to take the time deciphering the handwriting.

Â Returning to the Integer Multiplication problem, having now specified the problem

Â precisely, the input, the desired output. We'll move on to discussing an algorithm

Â that solves it, namely, the same algorithm you learned in third grade.

Â The way we will assess the performance of this algorithm is through the number of

Â basic operations that it performs. And for the moment, let's think of a

Â basic operation as simply adding two single-digit numbers together or

Â multiplying two single digit numbers. We're going to then move on to counting

Â the number of these basic operations performed by the third grade algorithm.

Â As a function of the number n of digits in the input.

Â 2:36

Here's the integer multiplication algorithm that you learned back in third

Â grade Illustrated on a concrete example. Let's take say the numbers 1, 2, 3, 4 and

Â 5, 6, 7, 8. As we go through this algorithm quickly,

Â let me remind you that our focus should be on the number of basic operations this

Â algorithm performs. As a function of the length of the input

Â numbers. Which, in this particular example, is

Â four digits long. So as you'll recall, we just compute one

Â partial product for each digit of the second number.

Â So we start by just multiplying 4 times the upper number 5, 6, 7, 8.

Â So, you know, 4 times 8 is 32, 2 carry to 3, 4 times 7 is 28, with the 3 that's 31,

Â write down the 1, carry the 3, and so on. When we do the next partial product, we

Â do a shift effectively, we add a 0 at the end, and then we just do exactly the same

Â thing. And so on for the final two partial

Â products. [SOUND] And finally, we just add

Â everything up. [SOUND], what you probably realized back

Â in third grade, is that this algorithm is what we would call correct.

Â That is, no matter what integers x and y you start with If you carry out this

Â procedure, this algorithm. And all of your intermediate computations

Â are done properly. Then the algorithm will eventually

Â terminate with the product, x times y, of the two input numbers.

Â You're never going to get a wrong answer. You're always going to get the actual

Â product. Well, you probably didn't think about was

Â the amount of time needed to carry out this algorithm out to its conclusion to

Â termination. That is the number of basic operations,

Â additions or multiplications of single digit numbers needed before finishing.

Â So let's now quickly give an informal analyses of the number of operations

Â required as a function of the input length n.

Â 4:50

Let's begin with the first partial product, the top row.

Â How did we compute this number 22,712? Well we multiplied 4 times each of the

Â numbers 5, 6, 7 and 8. So that was for basic operations.

Â One for each digit at the top number, plus we had to do these carries.

Â So those were some extra additions. But in any case, this is at most twice

Â times the number of digits in the first number.

Â At most two end basic operations to form this first partial product.

Â And if you think about it there's nothing special about the first partial product.

Â The same argument says that we need at most 2 n operations to form each of the

Â partial products of which there are again n, one for each digit of the second

Â number. Well if we need at most two n operations

Â to compute each partial product and we have n partial products.

Â That's a total of at most two n squared operations to form all of these blue

Â numbers, all of the partial products. Now we're not done at that point.

Â We still have to add all of those up to get the final answer, in this case

Â 7,006,652. And that's final addition requires a

Â comparable number of operations. Roughly, another say two n squared, at

Â most operations. So, the upshot, the high level point that

Â I want you to focus on, is that as we think about the input numbers getting

Â bigger and bigger. That is as a function of n the number of

Â digits in the input numbers. The number of operations that the

Â Grade-School Multiplication Algorithm performs, grows like some constant.

Â Roughly 4 say times n squared. That is it's quadratic in the input

Â length n. For example, if you double the size of

Â the input, if you double the number of digits in each of the two integers that

Â you're given. Then the number of operations you will

Â have to perform using this algorithm has to go up by a factor of four.

Â Similarly, if you quadruple the input length, the number of operations going,

Â is going to go up by a factor of 16, and so on.

Â 7:02

Now, depending on what type of third grader you were.

Â You might well of accepted this procedure as the unique or at least the optimal way

Â of multiplying two numbers together to form their product.

Â Now if you want to be a serious algorithm designer.

Â That kind of obedient tumidity is a quality you're going to have to grow out

Â of. And early and extremely important

Â textbook on the design and analysis of algorithms was by Aho, Hopcroft, and

Â Ullman. It's about 40 years old now.

Â And there's the following quote, which I absolutely adore.

Â So after iterating through a number of the algorithm design paradigms covered in

Â the textbook. They say the following, perhaps the most

Â important principle of all, for the good algorithm designer is to refuse to be

Â content. And I think this is a spot on comment.

Â I might summarize it a little bit more succinctly.

Â As, as an algorithm designer you should adopt as your Mantra the question, can we

Â do better? This question is particularly apropos

Â when your'e faced with a naive or straight-forward solution to a

Â computation problem. Like for example, the third grade

Â algorithm for integer multiplication. The question you perhaps did not ask

Â yourself in third grade was, can we do better than the straight forward

Â multiplication algorithm? And now is the time for an answer.

Â