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.