Introduction

This is a two part assignment that should help you solidify the concepts you have learened in Chapters 2 to 3 of the book. To start, complete the following steps:

• Create a github repo following the correct naming convention.
• If you have a partner, add you partner as a collaborator to the repo. Partner should accept the invitations to complete this process
• Join two team on submit.cs, one for each part of this assignment: pa03-part1 and pa03-part2
• Clone your lab03 repo in your home directory on CSIL and change into it.
• Get the starter code for this lab by doing a git pull in your starter-code repo and copying the files from ~/cs24/starter-code/pa03/

Part 1: Implement the class polynomial with a fixed array

This is the first in a series of three related programming assignments, two of which you will complete as part of pa03. Each one requires you to implement a class that represents polynomials. The class is introduced in the textbook’s Programming Project 9 at the end of Chapter 3, and here are the key points from that introduction:

“This is a simple version of a longer project that will be developed in Chapter 4. The project starts with the definition of a one-variable polynomial, which is an arithmetic expression of the form:

a0 + a1x + a2x^2 + ... + akx^k

The highest exponent, k, is called the degree of the polynomial, and the constants a0, a1, … are the coefficients. For example, here are two polynomials with degree 3:

2.1 + 4.8x + 0.1x^2 + (-7)x^3
2.9 + 0.8x + 10.1x^2 + 1.7x^3

Specify, design, and implement a class for polynomials. The class [will] contain a static member constant, [MAX_EX], which indicates the maximum degree of any polynomial. (This allows you to store the coefficients in an array with a fixed size.)”

Later, you will be able to drop the maximum degree requirement, first by dynamically allocating the array’s memory (for part 2 of this assignment), and then by using a linked list to store the polynomial’s terms (for PA4). But for this part of the assignment assignment your implementation will use a fixed size array as in the sequence class implementation of pa02. We have done the specification and design already - your job is to implement and test it according to the following specific instructions.

• Implement class polynomial in a new file that you create named poly0.cxx inside your pa03 repo.
• Type your name(s) and the date in a comment at the top of poly0.cxx. [Last reminder?] Implement the constructor and all of the member functions (except the two that are done inline) of class polynomial - as they are defined in the class header file: poly0.h. Be sure to #include poly0.h in your implementation file.
• Carefully read the documentation at the top of poly0.h to know how each of these functions must operate. Use assert to verify preconditions.
• Also read this discussion by Michael Main, the project’s primary creator, as it clarifies several details.
• Develop and test in small pieces (and be sure your final tests are done at CSIL), using this interactive test program: polytest0.cxx. Compile it along with your implementation as follows or better still using your own Makefile:

g++ -o polytest0 polytest0.cxx poly0.cxx

Use this interactive test program to test your functions one at a time. When ready for more comprehensive tests, try the non-interactive test program we will use when you submit:

polyexam0.cxx - give a command line argument ranging from 1 to 8 when you run it.

Submit the part 1 of this PA at https://submit.cs.ucsb.edu/, or use the following command from a CS terminal:

~submit/submit -p 721 poly0.cxx

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

Part 2: Implement the class polynomial with a dynamic array

In this part of the assignment you will implement a new version of class polynomial, one without a capacity constraint.

• Your implementation must be in a new file that you create named poly1.cxx.

• Type your name(s) and the date in a comment at the top of poly1.cxx.

You must implement each of the member functions (including both constructors, the destructor and the assignment operator) of class polynomial - as they are defined in this class header file: poly1.h

Probably you will want to begin with your solution for the part 1 of this assignment, and in fact we recommend it. If you were unsuccessful implementing the first version of class polynomial, then we highly recommend going back and fixing your work on that implementation now, before attempting this upgrade.

As this conversion is very similar to the one you did for class Words in Lab03, you can refer back to that lab for general guidance.

We suggest you also refer to the textbook’s conversion of the bag class from using a fixed size array (bag1) to using a dynamic array (bag2), as that implementation contains many parts you are likely to find useful. And read the parts of Section 4.6 (pp. 212-215) that you skipped while working on PA2.

Here are the basic changes that need to be made to your PA2 version (mostly in the words of Michael Main):

• Change the namespace to main_savitch_4, and change the include statement to include poly1.h.
• Delete the CAPACITY and MAX_EX constants. But add a constant called DEFAULT_CAPACITY, to be used for the initial size of the dynamic array in the basic constructor.
• Look at the new private member variables in poly1.h:

  private:
    double *coef;      // Pointer to the dynamic array
    unsigned int size; // Current size of the dynamic array
    unsigned int current_degree;
  

• There is a new reserve member function. The purpose of this function is the same as the bag’s reserve function in Chapter 4 (making sure that the size of the dynamic array is at least equal to the specified number). However, be careful that you understand how your reserve function may need to differ from the bag’s reserve function. For example, the newly allocated array for the polynomial must always be at least the degree plus one. Also, in the case of the bag, the new part of the larger array did not need to be initialized because it was not being used (but depending on how your coefficient function is implemented, your polynomial might expect the unused part of the array to contain zeros).

• Modify the other polynomial member functions to use the dynamic array. These functions should always work correctly, even if the programmer now tries to set a term with an exponent that is beyond the current size of the dynamic array. Note: The only functions that need to be modified are those functions that access your member variables directly. In Professor Main’s implementation, this included the constructor, add_to_coef, assign_coef, clear, coefficient, and the precondition check in operator *. No more precondition checks for array capacity are necessary, but calls to reserve in any function that calculates and returns a polynomial might be necessary.

• Implement a copy constructor, an assignment operator and a destructor. Be careful that you do not just copy the bag’s implementations for these functions. You must understand enough about your polynomial class to see what features differ from the bag.

• Challenge optional exercise. You will be required to implement this function for PA04. In this assignment it is given as an optional exercise and doesn’t carry any points. However, we highly recommend that you implement it if you have the time. Add one new function, find_root to search for a root of the polynomial, given a starting guess. See its documentation in poly1.h, and use this findroot algorithm (Newton’s Method) to implement it. You should be able to write this function with no direct access to the member variables. Use the function fabs(b) to compute the absolute value of a number b. Compile and test your program at CSIL. Perform basic unit tests with the interactive test program, polytest1.cxx. You can compile it as follows:

g++ -o polytest1 polytest1.cxx poly1.cxx

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: polyexam1.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 polyexam1 polyexam1.cxx poly1.cxx
./polyexam1 9

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

~submit/submit -p 722 poly1.cxx

Be sure to wait for the results of all eleven tests. If you score 90/90 and you’ve followed all of the other rules, then you’ll earn full credit. Be sure to push the latest version of your code to github.

Acknowledgements: Thanks to Mike Costanzo and Michael Main for making this available for CS24