# Divide-n-Conquer Algorithms in Python

*This assignment is a part of the course "Data Structures and Algorithms in Python".*

## Problem Statement - Polynomial Multiplication

Given two polynomials represented by two lists, write a function that efficiently multiplies given two polynomials. For example, the lists

`[2, 0, 5, 7]`

and`[3, 4, 2]`

represent the polynomials $2 + 5x^2 + 7x^3$ and $3 + 4x + 2x^2$.Their product is

$(2 \times 3) + (2 \times 4 + 0 \times 3)x + (2 \times 2 + 3 \times 5 + 4 \times 0)x^2 + (7 \times 3 + 5 \times 4 + 0 \times 2)x^3 + (7 \times 4 + 5 \times 2)x^4 + (7 \times 2)x^5$ i.e.

$6 + 8x + 19x^2 + 41x^3 + 38x^4 + 14x^5$

It can be represented by the list

`[6, 8, 19, 41, 38, 14]`

.

## The Method

Here's the systematic strategy we'll apply for solving problems:

- State the problem clearly. Identify the input & output formats.
- Come up with some example inputs & outputs. Try to cover all edge cases.
- Come up with a correct solution for the problem. State it in plain English.
- Implement the solution and test it using example inputs. Fix bugs, if any.
- Analyze the algorithm's complexity and identify inefficiencies, if any.
- Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.

This approach is explained in detail in Lesson 1 of the course. Let's apply this approach step-by-step.

## Solution

### 1. State the problem clearly. Identify the input & output formats.

While this problem is stated clearly enough, it's always useful to try and express in your own words, in a way that makes it most clear for you.

**Problem**

First, understand how does a polynomial multiplication works?

Say, we wish to multiply: (3x + 2) with (4x^2 – 7x + 5).

In simpler terms:

A list polynomial represented as `[2, 3, 5, 7, 9]`

can be read as: $2x^0 + 3x^1 + 5x^2 + 7x^3 + 9x^4$.

i.e. The `index`

value of the list can be interpreted as the power value of x.

For example, the lists `[2, 0, 5, 7]`

and `[3, 4, 2]`

represent the polynomials $2 + 5x^2 + 7x^3$ and $3 + 4x + 2x^2$.

Their product is

$2 \times (3 + 4x + 2x^2) + 5x^2 \times (3 + 4x + 2x^2) + 7x^3 \times (3 + 4x + 2x^2)$.

$2 \times 3 + 2 \times 4x + 2 \times 2x^2 + 5x^2 \times 3 + 5x^2 \times 4x + 5x^2 \times 2x^2) + 7x^3 \times 3 + 7x^3 \times 4x + 7x^3 \times 2x^2)$.

$2 \times 3 + (2 \times 4)x + (2 \times 2 + 5 \times 3) x^2 + (5 \times 4 + 7 \times 3)x^3 + (5 \times 2 + 7 \times 4)x^4 + (7 \times 2)x^5$.

$6 + 8x + 19x^2 + 41x^3 + 38x^4 + 14x^5$

It can be represented by the list

`[6, 8, 19, 41, 38, 14]`

.

**Input**

`[2, 4, 0, 0, 5]`

and`[4, 9, 5, 4]`

`[2, 4]`

and`[2, 7, 5]`

**Output**

`[8 34 46 28 36 45 25 20]`

`[4 22 38 20]`

Based on the above, we can now create a signature of our function:

### 2. Come up with some example inputs & outputs. Try to cover all edge cases.

Our function should be able to handle any set of valid inputs we pass into it. List a few scenarios here:

- If both lists are empty, result should be list of
`0`

- If one list is empty, then result would be
`0s`

- If one list of 1, then result would be
`Other List`

- Would a list containing list be a valid input?
**???**

(add more if required)

Create a test case of each of the above scenarios. We'll express our test cases as dictionaries, to test them easily. Each dictionary will contain 2 keys: `input`

