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.

Polynomials

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

anxn + an-1xn-1+ ... + a1x + a0,

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

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

For examples:

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.   

Problems

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.

  1. 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:
    anxn + an-1xn-1+ ... + a1x + a0 = ((..(anx + an-1) x + an-2)x + an-3)x + ... + a1)x + a0
    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 abLook for java.lang.Math.pow in the JDK documentation.
  2. 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.
  3. 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. 

Submission

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:


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