Assignment 3 - Sorting and Divide & Conquer Practice

Hi! Please guide me a little on how to test the code on the test cases defined.

Use evaluate_test_cases() function. The example of how to use it, has been shown in assignment 1.

2 Likes

Thanks a lot for this, now I am starting to understand this algorithm…sort of. I am getting an error when increasing exponents however
TypeError: can't multiply sequence by non-int of type 'float'

This seems to be caused due to n/2 being a non-integer at some point of the recursion. How should I change the product line to overcome this?

product = add(U,add(increase_exponent(add(V,W),n/2), increase_exponent(Z,n)))

You can use floor division instead of normal division, Python has an operator // that does floor division.

1 Like

There is an image given in the assignment page also a pdf link is provided there, try to follow that and figure out some logic.

Yes you get the point n/2 is a non-integer(floating). To solve this problem you can use floor division( // ).

product = add(U,add(increase_exponent(add(V,W),n//2),
increase_exponent(Z,2*(n//2))))

When you increase the exponent of Z then also floor division needed. For better understand see the algorithm.

For one test case use

evaluate_test_case()

For multiple test cases in a list use

evaluate_test_cases()

You can import these function using

from jovian.pythondsa import evaluate_test_case
or
from jovian.pythondsa import evaluate_test_cases

2 Likes

I tried doing floor division earlier (although using int() instead), but got a different error. Now I used ( // ) along with the change to 2*(n//2), and the algorithm mostly works, but I am randomly getting trailing 0s for some inputs.

For example, ‘poly1’: [1, 2, 3, 4, 5], ‘poly2’: [6, 7] gives the output [6, 19, 32, 45, 58, 35, 0, 0]. Why the trailing zeros? Trying other inputs works correctly mostly.

Such as using ‘poly1’: [1, 2, 3], ‘poly2’: [3, 2, 1] will give [3, 8, 14, 8, 3]

     if len(poly1) == 1 :
        product = [poly1[0]* poly2[i] for i in range(len(poly2))]
    elif len(poly2) == 1 :
        product = [poly2[0]* poly1[i] for i in range(len(poly1))]
    else:
        n = max(len(poly1),len(poly2))
    
        U = multiply_optimized(A[0],B[0])
        V = multiply_optimized(A[0],B[1])
        W = multiply_optimized(A[1],B[0])
        Z = multiply_optimized(A[1],B[1])
    
        product = add(increase_exponent(add(V,W),n//2),
increase_exponent(Z,2*(n//2)))
        return product

Why I am getting a None values in U and V, and while trying to get product, I get 'object of type ‘NoneType’ has no len()

Please help…

I am guessing you have defined poly1 and poly2 as None and not a list, define poly1 and poly2 as list.

Hi guys,

Im having trouble with my code, Im getting a “maximum recursion depth exceeded in comparison” error. Im not sure if this is the right way to do recursion.

Here is what I have so far

Thank you!

For example, ‘poly1’: [1, 2, 3, 4, 5], ‘poly2’: [6, 7] gives the output [6, 19, 32, 45, 58, 35, 0, 0].
Problem with this example is that it creates a empty list in the very beginning when it split first time and I think you have not specified what to do if this type of situation occur. Have to modify the code to handle this problem.

Exactly in which line of the code cause Error ???

RecursionError : maximum recursion depth exceeded in comparison for U and Z.

Line’s 29 and 12, I have a feeling its giving me this error because there is some problem with my end condition. Im really not sure.

Thanks for your help!

I replaced poly1 & poly2 with A & B, and sliced the product list to only output the required length. It works now!

Thanks a lot

Happy for you. Could you please help me…

Why I’m getting this error: " TypeError : object of type ‘NoneType’ has no len()"

I’m sure A,B, poly1 and poly2 are lists. the problem is while calculates U and V

def multiply_optimized(poly1, poly2):
   
    A,B = split(poly1,poly2)
    A = list(A)
    B = list(B)
   
    if len(poly1) == 1 :
        product = [poly1[0]* poly2[i] for i in range(len(poly2))]
    elif len(poly2) == 1 :
        product = [poly2[0]* poly1[i] for i in range(len(poly1))]
    else:
        n = max(len(poly1),len(poly2))
    
        U = multiply_optimized(A[0],B[0])
        V = multiply_optimized(A[0],B[1])
        W = multiply_optimized(A[1],B[0])
        Z = multiply_optimized(A[1],B[1])
    
        product = add(increase_exponent(add(V,W),n//2),increase_exponent(Z,2*(n//2)))
        return product

You need to use the split function under the else branch. In your algorithm A & B aren’t doing anything because you are using poly1 & poly2 throughout the code.

Remove -
A,B = split(poly1,poly2)
A = list(A)
B = list(B)

And add poly1, poly2 = split(poly1,poly2) under n = max(len(poly1),len(poly2))

It’s creates a infinite recursion call in u and z when it calls it again. The termination condition you have defined never satisfied than for u and z. You may include what to do when len(poly1) or len(poly2) equals to 1.

can anyone please share the Come up with a correct solution for the problem. State it in plain English.
I have been scratching my head over this assignment since days but can’t find a break through

3 Likes