CS 341 Project 1: Polynomial (Due via email by 11:00 PM on 3/2/2011)

Objective
This project is to reinforce the concept of ADT by the design and implementation of an ADT Polynomial.

Description
This project is to develop programs to deal with polynomials of single variable.  The interface and a driver program will be provided to you. 

ADT Polynomial
The following is the list of operations in the ADT Polynomial.

int degree();
// Determines the degree of a polynomial.

Polynomial add(Polynomial p);
// Adds polynomial p to this polynomial and returns the result.

Polynomial mult(Polynomial p);
// Multiplies polynomial p to this polynomial and returns the result.
// Throws: ExponentOutOfRangeException if exponent is out of range.

void mult(double scalar);
// Multiplies a scalar to this polynomial.

double getCoefficient(int power)
// Gets the coefficient of the x to the power term.
// Throws: ExponentOutOfRangeException if exponent is out of range.

void changeCoefficient(double newCoefficient, int power)
// Replaces the coefficient of the x to the power term with newCoefficient.
// Throws: ExponentOutOfRangeException if exponent is out of range.

double evaluate(double x);
// Evaluates the polynomial at x.

void displayPolynomial();
// Display the polynomial.

Your task is to implement the ADT polynomial, including the constructor and the operations defined in the interface, using two different approaches.  The first one is array based and the other one is reference based.

Array-Based Implementation
An array of doubles is used to represent a polynomial.  The index of an item in the array represents the exponent, and the value of the array element is the coefficient of the term.  For example, if the polynomial p(x) = 10x¹⁵ - 3.2x⁸  + x + 7.5 and is represented by an array p[], then p[15] = 10.0, p[8] = -3.2, p[1] = 1.0, p[0] = 7.5, and the other items in the array are zeroes.

Reference-Based Implementation
A reference-based linked list is used to represent a polynomial.  The node of the list has three fields: a double coefficient, an integer power, and a reference to a node next.  The terms of a polynomial are stored in the linked list according to their power in the descending order.  For example, if the polynomial p(x) = 10x¹⁵ - 3.2x⁸  + x + 7.5, then the linked list representing it is as follows:

p --> [10.0, 15] --> [-3.2, 8] --> [1.0, 1] --> [7.5, 0]

There are two cases of constant polynomials.  If the polynomial is not equal to 0, for example,  p(x) = 12.1, then the list is p --> [12.1, 0].  But, if the polynomial is a zero polynomial, then the list is a null list.

Development Details

1. Create two folders or two packages, one for your array-based work and the other for your reference-based work.
2. Set the array size to 100 in the array-based implementation.
3. The constructor (in both implementations) creates a zero polynomial.
4. When a polynomial is displayed, ^ is used to represent the power of a term.  For example, 10x¹⁵ - 3.2x⁸  + x + 7.5 is displayed as "10x^15 + -3.2x^8 + x + 7.5".  Note that this task is not as easy as you would think as there are a lot of details to deal with. However, do not spend too much time to make display perfect if you have not finished other parts.
5. You are required to implement the method evaluate() in the array-based using Horner's rule as described on page 134 in the book.
6. You are required to implement the method evaluate() recursively in the reference-based implementations.
7. You are NOT ALLOWED to modify the interface file PolynomialInterface.java and the exception file ExponentOutOfRangeException.java provided to you by the instructor.
8. You are required to manupulate references using getNext() and setNext() for your reference-based implementation . In the sense, you are NOT ALLOWED to use Java's java.util.LinkedList or something similar.
9. You should complete (at least most of) the array-based implementation within 7 to 10 days, otherwise you might have trouble completing the whole project in time.

Testing
Use PolynomialDriver1.java to test your implementations.  The results from the array-based and reference-based implementations should be identical to the instructor's result1 and result2, respectively.  The two results are different as there won't be exceptions thrown by the reference-based implementation.  You are encouraged to develop more test cases.

Programs and Report
Your programs should be written in a good style and well-documented.  Your report should describe the algorithms used to implement your methods, the comparison of the two implementations, and obstacles encountered when implementing your code.  In your report, also include what you learn from this project and any other suggestions and comments.

Submission: Zip everything you want to submit into a file and email it to the instructor.