In this lecture we're going to talk about a more complicated divide-and-conquer

algorithm to solve polynomial multiplication.

So first we'll talk about what polynomial multiplication is.

So polynomial multiplication is basically just taking two polynomials and

multiplying them together.

It's used in a variety of ways in computer science.

Error correcting codes, if you want to multiply large integers together.

Right, so if you've got thousand digit integers and

you want to multiply them together, there's a quicker way than doing it

the normal way you learned in elementary school.

And that uses the idea of multiplying polynomials.

It is used for generating functions, and for convolution.

Let's look at an example.

So let's say you have polynomial A, which is 3 x squared + 2x + 5,

and polynomial B, which is 5 x squared + x + 2.

If you multiply them together you get 15 x to

the fourth + 13 x cubed + 33 x squared + 9x + 10.

Why is that?

Well, let's look, for instance the 15 x to the fourth comes from multiplying 3 x

squared times 5 x squared, that's 15x to the fourth.

The 10 comes from multiplying 5 by 2.

The 13 x cubed comes from 3 x squared times x, which is 3 x cubed,

plus 2x times 5 x squared, which is 10 x cubed.

For a total of 13 x cubed.

So let's look at the problem statement.

So we're going to have two n- 1 degree polynomials, all right?

a sub n-1 is the coefficient of the x to the n-1 all the way down

to a0 which is the coefficient of the x to the 0 term or the one term.