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)