Update your repository as usual. You should see a

Click on the hyperlinked wordList(or any other such type) in this lab description to be taken to the online documentation for the object type.

We will be using the
`LinkedList` implementation. For now, its implementation is not of concern to us, but
we will be studying it along with implementation alternatives in the upcoming weeks.

For this lab, you will write a program that creates, manipulates, and evaluates polynomials of arbitrary degree. You will begin by creating a Polynomial class that, among other things, is capable of evaluating itself at points along the x axis.

Note: In the text of the lab, and in the output you generate, we'll use the caret (^) symbol to denote exponentiation. However, you should keep in mind that this isnotJava syntax for exponentiation. (In fact, you may recall that the symbol is used for the boolean operator xor in Java.)

In the file **Polynomial.java**, define the class
`Polynomial`

to satisfy
the following specification.

To expedite your work on this lab, we have provided a JUnit test filePolynomialTest.java. Use the test file as a guide, so that you develop and test your code in small steps.

Each polynomial object will need a way to store the coefficients of the polynomial that it represents. Since you won't know in advance how many coefficients there will be, your Polynomial class will store the coefficients in a list. In particular:

You must use aThis is the first time we will be usingLinkedListofDoubleobjects:

- Each
Doubleis one coefficient.- The length of the list will determine the degree of the polynomial
- The order of the coefficients in the list will correspond to the terms, in either increasing or decreasing order of degree,
whichever is more convenientfor your implementation

To specify aLinkedListofDoubles, you would say:LinkedList<Double> list = new LinkedList<Double>();This informs Java that the type of objects stored in the list areDoubles. ADoubleobject is essentially the object version of thedoubletype. To see how it works, just click on its name in this lab description and you will be escorted to the API forDouble.When you take an object from such a list, Java knows the object will be a

Double. Java is reasonable about casting betweendoubleandDouble, so that the following code:double coeff = list.getFirst()returns the first element in thelist, but it is known to be of typeDouble. Java converts this automatically todoublefor you.

- The constructor creates a polynomial with no terms. The value of
such a polynomial is
`0`at all points.The polynomial, with no terms added yet, presents a special case that you must treat properly in the methods for this ADT! We will be testing for this when you demo.

- The method
`toString`

takes no parameters and returns a String representation of the polynomial. For example, you might return something like`4x^0 + -7x^1 + 0x^2 + 11x^3`as the result.If you want to be clever about

`toString`

, you can treat the constant term and the`x`term specially, returning`4 + -7x + 0x^2 + 11x^3`. If you want to be even more clever about`toString`

, you can watch the signs and omit terms with a zero coefficient, returning something like`4 - 7x + 11x^3`instead. Even more betterer, show the high-order terms first, as in`11x^3 - 7x + 4`. - The method
`addTerm`

takes a double as its parameter. The result of the call is that the`Polynomial`. is modified to have a new higher-order term with the specified coefficient.The

For convenience, the method return`Vector`class you wrote for lab 7 was immutable, so the operations on`Vector`always returned a new`Vector`and could not modify the existing one.**Such is not the case here.**Although the`LinkeList list`is declared`final`in`Polynomial`, methods can be called on`list`, including those that add things to the linked list. It is the reference itself,`list`, that is`final`and cannot be modified to point to any other`LinkedList`.`this`so you can make subsequent calls on the same line. For example,Polynomial foo = new Polynomial(); foo.addTerm(4).addTerm(-7).addTerm(0).addTerm(11);

could be used as a shorthand forPolynomial foo = new Polynomial(); foo.addTerm(4); foo.addTerm(-7); foo.addTerm(0); foo.addTerm(11);

to create the polynomial`4 + -7x + 0x^2 + 11x^3`.Even if I had not said the following already, the above example confirms that

`Polynomial`must be mutable. The longhand sequence would have no cumulative effect if each call returned a new`Polynomial`. - The method
`evaluate`

takes a double value*x*as its parameter, and returns the double value of the polynomial at point*x*. For example, if the polynomial is`7 + 5x - 2x^2 + 5x^3`, then`evaluate(2.0)`

would return`49.0`. Use a**recursive**implementation of Horner's method as the algorithm for evaluation. For example,`7 + 5x - 2x^2 + 5x^3`=`7 + x(5 + x(-2 + x(5)))`(Hint: Pass an Iterator as one parameter to a recursive helper procedure.)

**To receive credit for this method, you***must*use recursion. - The method
`derivative`

takes no parameters and returns a**new**Polynomial that is the first derivative of this polynomial. For example, if this polynomial is`7 + 5x - 2x^2 + 5x^3`, you would return a Polynomial object representing the polynomial`5 - 4x + 15x^2`.If you have not studied calculus, point this out when you demo and you will not be held responsible for implementing this method.

- The method
`sum`

takes another Polynomial as its parameter and returns a**new**Polynomial that is the result of adding together the two polynomials. It should return the correct result even if the two polynomials are of different degree.

Be sure your work passes both thePolynomialTestand theMorePolynomialTestbefore you say you are ready to demo.

- You must commit all of your work to your repository. It's best to do this from the top-most level of your repository, which bears your name and student ID.
- You must demo the commited work to a TA. Make sure the TA knows that your demo is for credit at this point.
- Follow the directions below to have your demo for this work recorded.

Last modified 08:59:37 CST 09 January 2015

When you done with this lab, you must be cleared by the TA to receive credit.

- Commit all your work to your repository
- Fill in the form below with the relevant information
- Have a TA check your work
- The TA should check your work and then fill in his or her name
- Click
OKwhile the TA watches- If you request propagation, it does not happen immediately, but should be posted in the next day or so