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

def 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)	
	
def 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

def Quicksort(A, p, r):
	if p < r:
		q = Partition(A, p, r)
		Quicksort(A, p, q - 1)
		Quicksort(A, q + 1, r)
		
def Partition(A, p, r):
	x = A[r]
	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

def 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)

def 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

def 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