01.Divide and Conquer

Divide and Conquer paradigm

Divide and conquer is just one of several powerful techniques for algorithm design, which often leads to efficient algorithms. These algorithms can generally be easily analyzed using recurrences and the Master Theorem. A general DandC algorithm is built by:

1. Divide problem in sub-problems
2. Conquer sub-problems
3. Combine sub-problems to solve the main problem

Merge Sort

Merge Sort is the typical example of D&C algorithms.
$T(n)=2T(\frac{n}{2})+\Theta (n)$ Note that the number of subproblems are 2, $\frac{n}{2}$ is the size of each subproblem and $n$ is the work necessary to combine the subproblems (merge part of the algorithm). We can solve this using the master theorem (case 2 of master theorem): $f(n)=\Theta (n\log (n))$.

Binary search

1. Divide problem in sub-problem cutting in the middle element of the array
2. Conquer sub-problems
3. Combine sub-problems to solve the main problem, in this case $\Theta (1)$ because we have to combine nothing

$T(n)=1T(\frac{n}{2})+\Theta (1)$

undefined

So the complexity is: $T(n)=7T(n/2)+\Theta (n^2)$

Using Master theorem, case 1:

$n^{{\log }_{ba}a}=n^{{\log }_{2}7}\approx n^{2.81}\Rightarrow \Theta \left(n^{{\log }_{2}7}\right)$ The number $2.81$ may not seem much smaller than 3, but because the difference is in the exponent, the impact on running time is significant. In fact, Strassen’s algorithm beats the ordinary algorithm on today’s machines for $n\ge 32$ or so.

VLSI Layout

Embed a complete binary tree with $n$ leaves in a grid using minimal area.

where $H(n)=H(\frac{n}{2})+\Theta (1)={\log }_2(n)$ and $W(n)=2W(\frac{n}{2})=\Theta (n)$ using respectively the second and first case of MT. So we obtain a total complexity (area) of $\Theta (n\log (n))$ that can be improved using this new arrangement :

This new solution based on Divide and Conquer has a total complexity of $\Theta (n)$ obtained by $L(n)\cdot L(n)$ where $L(n)=2L(\frac{n}{4})+\Theta (1)$ which is $\sqrt{n}$ using the MT (first case).