CS307 Fall 2009 Final Exam
Suggested Solution and Criteria:

1 1.5 Each

A:      72
       /  \
      6   125
       \     \
       51    218
      /
     41
     
B: 12, 9, 0, -5, 25, 20, 30

C: -5, 0, 9, 25, 12, 20, 30

D: -5, 0, 25, 9, 30, 20, 12

E: No.

F: valid binary search tree using values between 1 and 10. No repeats.

G: The path rule is violated OR paths with different numbers of black nodes (1, 2, 3)
Or words to that effect.

H: Yes. (Explanation not required, but make 200 black, 400 red, and 70 red and magic number is now 2.
I: O(N) okay if just N

J: O(N^2) okay if N^2

K: Yes, it goes through all of the values in the list using an iterator instead of the get method. (Or words to that effect.)

L: O(NlogN) okay if just NlogN or base 2 included

M: (3 + 2) * (5 + 2)

N: 14 15 1 15 13 

O: z s p r s 

P: Variables must have  a box and arrow.






Q: 7 bits or just 7

R: Any value between 13 and 25. (10 not okay. That would be best case height which is not likely.)

S: add at front, remove from front, or add at end.

T: E can be thought of as a variable that stores the data that a particular LinkedList will hold. (or words to that effect)

2. Suggested Solution:

Simple version using look ahead:

public void split(){
	Node<E> temp = first;
	// if no next, next node, stop
	while(temp != null && temp.getNext() != null){ 
		temp.setNext( temp.getNext().getNext() ); // skips over odd
		temp = temp.getNext();
	}
}

// using trailer

public void split(){
	if(first != null){
		Node<E> trail = first;
		Node<E> lead = first.getNext();
		int index = 1;
		while(lead != null){
			if(index % 2 == 1)
				trail.setNext(lead.getNExt();
			index++;
			trail = lead;
			lead = lead.getNext();
		}
	}
}

// alternate trailer with no count

public void split(){
	if(first != null){
		Node<E> trail = first;
		Node<E> node = first.getNext();
		while(node != null); {
			trail.setNext(node.getNext());
			node = node.getNext();
			trail = node;
			if( node != null)
				node = node.getNExt();
		}
	}
}

Grading:
Use temp variable to move through list. (Okay if trailer)
attempt: 2 points
correct: 4 points

Stop correctly, no NPE
3 points

remove even positioned nodes form list
attempt: 2 points
correct: 4 points


3.
public static boolean balanced(String expr){
	Stack<Character> st = new Stack<Character>();
	boolean good = true;
	for(int i = 0; i < expr.length() && good; i++){
		char c = expr.charAt(i);
		int openIndex = OPEN.indexOf(c); 
		int closeIndex = CLOSE.indexOf(c);
		if(openIndex != -1) // if open symbol add to stack
			st.push(c);
		// if close symbol check that last open symbol matches
		else if(closeIndex != -1){ 
			good = !st.isEmpty(); // if none, bad
			if(good) {
				c = st.pop();
				openIndex = OPEN.indexOf(c);
				// if doesn't match, bad
				good = openIndex == closeIndex; 
			}
		}
	}
	return good && st.isEmpty();
}


Lots of poor solutions that put opening in one stack and close is another. Even if reverse close this still fails many cases.
4. 
public int range(){
	assert size() > 0;
	BSTNode<Integer> temp = root;
	int min, max;
	while(temp.getLeft() != null)
		temp = temp.getLeft():
	min = temp.getValue();
	
	temp = root;
	while(temp.getRight() != null)
		temp = temp.getRight():
	max = temp.getValue();	
	return max - min;
}

Grading:

find min:
attempt 1 point
correct 3 points

find max
attempt 1 point
correct 3 points

calculate range 1 point
return 1 point

-5 if use external data structure
-5 if destroy tree

5
public int numPresent(E obj){
	return helper(root, obj):
}

private int helper(BNode<E> n, E obj){
	if(n == null)
		return 0;
	int total = helper(n.getLeft(), obj) + helper(n.getRight(), obj);
	if( n.getValue.equals(obj)
		total++;
	return total;
}

Grading:

base case fo null or properly use look ahead: 2 points

check value in current node: 3 points (-1 if == instead of .equals)

recursive call to left child: 2 points

recursive call to right child: 2 points

return: 1 point

6. 
recursive version, depth first
 public boolean pathExists(int start, int end) {
 	// to track where we have been
	 ArrayList<Integer> visited = new ArrayList<Integer>();
	 visited.add(start);
	 return helper(visited, start, end); 
 }


private boolean helper(ArrayList<Integer> visited, int current, int end) {
	// base case, direct link exists
	if(adjMatrix[current][end])
		return true;
	boolean solved = false;
	// if not base case check nodes current links
	// to that we have not visited before
	for(int i = 0; i < numNodes() && ! solved; i++){
		if(adjMatrix[current][i] && !visited.contains(i)){
			// try this path!, but make sure we don't cycle
			visited.add(i);
			solved = helper(visited, i, end);
		}
	}
	// if found apth sovled will equal true, otherwise still false
	return solved;
}

create helper: 1 point

way of tracking nodes already visitied: 1 point

check success base case: 2 points

loop through columns: 2 points

check if not visited and link exists: 2 points

add node to list of visited: 2 points

recursive call:
	attempt: 1 point
	correct: 3 points (no early return)

return: 1 point

// don't actually need to keep track of path like we did with
// word ladder, just check to see if a path exists or not.
//iterative version, breadth first
public boolean pathExists2(int start, int end) {
	 ArrayList<Integer> visited = new ArrayList<Integer>();
	 Queue<Integer> paths = new Queue<Integer>(); 
	 // would really have to be  
	 // Queue<Integer> paths = new LinkedList<Integer>(); 
	 visited.add(start);
	 paths.enqueue(start); 
	 boolean found = false;
	 while(!paths.isEmpty() && !found){
		 int current = paths.dequeue(); 
		 found = current == end;
		 for(int i = 0; i < adjMatrix.length; i++){
			 if(adjMatrix[current][i] && !visited.contains(i)){
				 visited.add(i); 
				 paths.enqueue(i); 
			 }
		 }
	 }
	 return found;
 }
 
 track visited: 1 point
 
 init stack and queue correctly: 2 point
 
 loop until found or no more paths: 1 point
 
 check done: 1 point
 
 loop through columns for current top / row: 2 points
 
 check link exists and not visited: 2 points
 
 if link exists and not visited, create new stack, enqueue correctly, add to visited:
 attempt: 2 points
 correct: 2 points
 
 return: 1 point
 
 Graph altered permanently: 5 points