Chapter 5

This chapter deals with the Divide and Conquer problems involving recurrence relations.This method can sometimes improve O(n^2) time to O(nlogn) time.

This section introduces the first example in Divide and Conquer: mergesort. The idea of mergesort is to keep dividing a problem into two equal sizes, till the running time of dealing with the problem becomes constant, that is to T(2)⇐c. We need to find the relationship between each level of “division”, that is to T(2)⇐c. In order to achieve that, we need to find the running time used to join two parts together in each level, which is actually cn. Hence, we have: T(n)⇐2T(n/2)+cn. Two ways of analyzing the running time: 1, gradually “unroll” the recursion; 2, guess a solution. For the 1st method, the idea is to figure out the pattern of running time for each level and sum them up at the end. For the 2nd method, if we have good intuition, we simply plug in the guessed result and see if it satisfies our inequality. A stronger version of guessing is that we guessed out all the relevant constants. A weaker version is we leave the constants unknown and figure it out along the way. A natural “question” is, how do we attain such intuition? :P Readability is 6.

A more general case of the mergesort problem than dividing problem by 2 each time is dividing problem by q each time. Then the recurrence relationship becomes: T(n)⇐qT(n/2)+cn and T(2)⇐c The approach of analysing the running time in the “unrolling” way is similar with that presented in section 1: analyse a few levels and then identify a pattern, and then sum up all levels of recursion. The “guessing” way becomes more interesting in this case. Because the connecting time cn cannot cancel with anything here. Therefore, we slightly adjust the guess from kn^d to kn^d-ln so that the ln will do the cancellation. If we have a very special case, q=1, it is not hard to show that the running time is bounded by O(n). A related problem is to change the recurrence relationship a little: T(n)⇐2T(n/2)+O(n^2), from unrolling the recurrence we obtain that the bound of the running time os O(n^2). I wonder what application does this relationship has. Readability is 7, the modification of guessing part is fun to read.

This section talks about a concrete example using divide and conquer–counting inversion. The problem is to count how many inversions are there in a sequence of n numbers. The brute-force way is to check each pair which has a bad running time O(n^2). We want to use the divide and conquer method to improve the running time. What we do the merge-sort + count-sort algorithm. Basically, we look at two already sorted list and see how many inversions there are if combine them together-which can be counted in linear time when using a counter, then sort the combined list to add together with the other combined sorted list. The running time is then O(log(n)n) since the recurrence relationship is the T(n)⇐2T(n/2)+cn one. I think this way of counting inversion is smart. Readability is 7.

Here is another application of the divide conquer algorithm. The general idea is to divide the plane into two parts, find out the minimum distance of each part, compare both with the distances between points beside the boundary of the two planes and hence get a minimum distanced pair of the combined plane. The most difficult part to implement is the combining part. First it is not hard to conceive that let x be the smaller distance from the two planes to be combined, if the new minimum distance comes from between points from the two planes, then the points have to locate from the strip centered at the splitting vertical line with wideth 2x. Sort the points inside the strip according to their y coordinate in ascending order. Another smart observation is if si, sj are two points in the strip and |i-j|>=15 (or 12, or 7, the key is it to be a constant), then they must be apart more than x–I think it is very clever. This enables us to for each point only scan the 7 neighborhood above instead the entire collection of points in the strip, which only takes linear time instead of quadratic time. Hence the recursive relation is: T(n)⇐2T(n/2)+O(nlogn) (for sorting the points in the strip). =O(logn^2n) Readability is 8.

This section introduces another problem that uses the divide conquer algorithm–integer multiplication. This seemingly straight forward problem actually takes O(n^2) if using brute-force algorithm. But we can improve the running time using divide and conquer method. The first try is to divide the original problem into 4 subproblems: xy=x1y1+(x1y0)2^n/2+(x0y1)2^n/2+x0y0. However, the recurrence relationship T(n)⇐4T(n/2)+cn is still only bounded by O(n^2). But notice that if we only use 3 subproblems instead of 4, the running time can be reduced. We need to look at the problem slightly differently: xy=x1y1+(x1y1+x0y0+x1y0+x0y1-x1y1+x0y0)2^n/2+x0y0. =x1y1+(p-x1y1-x0y0)2^n/2+x0y0 where p=(x0+x1)(y0+y1). Now the recurrence relationship is T(n)⇐3T(n/2)+cn⇐O(n^1.59)

Readability is 7.