14. Divide and Conquer
Society for Industrial and Applied Mathematics eBooks · 2010
14.1 Patterns within Patterns Recursive Tiling 14.2 N and Half N Merge Sort 14.3 Looking for Trouble Adaptive Interpolation Divide-and-conquer is a well-known strategy in both politics and war. It is equally prominent in computing. Indeed, many of the most important algorithms in use today have this attribute. The idea is to (a) partition the given problem into two or more independent subproblems of the same variety and then (b) obtain the overall solution by synthesizing the subproblem solutions. For example, suppose your boss asks you to alphabetize a deck of 128 cards, each having the name of a customer. You split the deck in half and ask coworker A to alphabetize cards 1–64 and coworker B to alphabetize cards 65–128. After you receive the two alphabetized half-decks, it is an easy matter to merge the two piles into the single, required alphabetized deck. The interesting thing about this approach is that coworkers A and B can apply the same problem-solving strategy. For example, A can delegate to coworkers 1 and 2 the task of alphabetizing cards 1–32 and 33–64, respectively. B can do the same with quarter-decks 65–96 and 97–128. The quarter-deck problems could also be subdivided, etc. The example illustrates the process of recursion, and in this chapter we learn how to program divide-and-conquer strategies using this technique. We start with a recursive tiling problem in which triangles are repeatedly subdivided into smaller triangles. By using graphics we are able to track visually the “dividing” and the “conquering.” Next, we develop a sorting procedure along the lines of the motivating example above. The method is called merge sort and it turns out to be dramatically more efficient than the methods of §8.2. Our final example involves the production of plots where the underlying function f is sampled nonuniformly across a given interval. The idea is to cluster f-evaluations in regions where f is highly nonlinear. The “discovery” of the nonlinearity zones is done through an interval subdivision process that is determined by estimating the quality of a linear approximation.