Chapter 5

Section 5.1 introduces the divide and conquer style of algorithmic problem solving with the Merge-Sort algorithm. The algorithm can be represented by the following recurrence equation: T(n) = 2T(n/2) + cn for all n > 2. This algorithm basically splits the list of items down recursively until it gets to a “base case” where there are only one or two items. The comparison at this point is a simple greater than or less than. The sorted pieces are then combined back together into a full list. The runtime of this algorithm is O(nlogn).

I give this chapter a 6 for readability and a 6 on the interesting scale.

Section 5.2 dives deep into recurrence relations. It stars with by explaining the simple recurrence relation that arose in the mergesort algorithm. The mergesort is a good example since it has two subproblems and the total work per level does not change. As section 5.2 continues into recurrence relations of algorithms with more than two subproblems, we find that the work per level begins to increase, bounding those algorithms in O(n^logq), with q being the number of subproblems the algorithm has. The chapter goes onto show that recurrence relations with only one subproblem run in O(nlogn) time because the work being done decreases every level.

This chapter was cool. I give it an 8 on the interesting scale and a 7 for readability.

Section 5.3 was very helpful for me in illuminating the counting inversions problem. While I had a rough understanding of the algorithm during class, the book made the entire concept much clearer.

The concept behind counting inversions is to compare the similarity of two lists to each other. The idea is to sort and count the inversions in each list, then sort and count the inversions between the now sorted lists. The sorting and inversion of each individual list are not too difficult, but comparing the inversions and sorting the two distinct lists requires a new algorithm. It turns out not to be too crazy, just maintaining pointers on each element of each list, comparing those elements, and counting inversions, adding elements to the final list, and moving pointers along as necessary.

Like I said, I found the book to be very helpful in regards to this topic. I give this chapter a 9 for readability and a 9 on the interesting scale.