Divide & Conquer Algorithm Explained
Divide & Conquer is a powerful algorithmic paradigm that solves a problem by recursively breaking it down into smaller subproblems of the same or related type, until these subproblems become simple enough to be solved directly. The solutions to the subproblems are then combined to produce the solution to the original problem.
Algorithm
The Divide & Conquer paradigm generally involves the following three steps:
- Divide: The original problem is divided into smaller subproblems that are similar to the original problem but smaller in size.
- Conquer: The subproblems are solved recursively. If the subproblem is small enough, it is solved directly (base case).
- Combine: The solutions to the subproblems are combined to obtain the solution to the original problem.
Mathematics
The mathematical analysis of Divide & Conquer algorithms often involves recurrence relations. A recurrence relation is an equation that defines a function in terms of its values on smaller inputs. For example, the time complexity of a Divide & Conquer algorithm that divides a problem of size $n$ into $a$ subproblems of size $n/b$ and takes $O(n^k)$ time to combine the solutions can be expressed by the following recurrence relation:
$T(n) = aT(n/b) + O(n^k)$
The solution to this recurrence relation can be found using the Master Theorem, which provides a way to determine the asymptotic behavior of many recurrence relations that arise in the analysis of Divide & Conquer algorithms.
Master Theorem:
Given a recurrence relation of the form:
$T(n) = aT(n/b) + f(n)$
where $a \geq 1$, $b > 1$, and $f(n)$ is an asymptotically positive function, we can determine the asymptotic behavior of $T(n)$ as follows:
- If $f(n) = O(n^{\log_b a - \epsilon})$ for some constant $\epsilon > 0$, then $T(n) = \Theta(n^{\log_b a})$.
- If $f(n) = \Theta(n^{\log_b a})$, then $T(n) = \Theta(n^{\log_b a} \log n)$.
- If $f(n) = \Omega(n^{\log_b a + \epsilon})$ for some constant $\epsilon > 0$, and if $af(n/b) \leq cf(n)$ for some constant $c < 1$ and all sufficiently large $n$, then $T(n) = \Theta(f(n))$.
Time and Memory Complexity
- Time Complexity: The time complexity of a Divide & Conquer algorithm depends on how the problem is divided and how the subproblem solutions are combined. As mentioned above, recurrence relations and the Master Theorem are used to analyze this. Common examples include:
- Merge Sort: O(n log n)
- Quick Sort: Average case O(n log n), Worst case O(n^2)
- Binary Search: O(log n)
- Memory Complexity: The memory complexity also depends on the specific algorithm. Divide & Conquer algorithms often involve recursion, which uses stack space.
- Merge Sort: O(n) (due to the auxiliary array)
- Quick Sort: Average case O(log n), Worst case O(n) (due to recursion stack)
- Binary Search: O(1) (for iterative version), O(log n) for recursive
Easy Problems
Problem 1: Binary Search (Codeforces - Hypothetical)
Problem Statement (Hypothetical): Given a sorted array of integers `arr` and a target value `target`, find the index of the `target` in `arr`. If the `target` is not found, return -1.
Input Example:
arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23
Output Example:
5
C++ Code:
#include <iostream>
#include <vector>
int binarySearch(const std::vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // Avoid overflow
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
int main() {
std::vector<int> arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int target = 23;
int index = binarySearch(arr, target);
std::cout << index << std::endl;
return 0;
}
Problem 2: Find Minimum in Rotated Sorted Array (Codeforces - Variation)
Problem Statement (Variation): Suppose an array of length n sorted in ascending order is rotated between 1 and n times. Given the rotated array `nums`, find the minimum element of this array.
Input Example:
nums = [4, 5, 6, 7, 0, 1, 2]
Output Example:
0
C++ Code:
#include <iostream>
#include <vector>
#include <algorithm>
int findMinRotatedSortedArray(const std::vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left];
}
int main() {
std::vector<int> nums = {4, 5, 6, 7, 0, 1, 2};
int minVal = findMinRotatedSortedArray(nums);
std::cout << minVal << std::endl;
return 0;
}
Intermediate Problems
Problem 3: Merge Sort (Codeforces - Conceptual Adaptation)
Problem Statement (Conceptual Adaptation): Given an unsorted array of integers, sort the array using the Merge Sort algorithm.
Input Example:
arr = [12, 11, 13, 5, 6, 7]
Output Example:
[5, 6, 7, 11, 12, 13]
C++ Code:
#include <iostream>
#include <vector>
void merge(std::vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
std::vector<int> L(n1);
std::vector<int> R(n2);
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(std::vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6, 7};
mergeSort(arr, 0, arr.size() - 1);
for (int num : arr)
std::cout << num << " ";
std::cout << std::endl;
return 0;
}
Problem 4: Quick Sort (Codeforces - Conceptual Adaptation)
Problem Statement (Conceptual Adaptation): Given an unsorted array of integers, sort the array using the Quick Sort algorithm.
Input Example:
arr = [10, 7, 8, 9, 1, 5]
Output Example:
[1, 5, 7, 8, 9, 10]
C++ Code:
#include <iostream>
#include <vector>
#include <algorithm>
int partition(std::vector<int>& arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
return (i + 1);
}
void quickSort(std::vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
std::vector<int> arr = {10, 7, 8, 9, 1, 5};
quickSort(arr, 0, arr.size() - 1);
for (int num : arr)
std::cout << num << " ";
std::cout << std::endl;
return 0;
}
Hard Problem
Problem 5: Closest Pair of Points (Codeforces - Conceptual Adaptation)
Problem Statement (Conceptual Adaptation): Given a set of points in a 2D plane, find the distance between the closest pair of points.
Input Example:
points = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (30, 41)]
Output Example:
3.60555 (Distance between (2, 3) and (5, 1))
C++ Code:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <float.h>
struct Point {
int x, y;
};
double dist(Point p1, Point p2) {
return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
double bruteForce(const std::vector<Point>& points, int left, int right) {
double min_dist = DBL_MAX;
for (int i = left; i < right; ++i) {
for (int j = i + 1; j <= right; ++j) {
min_dist = std::min(min_dist, dist(points[i], points[j]));
}
}
return min_dist;
}
double closestPair(std::vector<Point>& points, int left, int right) {
if (right - left <= 3) {
return bruteForce(points, left, right);
}
int mid = left + (right - left) / 2;
double dl = closestPair(points, left, mid);
double dr = closestPair(points, mid + 1, right);
double d = std::min(dl, dr);
std::vector<Point> strip;
for (int i = left; i <= right; ++i) {
if (std::abs(points[i].x - points[mid].x) < d) {
strip.push_back(points[i]);
}
}
std::sort(strip.begin(), strip.end(), [](const Point& a, const Point& b) {
return a.y < b.y;
});
for (int i = 0; i < strip.size(); ++i) {
for (int j = i + 1; j < strip.size() && (strip[j].y - strip[i].y) < d; ++j) {
d = std::min(d, dist(strip[i], strip[j]));
}
}
return d;
}
int main() {
std::vector<Point> points = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {30, 41}};
std::sort(points.begin(), points.end(), [](const Point& a, const Point& b) {
return a.x < b.x;
});
double minDistance = closestPair(points, 0, points.size() - 1);
std::cout.precision(5);
std::cout << std::fixed << minDistance << std::endl;
return 0;
}