Divide-and-Conquer

The divide-and-conquer paradigm involves three steps at each level of the recursion:

1. Divide the problem into a number of subproblems that are smaller instances of the same problem.
2. Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.
3. Combine the solutions to the subproblems into the solution for the original problem.

When can we use Divide and Conquer?

• Original problem is easily decomposable into subproblems (we don not want to see “overlap” in the subproblems).
• Combining solutions is not too costly.
• Subproblems are not overly unbalanced.

Example - Counting inversions

Collaborative filtering:

• matches users preferences (movies, music, …)
• determine users with similar tastes
• recommends n ew things to users based on preferences of similar users

Goal: given an unsorted array $A[\mathrm{1..}n]$, find the number of inversions in it.

Def

$(i,j)$ is an inversion if $i<j$ and $A[i]>A[j]$

Example: with A=[1,5,2,6,3,8,7,4], we get

$(2,3),(2,5),(2,8),(4,5),(4,8),(6,7),(6,8),(7,8)$

Remark: we show the indices where inversions occur

Remark: easy algorithm (two nested loops) in $\Theta (n^2)$

random

Idea: solve the problem twice in size $\frac{n}{2}$ (we assume $n$ is a power of 2). Then the optimal subarray (if not empty)

1. is completely in the left half $A[\mathrm{1..}n/2]$
2. or is completely in the right half $A[n/2+\mathrm{1..}n]$
3. or contains both $A[n/2]$ and $A[n/2+1]$ (cases mutually exclusive)

PQ1

Tower Domination: There are $n$ towers defined by their integer coordinates $x_i$ and $y_i$, $i=1,2,...,n$. We say that a tower $i$ dominates a tower if and only if

$$(x_i>x_{j)}\wedge (y_i>y_{j)}\vee (x_i<x_{j)}\wedge (y_i<y_j)$$

That is, the coordinates of tower $i$ are either both greater, or both smaller, than the coordinates of tower $j$. Define the dominance factor of tower $i$ as the total number of towers dominated by it. Your task is to design a divide-and-conquer algorithm to compute the dominance factor of each tower.

My solution:

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
struct Tower {
	int index;
	pair<int, int> tower;
};
 
int divide_and_conquer_dominance(vector<Tower>& towers, vector<int>& dominance_factor, size_t start, size_t end) {
	if (start >= end) {
		return 0;
	}
	
	size_t mid = start + (end - start) / 2;
	
	divide_and_conquer_dominance(towers, dominance_factor, start, mid);
	divide_and_conquer_dominance(towers, dominance_factor, mid + 1, end);
	
	// merge the dominance factor
	//copy towers to a new array temp
	vector<Tower> temp(towers.begin() + start, towers.begin() + end + 1);
	
	//perform merge sort
	size_t i = 0, j = mid - start + 1;
	size_t k = start;
	
	while (i < mid - start + 1 && j < end - start + 1) {
		if (temp[i].tower.second < temp[j].tower.second) {
			dominance_factor[temp[i].index] += end -start - j + 1;
			towers[k++] = temp[i++];
		} else {
			dominance_factor[temp[j].index] += i;
			towers[k++] = temp[j++];
		}
	}
	
	while (i < mid - start + 1) {
		towers[k++] = temp[i++];
	}
	
	while (j < end - start + 1) {
		dominance_factor[temp[j].index] += i;
		towers[k++] = temp[j++];
	}
	return 0;
}
 
int main() {
	int n;
	cin >> n;
	vector<pair<int, int>> coordOfTowers(n);
	vector<int> dominance_factor(n, 0);
	
	vector<Tower> myTowers(n);
	for (int i = 0; i < n; ++i) {
		cin >> myTowers[i].tower.first >> myTowers[i].tower.second;
		myTowers[i].index = i;
	}
	
	// call libary function to sort the towers based on towers.first (x coordinate)
	sort(myTowers.begin(), myTowers.end(), [](Tower a, Tower b) {
		return a.tower.first < b.tower.first;
	});
	
	divide_and_conquer_dominance(myTowers, dominance_factor, 0, myTowers.size() - 1);
	
	// Output the dominance factor
	for (size_t i = 0; i < dominance_factor.size(); ++i) {
		cout << dominance_factor[i] << " ";
	}
	cout << endl;
	return 0;
}

Examples of use

• Merge Sort