Divide-and-Conquer

1. "Divide-and-Conquer" Paradigm and Its Three Fundamental Steps

The Divide-and-Conquer paradigm is a widely recognized and very efficient general algorithm design technique. It solves a problem by following a three-step plan:

1. Divide: The original problem is divided into several subproblems of the same type. Ideally, these subproblems should be of approximately equal size. For example, when summing n numbers, the problem can be divided into two subproblems: summing the first ⌈n/2⌉ numbers and summing the remaining ⌊n/2⌋ numbers.

2. Conquer (Solve): The subproblems are then solved, typically recursively. This means the same divide-and-conquer strategy is applied to each subproblem until they become small enough to be solved directly (base case).

3. Combine: If necessary, the solutions to the subproblems are combined to obtain a solution to the original problem. For instance, after computing the sums of the two halves of numbers, these two sums are added together to get the total sum.

This technique is especially well-suited for parallel computations, as subproblems can often be solved simultaneously by different processors.

2. Characteristics That Make a Problem Well-Suited for a Divide-and-Conquer Approach

Problems that are well-suited for a Divide-and-Conquer approach typically exhibit the following characteristics:

• Decomposability: The problem must be easily broken down into smaller subproblems that are identical in type to the original problem. This self-similar structure is crucial for recursive application.

• Independence of Subproblems: The subproblems should be largely independent of each other so that solving one does not heavily rely on the solution of another, allowing for parallel processing if desired.

• Efficiency of Combination: The cost of combining the solutions of the subproblems must not outweigh the benefits gained from dividing the problem. If the combination step is too expensive, the overall algorithm might not be more efficient than a brute-force approach.

• Base Case: There must be a base case where the subproblems become small enough to be solved directly without further recursion.

While not every problem can be solved efficiently with divide-and-conquer, it has led to some of the most important and efficient algorithms in computer science.

3. General Form of a Recurrence Relation for a Divide-and-Conquer Algorithm and the Role of the Master Theorem

The general form of a recurrence relation for a divide-and-conquer algorithm describes the running time T(n) of many such algorithms. This relationship is expressed as:

T(n) = aT(n/b) + f(n)

Here's an explanation of each term:

• a: Represents the number of subproblems that are solved recursively. The constant a must be greater than or equal to 1 (a ≥ 1).
• b: Denotes the factor by which the input size is divided for each subproblem. This means that each subproblem has a size of n/b. The constant b must be greater than 1 (b > 1), typically b ≥ 2.
• f(n): Accounts for the time spent on dividing the original problem into subproblems and combining their solutions.

The Master Theorem is a powerful tool that significantly simplifies the efficiency analysis of these recurrences. It determines the order of growth of the solution T(n) based on the values of a, b, and the order of growth of f(n). The theorem typically assumes that f(n) belongs to the class Θ(n^d), where d is a non-negative constant (d ≥ 0).

The Master Theorem provides the following cases for the order of growth of T(n):

• If a < b^d, then T(n) ∈ Θ(n^d).
• If a = b^d, then T(n) ∈ Θ(n^d log n).
• If a > b^d, then T(n) ∈ Θ(n^logba).

Similar results also apply to the O (big oh) and Ω (big omega) notations. This theorem allows determining an algorithm's efficiency class without the need to solve the recurrence relation explicitly.

4. Algorithm for Multiplying Two Large Integers Based on Divide and Conquer Strategy and Its Time Efficiency Analysis

The algorithm for multiplying two large integers based on the divide-and-conquer strategy addresses the challenge of multiplying numbers too long to fit into a single computer word.

The conventional "pen-and-pencil" method for multiplying two n-digit integers involves n² digit multiplications. The divide-and-conquer approach, developed by Anatoly Karatsuba in 1960, ingeniously reduces this number.

Let's consider two n-digit integers, a and b, where n is an even number. Both a and b are divided in the middle into two halves:

• a can be represented as a1 * 10^(n/2) + a0
• b can be represented as b1 * 10^(n/2) + b0 Where a1 and b1 are the first halves of the digits, and a0 and b0 are the second halves.

Multiplying a and b conventionally would involve four n/2-digit multiplications: c = a * b = (a1 * 10^(n/2) + a0) * (b1 * 10^(n/2) + b0) = (a1 * b1)10^n + (a1 * b0 + a0 * b1)10^(n/2) + (a0 * b0)

To reduce the number of multiplications, the algorithm applies a trick:

1. Compute c2 = a1 * b1 (product of their first halves).
2. Compute c0 = a0 * b0 (product of their second halves).
3. Compute the middle term, c1, using only one additional multiplication: c1 = (a1 + a0) * (b1 + b0) - (c2 + c0).

This means the four products required by the conventional method are replaced by three multiplications of n/2-digit numbers: a1 * b1, a0 * b0, and (a1 + a0) * (b1 + b0). The recursion stops when n becomes small enough, typically when n = 1, where numbers are multiplied directly.

Time Efficiency Analysis (Using Recurrence Relation and Backward Substitution)

Let M(n) be the number of digit multiplications performed by this algorithm when multiplying two n-digit numbers. Since the algorithm makes three multiplications of n/2-digit numbers, the recurrence relation for M(n) is:

M(n) = 3M(n/2) for n > 1, with a base case of M(1) = 1 (assuming n is a power of 2 for simplicity).

To solve this recurrence using backward substitutions:

• M(n) = 3M(n/2)
• Substitute M(n/2) = 3M((n/2)/2) = 3M(n/4):
• M(n) = 3 [3M(n/4)] = 3²M(n/4)
• Continuing this pattern for i substitutions: M(n) = 3^i M(n/2^i)

The recursion stops when the subproblem size becomes 1. This happens when n/2^i = 1, which means n = 2^i. Therefore, i = log2 n.

Substitute i = log2 n back into the equation: M(n) = 3^(log2 n) * M(1) Since M(1) = 1: M(n) = 3^(log2 n)

Using the logarithm property a^(logb c) = c^(logb a): M(n) = n^(log2 3)

Calculating the exponent: log2 3 ≈ 1.585. So, M(n) ≈ n^1.585.

This shows that the number of multiplications grows significantly slower than the n² multiplications of the conventional method.

The divide-and-conquer algorithm for large integer multiplication is in Θ(n^1.585). This is a better efficiency class than the Θ(n²) of the brute-force method.