CSE 131 Module 8: ADTs


Update your repository as usual. You should see a lab8 package in the labs source folder.

Project: A Polynomial ADT

In this lab, you will using an ADT (Abstract Data Type) 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 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.
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.

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

    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 cumulative 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.
    If you have not studied calculus, point this out when you demo and you will not be held responsible for implementing this method.

  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.

Be sure your work passes both the PolynomialTest and the MorePolynomialTest before you say you are ready to demo.

Submitting your work (read carefully)

Last modified 11:27:54 CST 30 November 2012
When you done with this lab, you must be cleared by the TA to receive credit.

If you worked in a team using a group– repository:
  • Your work must be committed in that repository for this demo.
  • Each team member must complete this form and have the TA authenticate.
    For example, if there are two of you, then the form must be submitted twice, so that each person's last name and 6 digit ID is captured with the repository name.
  • The repository name must be included on each of the submissions.

group– Enter the name of your group repository here
Last name 6-digit ID

TA: Password: