CS307 Fall 2007, Midterm 2 suggested solutions and grading criteria

Grading acronyms

OBOE - Off by one error. Calculation is off by one.
AIOBE - Array Index out of Bounds Exception will occur
NPE - Null Pointer Exception will occurs
ABA - Answer by Accident
GCE - Gross Conceptual Error. Did not answer the question asked or showed
fundamental misunderstanding
NAP - No answer provided. No answer given on test
ECF - Error carried forward.
BOD - Benefit of the Doubt. Not certain code works, but, can't prove otherwise
Gacky or Gack - Code very hard to understand even though it works or solution
is not elegant. (Generally no points off for this.)


1. 1. Answer as written or -1. Ignore differences in capitalization. On Big O,
it is okay if missing O(). On Big O if extra term or coefficient (other than
base on log) -2.

A. 7
B. stendts
C. 74
D. O(N)
E. O(N^2)
F. O(1)
G. O(N^2) // recall get from LinkedList is O(N)
H. O(NlogN) // base 3 on log okay
I. O(2^N)
J. 345
K. false // recall size is changing as we remove things. This is a cross over
logic error
L. 7856
M. 1553
N. 4 seconds
O. 160 seconds // selection sort is O(N^2)

2. A difficult question and there were a large variety of answers. Probably the
most difficult question on the test. You had to find the last node in the list
containing the target data or show it wasn't there. Walking off the end of the
list shouldn't have been too hard because you had the size instance variable
available. There were three main approaches.

1. The easiest approach was a 2 pass algorithm. Simply go through the whole list
once and determine the index of the last occurrence. This approach did not try
to maintain a pointer to the node before the last occurrence in the first pass.
In the second pass iterate to the node before the one to be removed and then
remove it.

Both of the one pass methods needed at least two temporary pointers. One to
iterate through the list and one to maintain a pointer to the node before the
last known occurrence.

2. Look ahead. Use a pointer but look at the node after this one.

3. Trailer. Use a pointer to iterate through list, but maintain a pointer behind
it in case the iterator pointer finds the data.

Both of the one pass approaches had to deal with more special cases which a lot
of students got wrong.

One more special cases was the possibility of having to move the head. Some
student only considered this if size was also 1, but it was certainly possible
for size to be >1 and the head node contains the last occurrence of the target.

Suggested Solution:

public boolean removeLastOccurrence(Object obj){
	int pos = -1;
	Node temp = head;
	// find where the last occurrence is located
	for(int i = 0; i < size; i++){
		if( temp.getData().equals(obj) )
			pos = i;
		temp = temp.getNext();
	}

	boolean result;
	if( pos == -1 )
		result = false;
	else{
		result = true;
		// special case if last occurrence is first element in list
		if( pos == 0 ){
			temp = head;
			head = head.getNext();
			temp.setNext(null);
		}
		else{
			// general case. get to node before one that contains last element
			temp =head;
			for(int i = 1; i < pos; i++)
				temp = temp.getNext();
			temp.setNext(temp.getNext().getNext());
		}
		size--;
	}
	return result;
}

Alternate solution. Trying to do it in one pass. Need 3 temp pointers. One to
traverse list, a trailer because we want to have a reference to the node before
the node that contains the data, and a pointer to the last occurrence of the
data.

public boolean removeLastOccurrence2(Object obj){
	Node temp = head;
	Node trailer = null;
	Node lastFound = null;
	for(int i = 0; i < size; i++){
		if(obj.equals( temp.getData() ) ){
			//found it. Reposition last found
			lastFound = trailer;
		}
		trailer = temp;
		temp = temp.getNext();
	}
	// Special case. Was only occurrence in head?
	if( lastFound == null && head != null && head.getData().equals(obj){
		lastFound = head;
		head = head.getNext();
		size--;
	}
	else if( lastFound != null ){
		//general case
		lastFound.setNext( lastFound.getNext().getNext() );
		size--;
	}
	return lastFound != null;
}

Grading Criteria:

traverse linked list attempt 2
traverse linked list correct 3

search for last occurrence of obj in list attempt 2
search for last occurrence of obj in list attempt 3

// in a one pass algorithm the following may be combined with traversing the
// linked list
move to node before last occurrence of obj in list attempt 2
move to node before last occurrence of obj in list attempt 3

remove node from list attempt 2
remove node from list correct 3

handle special case of first node containing last occurrence 2
update size 1
return true if obj was present, false otherwise 2

3. Suggested Solution

public ISet cartesianProduct(ISet other){
	ISet result = getEmptySet();
	Iterator itThis = iterator();
	Iterator itOther;
	Object temp;
	while( itThis.hasNext() ){
		temp = itThis.next();
		itOther = other.iterator();
		while(itOther.hasNext()){
			result.add(new Pair(temp, itOther.next()));
		}
	}
	return result;
}

Alternate solution assuming ISet or AbstractSet is Iterable

public ISet cartesianProduct(ISet other){
	ISet result = getEmptySet();
	for( Object obj : this ){
		for( Object otherObj : other ){
			result.add( new Pair(obj, otherObj) );
		}
	}
	return result;
}

Grading Criteria:

Create resulting, empty set attempt 1
Create resulting, empty set correct 2

Iterator through all elements of this set attempt 3
Iterator through all elements of this set correct 4

Iterator through all elements of other set attempt 3
Iterator through all elements of other set correct 4

Create new pair object and add to resulting set attempt 3
Create new pair object and add to resulting set correct 4

return 1

4. Suggested Solution

Students did well on this. There were lots of gacky ways of checking the
boundaries, which led to a lot of extra code having to be written. The most
common mistake was not realizing if there are adjacent 0s and a base case is not
added to not do anything if the boolean matrix show for the given position is
already true, to do nothing. If this check is not made then an infinite
recursive loop will ensue between adjacent 0s.

public void update(int row, int col){
	// only check cells in bounds and that have not already been revealed
	if(0 <= row && row < show.length
			&& 0 <= col && col < show[0].length
			&& !show[row][col]){

		// mines are easy, just call game over
		if(theTruth[row][col] == MINE)
			endGame();

		else{
			//show this cell
			show[row][col] = true;

			// if cell contains a 0 reveal neighbors.
			// note this makes call to myself, (same row and col)
			// but now I have been revealed so that will be a base case
			if( theTruth[row][col] == 0 ){
				for(int r = row - 1; r <= row + 1; r++)
					for(int c = col - 1; c <= col + 1; c++)
						update(r, c);
			}
		}
	}
}

Grading Criteria

Base case for cell has already been revealed 3

handles cell contains a mine 2

handles cell contains an int 1 through 8, this is a base case 2

if cell is a 0 makes recursive calls to neighbors attempt 3
if cell is a 0 makes recursive calls to neighbors correct 6

handles boundary cases (edges and corners) attempt 2
handles boundary cases (edges and corners) correct 2