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