Possible Solutions for Midterm 2, Spring 2002

On Big O any constants or lesser terms means -2 for that part

A.	O( N ^ 2 )  or N ^ 2

B.	O( N ) or N

C.	23

D.	50

E.	2 ^ N

F.	10    -    -     81    55
	back             front
	
G.	O( N ^ 2 log N ) or N ^ 2 log N     (base 2 included is okay)

H.	runitme error OR stack overflow OR exception.

I.	2

J.	A reference to the Head and Tail nodes and an integer variable to track the number of nodes in the list. (or words to that effect.)


Question 2:

if(myHead == myTail)
{	myHead = null;
	myTail = null;
}
else
{	ListNode temp = myHead;
	while(temp.getNext() != myTail)
		temp = temp.getNext();
	myTail = temp;
	myTail.setNext( null );
}
iMySize--;


Question 3: 

Solutions:

public static void printSubsets( int[] nums )
{	ArrayList set = new ArrayList();
	help( nums, 0, set );
}


public void help( int[] nums, int cur, ArrayList set)
{	if( cur == nums.length )
		System.out.println( set );
	else
	{	set.add( new Integer( nums[cur] ) );

		help( nums, cur + 1, set);

		set.remove( set.size() - 1 );

		help( nums, cur + 1, set);
	}
}


public void iterativePrintSubsets( int[] nums )
{
	boolean[] used = new boolean[ nums.length ];
	int numSubsets = 1;
	for(int i = 0; i < nums.length; i++)
		numSubsets *= 2;
	
	int place = 0;	

	for(int i = 0; i < numSubsets; i++)
	{	used[0] = !used[0];
		place = 0;
		while( place + 1 < used.length && !used[place] )
		{	used[place + 1] = !used[ place + 1 ];
			place++;
		}
		
		for( int j = 0; j < nums.length; j++)
			if( used[j] )
				System.out.print( nums[j] + " " );
		System.out.println();
	}
}

#4

13 7 2 102 101 39 12 571
2 7 12 39 13 102 101 571

#5
int result = 0;
for(int i = 0; i < iMySize; i++)
	if( myItems[i].equals(data) )
		result++;
return result;

#6

int[] results = new int[5];
int totalTemp = 0;
int numTemps = 0;

for(int row = 0; row < temps.length; row++ )
{	totalTemp = 0;
	numtemps = 0;
	for(int col = 0; col < temps[row].length; col++)
	{	if(temps[row][col] >= minTemp
			&& temps[row][col] <= maxTemp;
		{	
			numTemps++;
			totalTemp += temps[row][col];
			if( temps[row][col] > results[4] )
			{	results[2] = row;
				results[3] = col;
				results[4] = temps[row][col];
			}
		}
	}
	if( numTemps > 0 && (totalTemp / numTemps) > results[1] );
	{	results[0] = row;
		results[1] = totalTemp / numTemp;
	}
}
return results;