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)=aT(nb)+f(n)T(n)=a T\left({\frac{n}{b}}\right)+f(n)
  • a>1a>1
    the number of subproblems in the recursion
  • b>1b>1
    the factor by which the subproblem size is reduced in each recursive call
  • and
    ff
    is asymptotically positive (positive for sufficiently large
    nn
    )
  • base case:
    T(c)T(c)
    is a constant when
    cc
    is a constant
  • compare
    nlogban^{\log_{b}{a}}
    with
    f(n)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;
}