csc 148			Assignment 3 -- Answers to Questions
Fall 1995		Author: Vincent Gogan (csc 148 head TA)
==========================================================================

Answers to Questions:

(1) Time Complexity:
	Assume that the grid is NxN, there are 'm' organisms with
	at most 'c' non-empty columns and there are at most 'r'
	organisms in each column.

	The answers given here are with respect to the sample solution.

	* Initializing the data structure. In the solution, this is
	accomplished by the procedure 'Grid.initGrid()' which is O(1)
	time as it just does three assignment statements. 

	* Reading the data and building the data structure. The sample
	solution does this with the procedure 'Grid.readGrid' in O(m)
	time which is optimal. This is each new organism is added to
	the end of a column in O(1) time and the column is added to the
	grid in O(1) time as well.

	Other solutions may have higher complexity if the input format
	is not as structure as the one in the sample solution. It should
	never be worse than O(N^2) though.

	* Updating the data structure for the next generation.
	In the sample solution, the data structure is not updated
	in-situ. Instead, a new, updated, copy of the grid is created.
	The complexity of the procedure 'Grid.nextGeneration()' is
	O(c*N). The analysis goes like this:

		- For each non-empty column in the current generation,
		the procedure newColumn is called a constant number
		of times.

		- The procedure newColumn executes its loop 'height'
		times and each procedure it calls only has complexity
		O(1).
	
	The procedure newColumn could be improved so that it loops
	over just the elements in a column instead of every possible
	element location. This would give an overall complexity of O(m).

	A more naive approach that students may have taken is to visit
	every possible element location and proces it. Depending on how
	this was done, this could take either O(N^2) or even O(N^3) if
	there is no attention to efficiency.

	* Displaying the next generation. This is accomplished by the
	procedure 'Grid.displayGrid()' as required by the handout. The
	complexity of this procedure is O(m) as only grid locations with
	organisms are visited. If all grid locations are visited, this
	would require O(N^2).

(2) No other fields were added to the sample solution. This is because
adding extra fields can't really help that much. This is because the
overall amount of work that needs to be done doesn't change. If you do
some of the work in advance and store the result in the data structure,
all you are doing is using extra space. Doing the work as the
information is needed is much more space-efficient.

(3) Create and diplay method. The sample solution did not create and
display the next generation simultaneously. Doing so would go against
a 'modular' style solution without any real benefit. Conceptually, it 
makes sense to separate these two procedures. Putting them together will
just complicate the code. Any decrease in the running time would be by a
small constant factor (probably < 2).

(4) Time-space tradeoffs.

		Boolean array			List of lists of organisms
 
Space		O(n^2)				O(m) which could be O(n^2)
 
Initializing	O(n^2)				O(1)
 
Input and 	O(m)				O(m)
building
 
Update		O(n^2)				O(c*n)
 
Display		O(n^2)				O(m)