Chapter 5: Divide and Conquer

'The Mergesort Algorithm sorts a given list of numbers by first dividing them into two equal halves, sorting each half separately by recursion, and then combining the results of these recursive halves.' The abstract behavioral template for many common divide-and-conquer algorithms is this: 'Divide the input into two pieces of equal size; solve the two subproblems on these pieces separately by recursion; and then combine the two results into an overall solution, spending only linear time for the initial division and final recombining.' This type of recursive methodology requires a base case, having it 'bottom out' on inputs of some constant size. In the case of Mergesort, once input has been reduced to size 2, we stop the recursive process and sort the two elements in one comparison. For each recursive algorithm, there is a recursive relation to describe its processes. It follows the formula T(n) = cT(k) + O(l), where c is the number of subproblems, k is the factor by which the input size decreases, and l is the cost of recombining the subproblems into a single problem. The two basic ways to go about solving a recurrence are: 1) unrolling the recursion, accounting for the running time of across the first few levels and identifying a pattern of the recursion, and then summing the run times of all the levels to find the total run time, and 2) Start with a guess for the solution, substitute into the recurrence relation, and check that it works. For 1), we first analyze the first few levels, identify a pattern, and then sum over all levels of recursion. 'Any function T(-) satisfying T(n) ⇐ 2T(n/2) + O(n) is bounded by O(nlogn), when n > 1. For 2) we first take our guess for what the run time is, plug it into the recurrence relation, and check to see if completes the induction argument. There is also a weaker form of substitution when we are unsure of the whole run-time of our guess. This section was very easy to understand having talked about it in class, and given prior experience with the Mergesort Algorithm. I would give it a 9/10.

The Mergesort algorithm serves as a very good example of recursion that we can use to generalize for a much larger class of divide-and-conquer algorithms. These algorithms follow the same pattern of splitting the initial sample size into smaller samples of size n/2, however we want to look at cases where the number of smaller sizes is not binary, (i.e. q > 2). Analyzing the first few levels, we see that the total work per level is increasing as we proceed through the recursion. Identifying a pattern, we see that the total work performed at level k is q^k(cn/(2^k), which is equivalent to (q/2)^k*cn. Summing this over all levels of recursion, we see that the total run time for an algorithm of this setup is O(n^(logq)). Any algorithm that follows the recurrence relation of T(n) = qT(n/2) + O(n) with q > 2 will have a run time of the form O(n^(logq)). Considering an algorithm that follows that form with q = 1, we see that the work per level is actually decreasing as we proceed through the recursion. The pattern for the cost per level l is cn/2^l, and thus the sum of the total work of the algorithm is O(n). Any function with that form will always be bounded by O(n). Thus from this analysis, we see that the value of q in the algorithm has a major effect on the total run time. When q = 1, the run time is linear, when q = 2, the run time is O(nlogn), when q >2, the run time is O(n^(logq)). A related recurrence to those of which we have been looking at is T(n) = 2T(n/2) + O(n^2). This recurrence follows the structure of: divide the input into two pieces of equal size; solve the two subproblems on these pieces separately by recursion; and then combine the two results into an overall solution, spending quadratic time for the initial division and final recombining. Analyzing the first few levels, we see that the total amount of work per level is decreasing, as opposed to mergesort where the total work stays the same per level. Identifying a pattern, we see the total work per level l is cn^2/2l. Summing the total work over all levels, we find that the total run time is O(n^2). The beginning of this section was easy to follow having studied it in class and worked on the problem set. The second part was a bit more confusing, with regards to the different algorithm. I would give this section a 6/10.