Example:
2. 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
0 comments