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 coeffcients there will be,
your Polynomial class will store the coeffieints in a list. In particular, it can use a
`LinkedList`
of
`Double`
objects, where each `Double` is one coefficient. The length of the list will determine the degree of the polynomial, and the order of the coefficients in the list will correspond to the terms, in either increasing or decreasing order of degree, whichever is more convenient in the implementation.

This is the first time we will be usingparameterized types. 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 reasoanble 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 5 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 cummulative 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`. - 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.

- Complete the
`cover-page.txt`file in the repository for this lab. Just open it up in your eclipse editor and type in your responses. - In the
`cover-page.txt`file, be sure to indicate anybody with whom you have collaborated on the work you are submitting. - 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.
- The TA must have your name and information recorded on a lab demo sheet for this lab to be graded and counted. Be sure your name and ID are written clearly on the TA's demo sheet.

Last modified 22:14:02 CST 11 November 2009 by Ron K. Cytron