Explorar todo lo que Coursera tiene para ofrecer

For Enterprise

Join for Free
Log In

artes y humanidades
Negocios
Ciencias de la Computación
Ciencia de Datos
Tecnología de información
salud
Matemáticas y Lógica
Desarrollo Personal
Ciencias Físicas e Ingeniería
Ciencias sociales
Aprendizaje de un idioma
Grados
Certificados

Explorar todo lo que Coursera tiene para ofrecer

Explorar
Buscar
For Enterprise
Inicia Sesión
Únete de forma gratuita

Integer Multiplication

Loading...

Divide and Conquer, Sorting and Searching, and Randomized Algorithms

Universidad de Stanford

4.8 (2,907 calificaciones) | 95K estudiantes inscritos

Curso 1 de 4 en Algoritmos Programa Especializado

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).

Destrezas que aprenderás

Algorithms, Randomized Algorithm, Sorting Algorithm, Divide And Conquer Algorithms

Revisiones

4.8 (2,907 calificaciones)

5 stars
2,464 ratings
4 stars
376 ratings
3 stars
44 ratings
2 stars
10 ratings
1 star
13 ratings

CV

Jun 11, 2017

A really exciting and challenging course. Loved the way the instructor explained everything with so much detail and precision. Definitely looking forward to the next course in the specialization.

NE

Nov 07, 2016

Personally, I would recommend this course to anyone who really wants to learn how things work in that sort of algorithms. I found the assignments a little difficult, but also extremely helpful.

De la lección

Week 1

Introduction; "big-oh" notation and asymptotic analysis.

Why Study Algorithms?4:15

Integer Multiplication8:38

Karatsuba Multiplication12:39

About the Course17:19

Merge Sort: Motivation and Example8:44

Merge Sort: Pseudocode12:51

Merge Sort: Analysis9:02

Guiding Principles for Analysis of Algorithms15:17

Impartido por:

Tim Roughgarden
Professor

Transcripción

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.

Descargar en la App Store

Consíguelo en Google Play

Coursera
Acerca de
Liderazgo
Empleo
Catálogo
Certificados
Certificados MasterTrack™
Grados
For Enterprise
For Government

Comunidad
Learners
Partners
Developers
Beta Testers
Translators

Conectar
Blog
Facebook
LinkedIn
Twitter
Instagram
Youtube
Blog de Tecnología

Más
Términos
Privacidad
Ayuda
Accesibilidad
Prensa
Contacto
Directorio
Afiliados