Divide and Conquer Algorithms

• Process
  • Break up problem into several parts
  • Solve each part recursively
  • Combine solutions to sub-problems into overall solution
  • Use recurrences to analyze the runtime of divide and conquer algorithms
• Approaches to Solving Recurrences
  • Unroll recursion
    • Look for patterns in runtime at each level
    • Sum up running times over all levels
  • Substitute guess solution into recurrence
    • Check to make sure it works
    • Prove that it works using induction on n

Merge Sort

• Analyzing Merge Sort
  • General Template:
    • Break up problem of size n into two equal parts of size 1/2n → O(1)
    • Solve two parts recursively → T(n/2) + T(n/2)
    • Combine two solutions into overall solution → O(n)
  • Definition: T(n) = the number of comparisons to merge sort an input of size n
    • Recurrence relation: T(n) = 2T(n/2) + O(n)
      • T(n) =T(n/2) + c
    • Cost of each level in the tree is c*n
      • log n levels
    • Run time = log n

Binary Search

• Analyzing the algorithm
  • Instead of recursively solving 2 problems, solve q problems
    • Size of problems is still n/2
  • Combining solutions is still O(n)
  • Recurrence relation:
    • For some constant c, T(n) ≤ qT(n/2) + cn when n > 2 and T(2) < c
• Unroll the recurrence
  • T(n) = T(n/2) + c
    • Constant work at each level
    • Number of levels = log n
    • So the runtime is O(log n)
  • The case of q > 2
    • First level: qT(n/2) + cn
    • Next level: qT(n/4) + c(n/2)
    • qk problems at level k
    • size: n/2^k
    • Number of levels: log n
      • Each level takes q^k * c * (n/2^k) = (q/2)icn
    • Overall run time: O(n^{log q})

Merge-and-Count(A,B)
    Maintain a Current pointer into each list, initialized to point to the front elements
    Maintain a variable Count for the number of inversions, initialized to 0
    While both lists are nonempty:
        Let a<sub>i</sub> and b<sub>j</sub> be the elements pointed to by the Cuwent pointer
        Append the smaller of these two to the output list
        If b<sub>j</sub> is the smaller element then
            Increment Count by the number of elements remaining in A
        Endif
        Advance the Current pointer in the list from which the smaller element was selected.
    EndWhile
    Once one list is empty, append the remainder of the other list to the output
    Return Count and the merged list

Sort-and-Count(L)
    If the list has one element then there are no inversions
    Else
        Divide the list into two halves:
            A contains the first [n/2](ceiling) elements
            B contains the remaining [n/2](floor) elements
        (r<sub>A</sub>, A) = Sort-and-Count (A)
        (r<sub>B</sub>, B) = Sort-and-Count (B)
        (r, L) = Merge-and-Count (A, B)
    Endif
    Return r = r<sub>A</sub> + r<sub>B</sub> + r, and the sorted list L