What are other algorithms that use the divide-and-conquer paradigm aside from merge sort and quicksort?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ One example is QuickSelect. Another example is fast matrix multiplication. $\endgroup$ – Yuval Filmus Dec 3 '18 at 9:01
-
1$\begingroup$ We don't have a strict policy for list questions, but there is a general dislike. Please note also this and this discussion; you might want to improve your question as to avoid the problems explained there. If you are not sure how to improve your question maybe we can help you in Computer Science Chat? $\endgroup$ – Raphael♦ Dec 3 '18 at 17:03
-
2$\begingroup$ Also, one has to wonder if you've done any research on your own. Even Wikipedia has more examples! There are probably hundreds of examples in the literature. $\endgroup$ – Raphael♦ Dec 3 '18 at 17:04
Add a comment
|
$\begingroup$
$\endgroup$
There are many algorithms that uses the divide-and-conquer paradigm besides merge sort and quicksort.
"There is no accepted formal definition of the divide and conquer paradigm, and so we must regard this paradigm as an informal concept.", reads an answer by Yuval Filmus. I will use Wikipedia entry on divide-and-conquer as the reference to interpret its meaning.
That Wikipedia entry mentions quite a few examples. Here are some of them.
- Fast multiplication algorithms for large integers or polynomials. This includes Karatsuba multiplication (one of my favorites), Toom–Cook multiplication method and Fourier transform methods
- The planar case of closest pair of points. This is an unusual case as there are non-trivial but linear-time interactions between the smaller cases. This linearity is the key to its success.
- Top-down parsers. These are used widely in teaching and learning, although production compiler/parser generally uses bottom-up parsers for performance reasons. (Bottom-up parsers could be considered as using divide and conquer as well.)
- Mail sorting by post office where mail are sorted and delivered to smaller and smaller areas.
- [Strassen algorithm for matrix multiplication](multiplication(https://en.wikipedia.org/wiki/Strassen_algorithm)
As Raphael commented, there are probably hundreds of examples in the literature. Here are a few simple or notable ones.
- Quickselect as mentioned by Yuval's comment. This includes median of the medians algorithm as its special case. This double recursive algorithm is probably more subtle and ingenious then you might have thought. Yuval has also devised an divide-and-conquer algorithm to solve a recent question on how to find a pair of near numbers.
- Maximum subarray by divide and conquer. However, Kandane's algorithm is better in this case.
- Maximum single-sell profit. Here divide-and-conquer is beaten by dynamic programming, as what happens to the previous problem of maximum subarray.
We can also relate many structural decomposition techniques to divide and conquer. Whenever we are using the recursive nature of a tree graph, it could be considered an application of divide and conquer. Whenever we are using the Jordan blocks of a matrix, it could be considered likewise. When you reduce a problem about a graph to each of its connected component, it could be considered likewise. In this sense, divide-and-conquer appears even more pervasive.
There are also many examples that are better classified as decrease and conquer. Some notables of them are binary search, exponentiation by squaring, Johnson–Trotter algorithm that lists all permutations. Whether we or you would like to consider them as divide-and-conquer (proper) is up to our or your preferences. If you do, it may "help you conceptualize the algorithms that you learn in the course. If you don't find this helpful, just ignore it", says Yuval.
If you have plenty of time to kill, you may enjoy the following tedious exercise.
Exercise. Check which algorithms in the list of algorithms by Wikipedia use divide-and-conquer.
