Comp 212 Homework 1

Polynomials

Due Friday Feb. 04, 2000 10:00 AM.

This homework exercise serves as a "dry run" for the larger programming projects that will come later. It is based on the Polynomial example discussed in class.

A polynomial of one variable, p(x), is an expression of the form

a_{n}x^{n} + a_{n-1}x^{n-1}+
... + a_{1}x + a_{0},

where n is a non-negative
integer, a_{k} (k =
0.. n) are numbers, and a_{n}
is a number not equal to 0.

n is called the degree (or
order) of p(x),a_{k}
(k = 0.. n) are called the coefficients of p(x), and a_{n}
is called the leading coefficient of p(x).

For examples:

- p(x) = -12x
^{5}+ (-3)x^{2}+ 7 is a polynomial of degree (order) 5 with leading coefficient -12. (-3)x^{2}+ 7 is called the lower order polynomial for p(x). - p(x) = 7 is a polynomial
of degree 0 with leading
coefficient 7.
This is an example of a
*constant*polynomial. It has no lower order polynomial.

We can describe polynomials in the following manner. A polynomial can be constant or non-constant; if it is constant, it has a leading coefficient and degree (order) 0; if is not constant, it has a leading coefficient, a non-zero degree, and a lower order polynomial. As such, polynomials can be viewed as having a linear recursive structure. The polynomial's intrinsic behavior is to provide the clients with its degree, its leading coefficient, and its lower order polynomial (if any).

Your task is to design a system of classes to implement polynomials in the fashion shown in class.

Copy the files `~comp212/hw/01/*.java` into your
local directory, and modify them as follows. You are free
to add any private/protected methods to your classes to support
your public operations.

- Add the method
`public double evalHorner(double x)`

to class`APolynomial`

and appropriate methods to the supporting classes to evaluate the target (receiver) polynomial at a "point" x using Horner's algorithm:

a_{n}x^{n}+ a_{n-1}x^{n-1}+ ... + a_{1}x + a_{0}= ((..(a_{n}x + a_{n-1}) x^{ }+ a_{n-2})x^{ }+ a_{n-3})x + ... + a_{1})x + a_{0 }

This should give the same answer as the given`eval`

method. You should use the standard double Math.pow (double a, double b)to compute a^{b}. Look for java.lang.Math.pow in the JDK documentation. - Add the method
`public APolynomial div(APolynomial p)`

to class`APolynomial`

and appropriate methods to the supporting classes to compute the (long) division of the target`APolynomial`

by the parameter p and return the*quotient*`APolynomial`

. - Add the method
`public APolynomial mod(APolynomial p)`

to class`APolynomial`

and appropriate methods to the supporting classes to compute the (long) division of the target`APolynomial`

by the parameter p and return the*remainder*`APolynomial`

.

For each of the above problems, be sure to add test cases
which cover all reasonable cases. For instance, the method `APolynomial.evalHorner(...)`

should be tested on constant polynomials. Since polynomials
are mathematical objects that are intrinsically immutable, all
programs in this exercise should be written in a purely
functional style: no object fields should be modified once they
have been initialized by a constructor.

As with all programs in this course, lack of good coding style (good style includes reasonable variable names, a header before each non-overridden function, reasonable indentation) will result in a substantial loss of points. In the upcoming lab, you will be shown Java documentation style and javadoc, a tool to generate standard Java html documentation files. The provided java files can serve as examples of coding style and documentation format that are acceptable to us.

The homework is due Friday Feb. 04, 2000 at 10 AM. It is to be submitted electronically. Your labbies will give you specific submission instructions in the upcoming lab tutorial. No late submission will be accepted. The complete homework set should contain the following:

- An ASCII README file to indicate what you have and/or have not done, and to point out specific details that you feel we need to know when grading your work.
- StructureBuilder's UML diagrams of all your class designs.
- All the Java source code necessary to compile and execute your test code.

alc@cs.rice.edu dxnguyen@cs.rice.edu Please let us know of any broken links Revised Jan. 26, 2000