15-200 Fall 2006 Homework Assignment 5 OPTIONAL ASSIGNMENT FOR EXTRA CREDITS Polynomial Algebra

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

Overview:

This is a completely optional assignment. You are not required to complete the assignmnet if you choose not to. However, if you choose to do it you will earn up to 50 extra credit points. These extra points might boost your final grade.

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

9 x16 + 3.4 x5 - 1.89 x2 + 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).

Instructions:

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 x3 + 2 x3 should be stored as 3 x3 .

• 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 x4 + 2 x3 - 4 x to the polynomial 4 x5 - 2 x3 + 2 x + 3 would give 4 x5 + 3 x4 - 2 x + 3

• 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.

Requirements:

1. Terms with a "small" coefficient (its absolute value less than TOLERANCE) are not present in the linked list representation.

2. Terms of the same degree should be consolidated.

3. You may assume that a polynomial has only nonnegative integer exponents.

4. 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.

What You'll Need:

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

Handing in your Solution:

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