CSC 344
Homework 2

Assigned 14 Mar, due 4 Apr, to be done singly or in pairs.

Polynomials

1. Design a data type, in your favorite programming language, to represent a polynomial as a list of its coefficients. (You may assume the coefficients are real; we don't need to deal with complex numbers yet....) If you choose to store the coefficients in an array, you may assume that the polynomial has degree no higher than 7, i.e. it has only 8 coefficients. On the other hand, you may find it more convenient to store the coefficients as an arbitrary-length list (especially if you're writing in Scheme). Illustrate your data type by constructing several specific polynomials.

2. Write a program which takes in the coefficients of a polynomial and a value of x, and computes the value of the polynomial at x by Horner's method.

3. Write and analyze (i.e. tell me its run-time in big-O notation) a function (or method or whatever) which takes in two polynomials, as above, and computes their sum, another polynomial.

   Same thing, computing the product. If your polynomial data type is limited to degree 7, you may assume that each of the inputs is at most degree 3.

   Extra credit: Same thing, computing the quotient and the remainder. You may assume that the polynomial you're dividing by has at least one nonzero coefficient.

Gaussian elimination and accuracy

Consider the system of linear equations

   0.5x + 22.0y = 3.0
1000.0x -  5.0y = 4.0

Typically, floating-point numbers are represented with a fixed relative accuracy, such as 2^-23. For the purposes of this exercise, we'll assume that all six numbers in the example are represented to a relative accuracy of 1 in 1000, i.e. ± 0.1%, so the system is really

   (0.5 ± 0.1%)x + (22 ± 0.1%)y = 3.0 ± 0.1%
(1000.0 ± 0.1%)x + (-5 ± 0.1%)y = 4.0 ± 0.1%

or equivalently, written using absolute accuracy,

(0.5 ± 0.0005)x + (22 ± 0.022)y = 3.0 ± 0.003
(1000.0 ± 1.0)x + (-5 ± 0.005)y = 4.0 ± 0.004

Solve the above system, computing at each stage the bounds on the possible error in the results. (You may want to write a small program to help with this -- it took me 20-30 lines of Scheme -- or you can do it by hand.) For example, if the first thing you did were to compute the ratio of the entries in the first column, it would be

(1000 ± 0.1%) / (0.5 ± 0.1%) = 2000 ± 0.2% = 2000 ± 4

Multiplying this by the first row would give you

(1000 ± 0.3%)x + (44000 ± 0.3%) = 6000 ± 0.3%

or equivalently

(1000 ± 3)x + (44000 ± 132) = 6000 ± 18

So far everything has been multiplication, so we've been adding relative errors. The next step is to subtract the above equation from the second row, so we'll add absolute errors instead:

(0 ± 4)x + (-43995 ± 132.005)y = -5994 ± 18.004

Finish solving for x and y in this manner. What are the absolute and relative accuracies of the resulting x and y?

Then do the same again with pivoting, i.e. before you decide what to multiply by one row to subtract from another, shuffle rows so that the number with the largest absolute value is on the diagonal. You should get the same answers, but with different degrees of accuracy.

Another approach to polynomials

The "list of coefficients" representation given above is not the only reasonable way to represent a degree-n polynomial. Another way is a list of n+1 points on the curve, e.g. the polynomial

x2 - 3x + 7

could also be represented by the three points (1,6), (2,9), (3,16), or by the three points (-3,34), (0,7), (2,9), or many other sequences of points.
Note: for reasons discussed below, you may want to store more than n+1 points for a degree-n polynomial. Allow for this possibility in your data structure.

Write and analyze an algorithm (in pseudocode, or a real language if you prefer) which takes in two polynomials in this form and computes their sum, another polynomial in this form. You may assume that the x-coordinates are the same for both polynomials.

Same thing, computing the product.
Note: The product of two degree-n polynomials is a degree-2n polynomial, which means you'll need not n+1 but rather 2n+1 points to determine it uniquely. I recommend assuming that each of the input polynomials is represented with at least 2n+1 points; this will make the algorithm much easier.

Write and analyze an algorithm (in pseudocode, or a real language if you prefer) which takes in a polynomial in coefficients form and converts it to a polynomial in points form (say, with x-coordinates 0, 1, 2, ....)

Write and analyze an algorithm (in pseudocode, or a real language if you prefer) which takes in a polynomial in points form and converts it to a polynomial in coefficients form.