Description
Divide and Conquer
1. Erickson, Jeff. Algorithms (p.49, q. 6). Use recursion trees to solve each of the following recurrences.
(a) C(n) = 2C(n/4) + n
2
; C(1) = 1.
(b) E(n) = 3E(n/3) + n; E(1) = 1.
CS 577 Assignment 5 – Divide and Conquer
2. Kleinberg, Jon. Algorithm Design (p. 246, q. 1). 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 nth 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 kth
smallest value that it contains. Since queries are expensive, you would like to compute the median using
as few queries as possible.
(a) Give an algorithm that finds the median value using at most O(log n) queries.
(b) Give a recurrence for the runtime of your algorithm in part (a), and give an asymptotic solution to
this recurrence.
Page 2 of 6
CS 577 Assignment 5 – Divide and Conquer
(c) Prove correctness of your algorithm in part (a).
3. Kleinberg, Jon. Algorithm Design (p. 246, q. 2). 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 ai > aj .
We motivated the problem of counting inversions as a good measure of how different two orderings are.
However, this measure is very sensitive. Let’s call a pair a significant inversion if i < j and ai > 2aj .
(a) Give an O(n log n) algorithm to count the number of significant inversions between two orderings.
Page 3 of 6
CS 577 Assignment 5 – Divide and Conquer
(b) Give a recurrence for the runtime of your algorithm in part (a), and give an asymptotic solution to
this recurrence.
(c) Prove correctness of your algorithm in part (a).
Page 4 of 6
CS 577 Assignment 5 – Divide and Conquer
4. Kleinberg, Jon. Algorithm Design (p. 246, q. 3). You’re consulting for a bank that’s concerned about
fraud detection. They have a collection of n bank cards that they’ve confiscated, suspecting them of
being used in fraud.
It’s difficult to read the account number off a bank card directly, but the bank has an “equivalence
tester” that takes two bank cards and determines whether they correspond to the same account.
Their question is the following: among the collection of n cards, is there a set of more than n
2
of them
that all correspond to the same account? 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.
(a) Give an algorithm to decide the answer to their question with only O(n log n) invocations of the
equivalence tester.
(b) Give a recurrence for the runtime of your algorithm in part (a), and give an asymptotic solution to
this recurrence.
Page 5 of 6
CS 577 Assignment 5 – Divide and Conquer
(c) Prove correctness of your algorithm in part (a).
5. Implement the optimal algorithm for inversion counting in either C, C++, C#, Java, Python, or Rust.
Be efficient and implement it in O(n log n) time, where n is the number of elements in the ranking.
The input will start with an positive integer, giving the number of instances that follow. For each
instance, there will be a positive integer, giving the number of elements in the ranking. A sample input
is the following:
2
5
5 4 3 2 1
4
1 5 9 8
The sample input has two instances. The first instance has 5 elements and the second has 4. For each
instance, your program should output the number of inversions on a separate line. Each output line
should be terminated by a newline. The correct output to the sample input would be:
10