CSCI 2322 Homework 3

Polynomial Arithmetic Procedure Definitions

This assignment is an extension of the polynomial procedures developed in Chapter 5 of our text. Using the polynomial procedures already defined in the book (see above link for a file with the definitions), define three procedures:  p-quo, p-rem, and poly-print. p-quo takes two polynomials and returns the quotient of those polynomials. p-rem takes two polynomials and returns the remainder from the division of those polynomials. poly-print takes a polynomial and prints it out in a more readable format.

Examples:
(p-quo '((3 1) (2 1) (1 1) (0 1)) '((1 1)))  -->  ((2 1) (0 1))
(p-rem '((2 1) (0 -2)) '((1 1) (0 2)))  -->  ((0 2))
(poly-print the-zero-poly)  -->  [nothing prints out]
(poly-print '((3 2) (1 4) (0 5)))  -->  2*x^3 + 4*x + 5
Note that poly-print should not print exponents when the exponent is 0 or 1.

The algorithm for division of polynomials is as follows:
(the dividend is the first polynomial in the procedure call, and the divisor is the second polynomial in the procedure call)
  1. Divide the leading term of the dividend by the leading term of the divisor (this is the first term of the quotient)
  2. Multiply above result by the divisor
  3. Subtract above result from the dividend
  4. Divide above result by divisor and continue recursively
  5. If the degree of the divisor is greater than the degree of the dividend, stop and return dividend as the remainder
  6. If the dividend becomes zero, the quotient and remainder are both zero
Example:
(x^2 - 4) / (x - 2)
  1. x^2 / x = x
  2. x * (x - 2) = x^2 - 2x
  3. x^2 - 4 - (x^2 - 2x) = 2x - 4
  4. (2x - 4) / (x - 2) = 2
done:  answer is (x + 2) and there is no remainder

Define a helper procedure t/ that takes two terms (monomials) and returns a term that is the result of dividing the first term by the second.  Use t/ in your definitions for p-quo and p-rem.  Use let in each of your definitions where appropriate to improve readability of your code.  Run each procedure (p-quo, p-rem, and poly-print) twice on different non-trivial arguments to demonstrate they work.

Save copies of your procedure definitions and sample output and email them to me as separate text attachments.

Your homework is due at the beginning of class on Oct. 20.  Warning: I do not check my office email on the weekends. If you need help with the assignment, come see me during office hours.