Computer Science 3510
Spring 2001
Programming Assignment 2

First solution due: Tues, Oct. 1.
Second solution due: Thurs, Oct. 10

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, x² + 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, (x² + 3)(x - 4) = (x³ - 4x² + 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. For example, polynomial 4x² + 3 has degree 2 and an array of coefficients given by

coefficients[0] = 3

coefficients[1] = 0

coefficients[2] = 4

(Notice that 4x² + 3 is the same as 4x² + 0x + 3.)

Polynomial MakePolynomial(int d, const double* coef);

This function should return a polynomial of degree d, having coefficients given by array coef. The coefficient of x⁰ is stored in coef[0], the coefficient of x¹ is stored in coef[1], etc. Although this function cannot change the array coef, it cannot assume that some other function will not change that array. It will need to make a copy of the coefficient 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 allocate memory to store the result polynomial. 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*x² + 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*x² + 8x + 5 can be represented as follows.

      degree: 2      coef:    5
                              8
                              3.4

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, (x² + 2x + 4)*(3x² - x + 9) = 3x⁴ + 5x³ + 19x² + 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

name = P k c_k c_k-1 ... c₀

Make variable name be a polynomial of degree k given by coefficients c_k c_k-1 ... c₀. For example,

    foo = P 2 7.1 6 -4.2

makes name foo refer to polynomial 7.1x² + 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. But create a plan before starting to write this program. After devising your plan, put in deadlines that you think you can meet. Then meet the deadlines. Leave yourself room for difficulties.

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. For example, put some values into an array of coefficients, make a polynomial from the array, and print the polynomial. 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. For example, use makePolynomial to build two polynomials. The use Sum to compute the sum. Print the result. Be sure to test Sum two add two polynomials whose degrees are not the same.

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. Try inserting a few things into the table. Then look them up and print the polynomials that you get. Did it work?

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. Proofread your user interaction module. Check for memory leaks. Have you created something and not destroyed it when you were done with it? Also check whether you have deleted anything prematurely.

Testing

A tester is available. You can run it on the Unix machines in the lab. Get files

• polydata.txt
• pnomial.out
• pnomial.ast

  a.out <polydata.txt

I have provided a program that you can use to try some other sample data file. It is not written in C++. You can try it on sample file data.txt (which I presume you provide, or which might be a modification of polydata.txt) as follows.

  astr -m -i data.txt pnomial