CSE 326, Spring 1995: Homework 1

Due 4/5/95

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) The Fibonacci numbers, F(0), F(1), ..., are defined recursively by the following rules: F(0) = 0, F(1) = 1, and for n larger than 1, F(n) = F(n-1) + F(n-2).
   • Calculate the first 10 Fibonacci numbers by hand.
   • Give a pseudocode function which on argument n returns F(n). This code should be iterative, and not recursive.
   • Give a recursive pseudocode function for computing F(n).
   • Which is more efficient, your iterative code or your recursive code and why?
3. (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.