Divide and Conquer II
1. We have 𝑛 nuts and 𝑛 bolts. The nuts (and the bolts) are of different sizes. Each bolt fits in exactly 1 nut. We
would like to match the nuts with the bolts which fit into them. Since the dimensions of the nuts and bolts are so
small, we can not really tell if a nut (or a bolt) is bigger than another nut (or bolt). So the only operation that is
allowed is comparing a nut and a bolt – with such a comparison, we can distinguish between three cases,
namely, the nut fits a larger bolt, or the nut fits a smaller bolt, or the nut fits this bolt. Give a randomised
algorithm that matches nuts with bolts. The expected number of comparisons (of a nut with a bolt) done by this
algorithm should be 𝑂(𝑛 log 𝑛).
2. Weighted medians: You are given 𝑛 numbers 𝑎1, 𝑎2, ..., 𝑎𝑛. The number 𝑎𝑖 has a weight 𝑤𝑖. Find a number 𝑎𝑗 so
that the total weight of numbers less than 𝑎𝑗, as well as the total weight of numbers more than 𝑎𝑗, is at most half
the total weight of the set.
3. [KT-Chapter5] We are interested in analysing some hard-to-obtain data from two databases. Each database
contains 𝑛 numerical values (so there are 2𝑛 values in total). Assume that these values are distinct. We would
𝑡ℎ
like to determine the median of these 2𝑛 values, which we define as the 𝑛 smallest value. However, the only
way to access these values is through queries to the databases. In a single query, we specify a value 𝑘 to one of
𝑡ℎ
the two databases, and the chosen database returns the 𝑘 smallest value that it contains. Give an algorithm
that finds the median value using 𝑂(log 𝑛) queries only.
4. You are given a set 𝑆, |𝑆| = 𝑛, of distinct integers and two numbers 1 ≤ 𝑚1, 𝑚2 ≤ 𝑛. For any 𝑥 ∈ 𝑆 define
𝑟𝑎𝑛𝑘(𝑥) = |{𝑘 ∈ 𝑆: 𝑘 ≤𝑥}|. Show how to find all elements in 𝑆 whose rank falls in the interval [𝑚1, 𝑚2] in
𝑂(𝑛) time.
5. Given 𝑛 points in the 2D plane, determine their convex hull in 𝑂(𝑛 log 𝑛) time using divide and conquer.