Homework 7

Due Wednesday, April 1

1. You have been asked to analyze the incomes of all engineering and computer science faculty members at a college. This college employs the exactly same number of faculty in engineering and computer science, say, $n$ engineering faculty members and $n$ computer science faculty members. However, for a variety of practical reasons, the college's business office maintains two separate databases, one for the engineering faculty and another for the computer science faculty. Also, to protect privacy, the only way to access income data is through simple queries; in particular, in a single query, you are only allowed to ask, for any integer $k$, what the $k$-th smallest income is within each database. Design an efficient algorithm to determine the median income of all $2n$ engineering and computer science faculty members making $O(\log n)$ queries.

2. Recall the problem of finding the number of inversions: Given a sequence of $n$ integers $a_1, \ldots, a_n$, determine the number of pairs $a_i$ and $a_j$ such that $i < j$ but $a_j < a_i$. We now wish to determine the number of small inversions: pairs $a_i$ and $a_j$ such that $i < j$ and $a_j < a_i < 2a_j$. Design an efficient algorithm to determine the number of small inversions making $O(n \log n)$ comparisons.

3. Recall the median-of-medians algorithm to solve the selection problem.

   (a) To guarantee $O(n)$ time, the median-of-medians algorithm makes recursive calls only when the input size $n \ge 80$. It turns out that the choice of this constant $80$ is somewhat arbitrary. In fact, we can still achieve $O(n)$ time even if we make recursive calls on smaller input. What is the smallest input size with which we can make a recursive call, while maintaining $O(n)$ time? Carefully justify your answer.

   (b) The median-of-medians algorithm partitions the input into groups of five elements, but it also works if we partition the input into groups of seven. Prove carefully that this modified algorithm still runs in $O(n)$ time.

CPSC 320 home page