# Can divide-and-conquer be used for anything else besides Quick-sort and the Merge-sor

This topic is 4423 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I am still learning about divide and conquer and it seems to be very limited. I know its used with Quick-sort and Merge-Sort but what else?

##### Share on other sites
Binary search... kind of.

##### Share on other sites
Convex hulls, closest two points, collision detection or PVS in any quadtree/octree/BSP/space partitioning, almost any algorithm that relies on trees (such as tries, suffix trees, etc), heaps and heaps of distributed algorithms (including most Google algorithms), Karatsuba multiplication, and many, many other unnamed algorithms used in day-to-day work.

##### Share on other sites
As a couple of specific examples: There's the Cooley-Tukey FFT algorithm - a Fourier transform of size N is divided into two of size N/2, then the FFT algorithm is run on those recursively, then the results are combined.
There's also Strassen's algorithm for multiplying matrices. Calculating C=AB with n×n matrices can be done by splitting each into four n/2×n/2 matrices, then calculating two sets of seven n/2×n/2 matrices from them, and then recursively multiplying those pairs of matrices and eventually combining the results.

##### Share on other sites
I know it's not really "real-world" use, but the divide-and-conquer paradigm was needed to solve the problem Points in this year's IOI (International Olympiad in Informatics). Coincidentally (or not? :) it was the hardest problem of the competition, and only 1 contestant was able to fully solve it. The problem statement is here, and the solution here.

Cheers!

1. 1
Rutin
29
2. 2
3. 3
4. 4
5. 5

• 13
• 13
• 11
• 10
• 13
• ### Forum Statistics

• Total Topics
632959
• Total Posts
3009467
• ### Who's Online (See full list)

There are no registered users currently online

×