CSE 326, Spring 1995: Homework 1

Due 4/4/97

1. (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?
2. (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.