Homework 2
CS203, Spring 2006


Due: Wednesday, April 26

Please upload your source code and other files using CSNS. Note that file uploading will be disabled automatically after 11:59PM of the due date, so please turn in your work on time.

In this assignment you are going to create a Java class representing single-variable polynomials. A single-variable polynomial has the general form of

a0 + a1x + a2x2 + ... + an-1xn-1 + anxn

Usually there are two ways to represent a polynomial in computer programs: using an array or using a linked list. For example, the polynomial 1 + 5x2 + x5 can be represented with an array of [1, 0, 5, 0, 0, 1], or a linked list of (1,0) -> (5,2) -> (1,5). Clearly, the linked list representation is better in general because the array representation wastes lots of space to store the zero coefficients.

1. (50pt) Write a Java class Polynomial which represents a polynomial using a linked list of Terms, where each term consists of a coefficient and an exponent. Note that

For example, the polynomial 1 + x + 3x4 should be represented as (1,0) -> (1,1) -> (3,4), but not (3,4) -> (1,0) -> (1,1) or (1,0) -> (1,1) -> (1,4) -> (2,4).

The Polynomial class must have at least the following methods:
2. (30pt) What are the complexities of insertTerm(), add(), and multiply() methods in your Polynomial class? For add() and multiply(), the complexities may be functions of N and M, which are the numbers of terms in the two polynomials involved. Explain how you calculate/estimate the complexities. Note that you will not receive any credit if you simply give the Big-O notations without any explanation.