Assignment 3 - Sorting and Divide & Conquer Practice

:zap: In this assignment, you will apply the concepts learned in the first three lessons to:

  • Implement polynomial multiplication in Python
  • Optimize the algorithm using divide and conquer
  • Analyze the complexity of the algorithm
  • Ask questions and help others on the forum

:ledger: Assignment Notebook

Assignment 3 - Divide-n-Conquer Algorithms in Python

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.

:handshake: 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. :slight_smile:

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.

2 Likes

Hello everyone (surprisingly empty here :no_mouth:)

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

That makes sense… but isn’t it also what the solution suggests earlier in the notebook?

Y = (A0+A1)(B0+B1) ?

How do I implement this is python?

i am implementing like this way

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

Then appending co-efficient of each term to new list and performing print

That’s not the optimised solution though. How are you implementing the Divide & Conquer method later in the assignment?

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.

2 Likes

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

1 Like

Why am I getting this error? I don’t understand what’s wrong with this when for ‘poly1’ the same syntax works fine.

test0 = {
‘input’: {
‘poly1’: [2, 0, 5, 7]
‘poly2’: [3, 4, 2]
},
‘output’: [6, 8, 19, 41, 38, 14]
}
File “”, line 4
‘poly2’: [3, 4, 2]
^
SyntaxError: invalid syntax

2 Likes

I am getting this error as well.

1 Like

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.

you need to put a , after 'poly1':[2,0,5,7] as these are the elements of a dictionary

3 Likes

See here page-9 https://www.cse.ust.hk/~dekai/271/notes/L03/L03.pdf PolyMulti1 function.
Now come to your solution. In the very first of the function you should start with

if len(poly1) == 1 :
poduct = [poly1[0]* poly2[i] for i in range(len(poly2)) ]

and then you should check same in a elif block for poly2 and assign product according to that.
and then finally in the else block

n = max(len(poly1),len(poly2))
poly1,poly2 = split(poly1,poly2)

and find out the value of U,V,W,Z and assign product according to that .
Finally return the product.

3 Likes

Use comma in the dict, like:

test5 = {
‘input’: {
‘poly1’: [0, 1] , # Use ,
‘poly2’: [2, 6, -5, 3, 4]
}, # Use ,
‘output’: [0, 2, 6, -5, 3, 4]

}

1 Like

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?

2 Likes