Computer Science 3510
Spring 2001
Programming Assignment 2

First solution due: July 5
Second solution due: July 12

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 five files in all (a header file and implementation file for each of the two abstract data types, and an implementation file for the main part.) 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 MakePolynomial(int d, double* coef);

This function should return a polynomial of degree d, having coefficients given by array coef. The coefficient of x0 is stored in coef[0], the coefficient of x1 is stored in coef[1], etc.

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]. Notice that the coefficients are printed from high degree to low degree.

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.

This function is an exception to the persistent nature of this abstract data type. It is required for memory management.

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. If 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 for part 1

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 + 19x2 + 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 = P k ck ck-1 ... c0

Make variable name be a polynomial of degree k given by coefficients ck ck-1 ... c0. For example, 

    foo = P 2 7.1 6 -4.2
makes name foo refer to polynomial 7.1x2 + 6x - 4.2.

Notice that the letter is a capital P. If your program expects a lower case p, it is not correct, and will not work with my tester.

Just build this polynomial and store it in a hash table, with name as the key.

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.

Pay attention to memory management. Avoid memory leaks. Draw pictures.

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

    fred = P 0 2.0
    fred = [2]

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

    zz = P 1 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

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 MakePolynomial function. 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 =P, 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.

  8. Think about your user interaction module. Check for memory leaks. Check whether you have deleted anything prematurely.