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.

  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).
  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.