divide & conquer
Concept
Divide and Conquer
- divide into smaller sub-problems
- solve sub-problems recursively
- merge the solutions
Counting Inversions
- pair of indices
such that , basically out of order pairs - merge sort adjacent
CountInv(A): // returns (sorted copy of A, number of inversions in A)
if length(A) <= 1:
return (A, 0)
split A into consecutive halves AL and AR
(L, leftCount) = CountInv(AL)
(R, rightCount) = CountInv(AR)
i = 0
j = 0
crossCount = 0
S = empty list
while i < length(L) and j < length(R): // just have to check inversions between the two sorted halves, O(n), since sorted
if L[i] <= R[j]:
append L[i] to S
i = i + 1
else:
append R[j] to S
crossCount = crossCount + (length(L) - i)
j = j + 1
append remaining elements of L to S
append remaining elements of R to S
return (S, leftCount + rightCount + crossCount)
Lemma
Invariant
TODO
Correctness
- induction iwht base case of 1
Runtime
Maximum Subarray
- subarray can be, in either half, or span the boundary
- how to find subarrays that cross the divide?
MaxSubarray(A, lo, hi): // returns (start, end, sum)
if lo == hi:
return (lo, hi, A[lo])
m = floor((lo + hi) / 2)
L = MaxSubarray(A, lo, m)
R = MaxSubarray(A, m + 1, hi)
// search for subarray starting from the middle/boundary, O(n)
sum = 0
bestLeftSum = -infinity
for i = m down to lo:
sum = sum + A[i]
if sum > bestLeftSum:
bestLeftSum = sum
bestLeftIndex = i
sum = 0
bestRightSum = -infinity
for j = m + 1 to hi:
sum = sum + A[j]
if sum > bestRightSum:
bestRightSum = sum
bestRightIndex = j
C = (bestLeftIndex, bestRightIndex,
bestLeftSum + bestRightSum)
return the tuple among L, R, C with largest sum
Crossing lemma
- the two halves can be maximized separately
Correctness
- induction from base cas of 1
Runtime
Find Median/Select rank
- quick sort adjacent
Select(A, k):
choose pivot p
// partitioning, O(n)
L = elements of A smaller than p
E = elements of A equal to p
R = elements of A greater than p
if k <= length(L):
return Select(L, k)
if k <= length(L) + length(E):
return p
return Select(R, k - length(L) - length(E))
Partition lemma
Recursive contract
- when recursing right
Correctness
-
induction on array size, base case 1
-
in L, recurse with rank k
-
in E, return p
-
in R, recurse with rank k - |L| - |E|
Runtime
Median of Medians
- more deterministic, version of above
// ranks start at 1
Select(A, k): // returns
if length(A) <= 5:
sort A
return A[k]
// constant time to sort a small array, n/5 times, O(n)
divide A into groups of at most 5
M = list of the groups' medians
p = Select(M, ceil(length(M) / 2)) // find the median of medians
// partitioning, O(n)
L = elements of A smaller than p
E = elements of A equal to p
R = elements of A greater than p
if k <= length(L):
return Select(L, k)
if k <= length(L) + length(E):
return p
return Select(R, k - length(L) - length(E))
Pivot quality lemma
Runtime
Closest Pair
- yea wtf
TODO
Integer Multiplication
Matrix Multiplication
Application
- median of medians
Select(A, k): // ranks start at 1
if length(A) <= 5:
sort A
return A[k]
divide A into groups of at most 5
M = list of the groups' medians
p = Select(M, ceil(length(M) / 2))
L = elements of A smaller than p
E = elements of A equal to p
R = elements of A greater than p
if k <= length(L):
return Select(L, k)
if k <= length(L) + length(E):
return p
return Select(R, k - length(L) - length(E))
Majority element
- majority if it appears
times
Candidate(A, L, R): // returns (candidate, weight)
if L == R:
return (A[L], 1)
M = floor((L + R) / 2)
(x, p) = Candidate(A, L, M)
(y, q) = Candidate(A, M + 1, R)
if p == 0: // no majority in Left
return (y, q)
if q == 0: // no majority in Right
return (x, p)
if x == y: // same candidate, add weights
return (x, p + q)
if p > q: // Left majority dominates
return (x, p - q)
if q > p: // Right majority dominates
return (y, q - p)
return (NONE, 0) // different majority but equal weight on both sides
Majority(A):
if A is empty:
return "No Majority"
(x, weight) = Candidate(A, 1, length(A))
if weight == 0:
return "No Majority"
count = number of occurrences of x in A
if count > floor(length(A) / 2):
return x
return "No Majority"
- lemma
- consider
- correctness
- induction on array size, base case 1
- runtime