[Solved]: Theoretical foundations of Divide and Conquer

Problem Detail: 

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)?

Asked By : Cornelius Brand

Answered By : Cornelius Brand

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)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14022