Project 3

Due: Thursday, October 29, 2015 9:00PM


  1. Practice using C++ class syntax
  2. Practice using C++ dynamic memory
  3. Practice using linked lists


For this project, you will implement member functions of a C++ Polynomial class that stores univariate polynomials in linked lists. You will also complete the implementation of the Node class which describes linked list node. You will use C++ dynamic memory (new and delete) to allocate and destory nodes in the linked lists.

Polynomials are of fundamental importance in mathemtics as even very complex functions can often be approximated by polynomials. In addition, multi-precision numbers can be represented by polynomials. For example, the 192-bit number


is represented by the quadratic polynomial

  5833416998877842037 x^2 + 4432272967969985261 x + 10368951529917665809

with x equal to 264. Each coefficient of the polynomial requires at most 64 bits of storage, so this representation allows us to store and manipulate very large numbers on a computer with a 64-bit word size. This is especially useful for public key cryptographic algorithms which typically require arithmetic computations with large integers.

In addition to storing polynomials in linked lists, you will implement functions to add, subtract, and mutiply polynomials; to determine the degree of a polynomial; and to evaluate a polynomial for a given value of x. Lastly, you will overload the insertion operator (<<) to display a polynomial and the assignment operator (=) to make a deep copy of a Polynomial object.


Your assignment is to implement the member functions of the classes Polynomial and Node, defined below. A Polynomial object has a single variable, m_head, which is a pointer to the first node in the linked list. Your linked list implementation must be space-efficient, only storing what is necessary to represent the polynomial. The first node of a linked list must be a "dummy" node; the code will be cleaner and easier to write if you can assume that there is always at least one node in the linked list.

You must implement polynomial addition and subtraction (the add() and subtract() functions) efficiently, making a single pass through the linked lists of the two operands. Implementation of the remaining functions is fairly straight-forward.

#ifndef POLYNOMIAL_H #define POLYNOMIAL_H #include <iostream> #include "Node.h" using namespace std; class Polynomial { public: // Do not change the member function prototypes for // any public member function. // See documentation in Project 3 description. Polynomial(); Polynomial(const Polynomial& p); ~Polynomial(); void insertMonomial(long coeff, unsigned int deg); Polynomial add(const Polynomial& p) const; Polynomial subtract(const Polynomial& p) const; Polynomial multiply(const Polynomial& p) const; Polynomial modulo(const Polynomial& p) const; // Extra Credit unsigned int degree() const; long evaluate(long x) const; Polynomial& operator=(const Polynomial& p); friend ostream& operator<<(ostream& sout, const Polynomial& p); private: // Do not change the declaration of m_head Node *m_head; // Declarations for Additional private member functions // may be added below. Fully document these. }; #endif

Here are the requirements for the Polynomial member functions:

#ifndef NODE_H #define NODE_H using namespace std; // Do not change any part of this file // See documentation in Project 3 description. class Node { public: Node(); Node(long coeff, unsigned int deg); long m_coefficient; unsigned int m_degree; Node *m_next; }; #endif

The Node class has two constructors, but no other functions. The variable m_coefficient stores the coefficient of a monomial and m_degree stores the degree (power of x) of a monomial; m_next is a pointer to the next node in the linked list.

Here are the requirements for the Node member functions:

Implementation Issues

Here are some issues to consider and pitfalls to avoid. (You should read these before coding!)

Submitting your program

You should submit these files to the proj3 subdirectory:

If you followed the directions for setting up the shared directories, then you can copy your code to the submission directory with:

cp Polynomial.h Polynomial.cpp Node.cpp mytest.cpp ~/cs202proj/proj3/

You can check that your program compiles and runs in the proj3 directory, but please clean up any .o and executable files. Again, do not develop your code in this directory; you need to keep the main copy of your program elsewhere.