CSE 373, Autumn 2002: Homework 1
Due 10/11/2002
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. Straight pseudocode with no additional documentation is not
enough. Your pseudocode can contain English if needed. Each
problem should be answered on a separate sheets of paper so they can be
graded by different TAs. Your name should be at the top of every
page.
-
(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) We would like to implement the abstract data type called "bag
of blobs". A bag has a maximum size Msize and supports insert, delete,
IsEmpty, IsFull, and perhaps other operations. Insert adds a new
blob to the bag and Delete removes a blob from the bag. Assume blob
is a record type. A bag of blobs can be implemented using an array
A[1..Msize] of blob pointers. If there are k blobs in the bag then
the entries A[1], ..., A[k] point to these blobs. The remaining entries
of the array point to null.
-
Describe algorithms to implement Insert( p : blob pointer) which adds the
blob pointed to by p to the bag that is not full and to implement Delete(p:
blob pointer) which removes the blob pointed to by p from the bag.
Each blob in the bag should have an integer field that indicates where
it is in the array A. Your description can be written in pseudo code with
drawing to show how the code works. Your functions should each run
in constant time.
-
Distinguish the ADT bag from the ADT list.
-
(10 points) Consider the linked list representation of unbounded integers
described in the lectures. Carefully design a recursive pseudocode
function that adds two integers. The recursive function should follow
the examples on slides 21-23 of the lecture titled "Lists". Your
addition function should have two arguments which are node pointers, and
return a node pointer.