## 分治

### 1 Divide and Conquer

You are interested in analyzing some hard-to-obtain data from two separate databases. Each database contains n numerical values, so there are 2n values total and you may assume that no two values are the same. You’d like to determine the median of this set of 2n values, which we will define here to be the n th smallest value.

However, the only way you can access these values is through queries to the databases. In
a single query, you can specify a value k to one of the two databases, and the chosen database will return the k th smallest value that it contains. Since queries are expensive, you would like to compute the median using as few queries as possible.

Give an algorithm that finds the median value using at most O(log n) queries.

• The desciption of algorithm and the pseudo-code

• Subproblem reduction graph

• Prove the correctness

• The complexity of the algorithm

### 2 Divide and Conquer

Find the $k^{th}$ largest element in an unsorted array. Note that it is the $k^{th}$ largest element in the sorted order, not the $k^{th}$ distinct element.

INPUT: An unsorted array A and k.

OUTPUT: The $k^{th}$ largest element in the unsorted array A.

• The desciption of algorithm and the pseudo-code

• Subproblem reduction graph

• Prove the correctness

• The complexity of the algorithm

### 3 Divide and Conquer

Consider an n-node complete binary tree $T$ , where $n = 2^d − 1$ for some $d$. Each node $v$ of T is labeled with a real number $x_v$ . You may assume that the real numbers labeling the nodes are all distinct. A node $v$ of $T$ is a local minimum if the label $x_v$ is less than the label $x_w$ for all nodes $w$ that are joined to $v$ by an edge.

You are given such a complete binary tree $T$ , but the labeling is only specified in the following implicit way: for each node $v$, you can determine the value $x_v$ by probing the node $v$. Show how to find a local minimum of $T$ using only $O(\log n)$ probes to the nodes of $T$ .

• The desciption of algorithm and the pseudo-code

• Subproblem reduction graph

• Prove the correctness

• The complexity of the algorithm

### 8 Divide and Conquer

The attached file Q8.txt contains 100,000 integers between 1 and 100,000 (each row has a
single integer), the order of these integers is random and no integer is repeated.

1. Write a program to implement the Sort-and-Count algorithms in your favorite language, find the number of inversions in the given file.
2. In the lecture, we count the number of inversions in O(n log n) time, using the Merge-Sort idea. Is it possible to use the Quick-Sort idea instead ? If possible, implement the algorithm in your favourite language, run it over the given file, and compare its running time with the one above. If not, give a explanation.

1.Java源码如下：

2.不能用快排，因为在快排的过程中，每次选择的pivot两侧的数组都是乱序的，如果计算这两个数组包含的逆序对个数，时间复杂度为$O(n^2)$.

### 9 Divide and Conquer

Implement the algorithm for the closest pair problem in your favourite language.

INPUT: n points in a plane.

OUTPUT: The pair with the least Euclidean distance.

Java源码如下：