pa04 : Linked-list

PA4 must be done individually. In other words, you are not allowed to use pair programming for this assignment. We do expect you to use some of your solutions from the past two assignments - even though you may have developed those solutions with a partner. But major parts of PA4 require completely new code, and we expect each student to write those parts of the code alone. This assignment weighs more than the others, so we recommend you start early and make as much progress as possible within the deadline.

Create a new git repo names pa04_your_github_username, and clone it to your cs24 directory on CSIL. You must push intermediate versions of your code to github after you complete EVERY function in this assignment.

Get the starter code by doing a git pull in the starter-code repo and then copying over to your git repo directory

Implement one more version of class polynomial, as a linked list of terms this time. Create a new file named poly2.cxx Type your name and the date in a comment at the top of poly2.cxx.

You must implement class polynomial as it is defined in this class header file: poly2.h

Read this step-by-step discussion by Michael Main, the project’s primary creator. It details the changes that must be made to a PA3 solution in order to satisfy the PA4 requirements.

We suggest you refer to both the textbook’s implementation of the bag class using a linked list (bag3) in section 5.3, as well as the authors’ discussion of the sequence project in section 5.4. One nugget from the latter about your class invariant is worth repeating here:

“You might even write the invariant in large letters on a sheet of paper and pin it in front of you as you work. Each of the member functions count on that invariant to be true when the function begins. And each function is responsible for ensuring that the invariant is true when the function finishes.”

Here’s a copy of a solid poly2 invariant, thanks again to Prof. Main (this invariant is also copied at the top of the partial solution):

 INVARIANT for the polynomial class:
   1. head_ptr and tail_ptr are the head and tail pointers for a
      doubly-linked list of nodes that contain the polynomial's terms in
      order from smallest to largest exponent. To simplify certain operations,
      we always keep a node for the zero-order term (x^0), but other nodes are
      kept only if the coefficient is non-zero.
   2. We always maintain recent_ptr as a pointer to some node in the
      list--preferably the most recently used node. If the list is null,
      then we set recent_ptr to null.
   3. The degree of the polynomial is stored in current_degree
      (using zero for the case of all zero coefficients).

One more thing: usually your program’s segmentation faults will be due to attempts to dereference a null pointer, or worse, a pointer into nowhere your program belongs. You can easily check whether or not a pointer is null before trying to dereference it, and you should routinely do just that. The other type is most often the result of using an uninitialized pointer, so make sure to initialize all of your pointers, either to null or to a trusted address. And oh by the way, the CS compilers (that submit.cs uses) will not automatically set your pointers to null like your compilers at home might do.

Compile and test your program at CSIL. Perform basic unit tests with the interactive test program, polytest2.cxx. You can compile it as follows:

g++ -o polytest2 polytest2.cxx poly2.cxx

We recommend writing your own Makefile (starting with the one from the previous assignment).

Then when you are satisfied that your implementation is able to pass basic tests, run all eleven of the tests from the non-interactive test program that will be used by submit.cs to score your work: polyexam2.cxx. Run it by giving a test number between 1 and 11 as a command line argument. For example, the following commands demonstrate compiling this non-interactive program, and then running test9 with it:

g++ -o polyexam2 polyexam2.cxx poly2.cxx
./polyexam2 9

Perform the tests in order, as subsequent tests depend on successful earlier tests.

Submit PA4 at https://submit.cs.ucsb.edu/, or use the following command from a CS terminal:

~submit/submit -p 724 poly2.cxx

Be sure to wait for the results of all eleven tests. If you score 100/100 and you’ve followed all of the other rules, then you’ll earn full credit.