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

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

- 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) { LinkedList<Integer> result = new LinkedList<Integer>(); while (n >= 0) { result.addFirst(n); 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; } LinkedList<String> baz(LinkedList<String> a, LinkedList<String> b) { // Assume: a and b are not null Iterator<String> ls1 = a.iterator(); Iterator<String> ls2 = b.iterator(); LinkedList<String> result = new LinkedList<String>(); while (ls1.hasNext() && ls2.hasNext()) result.addLast(ls1.next() + " " + ls2.next()); return result; }

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

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.

- The constructor creates a polynomial with no terms.
- 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".) - 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(); 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. - 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.)

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

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.

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.

- cover-page.txt -- Be sure to fill in all information.
- Polynomial.java
- PolynomialTest.java
- any additional files for the optional extensions

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