Comp 151 -- Spring 2001



A polynomial    P     in x    is a function of the form

P(x) = x_n x^n + .... + x_3 x^3 + x_2 x^2 + x_1 x^1 + x_0 x^0

For example

       P_1(x)  = x^5 +  x - 1    and     P_2(X) = x^3 - 5x + 1

are both polynomials.  In this assignment you will design and
implement a class for symbolic manipulation of polynomials with
integer coefficients. By symbolic we mean that a polynomial P(x)
will be represented by a list  containing its coefficients and
exponents (powers).

When displaying  a polynomial its terms should be output from
largest exponent to smallest.  Terms with coefficients equal to zero
are not displayed.  A  term with exponent equal to 0 does not
show  the exponent since x^0 =1.  A term with exponent equal
to 1 should be written as cx instead of cx^1.  Also,  any coefficients
equal to 1  should not be displayed.  Thus,  we write

          x^4 + 2x^3 + x - 4     instead of    1x^4 + 2x^3 +0x^2 + 1x^1 - 4x^0

The one exception to the rules above is that the zero polynomial
                                      Q(x)  =  0
should be written out as
                                       Q = 0.

Addition and subtraction of polynomials is done on a term by term
basis.  For example,  referring to the two polynomials defined above,
setting                          Q      =    P_1 + P_2
means that                  Q(x)  =    x^5 + x^3 -4x

Multiplication is  the standard polynomial multiplication.

For example, if
      R_1(x)  = x^2 +  1    and     R_2(X) = x^3 - 2
setting                          Q      =    R_1*R_2
means that                  Q(x)  =    x^5 + x^3 - 2x^2 - 2

Since many polynomials have  a  large number of zero terms it
is convenient to represent them using a sparse pointer-based
linked-list representation rather than an array based one.  This
means that the  list will store only the Terms of the polynomial
with non-zero coefficients where a Term is of the form c x^p.

As an example,  your data structure for the polynomial
                   P = 5x^100 + 2x
should only store the two  terms  5x^100 and  2x.
It should not store any of the  zero terms between them.

You assignment is to write a a class     polyClass     whose interface is

// constructors
   // Creates a polynomial P(x) = 0;

   // Creates a polynomial P(x) = c x^p
   polyClass(int c, int p);

   // Copy Constructor  --  makes a deep copy of P
   polyClass(const polyClass& P);

//destructor -- needs to deallocate dynamically allocated data

// assignment operator  -- makes  a deep copy
   void operator=(const polyClass& P);

// Prints the polynomial following the instructions above
   void Display();

//Prints YOUR name, ID Number, Lecture and Lab section
//This will be used for marking purposes
  void Identify_Writer();

It should also support the following four functions that are friends
of the class

friend polyClass operator+( polyClass P1,  polyClass  P2);
friend polyClass operator-(polyClass P1,   polyClass P2);
friend polyClass operator*(polyClass P1, polyClass P2);
friend int operator==(polyClass  P1,  polyClass P2);

where P1+P2  and P1-P2  return the associated sum and
difference polynomials and P1*P2 returns the associated
product polynomial. P1==P2 should return 1 if the two
polynomials are the same (term by term) and 0 if they
are not the same.

Input Format

Your program does not have to read any input.

Output Format

Described in the interface

Testing your program

You should write two files:
Poly.h    containing the class definition
and   Poly.cpp   containing  the class and friend
function implementations.   We will test your files by compiling
them together with another program that will call all of your
functions and check if they perform correctly.

You must test your files yourself and satisfy yourself that
you've covered all possibilities.

We provide a small driver program     CheckPoly.cpp
that can be compiled together with
Poly.h   and    Poly.cpp      to test a few cases. Here
is the output      (revised on 18/4/01 -- see Notes below)
of  CheckPoly.

Note that this program DOES NOT cover all possible
test cases or functions and is not the program that we will
actually use to compile your program

Documentation:  Both files should contain your name, student ID, lecture
and Lab section at the top of the file in comments.  Also, you should
document the implementation of every function,  describing what it does.
Finally,  be sure that you indent your code so that it is readable.
Documentation will count towards part of the grade of this assignment.
If we can not read your program and easily understand from the documentation
what it is doing and why it works,  we will deduct points.

Hints , Ideas and Notes

Since we usually want to access a  polynomial's terms from
largest exponent to smallest exponent it makes sense to store
the terms in  a linked list in which the data items are Terms
and the Terms are sorted in decreasing order by exponent (power)

Recall that a  Term is an item of the form   c x^p

2 When writing your code you have many choices as to how
to implement the linked  list code .  One  is to write it from scratch.
Another is to take  already existing linked list code and modify it. Some
code that you can use if you want  is found in  NewListP.h and
NewListP.cpp (updated April 24 to correct a memory leakage problem).
Note that this list code contains some functions
that you might not want to use. Also,  if you do use this code,
you will have  to modify the data field of the linked list to contain
Term  data.  You can also try and modify the linked list code you
saw in COMP104. A third possibility, for the adventurous,  is to try
and use the list type in C++.

3. Your program will be tested using  the g++  running under  UNIX.
Before  submitting it please make sure that you have tested that your
code works properly in this environment.

4.  Copying of work is not permitted.  You may discuss the problem
with other people  but all of the code must be your own.   If you do
share ideas with other students you should  acknowledge their names
in  comments at the top of your files.

5.  The orginal output of  CheckPoly  had an error (x was written as x^1).
This has now been corrected (18/4/01)

Assessment task

Create a file  Poly.h    containing the class definition

Create a file  Poly.cpp   containing  the class and friend function implementations.

Add your student name, student id, email, and lab section in the very beginning of each file as comment

Create a directory "assign2" and place files  Poly.h  and Poly.cpp under ~/comp151/assign2

Our system will collect the files under ~/comp151/assign2 on Wednesday,  May 2, 2001 at 9:00 AM
(Please note that this date has been pushed later than the original date announced in class in Lecture 1.)

Submit a hard copy of  Poly.h  and Poly.cpp at the beginning of class on Wednesday, May 2, 2001

In the case of differences between the soft copy electronically collected and the hard copy submitted
in class, the soft copy will be considered as the authoritative submitted copy.