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