#####
CSC 8310 Linguistics of Programming Languages

Dr. David Matuszek

Fall 1997, Villanova University

### Polynomial Manipulation

A polynomial in one unknown may be represented as a list of (coefficient, exponent) pairs. For example, the polynomial
`x`^{4} - 7x + 3
may be represented as
`((1 4) (-7 1) (3 0))`.
We will say that a polynomial is *normalized* if

- the terms are ordered from largest exponent to smallest,
- no two terms have the same exponents, and
- zero terms are omitted.

In terms of a list of pairs, this means
- the pairs are in order by decreasing
`cadr`s,
- no two pairs have the same
`cadr`, and
- no pair has a
`car` of zero.

Write and test the following Lisp functions. All functions (except `NORMALIZE` and `EVALUATE`) should take normalized polynomials as input and return a normalized polynomial as their result.
`( ADD_POLY` *poly1 poly2*`)`
- Add the two normalized polynomials and return the normalized result.

`( SUBTRACT_POLY` *poly1 poly2*`)`
- Subtract the second polynomial from the first and return the normalized result.

`( MULTIPLY_POLY` *poly1 poly2*`)`
- Multiply the two normalized polynomials and return the normalized result.

`( NORMALIZE` *poly*`)`
- Normalize the possibly unnormalized polynomial and return the result.

`( EVALUATE` *poly integer*`)`
- Evaluate the polynomial at the given point and return the (integer) result.

Turn in a listing of your functions, along with a listing showing your tests of these functions.

It is good form to write additional "helper" functions as needed. For example, `ADD_POLY` will probably be much simpler to write if you first write a function `( ADD_TERM ` *pair poly* `)`. As a second example, a good way to write
`NORMALIZE` might be

`
(DEFUN NORMALIZE (POLY)
(DELETE_ZERO_TERMS (COMBINE_ADJ_TERMS (SORT POLY))) )
`

Hints:
- Start with the easiest ones:
`ADD_TERM`, then `ADD_POLY`, then `SUBTRACT_POLY`.
- If you do
`NORMALIZE` as suggested above, notice that the order in which you call the helper functions is important.
`SORT` is not difficult if you write a helper function `(INSERT_TERM ` *pair poly*`)` to insert a pair into a normalized polynomial.
`MULTIPLY_POLY` is probably the hardest; you really need a good helper function or two.
- Use meaningful names for your functions and/or include descriptive comments, particularly for helper functions not explicitly required by this assignment.