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

Comparing rankings

• To determine similarity of rankings we need a metric
• Similarity metric: number of inversions between two rankings
  • My rank: 1, 2, …, n
  • Your rank: a₁, a₂, …, a_n
  • Indices i and j are inverted if i < j but a_i > a_j
  • Geometric series

Brute force solution

• Look at every pair (i, j) and determine if they are an inversion
• Requires Θ(n₂) time
  • Note: already an efficient algorithm but we can try to improve on run time

Divide and conquer

• Assume number represents where item should be in the list, i.e., where it is in someone else’s list
• Divide: separate list into two pieces
• Conquer: recursively count inversions in each half
• Combine: count inversions where ai and aj are in different halves, and return sum of three quantities

Merging two sorted lists while also counting the number of inversions between them.

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

The Sort-and-Count algorithm correctly sorts the input list and counts the number of inversions; it runs in O(n log n) time for a list with n elements.

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