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.

  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.