COP 3530			Spring 1999 FINAL EXAM 			April 21, 1999

Kraynek									Name:_____________________

5 points
1. What is computed in the variable sum (as a function of n) in the following segment?

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


	
5 points
2. What is the Big-O running time as a function of n of the following segment?

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


10 points
3. Which function grows faster, 

a). n**(1/2) or log(n)**2 ?


b). n*log(n)**(1/2) or n**(1/2)*log(n)**(3/2)  


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

public  int  mystery(int[] A, int left, int right) {
     if( left > right) return 0;
     int middle = (left+right)/2;
     int l = mystery(A,left,middle-1); 
     int r = mystery(A,middle+1,right);
     int s = l + r +A[middle];
     while( left < right) {
         s = s + A[left] + A[right];
         left++;
         right--;
     } // end while
     return s;
}

20 points
5. 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 getWords(List words, String[] A);

that puts the Strings from the array A into the List Words in sorted order. 


10 points
6. Explain why any sort algorithm that exchanges adjacent elements must have a O(n**2) average case running time.

10 points
7. Consider the following tree:

A
				           /    |   \
				         /      |     \
				       B     C      D
				     /  |  \         /   |  \
				   /    |    \      /    |   \
				 E     F   G  H    I    J
			             /   \                |    
			           /       \              | 
			         K         L           M


a. List the nodes in preorder.

b. List the nodes in inorder

c. List the nodes in postorder

d. Give the left-most child next-sibling binary tree representation of the tree.

15 points
8.  Give implementation of the method  public void next() throws MyException for the ThreadedInorderItr class.

15 points
9. Consider the following class definition for a node of an arbitrary tree:
	public class TNode {
		Object data;
		LinkedList children;

		public TNode(Object data) {
			this.data = data;
			children = new LinkedList();
		}
		public void addChild(Object data) {
			TNode child = new TNode(data);
			children.addElement(child);
		}

		public LinkedList getChildren() {
			return children;
		}

		public Object getData() {
			return data;
		}
	}

Implement a method to output the nodes of the tree in preorder.
Use the declaration:

public void preorder(TNode T) throws MyException;


10 points
10. Explain the idea behind the quicksort algorithm. What is the worst case, best case and average case running time of the quicksort algorithm.

10 points
11. Consider the following partial implementation of an open Hash Table. The function 
int hash(Object x) takes any Object x and returns a non-negative int.

public class HashTable {

private List[] buckets;
private int size;

public HashTable(int size) {
	this.size = size;
	buckets = new List[size];
}

	....
}
Write the function public Object find(Object x) that returns a reference to x in the hash table or null if x is not in the table.
10 points
12. Explain why adding elements to a heap and then heapifying can be done in O(n) time. You do not need to give a mathematical explanation.

10 points
13. Suppose in the NCAA assignment we used the Java Hashtable class instead of a binary tree where the team name is the key and the corresponding TeamInfo object is the value where 
public class TeamInfo implements Comparable {
        protected String name;
        protected int wins;
        protected int losses;
        protected List years;

        public TeamInfo(String name,int wins,int losses,int aYear) {
                this.name = name;
                this.wins = wins;
                this.losses = losses;
                years = new LinkedList();
                years.addElement(new Integer(aYear));
        }
        public TeamInfo(String name) {
                this.name = name;
                wins = 0;
                losses = 0;
                years = new LinkedList();
        }
        public void addYear(int aYear) {
                Integer Year = new Integer(aYear);
                if( !years.contains(Year) ) {
                        years.addElement(Year);
                } // end if
        } 
        public boolean equals(Object x) {
                if( x instanceof TeamInfo ) {
                        return name.equals(((TeamInfo)x).name);
                } else {
                        return false;
                } // end if
        } 
        public void incrementWins() {
                wins++;
        }
        public void incrementLosses() {
                losses++;
        }
} // end TeamInfo
implement the method

       void insertOrUpdateWinner(Hashtable Teams, String winnerName, int year);

that inserts the team with name winnerName into the Hashtable Teams if it is a new team or updates it if it is already in the table.
15 points
14. Given the int array A = {5,3,8,6,10,4,11,15,1}, show the final array after heapifying it.

15 points
15. Implement the method
	public int find(int x);
from the DisjointSets class (with path compression) non-recursively.