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 have size
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).
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 elements, called q-quantiles. Considering the time to compare
elements 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?
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.
0 comments