Click on the hyperlinked word List (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 is not Java 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 file PolynomialTest.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 a LinkedList of Double objects:This is the first time we will be using parameterized types.
- Each Double is 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 convenient for your implementation
To specify a LinkedList of Doubles, you would say:LinkedList<Double> list = new LinkedList<Double>();This informs Java that the type of objects stored in the list are Doubles. A Double object is essentially the object version of the double type. To see how it works, just click on its name in this lab description and you will be escorted to the API for Double.When you take an object from such a list, Java knows the object will be a Double. Java is reasonable about casting between double and Double, so that the following code:
double coeff = list.getFirst()returns the first element in the list, but it is known to be of type Double. Java converts this automatically to double for you.
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.
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 abouttoString
, 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 abouttoString
, 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.
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 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.For convenience, the method return this so you can make subsequent calls on the same line. For example,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.
Polynomial foo = new Polynomial(); foo.addTerm(4).addTerm(-7).addTerm(0).addTerm(11);could be used as a shorthand for
Polynomial 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.
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,
(Hint: Pass an Iterator as one parameter to a recursive helper procedure.)
To receive credit for this method, you must use recursion.
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.
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 the PolynomialTest and the MorePolynomialTest before you say you are ready to demo.
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 OK while the TA watches