Chapter 5

Divide & Conquer notes

• Divide & conquer algorithms are characterized by the fact that they divide the input into smaller groups and solve the problem recursively.
• They're often used to get polytime to a lower polynomial.
• Mergesort is a D&C algorithm.
  • We divide the list to be sorted into smaller lists and sort each at the base level, then merges sorted lists.

• When there are more than two subproblems
  • For the first few levels, we have a problem of size n taking cn plus the recursive call time.
  • At the next level, we have q problems of size n/2, taking time cn/2 plus the recursive call times.
  • At the next level, we have q^2 problems of size n/4, taking time q^2*cn/4 time.
  • Thus we'll always have q^j distinct instances at level j, of size n/(2^j). Thus at level j we have time q^j(cn/(2^j).
  • After a lot of math, we get the important thing, which is that T(n)≤O(n^(log_2(q)).
    • If we apply partial substitution, we also get the same result.
• What if there's only one subproblem?
  • At level j we have one instance of size n/(2^j) and adds cn/(2^j) to the runtime, which converges as a sum to T(n) ≤ 2cn = O(n).
• Finally, for T(n) ≤ 2T(n/2) + O(n^2)
  • After some work (p 220, 221), we find that T(n) ≤ O(n^2).

• In ranking systems, we want to be able to count the inversions between two different rankings of the same objects. That is, if we take one list of rankings, we want to tell how many inversions are required to get to the other one.
• We recursively sort the list to be counted and the n find its inversions by merging back up.
• We sort the lists recursively, counting the number of inversions, then add the inversions for merging.
• We merge by maintaining a pointer into each list, initialized to the front. We keep count of the inversions. While neither list is empty, we add the smaller item being pointed to to the output list, and if the item in the rightmost list is smaller, we increment the number of inversions.
• This runs in O(nlogn) time for an n-element list.

• Consider a collection of n points in (x,y) space. We want to find the pair of points that are closest.
• We start by sorting those points in increasing x order.
• We then find the two points in the middle of the list of points and imagine a vertical line between them.
• We find the closest points on each side of the line
• We then find the closest points across the line, that is, the points closer together than the closest points on either side of the line.
  • Let d be the minimum distance between two points on either side.
  • Then we only have to look within d on each side of the line.
  • We divide this into d/2 by d/2 boxes, and for each box check the next 7 closest boxes.
• This only takes O(nlogn) time? DANG.