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;
}