CSCI 3510 Programming Assignment 2

First solution due: Fri, Nov 5, 5:00pm
Second solution due: Wed Nov 17 5:00pm
This assignment will take time to solve. Begin early. Ask questions early if you have them.

DO NOT WAIT TO GET STARTED.

This is an assignment in the use and creation of abstract data types. It involves two abstract data types and a program that uses them. It is required that there be separate files for each of the two abstract data types and a separate file for the application program. Do not violate the abstractions.

To implement this, prepare a refinement plan. That is, decide in what order you will implement different parts of the program. Then choose reasonable deadlines by which each part should be finished and tested. Be sure to leave extra room at the end for unforseen difficulties. Do not just type the whole program and then try to debug it.

Part 1.

A polynomial with real coefficients is an expression that can be constructed from real numbers and the special item x using only addition, subtraction and multiplication. For example, x^2 + 3x - 6 is a polynomial. (I will use ^ to indicate exponentation. So x^2 is x-squared.) Polynomials can be added, subtracted and multiplied.

Implement an abstract data type of polynomials called Polynomial. This will be a persistent ADT. That is, the functions will create new polynomials without destroying old ones. The interface should be as follows. It shows function prototypes in bold, followed by descriptions of what those functions are supposed to do.

Type: Polynomial.
You can assume that polynomials only need to be stored up to some maximum degree (say 30), but it must be very easy to change this maximum degree in your program.

Polynomial Constant(double c);
This function should return a constant polynomial c. For example, Constant(3.4) should return the polynomial 3.4. (This is the polynomial whose value is 3.4 regardless of the value of x. Its graph is a horizontal line.)

Polynomial Linear(double a, double b);
This function should return the polynomial ax + b.

Polynomial Sum(Polynomial p, Polynomial q);
This function should compute the sum of polynomials p and q, and return that sum. It should allocate memory to store the result polynomial.

Polynomial Product(Polynomial p, Polynomial q);
This function computes the product of polynomials p and q, and returns that product. It should allocate memory to store the result polynomial.

Polynomial Negative(Polynomial p);
This function should return the negation of polynomial p.

void Print(Polynomial p);
This function should print polynomial p on the standard output. To make things easy, print the polynomial just by showing its coefficients. Polynomial 3.4*x^2 + 5 should be printed as [3.4 0 5].

void DeletePolynomial(Polynomial p);
This function should delete the memory occupied by polynomial p.

Polynomial DuplicatePolynomial(Polynomial p);
This function should make a copy of polynomial p in new memory. This function must be designed so that doing 
  Polynomial q = DuplicatePolynomial(p);
  DeletePolynomial(p);
leaves polynomial q still viable; its memory has not been deleted.

Hints

A polynomial can be represented as a structure holding the degree of the polynomial and an array holding the coefficients of the polynomial. For example, polynomial 3.4*x^2 + 5 can be represented as follows. 
      degree: 2      coef:    5
                              0
                              3.4
You will find it convenient to put the coefficient of x^k at index k in the coefficient array. Start by writing the type definition for type Polynomial.

Now think about algorithms. Functions that compute new polymomials always allocate new space for the result. Addition is simple, since it is componentwise. That is, you just add corresponding coefficients. But be careful; multiplication is not componentwise. For example, (x^2 + 2x + 4)*(3x^2 - x + 9) = 3x^4 + 5x^3 + 13x^2 + 14x + 36.

Polynomial multiplication can be accomplished in a way that is quite similar to the way you learned to multiply integers in grade school. But with polynomials, there is no carry. Also, you don't need to store all of the intermediate results as you go. Just accumulate the coefficients in one answer array. Think carefully about how to do this before trying to code it.

Part 2

Modify the hash table implementation from assignment 1 so that the key is a string, but the value is a polynomial. Since your table that reallocates on need might not work, use the original table.cc that does not reallocate. This should be a very small modifiation, but pay attention to what you are doing nonetheless. You will need to change the definitions of HashValueType, and of macros deleteVal and dupVal.

Part 3

Write a program that performs polynomial operations for a user. The operations are as follows. Each is given along with its meaning.
name = C num
Make variable name be a constant polynomial given by the number num, and then print the polynomial.

name = L a b
Make variable name be a linear polynomial ax + b, and then print the polynomial.

name1 = + name2 name3
Make variable name1 be the sum of the polynomials that are in variables name2 and name3, and then print the polymomial.

name1 = * name2 name3
Make variable name1 be the product of the polynomials that are in variables name2 and name3, and then print the polymomial.

name1 = - name2
Make variable name1 be the negation of the polynomial that is in variable name2, and then print the polynomial.

name P
Print the value of variable name.

quit
Stop the program.
The values of variables should be stored in a hash table, and looked up when needed. The name of the variable is the key, and the value of the variable (a polynomial) is the associated value.

Here is an example session. Lines in black are typed by the user. Lines in red are typed by the program. 

    fred = C 2.0
    fred = [2]

    rod = L  -1.0 0.0
    rod = [-1 0]

    zz = L 2.5 4.1
    zz = [2.5 4.1]

    m = + rod fred
    m = [-1 2]

    sq = * rod rod
    sq = [1 0 0]

    t = + sq rod
    t = [1 -1 0]

    rod = + fred fred
    rod = [4]

    t P
    t = [1 -1 0]

    quit

Do not include much error checking in this program. Assume that the input is reasonable. I will only test it on input that makes sense.

Suggested refinement plan

Here is a suggested plan. If you adopt this plan, attach dates and times to each goal.

  1. Implement type Polynomial, and the Constant and Linear functions. Also implement the Print function. Test them, by calling them directly from a main program. Do not proceed to the next step until these functions work.

  2. Implement the Sum and Negative functions for Polynomial. Test them, again by calling them directly from a main program.

  3. Implement the DeletePolynomial and DuplicatePolynomial functions. Test them.

  4. Make the modification to the hash table implementation.

  5. Write the user interaction program, but only implement the C, L, p and quit operations. Test it.

  6. Add the + and - operations to the user interaction program. Test them.

  7. Write the Product functions for polynomials. Test it.

  8. Add the * operation to the user interaction program. Test it.