**CS246 [Winter 2012] Assignment 5**

**V0.2**

You are to re-implement the poly class (from Assignment 4).
The new implementation will replace vectors with linked lists. This
will also include adding a new constructor (a *copy constructor*) as well as a destructor and implementing an
overload of assignment =. Your program should, at least in principle,
behave just like your program from Assignment 4. However, your new
implementation of the poly class will be much more efficient in the case that
polynomials with high degree have many zero coefficients..

**Goals of assignment. **This assignment
illustrates and gives examples of a number of concepts. It illustrates
abstraction --- the poly class represents a high level concept (polynomials) which
can be implemented many different ways. It illustrates use of copy
constructors and destructors as well as overloading assignment =. It
illustrates how a driver (polyrun.cpp) can be largely independent of how its
target programs are implemented. It gives practice in using C and C++
pointers with dynamic allocation and how they can replace higher level
mechanisms such as C++ vectors.

**Replace the implementation of your poly class. **You
will develop a new implementation of the same data abstraction (polynomials)
but with vectors replaced by linked lists. You are to write your own
linked lists (do not use the C++ STL container). You are to use a modified
version of your existing header file poly.h to include the prototype for the
copy constructor and the destructor as well as overloaded assignment =, now
naming the file poly2.h. You will also need to modify it to replace
the old data structure (vector of terms) with the new data structure (the
linked list as described below). You will program a new implementation
file poly2.cpp which will replace the old implementation poly.cpp. The
new executable version of the polynomial calculator should be called
polyrun2. The old is simply polyrun.

Ideally, you will only change two files: poly.h and poly.cpp (renaming these to poly2.h and poly2.cpp as well as changing any #include files that reference them to use the new spelling of these file names). Each file other than poly.h and poly.cpp that you modify should include documentation explaining how you changed the file. This should be done as in comments in the file, beginning as follows:

// How this file was modified.

… more comment lines here …

Use the same *main* function (perhaps minimally
changed) and the same the same *help* function (in help.h and
help.cpp) from the last assignment.

**Use linked lists **In your implementation of the
poly2 class, you are to use linked lists instead of C++ “vectors”. At
runtime, generally when a term is added to a polynomial, a node is allocated to
store the coefficient with its exponent and it is linked to the list of nodes,
all representing the polynomial. Each node in the linked list will
consist of (1) a coefficient with its exponent and (2) a link (a pointer
to a node). Any terms with zero (0.0) for coefficient should NOT be
stored in a node. For each polynomial, you are to use a singly linked
list. So, the implementation will generally need to use new and
delete statements to create and destroy space for nodes. Each **polynomial**
object will contain a pointer named **first** which locates the its first
(if any) node. In the case of a null polynomial, the **first** pointer will
be NULL, with no allocation of space for terms. Your implementation
should make sure that no space is lost (no memory leakage) and that all
pointers are followed only when they actually locate legitimate data.

**Ordering and performance. **Your linked lists
should be ordered according to exponent values, e.g., 3.7e^4 would come before
1.67e^7 because 4 comes before 7. Your operations + and - should be
efficient in the following sense. An operation, such as polynomial
subtraction -, combining polynomial P1 having L1 non-zero terms with polynomial
P2 having L2 non-zero terms, should use at most (or about) L1 + L2 machine
level (double) subtractions. Put technically, these operations should run
in time O(L1 + L2), i.e., order of L1 + L2.

**Copy constructor and destructor. **For your new
implementation of the class to work correctly, you need to implement a “copy
constructor” as well as a destructor and overloaded assignment =.
Note that the copy constructor is implicitly invoked for value parameter
passing of objects. Hint: The Savitch text book gives a detailed example using
copy constructors. It also gives examples of overloading operators.

**Keep it short. ** As a rule, in this
assignment, shorter, more elegant solutions to this assignment are
preferable to more complex solutions. But you are still expected to meet
the performance requirements given above.

**Coverage
testing. **You
are to write a “driver” named **drive**, written as drive.cpp which is a C++
program that uses poly2.cpp to try out operations on polynomials (implemented
as poly2.cpp). Ideally, your driver should cause all lines of code in
poly2.cpp to be executed (though it is not necessary to exercise lines that
deal with errors). Your driver should have the following form:

// File drive.cpp --- Exercise poly2.cpp

#include "poly2.h"

#include <iostream>

using namespace std;

int main (){

// Lots of comments explaining what is being tested

poly F; // An example – declaring a polynomial

poly U(F); // Using copy constructor

F.setCoefficient(1, 1.01); // … another comment …

// … more here …

}

**Stress
testing.**
Carry out a stress test to compare the efficiency of poly.cpp (or
polyrun-solution) with poly2.cpp. Try running polyrun (from previous
assignment) and polyrun2 (from this assignment), setting various values of
exponents. Use the 'time' command to determine the time taken to execute
the polyrun and polyrun2 commands. For example, here is a session using
polyrun, with an exponent of a billion:

$ time ./polyrun

Polyrun Calculator. Type '?' for help.

Command: s

Set coefficient. Give A n c: x 1000000000 1.1

Command: q

Quitting

real 0m38.816s

user 0m0.690s

sys 0m0.360s

Do this for exponents of a million, 10 million, 100 million and a billion, for each of polyrun and polyrun2. Plot the results as follows: x-axis for exponent, y-axis for 'user' time (produced by ‘time’ command). For the x-axis, use a log scale so there is a fixed distance between a million and 10 million, between 10 million and 100 million, and so on. Also use a log scale for the y-axis. If you like, you can use a spreadsheet to plot the graph.

**Makefile. **You should use the provided makefile to produce *polyrun2*. You should use the provided alternate makefile named makedrive to
produce *drive*, by typing:

make -f makedrive

**Master solution. **For a master solution, you can use polyrun-solution from the previous
assignment. While it will give the
expected answers, it will not in general give the expected performance (speed).
You can run this under a UW student account to see if your solution gives the
same answers. Your output (except when there are user errors) from your
program should be the same, character for character, as the master
solution.

**Provided files. **Files provided for this assignment can be found on the student Linux
system in the directory:

~holt/cp-for-students/cs/246/2012/asgn05

**Files to submit for
marking.**

poly2.cpp New implementation for poly

poly2.h New interface for poly

polyrun.cpp Calculator

drive.cpp Driver

stress.pdf Graph from stress testing