- (20 points)
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[0] = a0, A[1] = 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?

- (10 points)
Consider sequences of numbers represented using linked lists. A
sequence a0,a1,a2,...,an is represented as a list of length n+1.
Nodes in the link list have a data field and next field. A useful
operation in divide and conquer algorithms is the operation
of splitting the list into
two equal, or almost equal, size lists.
- Design a recursive pseudocode function which splits a list into two lists, the first containing a0,a2,a4,... and the second containing a1,a3,a5,...
- Design an iterative algorithm to do the same thing.