This section introduces the Divide and Conquer algorithms as a whole by starting with the MergeSort algorithm. The text first covers the logic behind the algorithm. We take an input of size n, split this input into two pieces of equal size, solve the two subproblems separately by recursion, and then combine these two solutions to form an overall solution for the initial problem. And we only spend linear time on the division and recombining process. They also lay out the recurrence relation for Mergesort: T(n) ⇐ 2T(n/2)+cn when n>2 and T(2)⇐c.
The text then goes into the two ways we can solve recurrence relations to see the runtime complexity of an algorithm with a structure such as that of Mergesort. The first strategy is unrolling the recurrence and the second is to guess-and-check and prove your guess by means of induction. I far prefer unrolling the recurrence rather than induction. It makes more intuitive sense to me and the book does a good job reinforcing the material covered in class. The text uses the structure of unrolling and induction to prove that the mergesort algorithm runs in O(n log n) time. The text also briefly mentions a method to prove a recurrence relation using partial substitution, but I did not find this nearly as intuitive as simply using a regular inductive argument.
I would rate the readability at 9/10.
This section dives into a few different recurrence relations that are very similar to the mergesort relation covered in 5.1. The first of these is the general class of algorithms created by letting there be q subproblems (rather than 2) of size n/2 each and then combine those results in O(n) time. The text lets q=3 and dives into the example. They unroll the recurrence and give us some properties about summations such that we can derive the running time of this recurrence relation. It ends up that, with q>2 and subproblems of size n/2, we have that the relation is bounded by O(n^log_2(q)). I understood this argument. But the book also walks through a way of solving this using partial substitution, which again, I found far less intuitive than unrolling the relation as is. I was still able to follow the argument, but I far prefer unrolling the relation.
The text then covers the case of just one subproblem. That is, instead of generating more than one subproblem from T(n), we generate just one and are asked to find the recurrence relation. It turns out that this is fairly simple. We still have log(n) levels, and each subproblem (assuming we are starting at n) has size n/2. So we are creating a very similar sum as we created with q, another geometric series. And it ends up that T(n) ⇐ 2cn = O(n). The book's argument to prove this is clear and succinct.
The text ends the section by covering a related recurrence: T(n) ⇐ 2T(n/2)+O(n^2). This is the same as mergesort, except instead of the linear combine/recombine time, it is quadratic. Intuitively, we would think that this would be bounded by O(n^2log(n)). However, it turns out that n^2 changes the magnitude of the bound. The book walks through this clearly in identifying the pattern on page 221, but the convergent geometric series in this example sums similarly to the case when we have just one subproblem, which ends up yielding a runtime of O(n^2).
I would rate the readability of this section at 8/10. Some parts were difficult to follow(partial substitution). However, others flowed very smoothly.
The section begins by discussing a problem. In this section, the book seeks to address the problem surrounding rankings. If we have two sets of rankings, and we want to investigate how closely related this set of rankings is to another set, this could tell us whether or not people have similar rankings. And a way to quantify this subjective relation is by means of counting inversions.
The brute force way of doing this is, given two sets of numbers with corresponding positions, we could examine every pair of numbers and see if they are inverted, which would yield a runtime of O(n^2). We seek to shrink this down to O(nlogn).
In order to do this, we create and use two separate algorithms. The first of these is the Merge-and-Count algorithm. In this algorithm, we are given as input two sorted lists. We initialize a pointer to the front of each of these lists and maintain a variable count (to count inversions) starting at 0. While both of our input lists of nonempty, we let a_i and b_j be the elements pointed to by the Current pointer, append the smaller of these two to the output list, if b_j is the smaller element then we increment count by the number of elements remaining in A, then after that, we advance the Current pointer in the list from which the smaller element was selected. (endwhile) And once one of the two lists is empty, append the remainder of the other list to the output (the new sorted list). Note that the runtime of the Merge-and-Count algorithm is O(n).
Now, we can use this algorithm to create a new algorithm to count inversions in a given unsorted list. The text calls this algorithm Sort-and-Count. This algorithm takes a list as input. If the list has one element then there are no inversions. Otherwise, it divides the list into two halves, A containing the first [n/2] elements and B containing the remaining [n/2] elements. We then let (r_A,A) = Sort-and-Count(A), (r_B,B) = Sort-and-Count(B), and (r,L) = Merge-and-Count(A,B). Note the original input list is called L. And since Merge-and-Count runs in O(n) time, and we will divide the list log(n) to count inversions, our Sort-and-Count algorithm will run in O(n log n) time.
I would rate the readability of this section at 8/10.