1. Suppose we want to partition N items into G equal-sized groups of size N/G, such that the smallestN/G items are in group 1, the next smallest N/G items are in group 2, and so on. The groups themselves do not have to be sorted. For simplicity, you may assume that N and G are powers of two.
a. Give an O(N log G) algorithm to solve this problem.
b. Prove an 0.(N log G) lower bound to solve this problem using comparison-based algorithms.
2. Give a linear-time algorithm to sort N fractions, each of whose numerators and denominators are integers between 1 and N.
3. Suppose arrays A and B are both sorted and both contain N elements. Give an O(log N) algorithm to ?nd the median of A ∪ B.