Representative Problems for CSE 214 -- Midterm 1 
	------------------------------------------------

The first midterm exam will consist of about 4 questions of the following
difficulty.   I like questions which involve writing a procedure or answering
short answer questions.  Any topic we discussed in class is fair game.
Particularly important topics include:

	program design and Modula-3
	stacks and queues
	pointers
	parameter passing
	linked lists
	recursion
	
It should help to study the lecture notes on the WWW, however my questions
stress applying the concepts we have learned more than memorization.

Good luck,
Steven Skiena

=========================================================================


1. Suppose we augment the stack abstract data type with the operation INVERT,
which reverses the order of the top elements of the stack.
In other words, the element that was on top becomes the bottom element,
the element second from the top ends up second from the bottom, etc.

(a) Write a Modula-3 routine that efficiently implements the INVERT operation
using the array implementation of a stack.  The definition of the stack is
given below:

                 type
                      stack : array[1..STACKMAX] of integer;
                 var
                      top : integer;

(b) Repeat the previous part using a pointer (linked list) implementation
for the stack.       

                 type stackelem = record
                        data : integer;
                        next : ^stackelem;
                      end;
                 var
                      top : ^stackelem;


2. Write a procedure to delete the first node with the largest data value
from a linked list.
You must include your type declarations.
Also, give the complexity of your algorithm, where $n$ is the length of
the list.


3. Write brief essays answering the following questions.
Your answer must fit completely in the space allowed.

(a)  What happens when a Pascal program executes a  dispose(p) operation?

(b)  Why is the big Oh notation useful in analyzing algorithms?

(c)  Describe three advantages of using modules.

(d) A program to store name and grade information for all the members of a
class, with the scores accessible by name.
The class size will not exceed 1000 students.
Choose the best data structure for
solving the problem from among the structures discussed in class.

(e) Choose the data structure from above and list at least five procedures
or functions that would define the associated abstract data type.