Algorithms and Data Structures for Programming Contests

Divide-and-Conquer Algorithms

Discussion

What is it?

Recursive algorithm where solution to overall problem is obtained by splitting it up into subproblems, solving each subproblem recursively, and combining sub-solutions back into overall solution.

The Master Theorem

If T(n) is the worst-case running time of a divide-and-conquer algorithm, it often satisfies a "recurrence relation" (recursive equation) of the form:
T(n) = Θ(1) if n ≤ K
T(n) = a T(n/b) + Θ(n^d) otherwise
where a, b, d, K are constants determined by the algorithm.
Then,
T(n) = Θ(n^d) if d > log_b a,
T(n) = Θ(n^d log n) if d = log_b a,
T(n) = Θ(n^log_b a) if d < log_b a.

Try it!

Consider problem of multiplying two large integers, given as sequences of bits:
X = x_n−1 x_n−2 ... x₁ x₀
Y = y_n−1 y_n−2 ... y₁ y₀
Standard iterative algorithm involves repeated additions of appropriately shifted copies of X, according to bits of Y. This takes time Θ(n²).
Idea: let X₁ = x_n−1 ... x_n/2, X₀ = x_n/2−1 ... x₀, and define Y₁ and Y₀ similarly. (If n is odd, pad X and Y with an extra 0 on the left before doing this.)
Now we have
X = 2^n/2 X₁ + X₀
Y = 2^n/2 Y₁ + Y₀

where multiplication by a power of 2 indicates shifting of bits.
Based on this,
X Y = 2ⁿ X₁ Y₁ + 2^n/2 (X₀ Y₁ + X₁ Y₀) + X₀ Y₀

Recursive algorithm:

    multiply(X, Y):
        if n == 1:
            return x * y  # multiplication of 1-bit integers
        else:
            set lists X1, X0, Y1, Y0 as above
            p1 = multiply(X1, Y1)
            p2 = multiply(X1, Y0)
            p3 = multiply(X0, Y1)
            p4 = multiply(X0, Y0)
            return 2**n * p1 + 2**(n/2) * (p2 + p3) + p4

Runtime?

Regroup

Algorithms and Data Structures by François Pitt is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.