Text Book - Algorithm Design by Jon Kleinberg and Eva Tardos

Chapter 5 - Divide and Conquer

Exercises-

Q1. 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.

Q2. Recall the problem of finding the number of inversions. As in the text, we are given a sequence of n numbers a1,..., an, which we assume are all distinct, and we define an inversion to be a pair i < j such that a_i > a_j.

We motivated the problem of counting inversions as a good measure of how different two orderings are. However, one might feel that this measure is too sensitive. Let's call a pair a significant inversion if i < j and a_i > 2a_j. Give an O(n log n) algorithm to count the number of significant inversions between two orderings.

Q3. Suppose you're consulting for a bank that's concerned about fraud detection, and they come to you with the following problem. They have a collection of n bank cards that they've confiscated, suspecting them of being used in fraud. Each bank card is a small plastic object, containing a magnetic stripe with some encrypted data, and it corresponds to a unique account in the bank. Each account can have many bank cards corresponding to it, and we'll say that two bank cards are equivalent if they correspond to the same account.

It's very difficult to read the account number off a bank card directly, but the bank has a high-tech "equivalence tester" that takes two bank cards and, after performing some computations, determines whether they are equivalent.

Their question is the following: among the collection of n cards, is there a set of more than n/2 of them that are all equivalent to one another? Assume that the only feasible operations you can do with the cards are to pick two of them and plug them in to the equivalence tester. Show how to decide the answer to their question with only O(n log n) invocations of the equivalence tester.

Q4. You've been working with some physicists who need to study, as part of their experimental design, the interactions among large numbers of very small charged particles. Basically, their setup works as follows. They have an inert lattice structure, and they use this for placing charged particles at regular spacing along a straight line. Thus we can model their structure as consisting of the points {1, 2, 3, . . . , n} on the real line; and at each of these points j, they have a particle with charge q_j. (Each charge can be either positive or negative.)

They want to study the total force on each particle, by measuring it and then comparing it to a computational prediction. This computational part is where they need your help. The total net force on particle j, by Coulomb's Law, is equal to

It's not hard to analyze the running time of this program: each invocation of the inner loop, over i, takes O(n) time, and this inner loop is invoked O(n) times total, so the overall running time is O(n²). The trouble is, for the large values of n they're working with, the program takes several minutes to run. On the other hand, their experimental setup is optimized so that they can throw down n particles, perform the measurements, and be ready to handle n more particles within a few seconds. So they'd really like it if there were a way to compute all the forces F_j much more quickly, so as to keep up with the rate of the experiment. Help them out by designing an algorithm that computes all the forces F_j in O(n log n) time.

Q5. Hidden surface removal is a problem in computer graphics that scarcely needs an introduction: when Woody is standing in front of Buzz, you should be able to see Woody but not Buzz; when Buzz is standing in front of Woody,... well, you get the idea.

The magic of hidden surface removal is that you can often compute things faster than your intuition suggests. Here's a clean geometric example to illustrate a basic speed-up that can be achieved. You are given n non vertical lines in the plane, labeled L₁,..., L_n, with the i^th line specified by the equation y = a_ix + b_i. We will make the assumption that no three of the lines all meet at a single point. We say line L_i is uppermost at a given x-coordinate x₀ if its y-coordinate at x₀ is greater than the y-coordinates of all the other lines at x₀: a_ix₀ + b_i > a_jx₀ + b_j for all j ≠ i. We say line L_i is visible if there is some x-coordinate at which it is uppermost-intuitively, some portion of it can be seen if you look down from "y =∞."

Give an algorithm that takes n lines as input and in O(n log n) time returns all of the ones that are visible. Figure 5.10 gives an example.

Q6. 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 xv 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 xv 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.

Q7. Suppose now that you're given an n × n grid graph G. (An n × n grid graph is just the adjacency graph of an n × n chessboard. To be completely precise, it is a graph whose node set is the set of all ordered pairs of natural numbers (i, j), where 1≤ i ≤ n and 1≤ j ≤ n; the nodes (i, j) and (k, l) are joined by an edge if and only if |i - k|+|j - l|= 1.)

We use some of the terminology of the previous question. Again, each node v is labeled by a real number xv; you may assume that all these labels are distinct. Show how to find a local minimum of G using only O(n) probes to the nodes of G. (Note that G has n² nodes.)