Chapter 5 – Divide and Conquer

My notes on the assigned sections of Chapter 5 of Algorithm Design by Jon Kleinberg and Éva Tardos. This chapter details divide and conquer algorithms. A divide and conquer algorithm “breaks the input into several parts, solves the problem in each part recursively, and then combines the solutions” into an overall solution.

In the Mergesort algorithm, we divide the input into 2 pieces of equal size and solve the 2 subproblems. After solving the 2 halves by recursion, we combing the 2 results into an overall solution, spending linear time for everything. The recurrence relation for Mergesort is T(n) ⇐ T([n/2]) + T([n/2]) + cn. To solve such a recurrence you can either unroll the recursion or guess for the solution, substitute it into the recurrence relation, and then check and see if it works. Unrolling seems to be the most intuitive. Unrolling the recursion, we get that Mergesort takes O(nlogn).

Overall this section was very readable and interesting. I'd give it a 9/10 for both.

Mergesort creates recursive calls on q subproblems of size n/2 each and then combines them in O(n) time. For q > 2 subproblems, the functions bounded by O(n^logq). For 1 subproblem, the function is bounded by O(n). The summations mostly make sense, but I need to look at them a bit more in depth to make sense of them. Recurrence relations are still a bit tricky for me right now.

Overall I'd give this section a 6/10 on readability and a 7/10 on interestingness.

The inversion counting problem tends to arise in comparing two rankings. Any two indices i < j form an inversion if ai > aj. Or, in other words, if elements ai and aj are “out of order”. Brute force can solve this issue in O(n^2), but we can do better with MergeAnd Count and SortAndCount. These combine to run in O(nlogn) time.

Merge-and-Count(A,B):
  i=0
  j=0
  inversions = 0
  output = []
  while i < A.size and j < B.size:
    output.append( min(A[i], B[j]) )
    if B[j] < A[i]:
      inversions += A.size – i
    update i or j
  Append the remainder of the non-exhausted list to
  the output
  return inversions and output
  
Sort-and-Count(L)
  if list L has one element
    return 0 and the list L

  Divide the list into two halves A and B
  (iA, A) = Sort-and-Count(A)
  (iB, B) = Sort-and-Count(B)
  (i, L) = Merge-and-Count(A, B)
  total_inversions = iA + iB + i
  return total_inversions and the sorted list L

I'd give this section a 9/10 on readability and interestingness.