Note: these were written a while back (e.g. over a year ago), so if there are any clarity issues (or
mistakes), please let me know! Also, feel free to ask a question on Piazza if anything is unclear;
I’m sure I can probably come up with a better explanation for some of these questions right now
than I did back then. Good luck studying!
64. The correct answer is (C). Going to rewrite this since my old solution wasn’t thorough
enough. This question is also a bit unclear in what n is, which is the size of the vector (wrote
these questions a long time ago, when I was taking 281, so apologies for this oversight).
The auxiliary memory (or space) complexity of a function is how the additional memory usage
of the function scales with the size of the input . If the amount of additional memory used by
the function does not depend on the input size, we say that the function has a constant space
complexity (i.e. Θ(1) space). Here, the amount of memory used by the code scales linearly with
the size of the input. If the size of my vector doubles, the amount of additional space I need also
doubles, since I have to create an additional stack of size n to reverse my vector.
See note on Piazza @3383 for an update to this question.
73. The answer is (D). If the comparator returns left < right, it’s a less comparator, which
creates a max PQ (a rule of thumb - if you were to sort a vector using the comparator, the
element that ends up at the back after the sort is completed is the element with the greatest
priority). This comparator is in the format left > right, so it is a greater comparator (or min PQ).
This is a min PQ of elements based on distance from 25, so elements with a smaller distance to
25 (i.e. closer to 25) have the largest priority.
117. Bucket sort won’t be on the exam, so ignore this.