I need some help over here on assignment 3 optimized algorithm

here is my main multiply function:
def multiply_optimized(poly1, poly2):
m,n = len(poly1),len(poly2)
if m ==1:
return [poly1[0]*poly2[i] for i in range(n)]
elif n == 1:
return [poly2[0]*poly1[i] for i in range(m)]
else:
n = max(m,n)
a,b = split(poly1, poly2)
a0,a1,b0,b1 = a[0],a[1],b[0],b[1]
u = multiply_optimized(a0,b0)
z = multiply_optimized(a1,b1)
x = minus(minus(y, u),z)
return pro

and i have written another function to subtract 2 polynomials that is:
def minus(poly1, poly2):
result = [0] * max(len(poly1), len(poly2))
for i in range(len(result)):
if i > len(poly2)-1:
result[i] = poly1[i] - result[i]
else:
result[i] = poly1[i]-poly2[i]
return result

on giving the poly1 = [1,1] poly2 = [1,1] inputs the function gives [1, 4, 1] output.

can you tell me where i have done the mistake in the function? thanks.

Hey…

When I am running the code for `poly1 = [1,1]` and `poly2 = [1, 1]`, I am getting `[1, 2, 1]` as output which is the correct output and Also I think your code is good but you just have to add the case for `[]` empty array…
Also in `increase_exponent(z, n)` you have to do `n // 2 * 2` to go through the cases of odd length polynomial…

Also, go through this discussion as many of the problems are already solved…but don’t hesitate to ask if you are stuck…

yes i have corrected my code by using n//2n in the a1b1 part and it is working properly now but still i have not passed it my code is now this,
def multiply_optimized(poly1, poly2):
m,n = len(poly1),len(poly2)
if m == 0 and n == 0:
return [0]
if m == 0 or n == 0:
return [0]*max(m,n)
if m == 1:
return [poly1[0]*poly2[i] for i in range(n)]
elif n == 1:
return [poly2[0]poly1[i] for i in range(m)]
else:
x = max(m,n)
a,b = split(poly1, poly2)
a0,a1,b0,b1 = a[0],a[1],b[0],b[1]
#print(a0,a1,b0,b1)
u = multiply_optimized(a0,b0)
v = increase_exponent(multiply_optimized(a0, b1),x//2)
w = increase_exponent(multiply_optimized(a1, b0),x//2)
z = increase_exponent(multiply_optimized(a1,b1),2
x//2)
#print(u,v,w,z)
return pro

and it is not passing all evaluation tests such as test#13, test#15, 16, 17, 18, 19. i dont know why…

Suppose you get polynomial as [] and [1, 2, 3]
In this case, your code will give [0, 0, 0]
But we don’t need any trailing zeroes so our result should be [].

Also for a case like [] and [] your code would give [0] and we need it to be [].

So please make corrections to the code…

Hope it helps

Hi everyone can someone help me in this one ?
Divide and Conquer assignment all the test cases have been passed during my test cases but some are failed during the evaluation of the jovian . Can someone help me in this the code is attached below

1 Like

increase_exponent(Z, 2*(n//2))