Part 1: 15 points-------------------------------------------------------------------------
(a) 1: FIFO/queue mentioned
0: missing something
(b) 1: FILO/stack both mentioned
0: missing something
(c) 5: declare/initialize/assign/memory allocated/(get + set), 1 point each,
completely correct usage for each term
3: diagram completely correct with X & Y pointing to the same array, first = 10
2: minor error in diagram or first incorrectly identified
1: X & Y drawn as separate arrays or other error
(d) 2: fully correct answer identifying issues with public/private
1: some correct analysis but missing discussion of public/private
(e) 3: 1 point each for i, ii, & iii
Part 2: 15 points-------------------------------------------------------------------------
(algorithm) 10: completely correct with usage of the 4 stack methods only
9: correct but used a method or variable we don't know (i.e. size(), n)
7: correct but stack ends up upside-down, or other minor confusion
5: correct description but not in pseudocode or code
3: wrote a non-loop method for this specific case only (n=4), or
other major error in the method
(signature) 2: identified correctly as public and static
1: missing static or public, or adding extra terms (i.e. void)
(runtime) 3: correct as O(n) with analysis, also accepted linear but with a constant
2: minor error or correct answer but no explanation
1: any other runtime, O(1), O(n^2)
Part 3: 20 points-------------------------------------------------------------------------
(iterator) 12: all methods implemented correctly, with "index" or similar as a field
10: minor error (not incrementing index or similar)
8: correct iterator implementation, but for a list
4: some correct ideas or progress towards a correct solution
2: something on the right track
(bullet 1) 4: mentioned that arrays already have fast indexing, or similar
2: something on the right track but missing reasoning or reasoning incorrect
(bullet 2) 4: correct identification as an interface, empty methods
2: either interface or method analysis correct
1: defined methods or wrote something correct about iterators
Part 4: 20 points-------------------------------------------------------------------------
(a) 6: correct code and picture
5: correct code and picture, except missing loop back to itself
3: correct picture, but error in code
2: progress toward a correct solution
(b) 6: correct code and picture
4: correct code and picture, but missing loop component
2: progress toward a correct solution
(c) 8: correct code and picture, with analysis of issues and efficiency
6: minor error in code or picture, or lacking explanation
4: correct code and picture, but for a normal linked list, not loop
2: progress toward a correct solution
Part 5: 15 points-------------------------------------------------------------------------
(algorithm) 10: any correct pseudocode that is an improvement (based on insertion sort)
7: wrote something correct but equivalent to insertion sort
5: algorithm provided but with some errors or misconceptions
3: progress toward a correct solution
(example) 5: correct analysis (with work) based on the algorithm written
3: minor error in analysis of comparisons
1: some work on the right track
Part 6: 15 points-------------------------------------------------------------------------
(a) 9: O(n) with a complete and correct justification
-: it really varied here based on the justification. O(n^2) might be almost correct
if it was assumed that adding to a list was slow. O(n^2) might be very off if no
justification was given or it was based on there being two loops.
1: O(1) or a runtime with no justificaiton
(b) 6: O(n) with a complete and correct justification
5: O(nlogn) with justification
3: O(n^2) with argument of nested for loops
1: any runtime with no justification