Sign in to follow this  
chadsxe

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

Recommended Posts

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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this