CSE 326, Winter 1999: Homework 1

Due 1/15/99

For all program or data structure design problems such as the two below you must provide pseudocode (see the manual)and an adequate explanation of the methods. It is often helpful to include small examples demonstrating the methods. Staight pseudocode with no additional documentation is not enough.

(10 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 r 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*r.
- 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. Your function should have two arguments one for the number c and the other for the polynomial. The return value should be a number.
- Design an iterative algorithm (no recursion) 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.
(10 points) In this problem you will design a program to find the maximum and minimum in a list of N elements using about 3N/2 comparisons. The obvious way to find the maximum and minimum of a list is to first find the maximum (using the elegant recursive algorithm given in class), then to find the minimum by a variant of the same method. This takes about 2N comparisons. Here is the approach for reducing the number of comparisons to 3N/2. Suppose our list contains c1, c2, ... , cN. For each I between 1 and N/2 compare c(2I-1) and c2I. The larger goes on one list and the smaller on another list. If N is odd then cN goes on both lists. This process takes N/2 comparisons. Now, the maximum can be found on the list of larger elements and the minimum can be found on the list of smaller elements. Each of those lists has size N/2 if N is even and N/2 + 1 if N is odd.
- Consider the following recursive list max program:
```
max(x: node pointer) : integer
m: local integer;
if x = null then return(-infinity)
  else  { m := max(x.next);
      if m > x.data then return(m) 
          else return(x.data) }
```
  Modify it to be a recursive list min program:
- Design an elegant list max-min program that takes an list as input and returns an array M[0..1] with M[0] having the minimum and M[1] having the maximum in the list. Your program should do approximately 3N/2 comparisons on a list of size N. You may define and program helper functions as needed. Your program should call max and min, but only on lists of size approximately N/2. It is helpful to define a duo node to hold the two lists. Your program can destroy the original list.