Divide and Conquer

Algorithms

• Divide and Conquer
  • Recursion Tree Method
  • [Master Theorem](#master\ method)
  • [Merge Sort](#merge\ sort)
  • Quicksort
  • [Maximum Subarray](#max\ subarray)
  • Closest Points
  • Convex Hull

---

Master Method

$T(n)=aT(n/b)+f(n)$

$a\ge 1$ and $b>1$ and $f(n)$ is asymptotically positive

1. if $f(n)=O(n^{({\log }_{b}a)-ϵ})$ for $ϵ>0$ then $T(n)=\Theta (n^{{\log }_{b}a})$
2. if $f(n)=\Theta (n^{{\log }_{b}a})$ then $T(n)=\Theta (n^{{\log }_{b}a}\lg n)$
3. if $f(n)=\Omega (n^{({\log }_{b}a)+ϵ})$ and $af(n/b)\le cf(n)$ for $c<1$ then $T(n)=\Theta (f(n))$

---

Merge Sort

Merge-Sort(A, p, r):
if p < r:
	q = floor((p + r) / 2)
	Merge-Sort(A, p, q)
	Merge-Sort(A, q + 1, r)
	Merge(A, p, q, r)	

Merge(A, p, q, r):
n1 = q - p + 1
n2 = r - q
L[n1]
R[n2]
for i = 0; i < n1; i++:
	L[i] = A[p + i]
for i = 0; i < n2; i++:
	R[i] = A[q + i + 1]
L[n1] = INT_MAX
R[n2] = INT_MAX
i = 0
j = 0
for k = p to r:
	if L[i] <= R[j]
		A[k] = L[i]
		i++
	else 
		A[k] = R[i]
		j++

---

Quicksort

Quicksort(A, p, r)
if p < r
	q = PARTITION(A, p, r)
	QUICKSORT(A, p, q - 1)
	QUICKSORT(A, q + 1, r)

Partition(A, p, r)
int x = A[r];
int i = p - 1;
for (j = p; j < r; j++) {
	if (A<=x) {
		i++;
		swap(A[i], A[j]);
	}
}
swap(A[i+1], A[r]);
return i + 1;

---

Max Subarray

1. Divide and Conquer

Max-Subarray(A, l, r)
if l == r
	return A[r]
m = (l + r) / 2
l_sum = Max-Subarray(A, l, m)
r_sum = Max-Subarray(A, m + 1, r)
c_sum = Max-Crossing(A, l, m, r)
return MAX(l_sum, r_sum, c_sum)

Max-Crossing(A, l, m, r)
l_sum = INT_MIN
sum = 0
for i = m to l
	sum += A[i]
	l_sum = MAX(sum, l_sum)
r_sum = INT_MIN
sum = 0
for i = m + 1 to r
	sum += A[i]
	r_sum = MAX(sum, r_sum)
return l_sum + r_sum

2. Sliding Window

Kadane(A, n)
best_sum = INT_MIN
curr_sum = 0
for i = 0 to n
	curr_sum = MAX(A[i], curr_sum + A[i])
	best_sum = MAX(curr_sum, best_sum)
return best_sum

---