CMPS 101
Abstract Data Types
Fall 2003

Homework 2
(due at 11am on 10/20/03 in the class)
Write your name and student ID on all the pages of the written
assignment. Staple all the pages together.


* * * Abstract Data type * * *

1.	Do exercises: 2.1 , 2.2  (p95, p96)    (10 pts)

2.	Implement the different List ADT operations in C 
(makeEmptyList(..), cons(..), emptyList(..), first(..), rest(..),
changeFirst(..), changeRest(..)) (Fig 2.4, p76 provides the answer
as a Java Class, you have to rewrite the appropriate code for C and 
add the implementation of changeFirst(..) and changeRest(..) )  (20 pts)

3.	Read Example 2.1, p78 : insertion into a sorted list with
partial rebuilding

4.	 Rewrite the function insertl(..) using destructive 
operations   (appropriate for an implementation in C) (10pts )

5.	Use the List ADT operations to implement the following list
utilities, as a client of the ADT:
a. Count the number of elements in a list (list length)
b. Sum the elements in a list
d. Return the maximum element in a list
f. Return a new list consisting of the elements of the original
list in reverse order.
(20 pts)

Asymptotic Growth Rates
Do exercises: 1.27, 1.28, 1.31, 1.40		(40 pts)