====== Chapter 5 ======

===== 5.1: A First Recurrence: The Mergesort Algorithm =====

This section begins the chapter meant to break down and discuss several divide and conquer algorithms. We begin with the familiar Mergesort. This algorithm involves breaking up the input into smaller groups, organizing each group, and putting them back together. To use the book's words. The underlying concept is "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."
There are two main ways to solve a recurrence. The first is to unroll the recursion. The second way is guess and check.
To unroll a recursion, first you analyze the first few levels of the recursion. Then we identify a pattern. Then, we sum over all levels of recursion.
We can substitute (akin to guess and check) in two main ways. We can substitute an exact solution. Alternatively, we can test one that still contains variables for constants and look for solutions.

This section serves as a good introduction by applying the concept to a familiar problem. The section also did so concisely. I give the section a 7/10.

===== 5.2: Further Recurrence Relationships =====

This section attempts to break down recurrence relationships into classes in order to allow for generalization aimed at simplifying the problem and solution. In the case of Mergesort, we break up the problem into 2 subproblems, each half the size of the original. Another class of problem involves breaking up the problem into more than 2 subproblems. Similarly to before, we analyze the first few levels, identify a pattern, and sum over all levels of recursion. From this process, if q is the number of subproblems, we get that the class is bounded by O(n^(log2(q)). When working with problems with one subproblem, a similar process yields that the class of problems is bounded in O(n). From all of this, we are led to discuss what the number of subproblems does. Effectively, when q is 1, the run time comes from the top level, when q is greater than 2, it comes from the work done on the constant size subproblems. When q is 2, the work is divided evenly, which yields O(nlogn).

This section is extremely important. The last section simply illustrated a concept, but this section gives information on any recurrence problem we may face. It simply presents us with information (the upper bound on runtime for each class), but it also gives examples on how to perform our own analysis on various types of problems. As such, I give this section a 7/10.

===== 5.3: Counting Inversions =====

The beginning of this section discusses rankings. It gives collaborative filtering and meta-search tools as examples of applications that rely on rankings. In comparing sets of rankings, one can do so by counting the number of inversions. We then seek to find an algorithm that will count inversions. We ultimately will be able to count inversions in O(nlogn). We start by splitting the set in two. We then count the number of inversions in each half. Then we count the number of inversions that belong to the other half. We recursively sort the numbers in each set to aid us in our inversion search.
From this, we have the following pseudo code.
Merge-and-Count(A,B)

-Maintain a Current pointer into each list, initialized to point to the front elements

-Maintain a variable Count for the number of inversions, initialized to 0

-While both lists are nonempty:

--Let ai and bj be the elements pointed to by the Current pointer

--Append the smaller of these two to the output list

--If bj is the smaller element then

---Increment Count by the number of elements remaining in A

--Endif

--Advance the Current pointer in the list from which the smaller element was selected.

-EndWhile
-Once one list is empty, append the remainder of the other list
to the output

-Return Count and the merged list

We call this as a recursive subroutine to ultimately get the final number. This is done in the following pseudocode.

Sort-and-Count (L)

-If the list has one element then there are no inversions

-Else

--Divide the list into two halves:

---A contains the first [n/2] elements

---B contains the remaining [n/2] elements

--(rA, A) = Sort-and-Count (A)

--(rB, B) = Sort-and-Count (B)

--(r, L) = Merge-and-Count (A, B)

-Endif

-Return r=rA+rB+r, and the sorted list L

Ultimately, we are able to implement this in O(nlogn) as desired.


I felt this section was weaker than the previous one. I know it had to, but it only focused on one problem. I also found this section particularly boring, possibly because I have already read the other three. Regardless, I give it a 4.5/10.