Part 1: 20 points-------------------------------------------------------------------------
(a) 2: type and variable name (1 pt each)
(b) 6: 1 pt each, gave credit for O(n) and O(logn) for insertion into a list and tree,
respectively. did not give credit for O(1) for array insertion (O(1) for “set”)
(c) 1: array/vector
(d) 1: DFT
(e) 1: True
(f) 3: 1 pt for the first part (everyone got this), and 2 pts for the second part,
full credit for a for loop only, 1 pt for a while loop with correct stopping
(g) 3: 1 pt for summer, 2 pts for correct explanation of ambiguity with internal nodes
Part 2: 25 points-------------------------------------------------------------------------
(a) 5: correct tree and in-order traversal (sorted)
3: correct tree but incorrect in-order traversal, or a different tree that yields the
correct in-order traversal
2: placed elements in BFT and did in-order on that
(b) 3: correct post-order traversal of your tree from part (a), no matter what it was
1: in-correct traversal
(c) 2: correct heap result
(d) 5: correct max-heap following heapify procedure
4: result was a max-heap, but not the one resulting from our heapify procedure + work
3: same as above, but with no work
2: something that is not a max-heap or min-heap, but very close
1: something that is not close to a max-heap or min-heap
(e) 2: root and last node swapped
1: two other elements swapped
0: same tree as before or other major error
(f) 3: BFT results in a sorted list (accepted reverse order as well)
1: some other tree
(g) 5: thorough discussion of average case for both being O(nlogn), and a discussion
of insertion sort with a BST being O(n^2) in worst-case of already sorted list
4: correct analysis as described above, but missing some concrete runtimes
3: fully correct analysis of heap sort, but missing insertion sort
2: analysis on the right track for both algorithms, but minor errors
1: some analysis on the right track
Part 3: 10 points-------------------------------------------------------------------------
(a) 4: index + correct order
3: index + minor error in ordering
2: index + major error in ordering
1: index incorrect and major error in ordering
(b) 4: correctly inserted and 4-6 steps for Anita (+ work/justification)
3: correctly inserted and 3 steps for Anita (+ work/justification)
2: correctly inserted and 1-2 steps for Anita (+ work/justification)
(c) 2: said something about making the hash table larger or using an array of linked lists
1: suggested deleting elements
Part 4: 25 points-------------------------------------------------------------------------
(a) 6: correct steps with 2 disks (even if other disks are there)
4: minor error in steps
2: major error in steps
(b) 4: base case identified and correctly stated
3: minor error in base case
2: major error in base case
1: something other than a base case
(c) 8: correct number of times (31 or 15, depending on your base case)
6: say 15 when it should have been 31, or other minor error
3: multiplied n=4 by a constant or something related
2: did not include recursive calls
(d) 7: correct result with explanation
4: 2^logn, O(n^2) with explanation on the right track
2: other runtime with incorrect or minimal explanation
Part 5: 20 points-------------------------------------------------------------------------
(a) 6: correct order
4: minor error in order
2: major error in order
(b) 14: 2 pts per correct edge weight (with work)