Polynomial Operations

The questions below are due on Monday February 18, 2019; 11:00:00 PM.

You are not logged in.
If you are a current student, please Log In for full access to this page.

Over the next few weeks, we will build up representations (specifically, System Functionals) that allow us to use polynomial math to reason about signals and systems. Today, we will start building some tools in Python that will help us automate mathematical operations on polynomials (which we will be able to use to help us reason about signals and systems).

By the end of this exercise, we will not have a complete working representation of polynomials in Python, but we will have built up some necessary pieces.

For now, we will represent a polynomial by a list of coefficients, starting with the zeroth-order term. For example, here are some Polynomials and their representation as lists of this form:

Polynomial	Coefficient List
x^4-7x^3+10x^2-4x+6	`[6, -4, 10, -7, 1]`
3x^3	`[0, 0, 0, 3]`
8	`[8]`
0	`[]` or `[0]` (your code should handle both of these cases!)

In this exercise, we will define several functions that operate on polynomials represented in this form:

poly_order(coeffs) should return the order of the polynomial represented by the coefficient list coeffs. Note that the order of the polynomial representing 0 is usually either considered to be undefined, -1, or negative infinity. As such, your code can consider the order of the zero polynomial to be any of None, 0, -1, or float('-inf'); the checker will accept any of these answers as correct.
poly_coefficient(coeffs, i) should return the coefficient of the x^i term in the polynomial represented by coeffs. Note that your code should return the proper coefficient even if it is not explicitly represented in the coefficient list.
poly_evaluate(coeffs, value) should return the numerical result of evaluating the polynomial represented by coeffs when x equals value.
poly_add(coeffs1, coeffs2) should sum the polynomials represented by coeffs1 and coeffs2 and return the result as a new coefficient list.
poly_mul(coeffs1, coeffs2) should multiply the polynomials represented by coeffs1 and coeffs2 and return the result as a new coefficient list.
poly_roots(coeffs) should returns a list containing the root or roots of first or second order polynomials ¹. If the roots are real-valued, then return the roots as floats. If a root has a non-zero imaginary part, then return it as a complex number (Python has built-in support for complex numbers; see the Python documentation for numerical types). Note that \sqrt{x} can be computed as x**0.5 (or as math.sqrt(x) if import math has been executed).

Define all of these functions in a single file, debug and test on your own machine, and upload the resulting file when you are ready.

Note: Test Cases

When debugging on your own machine, come up with a few useful test cases for each of the functions described above, and set your machine up to run them when you execute your code. Carefully constructed test cases can often be very helpful in tracking down subtle issues in your code.

For example, some questions you might ask when coming up with test cases for poly_coefficient are: What should the result of asking for the coefficient associated with the x^3 term of 3x^3 + 4x + 8 return? The x^0 coefficient? The x^2 coefficient? The x^8 coefficient?

There is no special format required of a test case; they are simply there to help you! Often, the most straightforward way to encode test cases is to use the print function (which is also useful for debugging more generally!). For example, you could encode the first of the questions from above as a test case by using code something like the following:

print('Test 1: x^3 coefficient of 3x^3 + 4x + 8')
print('Expected: 3')
print('Produced:', poly_coefficient([8, 4, 0, 3], 3))

so that when you run your code, you can compare the expected result against what your code actually produced.

Note that you should always know what you expect from your test cases before you run your code (so that you can tell whether your code is working as expected or not!).

Warning

The test cases we use for checking whether your code is correct are often difficult to make sense of, as they may use random numbers that are hard to reason about. What's more, we will not always show you all of the test cases we are using to check your code for correctness. As such, it is important to get into the habit of writing your own test cases, and making them easy to understand and interpret!

If you ask for help debugging on Piazza or during office hours, don't be surprised if we ask to see your test cases first!

No file selected

Footnotes

¹For orders other than 1 and 2, just print an error message saying that you don't handle them, though if you have the time and interest, you might try implementing the Durand-Kerner method or something similar, to allow finding roots of higher-order polynomials (click to return to text)