Description
Problem 1[30 + 30 + 40 pts] To give you an input a polynomial it will be represented as a sequence of numbers, each
time an exponent followed by a coefficient as a list. The exponents will be in decreasing order. So for example,
3 5 1 10 0 5
represents the polynomial 5x
3+10x+5. While the exponents are always integers, the coefficients may be rational numbers.
Now, write programs to do the following:
(1) Prompt the user for a polynomial input. Once that is entered, prompt the user for the input of some number a. Now
compute the quotient and remainder obtained when the input polynomial P(x) is divided by x−a. For example, suppose
the user enters the polynomial 3x
4 + 7x
2 − x + 3 and enters a = 1, the result should be,
Quotient : 3x
3 + 3x
2 + 10x + 9, Remainder : 12.
Make sure this runs in O(n) time where n is the degree of the polynomial.
(2) Write code to compute (x − a1)(x − a2). . .(x − an) for n given numbers, in O(n
2
) time.
(3) Now write code to do interpolation in O(n
2
) time. The problem input be a set of pairs of (x, y) values like
3 4 7 2 4 10
where the list is the x value followed by the y value. Here, the output will be a polynomial of degree 2. It is computed as
follows. Suppose the inout is (x1, a1),(x2, a2), . . . ,(xn, an). Then the interpolated polynomial is given by Pn
i=1 aiPi(x),
where the polynomial Pi(x) is defined as,
Q
j6=i
(x − xj )
Q
j6=i
(xi − xj )
.
Notice that Pi(xi) = 1 and Pi(xj ) = 0 for j 6= i.
1