CSE 131 Module 6: Abstract Data Types



Update your repository as usual. You should see a lab6 package.

Project: A Polynomial ADT

In this lab, you will using an ADT (Abstract Data Tyep) provided in the Java library as the basis for creating an implementation of a new ADT (a Polynomial). The List interface defines the ADT's methods, and there are several implementations of List that can be used.
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 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 using parameterized types. 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 reasoanble 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.

Description of the Polynomial type

  1. 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.

  2. 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.

  3. 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 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.

    For convenience, the method return this so you can make subsequent calls on the same line. For example,
    Polynomial foo = new Polynomial();
    could be used as a shorthand for
    Polynomial foo = new Polynomial();
    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.

  4. 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.

  5. 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.

  6. 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.

Submitting your work (read carefully)

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