Homework Assignment 5

OPTIONAL ASSIGNMENT FOR EXTRA CREDITS

Polynomial Algebra

**Program Due:** Thursday Oct. 19, 2006 at 11:59pm

In this assignment you are to write an application that manipulates univariate polynomials (polynomials in one variable) over reals:

9 x^{16} + 3.4 x^{5} - 1.89 x^{2} + 0.45

The indeterminate variable may be either 'x' (default name) or carry a given name. We will represent the polynomial as a linked list. Each node in the list will have an integer degree, a double coefficient and a reference to the next term. The final node will have a null reference to indicate the end of the list. Here is a linked link representation for the above polynomial:

Terms with a zero coefficient should not be present in the list. You should use a
constant TOLERANCE which is 10^{-8} to remove any terms with such small
coefficients (i.e., if absolute value of the coefficient is less than the given
TOLERANCE).

Write a program that manipulates polynomials stored as linked lists. Your program
should have three classes **Term**, **Polynomial** and **MainDriver**.

The class **Term** should store an integer degree, a double coefficient and a
reference to the next term. You are free to add any private/public methods to support
functional operations.

The class **Polynomial** should store a linked list of terms and must support the
following operations:

- Create a new polynomial. You should have methods to add and remove terms to and from a polynomial. You store a polynomial in descending order of degrees. Terms of the same degree should be consolidated, for example, the polynomial x
- Add two polynomials. This method takes two polynomials, adds them up and returns a new polynomial. The method does not change any of the original polynomials. For instance, adding the polynomial: 3 x
- Multiply a polynomial by a real number. Method takes a polynomial and a real number, multiply them and returns a new polynomial. The method does not change the original polynomial.
- Multiply two polynomials. This method takes two polynomials, multiplies them and returns a new polynomial. The method does not change any of the original polynomials.
- Print a polynomial in descending order of degrees. Use the character '^' for the power sign.

You are to design and implement the **MainDriver** class that should contain test
cases for each of the above methods.

- Terms with a "small" coefficient (its absolute value less than TOLERANCE) are not
present in the linked list representation.
- Terms of the same degree should be consolidated.
- You may assume that a polynomial has only nonnegative integer exponents.
- You are responsible for providing a user interface, which must include
- prompting in a loop for terms to be added to a polynomial. You should prompt for an exponent and a coefficient. The loop should be terminated as soon as the user types a negative integer for the exponent.
- prompting for the operations (listed above) over polynomials. You should allow the user to choose various functional operations from a list. You should have the option for terminating this prompt.

Download the lab.zip. Save it to your temp directory and unzip the files. You should see the following files:

- lab.html
- lab.mcp
- Term.java
- Polynomial.java
- MainDriver.java

FTP your implementation to `/afs/andrew.cmu.edu/course/15/200/www/handin`