====== Chapter 5: Divide and Conquer ====== ===== Section 1: A First Recurrence: The Mergesort Algorithm ===== * **Summary:** Divide and conquer - break the input into several parts, solve the problem in each part recursively, combine the solutions to the subproblems into an overall solution. Recurrence relations are necessary to discuss the running time of these algorithms. These algorithms might not improve running time as much as in the previous section (because they're reducing the degree of a polynomial running time instead of solving a naturally exponential problem in polynomial time like before), but they're still really important. Mergesort sorts a list by dividing it into two equal halves, sorting each half separately by recursion, and then merging the two sorted halves. Pattern: "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." You need a base case for these problems - in this case when the list is 2 elements long, we sort it the "normal" way. The recurrence relation is: T(n) <= 2T(n/2)+cn for n>2 and T(2) <= c. There are two ways to figure out running time from this: unrolling the recurrence or substitution. We went through both of these in class, the notes are good, and it's on p.212. We didn't discuss partial substitution in class, but it's also useful. Substitution methods can help you work out the exact constants when you've got a guess about the general form of the solution. * **Insights and Questions:** I am curious about this concept of "exact constants" in running times. I don't know why I didn't think about it earlier. Is it just the number of steps or is it based on the complexity of each step? I know that sometimes a really big constant can make a "better" algorithm (i.e. better O-notationally) not run as fast, but I am not really sure still how they get this constant or what it means. * **Readability:** I found this section very readable, like the others. No exciting comments on that front. ===== Section 2: Further Recurrence Relations ===== * **Summary:** More generally, there are problems where you can split the input of size n into q subproblems of size n/2 and recombine solutions in constant time. This gives the recurrence relation T(n) <= qT(n/2)+cn for n>2 and T(2)<=c. They go into how to figure out running times by unrolling the recursion and substitution and partial substitution. We did the first two in class so see those notes. You end up with an O(n^(logbase2q)) running time. Then they go into the case of one subproblem. I guess I'll have to trust them that this is useful (it won't come up until Ch 13), but it seems strange to me that this would ever happen. This problem's bounded by O(n), which is interesting because that means that half of the work for the entire problem is done at the top "level." A final recurrence relation: T(n)<=2T(n/2)+O(n^2). Based on this: "divide the input into two pieces of equal size; solve the two subproblems separately by recursion; and then combine the two results into an overall solution, spending quadratic time for the initial division and final recombining." They unroll the recurrence and show that it's bounded by O(n^2) instead of O(logn*n^2) like you might expect. That's because the work decreases a lot at every level and it turns out to be a converging geometric sum. * **Insights and Questions:** Just the one already sort of mentioned. I can't imagine a problem that could be solved with q=1. * **Readability:** I think these sections would have been easier to read with more motivation for these recurrence relations, but it was generally pretty readable. ===== Section 3: Counting Inversions ===== * **Summary:** The mergesort technique can be applied to a problem that doesn't directly involve sorting numbers. The problem has to do with rankings. A lot of sites online use collaborative filtering, so they try to figure out what else you might like based on your preferences and other people's preferences (they look for people with similar taste). This also comes up with meta-search tools, where you give different search engines the same query and try to synthesize results by looking for similarities and differences in the results. So, really it's a matter of comparing rankings. We rate the similarity of two rankings based on the number of inversions between them (this may not be the best way to do this, but it's not terrible, and it works for our case). See class notes if some of this is unclear ... the pictures will help more than any explanation. We need an algorithm to count up these inversions. The simplest way to do it would be to look at every pair of numbers and determine if they are inverted. That would take O(n^2) time, which isn't bad, but it can be improved upon to get an O(nlogn) running time. Algorithm: split the list into two, count the number of inversions in each half separately, then count the number of inversions where the numbers belong in different halves. We have to figure out how many inversions there are for numbers that belong in the opposite half in O(n) time, though. We also need to sort the entire list in that step. We use a technique like we use for the combine step of mergesort to do this, but we add a step that lets us know how many inversions there were (again, the class notes and pictures say it better than I can write it). The book then goes into the exact algorithms for this problem and show by comparison to the mergesort problem that this gives us an O(nlogn) running time. * **Insights and Questions:** None really. I'm curious about how you deal with real rankings. There are so many more problems, like not every element in one person's list is in every other person's ... how do you compare them then? If they have completely different ordering but all of the same elements are they more or less similar than someone who has some of the same orderings but different elements? Oh man, there's just so much to think about with the real-life problem. * **Readability:** As always, I found it very easy to read. ===== Section 4: Finding the Closest Pair of Points ===== * **Summary:** This problem also uses the same techniques. Given a set of n points in a plane, find the pair that's the closest together. They talk about the history of the problem and get into notation, but I'm going to assume I'll remember that or that I'll find the notation intuitive. The 1-D problem is useful to think about. If all of the points are along a line, then you just need to sort them on the line (O(nlogn) time) and then you can go through and just look at the next point along the line and keep track of the minimum distance and which points it was between. The 2-D problem can be solved by sorting according to one coordinate, splitting the points into two halves, finding the closest two points in each half recursively, and then combining. The combining step is tricky, though, because the two closest points might have gotten split up between the two halves. Whichever of the pair of points that was closest in each half is closer, we take the distance that they are from each other, call it d, and only look at points within d of the "center" line we drew down the middle to split the points into two halves. Then there's more trickiness that goes into this that shows that we have to look at only 7 or less other points for every point in that strip (which makes that step linear). If there are two points that are closer than d in the strip, then they're the closest pair of points, otherwise we stick with the one we found before. The book goes into more formal algorithms for this and explains the trickiness of proving that you have to look at at most 7 other points for each point (remember the boxes of side length d/2). They also analyze the algorithm to prove that it actually finds the closest pair of points, and they bound the running time with O(nlogn). * **Insights and Questions:** They say that you can get the running time down to O(n) with randomization. This isn't necessarily directly in reference to this particular problem, but in general I just don't understand how randomization can help solve problems more quickly. Hmm. * **Readability:** Great! They've gotten away from the end-of-section proof that it works and analysis of running time. I'm not sure if it helps or if it would be just as good to do it as they give the algorithm, but it was interesting that it came back. ===== Section 5: Integer Multiplication ===== * **Summary:** This problem will reduce running time by having more than two recursive calls at each level. The elementary school way of multiplying two numbers takes O(n^2) time, which is good, but it could be better. Instead of doing it that way, though, you can separate n-bit binary numbers (they say it works for other number systems, too) into two n/2-bit binary numbers (the first n/2 digits, "high-order" digits, x1 and y1 and the last n/2 digit, "low order" digits, x0 and y0). Then xy = x1y1*2^n + (x1y0+x0y1)*2^n/2 + x0y0 ... anyway, the equation's not the point. The point is that you trade multiplication for addition (which takes O(n) time). So the recurrence relation is T(n) <= 4*T(n/2) + cn, but that just gives us O(n^2) time back ... so there was no advantage to doing this. So instead, you can modify it a little so that you do determine x1y1 and x0y0 by recursion and get the outermost terms explicitly and the middle term by subtracting x1y1 and x0y0 from (x1+x0)(y1+y0). They show that algorithm. So now the recursive relation is T(n)<= 3*T(n/2)+cn, which results in an O(n^logbase2(3)) or O(n^1.59) running time, which is a significant improvement! * **Insights and Questions:** This is a really interesting example of how differently computers and people think. There's no way it would be easier or more efficient for a human to solve this problem this way. It's also an interesting example of a tradeoff between efficiency and intuitiveness ... hmm. * **Readability:** I thought that, once again, this section was very readable!