(a dictionary itself containing one key for each argument to the function and `output`

(the expected result from the function).

Let's store all the test cases in a list, for easier automated testing.

### 3. Come up with a correct solution for the problem. State it in plain English.

Our first goal should always be to come up with a *correct* solution to the problem, which may not necessarily be the most *efficient* solution.

Here's the simplest solution: If you have lists `poly1`

and `poly2`

representing polynomials of length $m$ and $n$ respectively, the highest degree of the exponents are $m-1$ and $n-1$ respectively. Their product has the degree $(m - 1) + (n - 1)$ i.e $m + n - 2$. The list representing the product has the length $m + n - 1$. So, we can create a list `result`

of length $m + n - 1$, and set

`result[k]`

= Sum of all the pairs `poly1[i] * poly2[j]`

where `i+j = k`

Example:

$(2 + 5x^2 + 7x^3) \times (3 + 4x + 2x^2)$

$= (2 \times 3) + (2 \times 4 + 0 \times 3)x + (2 \times 2 + 3 \times 5 + 4 \times 0)x^2 + (7 \times 3 + 5 \times 4 + 0 \times 2)x^3 + (7 \times 4 + 5 \times 2)x^4 + (7 \times 2)x^5$

$= 6 + 8x + 19x^2 + 41x^3 + 38x^4 + 14x^5$

Explain this solution in your own words below:

`m = len(poly1) and n = len(poly2)`

`result = [0]*(m+n-1)`

`result[0] = poly1[0]*poly2[0]`

`result[1] = poly1[1]*poly2[0] + poly1[0]*poly2[1]`

`result[2] = poly1[1]*poly2[1] + poly1[0]*poly2[2] + poly1[2]*poly2[0]`

(add more steps if required)

Let's save and upload our work before continuing.

### 4. Implement the solution and test it using example inputs. Fix bugs, if any.

Implement the solution

Test your solution using the test cases you've defined above.

### 5. Analyze the algorithm's complexity and identify inefficiencies, if any.

Can you analyze the time and space complexity of this algorithm?

### 6. Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.

We can apply the divide and conquer technique to solve this problem more efficiently. Given two polynomials `A`

and `B`

, we can express each of them as a sum of two polynomials as follows:

We need to compute the terms `A0 * B0`

, `A1 * B0 + A0 * B1`

and `A1 * B1`

. This can obviously be done using 4 multiplications, but here's a way of doing it with just three multiplications:

Each of the products can themselves be computed recursively. For a more detailed explanation of this approach see http://www.cse.ust.hk/~dekai/271/notes/L03/L03.pdf .

Need help? Discuss and ask questions on the forum: https://jovian.ai/forum/c/data-structures-and-algorithms-in-python/assignment-3/89

### 7. Come up with a correct solution for the problem. State it in plain English.

Explain the approach described above in your own words below:

**???****???****???****???****???**

(add more steps if required)

Let's save and upload our work before continuing.

### 8. Implement the solution and test it using example inputs. Fix bugs, if any.

We are now ready to implement the solution. You may find the following functions `add`

, `split`

and `increase_exponent`

useful.

Implement the optimized multiplication algorithm below. You may use the some or all of the helper functions defined above.

Test your solution using the empty cells below.

### (Optional) 9. Analyze the algorithm's complexity and identify inefficiencies, if any.

Can you analyze the time and space complexity of this algorithm?

Hint: See the tree of subproblems below (source). Substitute the right values for `n`

and `b`

to determine the time complexity.

### Cheat Code:

The numpy.polymul() method evaluates the product of two polynomials and returns the polynomial resulting from the multiplication of two input polynomials ‘p1’ and ‘p2’.

```
Syntax : numpy.polymul(p1, p2)
Parameters :
p1 : [array_like or poly1D]Input polynomial 1.
p2 : [array_like or poly1D]Input polynomial 2.
Return: Polynomial resulting from multiplication of the inputs.
Constructing polynomial and defining ndarray
x = np.array([1, 2])
y = np.array([4, 9, 5, 4])
mul = np.polymul(y, x)
print("\n1D array : ")
print("Multiplication Result : ", mul)
Would result in :
```

A[] represents coefficients of first polynomial B[] represents coefficients of second polynomial m and n are sizes of A[] and B[] respectively def multiply(A, B, m, n):

```
prod = [0] * (m + n - 1);
# Multiply two polynomials term by term
# Take ever term of first polynomial
for i in range(m):
# Multiply the current term of first
# polynomial with every term of
# second polynomial.
for j in range(n):
prod[i + j] += A[i] * B[j];
return prod;
```

A utility function to print a polynomial def printPoly(poly, n):

```
for i in range(n):
print(poly[i], end = "");
if (i != 0):
print("x^", i, end = "");
if (i != n - 1):
print(" + ", end = "");
```