Algorithm
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.
