Homework Assignment 4 Grading:

Comments to add to student's gradesheet (as an overall comment):
  Good job!
  No work submitted.
  Warning: Wrong file name!  Name should have been 'H3.txt'
  Warning: Extra files!  Please hand in only what is asked.
  Unreadable homework - meet me
  Note: Please ensure file is readable before turning in


Note: for each question or question part that a student gets completely correct,
make sure to add the comment:
  Good job!
so the student's gradefile contains some feedback for that question/question
part


For question 2, when justifying their answers, to get full credit, students 
should look at the methods being called as well as the loop and indicate the 
complexity of each method being called:
(Note: for size() and isEmpty(), it is ok if they only state their complexities 
one time and use that info in multiple places, e.g., stating in part A.i that 
size is O(1) means they aren't required to state that size is O(1) in parts B 
and C as well.)

Part A.i) answer should include the following info/ideas:
	size is O(1)
	add (to end) is O(1)
	remove (last item) is O(1)
	overall complexity is O(N)
	
Part A.ii) answer should include the following info/ideas:
	isEmpty is O(1)
	add (to end) is O(1)
	remove (first item) is linear in # of items in list (i.e., remove
	    requires shifting)
	each time through the loop, a different # of items is being shifted
	overall complexity is O(N^2)	
	note: it is an incomplete answer to state that remove is O(N), loop 
	      runs N times so overall complexity is O(N^2)


Part B.i) answer should include the following info/ideas:
	size is O(1)
	add (to end) is O(1)
	remove (last item) requires walking chain to find item (so it's linear
	    in the size of the list)
    each time through the loop, a different # of nodes will be traversed
	overall complexity is O(N^2)
	note: it is an incomplete answer to state that remove is O(N), loop 
	      runs N times so overall complexity is O(N^2)	
		  
Part B.ii) answer should include the following info/ideas:
	isEmpty is O(1)
	add (to end) is O(1)
	remove (first item) is O(1)
	overall complexity is O(N)	

Part C.i) answer should include the following info/ideas:
	size is O(1)
	add (to end) is O(1)
	remove (last item) requires finding the last item
	note: depending on whether they assume that the list is optimized to 
	recognize that if it is at the last node, it doesn't need to traverse
	the chain, they will get a different answer (either answer is ok)
	- if they assume that list will recognize it's removing the last node,
	  then remove will be O(1) and the overall complexity will be O(N)
	- if they assume that remove will traverse the chain regardless of the
	  position, then remove will be linear and the overall complexity will
	  be O(N^2) (and in this case, don't count off if they say remove is O(N),
	  loop executes N times, so it's O(N^2))

Part C.ii) answer should include the following info/ideas:
	isEmpty is O(1)
	add (to end) is O(1)
	remove (first item) is O(1)
	overall complexity is O(N)