Jump to content
  • Advertisement
Sign in to follow this  
chadsxe

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.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!