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()
def multiply(poly1, poly2):
pass
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]
}
tests = [test0, test1, test2, test3, test4, test5, test6]
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]
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]
multiply_basic_time_complexity = 'O(???)'
multiply_basic_space_complexity = 'O(???)'
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)
def multiply_optimized(poly1, poly2):
???
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)
