PA3: Karatsuba's Algorithm

The objective of PA3 is to create an implementation of Karatsuba's Polynomial Multiplication Algorithm that is correct and meets the complexity expectations.
Download PA3.tar to get started.

In the file Polynomial.py, some of the Polynomial class has been implemented for you. These functions include:

• indexing (__getitem__)
• comparison (__eq__)

Your task is to implement the following functions.

• addition (__add__)
• subtraction (__sub__)
• multiplication (__mul__)

Several steps of these function have been implemented for you.

• Do not change these steps.
• Do not assign an integer to any element of a Polynomial (your submission will not be tested using integer polynomials).

Complete the Polynomial class by implementing the sections labeled with "STUDENT_CODE".

The convolution algorithm has been provided to test correctness. This is the O(n^2) algorithm from lecture. The test_mul function is used to compare the results of convolution to (__mul__).

PA3.tar includes CountyInt.py, which will be used to test the complexity of your code. Feel free to implement your own tests in CountyInt.py.
CountyInt.py shows how the static variable, Polynomial.zero, which will be changed to a CountyInt for grading.

For your submission to be graded properly, do not print to stdout in any function in the Polynomial class.

Submit your completed Polynomial.py to Checkin.

Rubric

• Correctness: 40 pts
• Complexity: 60 pts