Goals

By the end of this lab, you should...
• be able to use ADTs that encapsulate simple data structures.
• be able to implement a class that encapsulates a list as its internal representation.
• understand Horner's algorithm for polynomial evaluation.

Practice Problems

Expect exercises like these on the quiz. There will be a help session covering these exercises on Wednesday at 10:00am in the Steinberg 105 lecture hall. You will benefit most by doing the exercises before you look at the solutions or attend the Wednesday help session when they will be discussed.

Directions: Familiarize yourself with the documentation for Java's built in LinkedList class, which is an implementation of a list abstraction as discussed in lecture.

Primitives like int and double are not classes, so their values are not Objects. However, sometimes we want to be able to put a primitive value in a data structure where an Object is required. Therefore, as a convenience, Java provides classes that correspond to each of the primitive types. For example, the Integer class provides a constructor whose parameter is the int value that should be held inside the object, and provides an accessor intValue that returns the int value that was stored in the Integer object. (In Java 5.0 and later, this conversion happens automatically. For example, if you pass an int to the add method of a List, the Java compiler will insert code that will automatically create an Integer object corresponding to that int value.)

1. Study the following procedures and then write specifications of what they do. If in doubt, try hand simulating the execution of the procedure on some small test cases.

```LinkedList<Integer> foo(int n) {
while (n >= 0) {
n--;
}
return result;
}

double bar(LinkedList<Integer> numbers) { // asssume: numbers is not null
double result = 0;
for (Integer i : numbers)
result += Math.pow(i, 0.5);
return result;
}

// Assume: a and b are not null
Iterator<String> ls1 = a.iterator();
Iterator<String> ls2 = b.iterator();
while (ls1.hasNext() && ls2.hasNext())
result.addLast(ls1.next() + " " + ls2.next());
return result;
}
```
2. Write a procedure pairwiseSum that takes as its parameters two LinkedLists of Integers and returns a new LinkedList that is the pairwise sum of the lists. If the lists are of different lengths, do the computation as if the shorter list has zeros at the end. For example, if the given lists are (1 2 3 4) and (4 5), the resulting list would be (5 7 3 4).

3. Write a procedure reverse that takes as its parameter a LinkedList and returns a new LinkedList with the same data, but in the reverse order.

4. Write a procedure multiplyPosition that takes as its parameter a LinkedList containing Double objects as data, and returns another LinkedList in which each of the original values was multiplied by its position (index) in the list. For example, if the input was (2 2 2 1 9), the result would be (0 2 4 3 36), computed as follows: (2*0 2*1 2*2 1*3 9*4).

In this lab, you will using an ADT provided in the Java library (the List) as the basis for creating an implementation of a new ADT (a Polynomial). Specifically, 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. Then you will create a ListOfPoints class that you will use to keep track of a list of points along the curve of the polynomial. If you do the extra credit part, you'll use the ListOfPoints to help you graph polynomials on the screen.

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. In the JUnit test file PolynomialTest.java, write test methods that thoroughly tests each of your Polynomial methods. Use test-driven development, writing your test cases before implementing each method.

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.

1. The constructor creates a polynomial with no terms.

2. The method `toString` takes no parameters and returns a String representation of the polynomial. For example, you might return something like "4 + -7x + 0x^2 + 11x^3" as the result. (Note: If you want to be 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 better, show the high-order terms first, as in "11x^3 - 7x + 4".)

3. The method `addTerm` takes a double as its parameter and creates a new high-order term of the polynomial with that coefficient. For convenience, let your 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.

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

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.

Optional Extension 1: Product of Polynomials

In the Polynomial class, write a method `product` that takes another Polynomial as its parameter and returns a new Polynomial that is the result of multiplying the two polynomials.

Optional Extension 2: Graphing Polynomials

The purpose of this extension is to graph polynomials within YOPS. More specifically, Write a main method in Polynomial.java that creates a YOPS window with several panels and displays several different functions in various panels by sampling the polynomial. Draw tiny circles for the points and draw lines to connect them. If you want to really impress us, create sliders for the coefficients of the polynomical and update the graph of the function as the user moves the slider. You should draw the X and Y axis on the graph, with tick marks (or a grid). Use the yops.Text class to label the tick marks (or grid) on each axis at regular intervals. If the the origin (0,0) is not part of the region that you are graphing, you can show the two axes as perpendicular non-intersecting line segments.

Remember that in computer graphics, the coordinate (0,0) is at the upper left, and y increases down the screen. Therefore, after you rescale the points, you'll need to "flip over" the graph so that it doesn't look upside down to a mathematician. You may want to write a separate method in ListOfPoints to flip over the points.

What To Turn In:

Follow these submission instructions to turn in the following files and demonstrate your running program for a TA.
1. cover-page.txt -- Be sure to fill in all information.
2. Polynomial.java
3. PolynomialTest.java
4. any additional files for the optional extensions
Reminder: All code you turn in should conform to the CSE131 Style Guide. Full credit will be given only if your work is well organized, clear, readable, and properly documented.

Demo: After submitting your files, show a TA what your program does. You may be asked to make modifications to your program and/or predict what will happen if certain changes are made.

Kenneth J. Goldman (kjg@cs.wustl.edu)