Prelim 2 grading guide:

Problem 1:
1a)
+2: Good descriptions mentioned at least one of: branching degree, number of paths through the data structure, and/or degree of connectivity.  Decent descriptions mentioned hierarchical in general have multiple levels.
+1: If one of the two terms was sufficiently described, or if both were described very weakly.
+0: Many people mentioned lists, arrays, and tress, but simply listing which category each of those falls into (i.e. not providing a description of why) does not answer the question.

1b)
+2: A data structure that allows efficient searching for an item.  Also awarded full credit answers using the similar terms quick, facilitate, etc.
+1: Descriptions using weak terms as a substitute for 'efficient', such as 'good'.
+0: Answers which simply stated 'a structure that allows searching'.

1c)
no partial credit

1d)
Many people lost points for not being precise enough.  For example, f1(x)=n2 is an upper bound for f2(x)=n, n>1.  Also, some people only restated the information given in the problem statement and did not answer "Why?".

1e)
1 point for correct counting of each of the 6 lines of code.  1 point for the correct final answer.  We allowed some deviation on how people counted (ex. counting loading of constants or not), as long as a student was consistent among all lines of code.

1f)
The answer says to "Express your answer in big-O notation", so the only acceptable answer was: O(n)

Problem 2:

2a)

1 point: Saying True
1 point: Correctly stating meaning of O(h(n))
2 points: Correct c, n0, saying it's a witness pair
	1 point: correct c or n0, correct c, n0 without saying witness pair

2b)

2 points: Saying False
Specific Example:  
	2 points: specifying f(n), g(n) and h(n)
		1 point for only f(n) and g(n)
	2 points: Showing that f(n)/g(n) not O(1)


Problem 3:

Coming soon!

Problem 4:

-2 points: Trying to create new Iterator in constructor
-4 points: having/not having .next (depends on solution)
-4 points: did not increment cursor in next()
-2 points: returned cursor instead of data in next()
-2 points: cast object to Node
-1 point: incorrect syntax anywhere.

Problem 5:

Base Case: 4 points
-4 points: No base case
-1 point: Doesn't return true for null tree

Recursive Calls: 5 points
-1: No notion of subtree analysis
-2: Doesn't call on left subtree
-2: Doesn't call on right subtree

Value Tests: 9 points
-2: Does not handle possibility of null pointers when calling methods
-1: Does not cast to Comparable
-3: Correct direction on comparisons
	-2: Using right find (right or left) based on which subtree
	-1: Using < or > for compareTo properly
-3: compareTo issues
	-2: Doesn't use compareTo
	-1: Calls on n instead of n.data
-6: Doesn't check full subtree. i.e. only checks immediate children for data relation, not entire subtree.

Combining Conditions: 2 points
-1: Return true appropriately
-1: Return false appropriately

Problem 6:
(partial credit allowed)

Base Case: 3 points
Calculate R1 index correctly: 3 points
Calculate L2 index correctly: 3 points
Loop condition for swap: 3 points
Swapping code: 3 points
Computing which elements to swap: 4 points
Recursion: 6 points

Use of extra space, but follows algorithm: -10 points
Use of helper methods: -10 points