Comment on page

# Divide and Conquer

### Three Steps

• Divide the problem into multiple subproblems in smaller size.
• Conquer the subproblems recursively; set a straight forward way for base case.
• Combine the solutions to the subproblems into the solution for the original problem.

### Master Theorem

• recurrence relation:
$T(n)=a T\left({\frac{n}{b}}\right)+f(n)$
• $a>1$
the number of subproblems in the recursion
• $b>1$
the factor by which the subproblem size is reduced in each recursive call
• and
$f$
is asymptotically positive (positive for sufficiently large
$n$
)
• base case:
$T(c)$
is a constant when
$c$
is a constant
• compare
$n^{\log_{b}{a}}$
with
$f(n)$
and this will lead to three regimes (>, =, <)
• in recursion tree, compare root with leaves and see which part dominates
• more reference: CLRS book page 94

### Example Code: Merge Sort

#include <iostream>
#include <vector>
int merge(std::vector<int>& A, int start, int end, int middle, std::vector<int>& B){
// combine
int i = start;
int j = middle;
for (int k = start; k<= end; ++k){
if (i < middle && (j > end || A[i] <= A[j]))
B[k] = A[i++];
else
B[k] = A[j++];
}
for (int k = start; k<= end; ++k){
A[k] = B[k];
}
}
int mergeSort(std::vector<int>& A, int start, int end, std::vector<int>& B){
// divide and conquer
if (end == start)
return 0;
int middle = (start + end + 1) / 2;
mergeSort(A, start, middle - 1, B);
mergeSort(A, middle, end, B);
merge(A, start, end, middle, B);
}
int main(){
int n;
std::cin >> n;
std::vector<int> score(n);
std::vector<int> temp(n);
for (int k = 0; k < n; ++k)
std::cin >> score[k];
mergeSort(score, 0, n-1, temp);
std::cout << n << std::endl;
for (int k = 0; k < n; ++k)
std::cout << score[k] << std::endl;
return 0;
}