# Theoretical foundations of Divide and Conquer

When it comes to the design of algorithms, one often employs the following techniques:

• Dynamic Programming
• The Greedy-Strategy
• Divide-and-Conquer

While for the first two methods, there are well-known theoretical foundations, namely the Bellman Optimality Principle and matroid (resp. greedoid) theory, I could not find such a general framework for algorithms based on D&C.

Firstly, I am aware of something that we (or rather, the prof) introduced in a functional programming class, called an "algorithmic skeleton", that arose in the context of combinators. As an example hereof, we gave such a skeleton for D&C algorithms as follows:

Definition: Let $A,S$ be non-empty sets. We call the elements of $S$ solutions, and the elements of $P:=\mathfrak{P}(A)$ (that is, the subsets of $A$) are referred to as problems. Then, a D&C-skeleton is a 4-tuple $(P_\beta, \beta, \mathcal{D}, \mathcal{C})$, where:

• $P_\beta$ is a predicate over the set of problems and we say that a problem $p$ is basic iff $P_\beta(p)$ holds.
• $\beta$ is a mapping $P_\beta \rightarrow S$ that assigns a solution to each basic problem.
• $\mathcal{D}$ is a mapping $P \rightarrow \mathfrak{P}(P)$ that divides each problem into a set of subproblems.
• $\mathcal{C}$ is a mapping $P\times \mathfrak{P}(S) \rightarrow S$ that joins the solutions (depending on kind of a "pivot problem") of the subproblems to produce a solution.

Then, for a given skeleton $s=(P_\beta, \beta, \mathcal{D}, \mathcal{C})$ and a problem $p$, the following generic function $f_s: P\rightarrow S$ computes a solution (in the formal sense) for $p$:

$f_s(p)= \left\{ \begin{array}{l l} \beta(p) & \quad \text{if$p$is basic}\\ \mathcal{C}(p,f(\mathcal{D}(p))) & \quad \text{otherwise} \end{array} \right.$

where in the second line we use the notation $f(X) := \{f(x) : x\in X\}$ for subsets $X$ of the codomain of a mapping $f$.

However, we did not further examine the underlying, "structural" properties of problems that can be formulated this way (as I said, it was a functional programming class and this was only a small example). Unfortunately, I could not find further reference on this very approach. Hence I don't think the above definitions are quite standard. If someone recognizes what I have stated above, I would be glad about related articles.

Secondly, for the greedy strategy we have the famous result that a problem is correctly solved by the general greedy algorithm if and only if its solutions constitute a weighted matroid. Are there similar results for D&C-algorithms (not necessarily based on the method outlined above)?

A formal treatment (somewhat resembling the model proposed in the question) of the subject using what is called pseudo-morphisms (that is, functions that are almost morphisms, with some pre- and post-computation done), as well as considerations of complexity analysis and parallel implementation of such algorithms are given in:

An algebraic model for divide-and-conquer and its parallelism by Zhijing G. Mou and Paul Hudak (in The Journal of Supercomputing , Volume 2, Issue 3, pp. 257-278, November 1988)

I'm not aware of something as concrete as Bellman's Optimality Principle for Divide and Conquer algorithms. However, the underlying foundation of divide and conquer seems to me to be a recursive (or inductive) definition of the problem's input and then a means of combining solutions to the problem in to larger solutions. The key insight here is thinking about problem inputs recursively and leveraging that in to recursive, D&C algorithms.

Take mergesort as an example. Let's begin with the input, an array of $n$ elements. One can recursively define the structure of the array as follows:

• For $n=0$, the array is empty.
• For $n=1$, The array is a singleton element
• For $n>1$, the array is the concatenation of an array of of size $\lceil{\frac{n}{2}}\rceil$ (left) and size $\lfloor{\frac{n}{2}}\rfloor$ (right)

We then approach the mergesort algorithm by then mapping sort to this structure. The base cases, where $n\leq1$ are trivially sorted. The recursive case begins by recursively sorting where the data is recursive, namely left and right. We then essentially find a replacement for concatenate, which ends up being merge. So notice we've basically just taken the recursive structure of the data and mapped that to a recursive solution.

It's important to note that this doesn't necessarily lead to what you expect from D&C algorithms. We could define the array structure as follows:

• For $n=0$, the array is empty.
• For $n>0$, the array is a single element concatenated to an array of size $n-1$.

Following the same strategy we used for mergesort here leads to recursive insertion sort. So, typically we develop recursive definitions that involve multiple recursive elements, i.e. cut the data set in half or third.

Now, there is the Master Theorem for analyzing D&C algorithms and this sheds some light on the efficiency expectations for the sub-components of a D&C algorithm with a particular overall run-time efficiency.

• The examples you give fit into the general context I give in my question (and in fact, it might be helpful that you give a concrete application). However, my question was whether there is a criterion (such as BOP or matroid structure) for problems to be solvable by algorithms that fit into this pattern. – Cornelius Brand Dec 19 '13 at 23:05