Answers and Criteria for CS307 Midterm 2, Spring 2006.

Acronyms on test:
OBOE = off by one error
BOD = benefit of the doubt
GCE = gross conceptual error

1. Answer as written or -2. On Big O okay if missing O() or use variable other than N.

A. 16
B. 5
C. 31
D. O(N)
E. O(N)
F. GLTF
G. O(1)
H. O(N)
I. O(N)
J. O(N^2)
K. O(N^2 log N) okay if base on log
L. 24 seconds
M. 40 seconds
N O(log N) okay if base on log
O. O(N)


2. Reverse array based list.
Suggested solution:

public void reverse(){
	Object temp;
	int limit = mySize / 2;
	for(int i = 0; i < limit; i++){
		temp = myCon[i];
		myCon[i] = myCon[mySize - 1 - i];
		myCon[mySize - 1 - i] = temp;
	}
}

Okay to use temp array. Lots of "off by one errors". Many people who used temp array did not assign myCon to temp.

Point break down

Loop through elements: 	attempt +5
						correct +5
Swap or move elements to reverse:	attempt +5
									correct + 5
									

3. Split singly linked list based on position
Suggested solution:

public SinglyLinkedList split(int position){
	SinglyLinkedList result = new SinglyLinkedList();

	if( position != mySize ) //if position == mySize result is empty
		//always position tail of result at my tail and update sizes
		
		result.myTail = myTail;
		result.mySize = mySize - position;
		mySize = position;
		
		if( position = 0 ){
			// this list is going to be empty
			result.myHead = myHead;
			myHead = null;
			myTail = null;
		}
		else{
			// general case. Move to correct position and split
			// must move to node before first node in new list.
			// (new last node in this list) 
			Node temp = myHead;
			for(int i = 1; i < position; i++){
				temp = temp.getNext();
			
			myTail = temp;
			result.myHead = temp.getNext();
			// do the split
			temp.setNext(null);
		}
	}
	
	return result;
}

Point break down.

position == mySize
resulting list is empty: 	
attempt +2
correct +2

position == 0
resulting list is entire original list
and this list is made empty
attempt +2
correct +2

general case
move to correct node to split: 	attempt +3
								correct +4
update myTail:	attempt: +1
				correct: +1
set result's myTail:	attempt +1
						correct +1
set result's myHead: 	attempt +1
						correct +1
update sizes	attempt +2
				correct +2

-5 if assume methods exists without actually writing them. (remove, add)
-7 if worse than O(N). (Watch for O(N^2) when using self written remove.)

4. sudoku

Suggested Solution:
public boolean solverHelper(int[][] board, boolean[][] given, int row, int col){
	//base case done?
	if( sudokuStatus(board) == 0 )
		return true;
	
	//calculate next coordinates of next cell. (Many ways to do this.)
	int nextCol = (col + 1) % 9;
	int nextRow = nextCol == 0 ? row + 1 : row;
	
	//check if cell given. If so, just move on to next cell
	if( given[row][col] )
		return solverHelper( board, given, nextRow, nextCol );
	
	// not a given try all values 1 through 9
	boolean solved = false;
	for( int i = 1; i <= 9 && !solved; i++ ){
		board[row][col] = i;
		// if this works for now move on to next cell
		if( sudokuStatus(board) != 2 )
			solved = solverHelper( board, given, nextRow, nextCol );
	}
	// did we find a solution? If not, reset cell to 0 for backtracking
	if( !solved)
		board[row][col] = 0;
	return solved;
}

point break down.

Comments +3
base case +2

determine coordinates for next cell:	attempt: +2
										correct: +2

check for given values and leave them alone: +3 (must move on)

if not given try values 1-9 in current cell:	attempt: +2
												correct: +

Perform recursive call:	attempt: +3
						correct: +3 (lose for early return)

reset to 0 if no solution: +3