====== Chapter 5 Divide and Conquer algorithms ====== ===== Section 5.1 The Mergesort Algorithm ===== The mergesort algorithm with which we are all familiar provides an excellent opportunity to study recurrence relations. As with many divide-and-conquer algorithms, the behvior of mergesort can be described with a template such as: divide the input into two equally-sized pieces, recursively solve those pieces and then recombine the results into an overall solution. For mergesort, as with many algorithms of this nature, it will "bottom out" at a base case of constant size. The recurrence relation for mergesort is T(n) <= 2T(n/2) + cn since it takes constant time to divide the input up into two pieces of size n/2 and then T(n/2) time solving each piece before they are combined back together, again in linear time. This type of analysis can be completed by a method known as "unrolling" the recursion. Unrolling the recursion of a problem involves a few steps. The first consists of analysing the first few levels to determine how much time each of these levels will take. Eventually, a pattern will make itself evident to the careful observer and so the next step is observing that pattern and formalizing it. Finally, the algorithm analyst must sum the running time for each level of recursion to find the total running time of the algorithm. There are also methods using substitution and partial substitution to solve for the running time but these seem to me to be unhelpful unless you already have a solid guess for the running time. Even in the case that you have a solid guess for running time though, it is still a guess and more likely to lead you down the wrong path than unrolling the recursion, so why not just unroll it from the start in order to save yourself time, frustration and guesswork? These two substitution sections at the end are my main issue with the section 5.1 since they seem to add now value, at least in my mind. Maybe I simply don't understand them though. ===== Section 5.2 Further Recurrence Relations ===== This section explores a more general version of recurrence problem than the previous one did. This type of recurrence creates recursive calls on q subproblems of size n/2. Mergesort uses q = 2, but can in fact be 1 or >2. Generalizing the inequality from the previous section gives us: T(n) <= qT(n/2) + cn when n > 2. For algorithms that split the input into more than 2 subproblems we can still use the same unrolling technique discussed in the previous section. Consider a problem where q = 3. The first level will have 1 problem of size n, which will be split into 3 problems of size n/2, which is then split into 9 problems of size n/4 and so on. This makes it obvious that work is increasing throughout the running of the problem. To identify the pattern, we can notice that the number of problems per level is simply our q (3) raised to the power which is equal to the level number. Additionally, the size of each problem is n/(2^r) where r is the number of the level. Finally, summing over the levels of recursion, we can say that any function satisfying the inequality mentioned in the first paragraph with q > 2 is bounded by O(n^log₂q). Again the section mentions an alternative method of finding the bound using partial substitution, but I can't honestly say that I understand how this method adds anything that unrolling the substitution will not. Another case to be considered is one where q = 1. In the first level, there is one problem of size n. Then one problem of size n/2, then one problem of size n/4 and so on down the line. We can see that the amount of work is decreasing. It is clear from analyzing just these few levels that layer r will have size n/2^j and it will contribute cn/2^j to the running time. Finally, summing the levels of recursion will give us T(n) <= 2cn = O(n). Thus, any T satisfying the inequality from paragraph 1 with q = 1 is bounded by O(n). It is interesting to note these differences in running times all fall around q = 2, with radically different behavior observed when q = 1 and when q = 3. It leads me to wonder what happens when q is a non-integer number between 1 and 2. Finally, we can consider what happens in the case that the algorithm "divides up the input into two different pieces of size n/2, solves the subproblems by recursion, and then combines the two into an overall solution, spending quadratic time instead for the initial division and final recombining." This is different from the problems such as mergesort since it takes quadratic time for the division and recombining instead of linear. So the problems take this form: T(n) <= 2T(n/2) + cn². Instinctively, one would like to say that this should be bounded by O(n² log n) however it is actually bounded by O(n²) due to how quickly n² decreases as it is replaced with n/(2^j) ===== Section 5.3 Counting Inversions ===== The motivation for this type of problem is based in the analysis of a set of rankings compared to a different set of rankings of the same items. A way to compare these sets of ordered items is to look at how many pairs are "out of order" from one ranking to another. An inversion occurs when indices ii>a_j. Looking at every pair of numbers would require O(n²)time, so to find the O(n log n) solution, we must find one that does not even have to evaluate every value. This solution is to divide the list of numbers into two half-sized sublists then counting the number of inversions in each half and finally counting inversions between the two halves. The merge-and-count algorithm is the solution that hinges on this principle. Merge-and-count works by maintaining pointers to the front of each sublist and removing the lesser one from its sublist when it is added to what will become the sorted list. The algorithm must also count the number of inversions in addition to ordering the list. It does this by increasing the count of inversions by whatever the remaining size of the first subset of rankings is. This operation counts a possibly large number of inversions in constant time. Thus, O(n log n) running time. I found this chapter fairly straightforward to understand.