> For the complete documentation index, see [llms.txt](https://republic-of-cs.gitbook.io/e/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://republic-of-cs.gitbook.io/e/rcs.102/divide-and-conquer.md).

# ⌛ Divide & Conquer

> In [computer science](https://en.wikipedia.org/wiki/Computer_science), divide and conquer is an [algorithm design paradigm](https://en.wikipedia.org/wiki/Algorithm_design_paradigm). A divide-and-conquer [algorithm](https://en.wikipedia.org/wiki/Algorithm) [recursively](https://en.wikipedia.org/wiki/Recursion_\(computer_science\)) 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](https://en.wikipedia.org/wiki/Sorting_algorithm) (e.g., [quicksort](https://en.wikipedia.org/wiki/Quicksort), [merge sort](https://en.wikipedia.org/wiki/Merge_sort)), [multiplying large numbers](https://en.wikipedia.org/wiki/Multiplication_algorithm) (e.g., the [Karatsuba algorithm](https://en.wikipedia.org/wiki/Karatsuba_algorithm)), finding the [closest pair of points](https://en.wikipedia.org/wiki/Closest_pair_of_points_problem), [syntactic analysis](https://en.wikipedia.org/wiki/Syntactic_analysis) (e.g., [top-down parsers](https://en.wikipedia.org/wiki/Top-down_parser)), and computing the [discrete Fourier transform](https://en.wikipedia.org/wiki/Discrete_Fourier_transform) ([FFT](https://en.wikipedia.org/wiki/Fast_Fourier_transform)).[\[1\]](https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm#cite_note-1)

> Designing efficient divide-and-conquer algorithms can be difficult. As in [mathematical induction](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Recurrence_relation).

> Related
>
> * [**Decrease and Conquer**](https://erode-sengunthar.ac.in/wp-content/uploads/2023/07/DECREASE-AND-CONQUER-TECHNIQUE-1-3.pdf), Transform and Conquer

{% hint style="info" %}

#### Learning Material (understanding classic instances of Divide & Conquer)

* [**UCB CS170 \[1\] Introduction, Big-O Notation, Arithmetic**](https://www.bilibili.com/video/BV1BU4y1b7RK?p=1) (introduces **Karatsuba** & $$O(n\log n)$$ **Multiplication**)
* [**UCB CS170 \[2\] Divide-and-Conquer (Part 1)**](https://www.bilibili.com/video/BV1BU4y1b7RK?p=2)
* [**UCB CS170 \[3\] Divide-and-Conquer (Part 2)**](https://www.bilibili.com/video/BV1BU4y1b7RK?p=3\&vd_source=9621e539f648f22172899af8f4fc2ab7)
  {% endhint %}

## Practices

* [ ] [**VFMUL - Very Fast Multiplication**](https://www.spoj.com/problems/VFMUL/) (implement via **Karatsuba**)
* [ ] Median-Finding
* [ ] Merge Sort
* [ ] Quick Sort
* [ ] Convex Hull ([**Divide-and-Conquer**](https://web.ntnu.edu.tw/~algo/ConvexHull.html) method)

## Graduation Challenge

* [ ] Median-Finding