Divide-and-Conquer Learning Algorithm

A Divide-and-Conquer Learning Algorithm is an Machine Learning Algorithm that employs an Algorithm Strategy where a Task is divided into smaller Subtask of the same type and then solved Recursively.

• AKA: Divided and Conquer Algorithm Strategy, Divide and Conquer, Divided and Conquer Strategy.
• Context:
  • It can be implemented by a Divide-and-Conquer Learning System to solve a Divide-and-Conquer Learning Task.
  • It can combine the solutions to the subproblems into a solution to the original problem.
  • It generally requires at least two recursive calls
• Example(s):
  • Quicksort Algorithm, (also uses Randomization).
  • Mergesort Algorithm.
  • …
• Counter-Example(s):
  • Binary Tree Lookup, uses only one Recursive Step.
  • Separate-and-Conquer Algorithm.
• See: Dynamic Programming Algorithm.

---

---

References

2021

• (Wikipedia, 2021) ⇒ https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm Retrieved:2021-5-16.
  • In computer science, divide and conquer is 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), 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 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.

2017

• (Sammut & Webb, 2017) ⇒ Claude Sammut (editor), and Geoffrey I. Webb (editor). (2017). “Divide-and-Conquer Learning”. In: (Sammut & Webb, 2017).
  • QUOTE: The divide-and-conquer strategy is a learning algorithm for inducing Decision Trees. Its name reflects its key idea, which is to successively partition the dataset into smaller sets (the divide part) and recursively call itself on each subset (the conquer part). It should not be confused with the separate-and-conquer strategy which is used in the Covering Algorithm for rule learning.

2009

• (Wikipedia, 2009) ⇒ http://en.wikipedia.org/wiki/Algorithm#Classification_by_design_paradigm
  • Another way of classifying algorithms is by their design methodology or paradigm. There is a certain number of paradigms, each different from the other. Furthermore, each of these categories will include many different types of algorithms. Some commonly found paradigms include:
  • Divide and conquer. A divide and conquer algorithm repeatedly reduces an instance of a problem to one or more smaller instances of the same problem (usually recursively) until the instances are small enough to solve easily. One such example of divide and conquer is merge sorting. Sorting can be done on each segment of data after dividing data into segments and sorting of entire data can be obtained in the conquer phase by merging the segments. A simpler variant of divide and conquer is called a decrease and conquer algorithm, that solves an identical subproblem and uses the solution of this subproblem to solve the bigger problem. Divide and conquer divides the problem into multiple subproblems and so conquer stage will be more complex than decrease and conquer algorithms. An example of decrease and conquer algorithm is the binary search algorithm.

---