Computer Science 3510
Spring 2001
Programming Assignment 2

First solution due: Fri, Feb 16
Second solution due: Mon, Mar 6

This assignment will take time to solve. Begin early. Ask questions early if you have them.

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. So there should be three files in all. 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, x2 + 3x - 6 is a polynomial. (Since exponentiation to a fixed positive integer power is just an abbreviation of doing multiplications, we are really just using addition, subtraction and multiplication.)

Polynomials can be added, subtracted and multiplied. For example, (x2 + 3)(x - 4) = (x3 - 4x2 + 3x - 12).

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. A polynomial should be stored as an array of its coefficients, along with its degree.

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. It has degree 0 and only one coefficient, the constant term.)

Polynomial Linear(double a, double b);
This function should return the polynomial ax + b. (This is degree 1 polynomial, with two coefficients in its array.)

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. It should not alter either p or q.

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. It should not alter either p or q.

Polynomial Negative(Polynomial p);
This function should return the negation of polynomial p. (Just negate all of the coefficients, but keep the degree the same.) It should not alter 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*x2 + 5 should be printed as [3.4 0 5].

void DeletePolynomial(Polynomial p);
This function should delete the memory occupied by polynomial p. Be careful with this one. Be sure ONLY to delete memory that was given to you by the new operator.

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.

Be careful with this one as well. DRAW PICTURES. When you are using call-by-value, remember that the value being passed is copied automatically. DRAW PICTURES to see what is happening, and what needs to be copied explicitly.

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*x2 + 5 can be represented as follows. 
      degree: 2      coef:    5
                              0
                              3.4
You will find it convenient to put the coefficient of xk 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 that the coefficients you add are meaningful. Try adding polynomials whose degrees are not the same.

Be careful with multiplication; it is not componentwise. For example, (x2 + 2x + 4)*(3x2 - x + 9) = 3x4 + 5x3 + 13x2 + 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, so it is simpler. Also, you don't need to store all of the intermediate results before computing the answer, the way you learned to multiply integers in grade school. Just accumulate the coefficients in one answer array. Think carefully about how to do this before trying to code it. You will need two nested loops. When multiplying polynomial a and b, yielding polynomial c, term a[i]*b[j] is added into c[i+j]. Make that clear in your program. Try not to use a strange and convoluted method here.

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 implementation from assignment 1 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. (This module is where the main program should be written.) 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. Notice that the letter is a capital C. If your program expects a lower case c, it will not work with my tester. Just build this polynomial and store it in a hash table, with name as the key.

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

name1 = + name2 name3
Make variable name1 be the sum of the polynomials that are in variables name2 and name3, and then print the polymomial. (Just look up name2 and name3 in the hash table to get the polynomials to add. If either one is not there, print an error message and continue to the next line.)

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]

    s = - t
    s = [-1 1 0]

    quit

Note the case of letters. A lower case c is not the same as an upper case C.

Do not include much error checking in this program. Assume that the input is reasonable, in terms of syntax. For example, if you see that the * operator is being used, assume that it is followed by two names. But do not assume that the names have been defined. Report use of undefined names.

Suggested refinement plan

Here is a suggested plan. Your plan might differ from this. After devising your plan, put in deadlines that you think you can meet.

  1. Implement type Polynomial, and the Constant and Linear functions. Also implement the Print function for polynomials. Test them, by calling them directly from a test 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. You will not be able to tell that DeletePolynomial actually deletes just by testing it, but at least try copying a polynomial, deleting the original, and then printing the copy. These functions require extra thought because they are difficult to test thoroughly. DRAW PICTURES.

  4. Make the modification to the hash table implementation. This should be very short.

  5. Write the user interaction program, but only implement the C, L, P and quit operations. Test it. Be sure that the user interaction module only uses the advertised features of the polynomial module.

    (Note: you can save yourself some effort by writing some commands for the program in a file, and just redirecting the standard input to that file. This makes running tests much easier than if you have to type in the instructions yourself at every test. For example, if your program is called poly, and your input file is called sample, write 

         poly <sample
    to run a test.)

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

  7. Write the Product functions for polynomials, and add it to the user interaction program to make testing simple. Test it.