COP 3530 Section 1			EXAM 1			February 10, 1999

Kraynek							Name:_______________

10 points
1. Consider the following Java declarations where List is an interface and LinkedList is a   
    class that implements List:

	Object O;
	String S = new String("S");
	List aList;
	LinkedList LL = new LinkedList();

In the following segment, which of the following statements will not compile and which will cause a runtime error.

	O = S;
	S = O;
	S = (String)O;
	O = new Integer(37);
	S = (String)O;
	aList = new List();
	aList = LL;

10 points
2. What is computed in the variable sum (as a function of n) in the following segments?

a.  int sum = 0;
	     for(int i = 1; i <= n; i++)
	          for(int j = 1; j <= n; j++)
		    sum++;

	b.  int sum = 0;
	     for(int i = 1; i <= n; i++)
	          for(int j = i+1; j <= n; j++)
		   sum++;

	
10 points
3. Which function grows faster, n*log(n)**2 or (n**2)*log(n) ?



10 points
4. What is the running time of the following method?

public static int numZeros(int[] A, int left, int right) {
     if( left > right) return 0;
     int middle = (left+right)/2;
     return numZeros(A,left,middle-1) + numZeros(A,middle+1,right) + (A[middle]==0?1:0);
}

35 points
5. Recall the interface for Stack
 
public interface Stack {
    public boolean isEmpty();
    public void makeEmpty();
    public void push(Object x);
    public void pop() throws MyException;
    public Object topAndpop() throws MyException;
    Object top() throws MyException;
}

Using 

class ListNode {
    ListNode(Object element, ListNode next) {
            this.element = element;
            this.next = next;
    }
    Object element;
    ListNode next;
} 

write the class LinkedStack that implements Stack using a linked list.

25 points
6. Recall the interfaces List and ListIterator:

public interface List {
    public boolean isEmpty(); 
    public void makeEmpty(); 
    public void addElement(Object x); 
    public void removeElement(Object x);  
    public boolean contains(Object x); 
    public int size();
    public ListIterator iterator();
} // end List

public interface ListIterator {
    public void insert(Object x);
    public void first();
    public void find(Object x);
    public void end();
    public boolean isInList();
    public void next() throws MyException;
    public void previous() throws MyException;
    public void kth(int k);
    public Object elementAt();
    public void remove();
}

Write a method 

      void getNumbers(List Nums, int[] A);

that puts the ints from the array A into the List Nums in sorted order. Hint: Get a ListIterator for the List Nums.