Divide-and-conquer algorithm

In computer science, divide and conquer, originally a political maxim, designates an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

The divide-and-conquer technique is the basis of efficient algorithms for many problems, such as sorting (e.g., quicksort, merge sort), multiplying large numbers (e.g., the Karatsuba algorithm), finding the closest pair of points, syntactic analysis (e.g., top-down parsers), SAT solving, and computing the discrete Fourier transform (FFT).

Designing efficient divide-and-conquer algorithms can be difficult. As in mathematical induction, it is often necessary to generalize the problem to make it amenable to a recursive solution. The correctness of a divide-and-conquer algorithm is usually proved by mathematical induction, and its computational cost is often determined by solving recurrence relations.

n to move a tower of height p of sub-problems of size ~ cn time, where n<2, the algorithm takes time upper-bounded by n2. Then, the running times are as follows:

• if the number of subproblems 2"}}'>q>2, then the divide-and-conquer algorithm's running time is bounded by cn2 time, and there are 2 subproblems where each has size log2n nested recursive calls to sort n quicksort calls that would do nothing but return immediately. Increasing the base cases to lists of size 2 or less will eliminate most of those do-nothing calls, and more generally a base case larger than 2 is typically used to reduce the fraction of time spent in function-call overhead or stack manipulation.

  Alternatively, one can employ large base cases that still use a divide-and-conquer algorithm, but implement the algorithm for predetermined set of fixed sizes where the algorithm can be completely unrolled into code that has no recursion, loops, or conditionals (related to the technique of partial evaluation). For example, this approach is used in some efficient FFT implementations, where the base cases are unrolled implementations of divide-and-conquer FFT algorithms for a set of fixed sizes. Source-code generation methods may be used to produce the large number of separate base cases desirable to implement this strategy efficiently.

  The generalized version of this idea is known as recursion "unrolling" or "coarsening", and various techniques have been proposed for automating the procedure of enlarging the base case.

  Dynamic programming for overlapping subproblems

  edit

  For some problems, the branched recursion may end up evaluating the same sub-problem many times over. In such cases it may be worth identifying and saving the solutions to these overlapping subproblems, a technique which is commonly known as memoization. Followed to the limit, it leads to bottom-up divide-and-conquer algorithms such as dynamic programming.

  See also

  edit
  Wikimedia Commons has media related to Divide-and-conquer algorithms.

Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (31 July 2009). Introduction to Algorithms. MIT Press. ISBN 978-0-262-53305-8.

↑ Brassard, G., and Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.

↑ Anany V. Levitin, Introduction to the Design and Analysis of Algorithms (Addison Wesley, 2002).

1 2 3 Donald E. Knuth, The Art of Computer Programming: Volume 3, Sorting and Searching, second edition (Addison-Wesley, 1998).

↑ Heideman, M. T., D. H. Johnson, and C. S. Burrus, "Gauss and the history of the fast Fourier transform", IEEE ASSP Magazine, 1, (4), 14–21 (1984).

↑ Karatsuba, A.; Ofman, Yu. (1963). "Multiplication of Multidigit Numbers on Automata". Soviet Physics Doklady. 7: 595–596. Bibcode:1963SPhD....7..595K.

1 2 Frigo, M.; Johnson, S. G. (February 2005). "The design and implementation of FFTW3" (PDF). Proceedings of the IEEE. 93 (2): 216–231. Bibcode:2005IEEEP..93..216F. CiteSeerX 10.1.1.66.3097. doi:10.1109/JPROC.2004.840301. S2CID 6644892.{{cite journal}}: Cite uses deprecated parameter |citeseerx= (help)

↑ Radu Rugina and Martin Rinard, "Recursion unrolling for divide and conquer programs" in Languages and Compilers for Parallel Computing, chapter 3, pp. 34–48. Lecture Notes in Computer Science vol. 2017 (Berlin: Springer, 2001).