Can divide-and-conquer be used for anything else besides Quick-sort and the Merge-sor
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?
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.
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.
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.
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!
Cheers!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement