Assignment 5 -- Polynomials!

Submit all .java source code files (and ONLY .java files) as one .zip file. Hand in a printed report during the next class. Value 30 points.

NOTE: You should do a custom linked list implementation for this assignment -- do not use the SimpleLinkedList class or the LinkedList class built into Java.

Read this entire specification before beginning work on the assignment!

Concepts

Implementing a data structure

Working with linked lists

Unit testing

Overview

Your tasks for this assignment are 1) to write a class named Polynomial that models a polynomial, and 2) to write a complete unit test class for your Polynomial class. There is no user interface this time -- just a 'model' and a test class that acts as the client code.

Class Polynomial

You are going to write the class Polynomial to model a polynomial expression. A polynomial has one variable x, real number coefficients, and non-negative integer exponents. Such a polynomial can be viewed as being a finite sum of terms having the form:

Anxn + An-1xn-1 + ... + A2x2 + A1x + A0

where the An are the real number coefficients . The coefficient A0 is called the "constant" or "zeroth" term of the polynomial. If you are not familiar with any of the math in this project, and the descriptions are not adequate, please ask for help!

Your class needs to implement only the methods listed below. Your implementation of the class Polynomial must make use of a linked list to represent the polynomial. The list will be a "sparse" representation of the polynomial. This means that the list will contain entries only for terms with non-zero coefficients. Each node in the list contains the coefficient (a double) and exponent (an int) of one term in the polynomial. For example, the polynomial 4x5 + 3x2 - 5 can be represented like this:

Here are some key class invariants your class must guarantee:

No term shall have a coefficient of zero. If the coefficient works out to zero (as the result of addition or multiplication, for example), eliminate the term.

No two terms may have the same exponent.

Terms must be maintained in the linked list in decreasing order by exponent.

Here is the class specification. I have not specified what the preconditions are and what the methods should do if preconditions are not met. I leave that to you to determine based on discussions we've had in class.

Methods	Descriptions
Polynomial(String s)	Construct a Polynomial based on a string which contains a series of numbers separated by whitespace. The numbers are always in pairs: coefficient followed by exponent. For example, this statement should create the polynomial illustrated in the example above: Polynomial p = new Polynomial( "4 5 3 2 -5 0" ); This would also be a legal statement: Polynomial p = new Polynomial( "4.8 5 -3.5 2 1.5 0" );
Polynomial(Polynomial p)	Construct a Polynomial that is a duplicate (a deep copy) of the one provided without modifying p.
int terms( )	Returns the number of terms in this Polynomial.
void addTerm(double coef, int exp)	Add a new term to this Polynomial if there is not already a term with the specified exponent. If a term with the specified exponent already exists, update its coefficient by summing it with the new one.
double deleteTerm(int exp)	If a term with the specified exponent exists in this Polynomial, delete that term and return its coefficient; otherwise return 0.0.
double getCoefficient(int exp)	Return the coefficient for the specified exponent; return 0.0 if no such term.
double evaluate(double x)	Return the value of this Polynomial for the given value for the variable x.
boolean equals(Object o)	Override the equals method in an appropriate way.
Polynomial derivative( )	Return the first derivative of this Polynomial. If you are not familiar with finding the derivative, you can read about it here (Links to an external site.)Links to an external site..
String toString( )	See instructions below for the string formatting requirements.
String description( )	See instructions below for the string formatting requirements.
static Polynomial sum( Polynomial a, Polynomial b)	Returns a new Polynomial that represents the sum of two Polynomials (a + b) without modifying a or b.
static Polynomial product( Polynomial a, Polynomial b)	Returns a new Polynomial that represents the product of two Polynomials (a * b) without modifying a or b.

IMPORTANT: Be aware that special care is required to ensure that all class invariants are satisfied for every Polynomial object. Consider these examples, and use care to identify all special cases:

(4.0x5 + 3.0x2 - 5.0) + (x4 - 3.0x2 - 2.0) ==> (4.0x5 + x4 - 7.0)

(3.6x2 - 9.0) * (2.0x2 + 5.0) ==> (7.2x4 - 45.0)

(3.0x2 - 2.0) + (-3.0x2 + 2.0) ==> 0 // a Polynomial with zero terms

The 'toString' Method

The 'toString' method should produce output that represents the Polynomial in the normal fashion (use ^ to represent exponentiation in this simple text representation). This means:

Terms shall be shown in descending order by exponent.

If the coefficient is 1 or -1, the number is dropped and only the sign is shown.

If the exponent is 1, it is not shown.

If the first coefficient is positive, no leading + sign is shown.

If the exponent is zero (the constant term), no variable name or exponent are shown.

If the polynomial has zero terms, "0.0" is returned.

Here are a few examples:

( new Polynomial( "-2 2 5 0" ) ).toString( ) ==> "-2.0x^2 + 5.0"

( new Polynomial( "5.4 3 2 1 -5 0" ) ).toString( ) ==> "5.4x^3 + 2.0x - 5.0"

( new Polynomial( "1 3 -1 1" ) ).toString( ) ==> "x^3 - x"

( new Polynomial( "" ) ).toString( ) ==> "0.0"

JUnit test code for the toString method is provided here to help you understand these formatting requirements: A5testToString

The 'description' Method

The 'description' method should produce output that represents the Polynomial in a different way -- with each term described in a separate line. Here are a few examples to illustrate the intended format (notice the presence of the "newline" character ' '):

( new Polynomial( "-2 2 5 0" ) ).description( ) ==> "constant term 5.0 exponent 2, coefficient -2.0"

( new Polynomial( "5.4 3 2 1 -5 0" ) ).description( ) ==> "constant term -5.0 exponent 1, coefficient 2.0 exponent 3, coefficient 5.4"

( new Polynomial( "1 3 -1 1" ) ).description( ) ==> "exponent 1, coefficient -1.0 exponent 3, coefficient 1.0"

( new Polynomial( "" ) ).description( ) ==> "0.0"

IMPORTANT: A key requirement for this method is that it must make use of a private, recursivemethod to create the output for any Polynomial that has one or more terms.

coefficient: 4 coefficient: 3 coefficient first exponent: |5 exponent: 2 exponent: O next next next coefficient: 4 coefficient: 3 coefficient first exponent: |5 exponent: 2 exponent: O next next next