• Home
  • Blog
  • 5 simple Computer science questions: Algorithm

5 simple Computer science questions: Algorithm

0 comments

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.

About the Author

Follow me


{"email":"Email address invalid","url":"Website address invalid","required":"Required field missing"}