Chapter 5

Divide and conquer algorithms are algorithms that break the input into parts, solve the parts recursively, and then combine the solutions. When analyzing them, we will often look at recurrence relations, recursive functions that bound the running time of the algorithm.

The first algorithm we look at is the Mergesort Algorithm. In this algorithm, we break the input into two pieces, sort each recursively, and then merge the results together. The running time T(n) satisfies the recurrence relation T(n)⇐ 2T(n/2) + cn. To find a bound on the run time, we need to solve the recurrence relations.

We can solve recurrence relations in two ways: unrolling the recursion or substituting a possible solution. In the unrolling method, we analyze the first few levels, find a pattern, and sum over the levels of recursion. When trying substitution, we inductively prove our guess is correct. We can also use a weaker substitution if we are unsure of exact constants to help us find them. Solving the recurrence relation for mergesort shows the algorithm is O(nlogn).

Readability: 8

For a recurrence relation of T(n) ⇐ q*T(n/2) + cn, unrolling recursion shows the running time is:

O(n^log2(q)) when q > 2 O(n) when q =1

For the relation T(n) ⇐ 2*T(n/2) + cn^2, unrolling shows the running time is O(n^2).

Just as before, we find these by analyzing the first few levels, identifying a pattern, and summing over all the levels.

Readability: 8

One application of divide and conquer algorithms is counting inversions to determine taste similarity. In this problem, we order our rankings and a stranger's rankings. An inversion is any situation where the stranger ranked j before i while we ranked i before j. We want to count inversions to see how similar we are to the stranger.

A brute-force approach to this problem would take O(n^2) time to check every pair of rankings. We can use a divide and conquer algorithm to improve run time. By splitting the list in two, counting the inversions in each list, and combining in O(n) time, we can improve run time. But how to combine in O(n) time is not obvious - checking to find all the inversions that include a number from each half could take much longer. We are able to combine in O(n) time by adding the extra step of sorting, which makes counting inversions and merging back into a sorted list O(n). This allows us the count the inversions in O(nlogn) time (p 224).

Readability: 8

Another use for a divide and conquer algorithm is finding the closest pair of points in the plane. We can do this by finding the closest pair in each half of the plane and then combining. Again, combining the solutions is somewhat tricky. First, we note we only need to check distances within +- delta of the dividing line (where delta is the smallest distance found between points so far). Then we divide this region of width 2*delta into a grid with boxes of width .5 * delta. Now, we can see that there can be at most one point per box and we only need to check a constant number of boxes around each point to see if there is a pair with distance less than delta. So combining is O(n) and the algorithm has O(nlogn) run time (p 230).

Readability: 7

We can also improve integer multiplication run time using a divide and conquer algorithm. Again, our elementary school algorithm for multiplication would allow us to multiply in O(n^2) time but we want to improve it. We can use a divide and conquer algorithm that breaks each of the two numbers x and y into two parts (the higher order part and the lower order part) and then FOILs. This creates 4 sub problems of size n/2. Adding is O(n) so the combination cost is O(n) and we have a recurrence relation of T(n) ⇐ 4T(n/2) + cn. We can then slightly improve on this by using the relation xy = x1*y1 + (xy - x1*y1 - x0*y0) + x0*y0 to reduce the number of sub problems to 3, which gives us a run time of O(n^log2(3)) = O(n^1.59).

Readability: 8