Programming Project I

Overview

Recall that in problem 1 of homework 2, we requested that you write algorithms to perform polynomial addition and multiplication. The polynomials were stored as linked lists in which each entry was a (coefficient, exponent) pair and the lists were kept in sorted order by exponent. If the polyomials were of length m and n, then the worst-case time of addition and multiplication were to be O(m + n) and O(mn log(mn)) respectively. In this assignment, you will implement those algorithms.

Guidelines:You should write your programs individually, but you can consult with other students on all aspects of the work. A good rule of thumb is that I should not be able to hold two programs side by side and easily identify areas that were written jointly. You can use any language and computing platform that you like. As described in more detail below, you will hand in a printed copy of your program and sample output on specific test cases given below. Also see the programming project web page for grading guidelines.

Specific Instructions and Advice

In order to receive full credit, your program must have the following features:

• It must store polynomials in sorted linked lists.
• It must be capable of reading input polynomials from the user.
• It must be capable of printing the results of adding and multiplying the input polynomials. The output should have only one term per exponent and have the exponents in sorted order.

Here is a breakdown into small steps which might be helpful, although you are not required to follow it.

1. You might find it useful to begin by implementing a linked list ADT (assuming you're not using a language like LISP).
2. Write a routine to read in polynomials from the user. The input mechanism and format is up to you. It is easiest to assume that the terms are given in sorted order by exponent.
3. Write a routine to print polynomials. Writing it before any of the algorithms will make debugging that much easier. Get input and output working before going on.
4. The algorithm for polynomial addition is basically like the merge step in merge sort with a special addition which gathers terms with the same exponent into one list node. I recommend writing this merge() function first and then writing addition in terms of it. The merge function will also be useful for multiplication.
5. Get addition working before trying to implement multiplication!
6. Implement multiplication. It is easiest to generate all the terms first, without worrying about duplicates or exponent order.
7. Once all of the terms are generated correctly, use your merge function from the addition algorithm to implement mergesort. This will put the product into proper order and gather duplicate entries.

Submission Procedure

1. You must print out, staple, and hand in a copy of your code.
2. You must print out the results of running your program on the following test cases. Print out both the product and the sum for each pair of polynomials.

         (a)  x + x^3 + x^5 + x^7,
              x^2 + x^4 + x^6 + x^8
   
         (b)  x + x^2 + x^4 + x^6,
              2*x + x^2
   
         (c)  x + x^3 + x^7 + x^9,
              x + x^2 + x^3 + 2*x^10000