History

Originates as a maxim attributed to Philipp II of Macedon: Διαίρει καὶ βασίλευε, literally “divide and reign”.

Principle

Simplify a problem by decomposing it in subproblems:

• Divide (decompose) the problem into subproblems.
• Conquer, ie solve the subproblems.
• Combine (compose) the solutions to the subproblems into the solution to the problem.

Principle

If the subproblems are of the same nature as the problem, just smaller (where the size of the problem is defined by an order on the size of its parameters), the problem can be defined recursively.

A very simple example: the Fibonacci numbers

The sequence $$F_n$$ is defined by a recurrence relation:

• $$F_0 = 0$$
• $$F_1 = 0$$
• $$F_n = F_{n-1} + F_{n-2}$$

The problem of computing $$F_n$$ is decomposed into two smaller subproblems of the same nature: compute $$F_{n-1}$$ and $$F_{n-2}$$. Their solution can be composed to return the solution to the initial problem!

Implementation in Python

Simply use recursive functions:

def fib(n: int) -> int:
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

Issue

The problem may exhibit overlapping subproblems, ie the same (sub*)problems must be solved multiple times.

Illustration

Here is the call tree of fib(5):

fib(2) is computed three times.

Consequence

The running time explodes. In the case of fib, it is exponential in time !

Principle

Record the (sub*)problem solutions in a memo (a dictionary, an array…) in order to avoid recomputations.

Using a dictionary

A dictionary stores $(key, value)$ pairs and retrieves the value associated to any key, if there is one (with a $O(1)$ complexity on average).

Calling a memoized version of the function $f$ with the argument $e$ works as follows:

• Check whether there exists a value for the the key $e$.
• If true, return the value (this is $f(e)$).
• Otherwise, compute $f(e)$.
• Store the new pair $(e, f(e))$ in the dictionary.
• Return $f(e)$.

Using an array

Assume the parameter of $f$ is an integer, the previous key can be turned into an index in an array of values (with an access of complexity $O(1)$).

The program

def fib_memo(n):
    memo = [-1 for _ in range(n + 1)]  # initialization of memo

    def fib_memo_aux(n):
        if memo[n] != -1:  # if the result has already been computed 
            return memo[n] # return it
        if n == 0:         # else compute it (see recursive version)
            result = 0
        elif n == 1:
            result = 1
        else:
            result = fib_memo_aux(n - 1) + fib_memo_aux(n - 2)
        memo[n] = result   # record the result in memo
        return result      # and return it

    return fib_memo_aux(n)

Effect on the call tree

The computation of fib-memo($n$) requires 2n - 1 calls.

Big success: the running time is now linear in n.

From top-down to bottom-up computation

Interpret the arrows as problem dependencies, eg solving the problem fib-memo(5) depends on the solutions to the problems fib-memo(4) and fib-memo(3).

It is possible to first solve the smaller subproblems and then traverse the tree up to its root.

Effect on complexity

• The time complexity does not change (but the program is faster by a constant factor).
• The space complexity changes because intermediate function calls are eliminated (no use of the stack). It goes from $O(n)$ to $O(1)$.

Search problems

There are choices, which leads to potentially multiple solutions.

Example: if the problem is to change 3 euros, it is possible to use a 2-euro coin or not.

Optimization problems

An optimization problem is based on a search problem, but each solution $s$ has a cost $c(s)$, where $s$ is a so-called cost function. The optimization problem finds the best solution to the search problem, ie the solution minimizing the cost (or maximizing it, depending on the problem) ?

Example : if the problem is to change 3 euros with the minimal amount of coins, the best solution uses 2 coins (a 2-euro coin and a 1-euro coin).

Principle

The condition for applying the previous techniques to an optimization problem is that it exhibits the optimal substructure property, ie

• it can be decomposed in smaller subproblems and
• the optimal solutions to these subproblems can be composed into an optimal solution to the initial problem.

Example

In the case of the change making problem, we want to find the minimal number of coins necessary to make change for an amount $a$.

• Decomposition: there is the choice of taking (1) or not (2) a given coin of value $v$ in the list of the possible coins.
  • (1) The subproblem is making change for $a - v$ with all the coins.
  • (2) The subproblem is making change for $a$ with the remaining coins.
• Composition: assume the subproblems return the optimal solutions $n_1$ and $n_2$, the optimal solution is $min(1 + n_1, n_2)$.

Principle

In case of a choice, limit the exploration to the most promising alternative(s). This prunes the search and results in more efficiency.

Example: change making

• Order the coins and start with the coin with the highest value.
• If possible ($v \leq a$), take the coin! This may look like the most efficient way to decrease $a$.

Dynamic programming algorithms vs greedy algorithms

Can’t we miss an optimal solution that does not use the coin with the highest value?

• No with the euro system [1, 2, 5, 10, 50]: the greedy algorithm is a good choice, it is more efficient than the DP algorithm.
• Yes with the old British pound sytem [1, 3, 6, 12, 24, 30]: the greedy algorithm is a very bad choice, it is not correct!