Use the starter notebook(s) to get started with the assignment. Read the problem statement, follow the instructions, add your solutions, and make a submission.

Share your work

Share your work on the Share Your Work Category on the respective monthly threads.

Maybe I missed some information, but shoudln’t this Assignment 3 be the next step for completing this course? When will it be available? I am motivated to dive into these new topics.

Hey, welcome to the community, It’s great that you are this excited to complete this course and dive into these new topics, Assignment 3 will be available soon and course participants will be informed about it, Until then you can do DSA practice in different coding platforms like LeetCode, Codeforces, TopCoders, etc. Happy Learning.

I’m struggling with the optimised multiplication algorithm. I’ll be honest, I’m not entirely sure about what I am doing so I am looking for some pointers about how to implement this.

Here’s my code so far:

def multiply_optimized(poly1, poly2):
n = max(len(poly1),len(poly2))-1
A, B = split(poly1, poly2)
Y = multiply_optimized(add(A[0],A[1]), add(B[0],B[1]))
U = multiply_optimized(A[0],B[0])
Z = multiply_optimized(A[1],B[1])
product = U + increase_exponent([Y-U-Z],n/2) + increase_exponent(Z,n)
return product

I am getting a RecursionError (maximum recursion depth exceeded in comparison) on the line Y = mult.... . Any ideas on how to properly implement this algorithm without error?

@ahmedsadid , in your code Y = multiply_optimized(add(A[0],A[1]), add(B[0],B[1])) … this line and def multiply_optimized(poly1, poly2): this literally means the same line … which thus results in eternal recursion

def multiply(A, B, m, n):
prod = [0] * (m + n - 1);
for i in range(m):
for j in range(n):
prod[i + j] += A[i] * B[j];
return prod;
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 = "");
# Driver Code
A = [5, 0, 10, 6];
B = [1, 2, 4];
m = len(A);
n = len(B);
print("First polynomial is ");
printPoly(A, m);
print("\nSecond polynomial is ");
printPoly(B, n);
prod = multiply(A, B, m, n);
print("\nProduct polynomial is ");
printPoly(prod, m+n-1);

You have not specified any condition to stop the recursion. So when you call the function again in this line Y = multiply_optimized(add(A[0],A[1]), add(B[0],B[1])) . It creates a infinite recursion call.

Everything else is good in your implementation except the product = … line. There is a reason the add function is predefined so use that for everything possible. That is the only hint I can give right now, reply if it still does not work.

I can point at a number of things that need to be changed:

n should be the max length of either of the arrays, without the minus 1;

You need to implement array subtraction (or modify the add function) to achieve [Y - U - Z];

You need to implement the base condition that will terminate the recursion (e.g., when the size of either array is 1, multiply its value with the other array); and

You need to use the add function in U + increase_exponent([Y-U-Z],n/2) + increase_exponent(Z,n).

I am not sure if all these will get your code to evaluate correctly, but I am sure they will get you closer.

Edit: n as used increase_exponent(Z,n) should instead be len(poly1) + len(poly2) - 1 - len(Z).

Is it some problem on our end by any chance? I think not because the function is already defined in the notebook. Please let me know in case you figure it out.

Someone please guide me how to test the solutions of the test cases defined once we’ve written the algorithm. I’m stuck on this part: Test your solution using the test cases you’ve defined above.

I am just not getting the logic behind the optimized algorithm. There is no video on this assignment, and Divide and Conquer algorithm wasn’t explained in the earlier lesson as well. Can someone help me out here?