The classic way to evaluate a polynomial is Horner's Rule. Horner's rule
can be stated recursively as follows:
Let p(x) = a0 + a1*x + a2*x^2 + ... + ak*x^k be a polynomial. Note
that * means "times"and ^ means "to the power". To evaluate the polynomial
p(x) at c, first let y be the result of evaluating the polynomial
a1 + a2*x + a3*x^2 + ... + ak*x^(k-1) at c, then evaluate the final result
as a0 + c*y.
- Briefly argue that that process described above correctly evaluates
the polynomial p(x) at c.
- Design recursive pseudocode function
which more precisely defines Horner's Rule.
Assume that the coefficients of the polynomial is stored in a linked
list with a0 stored at the head of the list.
Hint: your function should have arguments p and c
where p is a pointer to a list of coefficients
and c is the value that the polynomial is evaluated at.
- Design an iterative algorithm and its pseudocode for Horner's Rule.
Your iterative algorithm should be a simple for loop. In this
case assume that the polynomial is stored in an array, not a linked
list. The array value A = a0, A = a1, and so on.
- What difficulty, if any, is there in implementing Horner's Rule
iteratively when the coefficients are stored in a linked list?