Spring 2003 Final Solution and Criteria

1. Same as key or -2 (except as noted.) On Big O missing O( ) is okay if function correct. Example, O(N) same as N or linear.

A.	101
         /   \
       -12    201
          \
          59
         /  \
       37    91
       
       
       
B.	19 11 7 5 17 113 61 131 151

C.	5 7 11 17 19 61 113 131 151

D.	5 7 17 11 61 151 131 113 19

E.	yes

F.	13 12 12

G.	3 1 2 4 8 16

H.	O(N)

I.	O(log N)

J.	N^2

K.	O(N^2)

L.	O(N)

M.	2 5 8 11

N.	O(N)

O.		






P.	O(N), N = number of nodes in tree (-1 for either part missing)

Q.	O(log N)

R.	O(N^2)

S.	0010

T.	O(1)


2.	Solution

//base case, trees are mirror images, same structure

if( t1 == null && t2 == null)
	return true;

// base case, one root null, other not, -> not mirror images
else if ( t1 == null || t2 == null)
	return false;

// recursive step. t1 and t2 might be the mirror images of each other
// must check to see that left subtree of t1 is same structure as right of t2 
// and right subtree of t1 is same structure as left of t2

return areMirrorImages(t1.getLeft(), t2.getRight) &&
	are MirrorImages(t1.getRight(), t2.getLeft());



3.	Solution

// enough space? If not resize
if( iMySize == myCon.length)
	resizeMyCon(2);

int loc = 0;
while(loc < mySize && pri >= myCon[loc].pri)
	loc++;

// found spot for new item. shift down
for(int index = mySize; index > loc; index--)
	myCon[index] = myCon[index - 1];

myCon[loc] = new PriPair(item, pri);

iMySize++;


Criteria

-2 no resize (any integer factor > 1 okay)

-1 resize with double less than 1 or integer = 1

-5 no attempt to search for correct spot in myCon

-3 search attempted, but will not ever work (except off by 1)

-1 search attempted, but fails for some special cases or always off by 1

-2 search causes array index out of bounds exception (except for off by 1)

-5 no attempt to shift elements down

-3 shift attempted, but will not ever work (except off by 1)

-1 shift attempted, but fails for some special cases or always off by 1

-2 shift causes array index out of bounds exception (except for off by 1)

-1 iMySize not incremented

-5 algorithm is worse than O(N)

-4 other major logic error

-2 other minor logic error


4.	Iterarive Solution using Queue

// creatue array of nodes already visited. +1 to avoid adjustment
boolean[] used = new boolean[g.numNodes() + 1];
used[nodeNum] = true;

Queue q = new Queue();

// go through start node and enqueue all nodes it connects to (besides itself)
for(int i = 1; 1 <= g.numNodes(); i++)
	if( g.linkExists(nodeNum, i) && i != nodeNum )
	{	q.enqueue(new Integer(i) );
		used[i] = true;
	}

// as long is the queue is not empty we have to check to see if we can find a path

boolean found = false;
int currentNode = 0;

while( !found && !(q.size() == 0) )
{	//take front node and enqueue all nodes it links to orginal node
	// if so cycle found

	currentNode = ((Integer)(q.dequeue())).intValue();	
	found = g.linkExists(currentNode, nodeNum);
	
	// if cycle not found enqueue all nodes current node connects to
	// that have not been used yet. Must not repeat nodes to avoid
	// infinite loops
	if(!found)
		for(int i = 1; i <= g.numNodes(); i++)
			if( g.linkExists(currentNode, i) && !used[i] )
			{	q.enqueue( new Integer(i) );
				used[i] = true;
			}
}

return found;


Recursive Solution

boolean[] used = new boolean[g.numNodes + 1];
used[nodeNum] = true;
return helper(nodeNum, nodeNum, used, g)


public boolean helper(int tgt, int current, boolean[] used, Graph g)
{	// base case. have not used node and links to tgt
	if( !used[current] && g.lineExists(current,tgt) )
		return true;
	
	// mark current as visited
	used[current] = true;
	
	// recursive step. check all links out of current that have not
	// been used
	for(int i = 1; i <= g.numNodes(); i++)
		if(g.linkExists(current, i) && !used[i])
		{	if(helper(tgt, i, used, g)
				return true;
		}
	
	// no cycle found
	return false;
}