⌛ Divide & Conquer

In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem

The divide-and-conquer technique is the basis of efficient algorithms for many problems, such as sorting (e.g., quicksort, merge sort), multiplying large numbers (e.g., the Karatsuba algorithm), finding the closest pair of points, syntactic analysis (e.g., top-down parsers), and computing the discrete Fourier transform (FFT).[1]

Designing efficient divide-and-conquer algorithms can be difficult. As in mathematical induction, it is often necessary to generalize the problem to make it amenable to a recursive solution. The correctness of a divide-and-conquer algorithm is usually proved by mathematical induction, and its computational cost is often determined by solving recurrence relations.

Related

• Decrease and Conquer, Transform and Conquer

Learning Material (understanding classic instances of Divide & Conquer)

• UCB CS170 [1] Introduction, Big-O Notation, Arithmetic (introduces Karatsuba & $O(n\log n)$ Multiplication)

• UCB CS170 [2] Divide-and-Conquer (Part 1)

• UCB CS170 [3] Divide-and-Conquer (Part 2)

Practices

• VFMUL - Very Fast Multiplication (implement via Karatsuba)

• Median-Finding

• Merge Sort

• Quick Sort

• Convex Hull (Divide-and-Conquer method)

Graduation Challenge

• Median-Finding