Comp 212 Assignment # 2
Polynomials

Due Monday, September23, 2002 11:59 PM - No Late Submission will be accepted

This homework illustrates the use of abstraction to implement polynomial and turn it into what is coined as a "component software".  It makes use of the visitor pattern, the composite pattern, and the abstract factory pattern.

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 order (or degree) 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.  There is an abstraction called polynomial.  A constant polynomial is a polynomial with a leading coefficient and order (degree) 0.  A non-constant polynomial is a polynomial with a leading coefficient, a positive order, and a lower order polynomial.  The polynomial's intrinsic behavior is to provide the clients with its order -getOrder (), its leading coefficient - get LeadCoef (), and, in the case of a non-constant polynomial, its lower order polynomial  - getLowerPoly ().  Constant polynomials do not contain lower order polynomials and have no getLowerPoly() method.

Polynomials can be viewed as having an immutable linear recursive structure and can be implemented using the composite pattern.  All extrinsic operations on polynomials can be implemented as visitors to polynomials.  Below is a UML class diagram showing the design of polynomials as framework analogous to that of the immutable list structure, IList.

 

Click here to see the javadoc for the above framework..

Your task is to implement a concrete factory to manufacture IPoly objects and to write a few concrete IPolyOp as operations on IPoly.

  1. Write the code for the interfaces IPoly, IConstPoly, INCPoly, IPolyOp, and IPolyFact as shown in the above UML class diagram. Package them in a package named poly.
  2. Write a concrete IPolyFact that implements IPolyFact.  This concrete factory must be a singleton and must use the composite design pattern to implement IPoly, IConstPoly, and INCPoly.  Name this class anything you want.  Package this concrete class in a package named poly.factory.  You must hide all details of implementation from any client code of this class.
  3. Write Add, an IPolyOp to add a polynomial to the host and return the resulting sum polynomial.  Add should take an IPolyFact as input parameter to the constructor, and the right-hand-side polynomial operand as the input parameter.  Use anonymous inner classes as helpers.  Package this concrete class in a package names poly.op.
  4. Write Mul, an algorithm to multiply a polynomial to the host and return the resulting sum polynomial.  Mul should take an IPolyFact as input parameter to the constructor, and the right-hand-side polynomial operand as the input parameter.  Use anonymous inner classes as helpers.  Package this concrete class in a package names poly.op.
  5. Write LongDiv, an algorithm to perform long division on polynomials as described by the following.  The host polynomial is the divisor; the input parameter is the dividend polynomial; the result to be returned is the pair of quotient/remainder polynomials defined by:
    package poly.op;

import poly.*;

/**
 * Holds the quotient/remainder pair in polynomial long division.
 */
public class QRPair {
    private IPoly _quotient;
    private IPoly _remainder;

    public QRPair(IPoly quotient, IPoly remainder) {
        _quotient = quotient;
        _remainder = remainder;
    }

    public final IPoly getQuotient() {
        return _quotient;
    }

    public final IPoly getRemainder() {
        return _remainder;
    }
}

    LongDiv should take an IPolyFact as input parameter to the constructor.  Use anonymous inner classes as helpers.  Package this concrete class in a package names poly.op.

  6. Write EvalHorner to evaluate the host 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

    You may use the standard double Math.pow (double a, double b)to compute ab.  Look for java.lang.Math.pow in the JDK documentation.
    EvalHorner should take a Double (the value x to be evaluated at) as input parameter.  Use anonymous inner classes as helpers.  Package this concrete class in a package names poly.op.

For each of the above problems, be sure to add test cases which cover all reasonable cases. For instance, the visitor EvalHorner should be tested on constant polynomials.  The client test program may be in the default (no-name) package.   Since polynomials are mathematical objects that are intrinsically immutable, all polynomials in this exercise should NOT be modified once they are manufactured by a factory.

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.

Submission

The homework is due Monday, September 23, 2002 11:59 PM .  It is to be submitted electronically.  The electronic submission project name is "poly".   The complete homework set should contain the following:

 dxnguyen@cs.rice.edu         Please let us know of any broken links             Revised Sept. 15, 2002