divide & conquer

Work in Progress

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

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

th smallest number in unsorted list

  • 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