DIVIDE AND CONQUER ALGORITHMS THEORY

Nur Aimielia binti Rahim #1, Mohamed Faidz Mohamed Said #2

# Universiti Teknologi MARA
70300 Seremban, Negeri Sembilan, MALAYSIA

1 nuraimieliarahim@gmail.com
2 faidzms@ieee.org 

 
Abstract— Divide and Conquer is an algorithms design paradigm based on multi-branches recursion. This algorithm works by recursively breaking down a problem into two or more sub-problems, until these become simple enough to be answered directly. The arrangement common to a class of Divide and Conquer algorithms is represented by a program scheme which a theorem is presented that relates the functionality of this algorithm based on its structure and the functionalities of its sub algorithms. Various strategies for planning these algorithms ascend from this theorem and they are used to formally derive algorithms for sorting a list of numbers, forming the Cartesian product of two sets, and finding the convex hull of a set of planar points. Lastly, these algorithms had many beneficial qualities that make it a very significant algorithms design paradigm.

Keywords: Divide, Conquer, algorithm, recursion, branches 



REFERENCES

[1] 	Smith, D. R. (1985). The Design of Divide and   Conquer Algorithms. Science of Computer Programming, 5, 3754-5158

[2] 	Aho, A. V., Hopcroft, J. E., & Ullman, J. D. (1983) Data  Structures and Algorithms.

[3] 	J. Bentley. (1980), Multidimensional Divide and Conquer, Comnt ACM 23 214-229.

[4]	D.R. Smith, (1983). The Structure of Divide and Conquer Algorithms, Technical Report NPS 52-83-002, Naval Postgraduate School, Monterey, CA 

[5] 	Smith, D. R., & Lowry, M. R. (1990). Algorithm Theories and Design Tactics. Science of computer programming, 14(2), 305-321.

[6] 	Smith, D. R. (1987). Applications of a Strategy for Designing Divide-and-Conquer Algorithms. Science of Computer Programming, 8(3), 213-229.

[7] 	Messinger, E. B., Rowe, L. A., & Henry, R. R. (1991). A Divide-and-Conquer Algorithm for The Automatic Layout of Large Directed Graphs. Systems, Man and Cybernetics, IEEE Transactions on, 21(1), 1-2

[8] 	Chandrasekaran, S., & Gu, M. (2004). A Divide-and-Conquer Algorithm for The Eigendecomposition of Symmetric Block-Diagonal plus Semiseparable Matrices. Numerische Mathematik, 96(4), 723-731.

[9] 	Carmona, J., Cortadella, J., & Kishinevsky, M. (2009). Divide-and-Conquer Strategies for Process Mining. In Business Process Management (pp. 327-343). Springer Berlin Heidelberg.

[10]	Stach, W., Kurgan, L., Pedrycz, W., & Reformat, M. (2005). Genetic Learning of Fuzzy Cognitive Maps. Fuzzy sets and systems, 153(3), 371-401.

[11]	Stach, W., Kurgan, L., Pedrycz, W., & Reformat, M. (2004). Learning Fuzzy Cognitive Maps with Required Precision using Genetic Algorithm Approach.Electronics Letters, 40(24), 1.

[12]	Krishnakumar, A. S., & Morf, M. (1986). Eigenvalues of a Symmetric Tridiagonal Matrix: A Divide and Conquer Approach. Numerische Mathematik,48(3), 349-368.

[13]	Shmoys, D. B. (1997). Cut Problems and Their Application to Divide-and-Conquer. Approximation algorithms for NP-hard problems, 192-235.