Divide-n-Conquer Algorithms in Python

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

import pandas as pd df = pd.read_csv('/datasets/quantium_qvi/QVI_data.csv')

!ls /datasets/quantium_qvi

df.info()

def min_edit_distance(str1, str2, i1=0, i2=0): if i1 == len(str1): return len(str2) - i2 if i2 == len(str2): return len(str1) - i1 if str1[i1] == str2[i2]: return min_edit_distance(str1, str2, i1+1, i2+1) return 1 + min(min_edit_distance(str1, str2, i1, i2+1), # Insert at beginning min_edit_distance(str1, str2, i1+1, i2), # Remove from min_edit_distance(str1, str2, i1+1, i2+1)) # Swap first min_edit_distance('110', '101')

df.head()

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:

def multiply(poly1, poly2): pass

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

test0 = { 'input': { 'poly1': [2, 0, 5, 7], 'poly2': [3, 4, 2] }, 'output': [6, 8, 19, 41, 38, 14] }

test1 = { 'input': { 'poly1': [2, 4, 0, 0, 5], 'poly2': [4, 9, 5, 4] }, 'output': [8, 34, 46, 28, 36, 45, 25, 20] }

test2 = { 'input': { 'poly1': [2, 4], 'poly2': [2, 7, 5] }, 'output': [4, 22, 38, 20] }

test3 = { 'input': { 'poly1': [1, 1, 1], 'poly2': [2, 7, 5] }, 'output': [2, 9, 14, 12, 5] }

test4 = { 'input': { 'poly1': [], 'poly2': [2, 7, 4] }, 'output': [0, 0, 0] }

test5 = { 'input': { 'poly1': [0], 'poly2': [2, 6, 5, 3, 4] }, 'output': [0, 0, 0, 0, 0] }

test6 = { 'input': { 'poly1': [1], 'poly2': [2, 6, 5, 3, 4] }, 'output': [2, 6, 5, 3, 4] }

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

tests = [test0, test1, test2, test3, test4, test5, test6]

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

def multiply_basic(poly1, poly2): m = len(poly1) n = len(poly2) result = [0]*(m+n-1) # print(result) for k in range(len(result)): # print('k is', k) for i in range(m): # print('i is',i) for j in range(n): # print('j is',j) while i+j == k: result[k] = poly1[i]*poly2[j] # print('result[k] is',result[k], 'for', i, j, k) i += 1 j += 1 return result # result[1] = poly1[1]*poly2[0] + poly1[0]*poly2[1] # result[2] = poly1[1]*poly2[1] + poly1[0]*poly2[2] + poly1[2]*poly2[0]

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

poly1 = [2, 4, 0, 0, 5] poly2 = [4, 9, 5, 4] multiply_basic(poly1, poly2) # Output # [4 22 38 20]

poly3 = [2, 4] poly4 = [2, 7, 5] multiply_basic(poly3, poly4) # Output # [4 22 38 20]

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

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

multiply_basic_time_complexity = 'O(???)'

multiply_basic_space_complexity = 'O(???)'

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.

def add(poly1, poly2): """Add two polynomials""" result = [0] * max(len(poly1), len(poly2)) for i in range(len(result)): if i < len(poly1): result[i] += poly1[i] if i < len(poly2): result[i] += poly2[i] return result

add([1, 2, 3, 4], [0, 4, 3])

def split(poly1, poly2): """Split each polynomial into two smaller polynomials""" mid = max(len(poly1), len(poly2)) // 2 return (poly1[:mid], poly1[mid:]), (poly2[:mid], poly2[mid:])

split([1, 2, 3, 4], [0, 4, 3, 6, 7, 8, 2])

def increase_exponent(poly, n): """Multiply poly1 by x^n""" return [0] * n + poly

increase_exponent([1, 2, 3, 4], 3)

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

def multiply_optimized(poly1, poly2): ???

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 = "");

import pandas as pd import numpy as np x = np.array([2, 4, 0, 0, 5]) y = np.array([4, 9, 5, 4]) mul = np.polymul(y, x) print("\n1D array : ") print("Multiplication Result : ", mul)