Midterm 1
posted: 9 am, 07.06.2021 due: midnight, 11.06.2021
You are not allowed to work in groups for the midterm. You can look in books and online, but you must
not ask discuss the exam problems with anyone. If you don’t understand a question, contact Travis or one
of the TAs for an explanation (but no hints). All problems are weighted the same and, for problems broken
down into subproblems, all subproblems are weighted the same.
1. For each cell (i, j) in the matrix below, write o, O, Θ, Ω or ω to indicate the relationship of the the
ith function on the left to the jth function along the top. If none of those relationships hold, leave
the cell blank. Only the best answer possible will be considered correct (so writing O when the best
answer is o doesn’t count, for example). The cell (1, 1) is filled in as an example: n1/4 ∈ o(n2), so that
cell contains “o”. You do not need to explain your answers.
n2 ((−1)n + 1)n 3lgn nlg lgn n lg n
n1/4 o
2n
dlg ne!
n
∑n
j=1(1/j)
T (n) = 5T (n/4) + n3/2
2. Assuming you have an O(n)-time algorithm to find a separator of a planar graph on n vertices — that
is, a subset of at most 2
√
n vertices after whose removal all remaining connected components each
consist of at most 2n/3 — give a divide-and-conquer algorithm to find a minimum vertex cover of
a planar graph on n vertices, similar to our algorithm for colouring a planar graph. Your mark will
partly depend on how fast your algorithm is (although there is not believed to exist a polynomial-time
algorithm). You do not need to analyze your algorithm or prove it correct.
3. Suppose we have a function that, given an unsorted sequence of n integers, in O(n) time returns the
(n/q)th, (2n/q)th, . . . , ((q − 1)n/q)th smallest integers in the array, called q-quantiles. Considering
the time to compare integers in the array to quantiles,
(a) how quickly can we sort with this function when q is constant?
(b) how quickly can we sort with this function when q =
√
n?
(c) if we can choose q freely, how should we choose it to sort as quickly as possible with this function?
You do not need to explain your answers.
(10% bonus question) How fast can we sort if the function takes O(n) time and separates the
integers in the array into
√
n bins such that the ith bin contains the ((i− 1)
√
n + 1)st through i
√
nth
smallest integers? (That is, the first bin contains the smallest
√
n elements, the second bin contains
the next
√
n elements, etc.) You do not need to explain your answer.
Continued on next page!
1
4. Imagine you’re planning a post-lockdown canoe trip with friends, but
� people want to bring different amounts of equipment,
� everyone wants to be in the same canoe as their equipment,
� you can have only so much equipment in each canoe (all the canoes are the same, and consider
only the weight of the equipment),
� any single person’s equipment fits in one canoe,
� everyone wants to row (so you can have at most two people in each canoe).
You have a list of how much equipment each person wants to take (in kilos), and you know how much
fits in a canoe. For example, if there are 3 people going and they want to take 37 kg, 52 kg and 19 kg
of equipment and a canoe can hold up to 60 kg of equipment (plus up to 2 people), then you need at
least 2 canoes: you can put the first and third people and their 37 + 19 = 56 kg of equipment in one
and the second person and their 52 kg in the other.
Give a greedy algorithm to find the minimum number of canoes you need AND GIVE A PROOF OF
CORRECTNESS!
5. Give a greedy algorithm for Binary Knapsack that runs in O(n log n) time, where n is the number of
items to consider, and achieves at least half the maximum profit when all the items have the same
profit-to-weight ratio. Explain why your algorithm achieves this.
2