COP 3530 Section 1			EXAM 1		May 29, 2002

Kraynek							Name:_______________

5 pts.
1. Which function grows faster, n1/2 or (log(n))2 ?




5 pts.
2. What is the big-0 running time in terms of n of the following segment?

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



15 pts.
3. Suppose that A is an ArrayList whose elements are LinkedLists of Strings. Write a method

	void toLowerCase(ArrayList A);

that converts all Strings in A to lower case. Note: the String class has a method String toLowerCase() that converts all characters in the String to lower case.


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

	int problem3(int[] a, int left, int right) {
	     if( left > right ) return 0;
	     int middle = (left+right)/2;
	     return problem3(a,left,middle-1) + problem3(middle+1,right) + a[middle];
	}





10 points.
5a.  Write a method

	String inNaturalOrder(Set s);

that returns a String of all the elements in the Set s in it’s natural order.





15 points.
5b. Write a method

	String inReverseOrder(Set s);

that returns a String of all the elements in the Set s in the reverse of it’s natural order.  

15 points.
6. Let class Node be defined as:
 class Node {
	Object data;
	Node next;
	Node() {}
	Node(Object data, Node previous, Node next) {
		this.data = data;
		this.next = next;
	}
} // end Node
Suppose we have a single linked list with a list head. Write a method
	deleteAfter(Node p);
that deletes the Node immediately following p in the list.


15 points.
7. Let class Node be defined as:
 class Node {
	Object data;
	Node next;
	Node previous;
	Node() {}
	Node(Object data, Node previous, Node next) {
		this.data = data;
		this.previous = previous;
		this.next = next;
	}
} // end Node
Suppose we have a a circular doubly linked list with a list head of Nodes pointed to by header, a Node variable. Write the method 
       Object insertLast(Object x);
that inserts x in a Node that becomes the  last Node in the list.	

15 pts.
8. Let words be a Map object constructed from a file as in the TreeMapExample. Recall that the entries are pairs, <aWord, anInteger>, where aWord appears anInteger times in the file. Write a method

	void frequencyOrder(Map words);

that prints to the screen the opposite pairs (anInteger  aWords) in order from the lowest frequency (Integer) to the highest. For example if <a,3>, <is,5> and <the,2> are entries in words 
2 the
3 a
4 is
would be printed to the screen.