Assignment 3 - Divide-n-Conquer Algorithms in Python

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

In this assignment, we will implement an efficient algorithm for polynomial multiplication.

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:

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

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

Given two polynomial represented by two lists, we have to write a function that multiplies the given two polynomials.

Input

1. poly1 - List representation of first polynomial.
2. poly2 - List representation of second polynomial.

Output

1. result - List representation of multiplied polynomial.

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