Prelim 1 Grading Guide:
Problem 1:
1a. 15 points
(-2) for pushing operators onto the stack.
(-5) for using more than one stack, but basically using an algorithm that works.
(-10) for a wrong algorithm,incorrect use of stacks.
1b. 5 points
(+3) for methodology
(+2) for the right answer.
Problem 2:
2a. 10 points
(+6) Correct recurrence
(+4) Proof by induction
2b. 10 points
The solution must either sort the letters and compare the strings letter by letter.
Or, you may use a hashmap and put (letter,count) pairs.
2c. 5 points
Correct Big O running time
2d. 15 points
(+10) Some kind of hash map that keeps all the words which are anagrams of each other in the same list.
(+5) Correct running time
Problem 3:
(-10) If you try to remove an object from the queue.
(-10) No index
(-2) Change index as you bubble up/down.
(-5) If no inequalities are given, i.e. you just say reheap.
(-5) If you forgot to compare the priority of a node with its parent/child.
In short,
(+10) for finding the node
(+10) for a complete explanation of reheap.
(+2) for an attempt.
Problem 4:
2 points: handling of base cases
full credit if properly guards for children being null,
and incorporates the information properly in those cases.
1 point may be awarded for a broken implementation that
shows understanding of the relevant cases.
4 points: use of recursion and proper computation of the range
-2 if only handles one side properly.
No credit if recursive calls not used or the return value
of calls is unused.
4 points: properly checks invariant
-3 if does not use recursive call's information properly
-1 if fails to account for recursive calls returning null (unless above)
If the submitted code does not come close to working, partial credit may be awarded in
areas that show strong understanding of the problem; however solutions that are not easily fixable to be correct shall not receive more than 4 points.
Problem 5:
(+1) frame
(+2) title
(+1) layout
(+3) 1st set of buttons
(+4) 2nd set of buttons
(-2) Array indices start with 1.
(-1 or -2) for extra boxes
(-2) String content (vs numbers)
(-2) If you only increment a single button