This is an old revision of the document!
Table of Contents
Chapter 5: Divide and Conquer
Divide and conquer algorithms break the problem into smaller sections, solve those sections, and then put the sections back together. This is done in the hopes that we will be able to reduce the run time of the algorithm.
Chapter 5.1: A First Recurrence: The Mergesort Algorithm
The Mergesort algorithm splits a list of numbers in half and in half again and then sorts each side and then puts the two halves together. We then designate T(n) to be the worst-case running time of n input. Then for some c T(n) < 2T(n/2)+cn when n>2. This represents the run time of one recurrence relation. We can solve recurrences in two ways: unroll the recursion or guess and check. Unrolling the recurrence means that we analyze the first few levels and at each level, it takes at most cn run time. Then we can find a pattern, and we can sum over this pattern to find the running time. The unrolling method takes O(nlogn) time. Guessing and checking the algorithm, we use a proof by induction to show that T(n) = cnlogn. Since T(n) is the worst case run time, then we can see that the guessing and checking method will also run in O(nlogn). We can also use a partial substitution method that is a little weaker than the other substitution metho but will run in the same time.
We are still going over this is class so it is a little confusing. I also had forgotten what Mergesort was, so this was a good refresher. I'll need to continue to remember things from 112.
I would give this section a 7/10 as it was helpful but a little confusing for me.
Chapter 5.2: Further Recurrence Relations
This section generalizes recurrence relations and allows us to create a formula that we can use to determine the run time of later recurrence relations. The generalized formula (on page 215 of the text) must be broken down into 3 cases. The first when q=1, the second when q=2, and finally when q>2. (We went over the case where q>2 Wednesday in class). In order to determine the run time of the q>2 case, we unroll the recurrence relation T(n) ≤ qT(n/2) + cn and find that at any level j, we have q^j instances, each with size n/2^j, which will perform (q/2)^j*cn work. Then if we sum over these levels, we can
Practicing unrolling the recurrence relations in class was incredibly helpful as was having concrete examples of algorithms that have that particular recurrence relation.
