The primary topics in this part of the specialization are: asymptotic ("Big-oh") notation, sorting and searching, divide and conquer (master method, integer and matrix multiplication, closest pair), and randomized algorithms (QuickSort, contraction algorithm for min cuts).
Integer Multiplication
Loading...
Del curso dictado por Stanford University
Divide and Conquer, Sorting and Searching, and Randomized Algorithms
2683 calificaciones
De la lección
Week 1
Introduction; "big-oh" notation and asymptotic analysis.
Conoce a los instructores
Tim RoughgardenProfessor
Computer Science
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.
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.
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.
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.
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.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2019 Coursera Inc. Todos los derechos reservados.
