Spring 2003 M2 Model Solution

1.
A. 80 sec

B. 960 sec (64 * 15) sec okay

C. Yes, if the Big O were quadratic (O(N^2)) execution time would increase by a factor of 4 when doubling the size of the data set. 1000 -> 2000 expected time 20 sec, actual 15 sec. 2000 -> 4000 expected time 60 sec, actual 45 seconds. (or words to that effect.)

D. O(1)

E. O(N)

F. O(N^2)

G. O(N^3)

H. O(N^2 * log N)

I. abretc

J. 86

K. 3 2 19 5 23 16 101 97 42 17 155 105 43 88

L. O(N)

M. O(N* log N) if sort is quicksort
   O(N^1.3) if shellsort used (1.2 - 1.3 okay)
   O(N^2) if selection, bubble, or insertion sort used

N. The comparable interface allows classes to inherit one class and still inherit Comparable. Objects of a given class can now be multiple data types, Comparable, and parent class. compareTo allows objects to be ordered according to their natural ordering. This allows for generic sorting and searching methods.

O. One implementation of a data structure can be used to hold or store all data types. Java achieves this through inheritance and polymorphism.


2.
public void reverse(List a)
{	Object temp;
	int lastElement = a,getSize() - 1;
	for(int i = 0; i < a.getSize() / 2; i++)
	{	temp = a.get(i);
		a.set(i, a.get(lastElement - i);
		a.set(lastElement - i, temp);
	}
}


3. 
public Set union(Set otherSet)
{	Set result = new Set();
	result.mycon = new Object[iMySize + otherSet.iMySize];
	
	// copy items from calling object
	for(int i = 0; i < iMySize; i++)
		result.myCon[i] = myCon[i];
		
	boolean found = false;
	result.iMySize = iMySize;
	int index = 0;
	
	// go through all elements in other Set
	for(int i = 0; i < otherSet.iMySize; i++)
	{	found = false;
		index = 0;
		// check to see if current item from otther Set is in this Set
		while(!found && index < iMySize)
		{	found = otherSet.myCon[i].equals(myCon[index]);
			index++;
		}
		
		//was current item from other set found? if not add to result
		if(!found)
		{	result.myCon[result.iMySize] = otherSet.myCon[i];
			result.iMySize++;
		}
	}
	return otherSet;
}

4. 
public double getAveragePayout(SlotMachine s)
{	double numCombos = Math.pow(s.symbolsPerReel(), s.getNumReels());
	double totalPayouts = helper(s, 1, 1, 0);
	return totalPayouts / numCombos;
}

private double helper(SlotMachine s, int reelNum, double totalMult, double totalAdd)
{	double result = 0.0;	
	// Base cases: 1. No more reels, mult = 0
	if( reelNum > s.getNumReels() || totalMult == 0)
		result = totalMult * totalAdd;
	else
	{	// recursive step. iterate through symbols on this
		// reel and for each figure all 
		// remaining combinations of sybols
		// on remaining reels
		Symbol tempSym
		for(int sym = 1; sym <= s.symbolsPerReel(); sym++)
		{	tempSym = s.getSymbol(reelNum, sym);
			result += helper(s, reelNum + 1, 
				totalMult * tempSym.multipliesPayoutBy(),
				totalAdd + tempSym.addsToPayout() );
		}
	}
	return result;
}