[Algorithm] Divide and Conquer(D&C) Paradigm

Divide & Conquer (D&C) Paradigm

• Breaking down a problem into two or more subproblems of the same or related type.
• The solutions to the subproblems are combined to be a solution to the original problem.

• main step
  1. Divide: Break the original problem into smaller, often identical or similar subproblems. This division continues recursively until the subproblems become simple enough to be solved directly.
  2. Conquer: Solve the subproblems independently. This is often done recursively, using the same Divide and Conquer approach until the base cases are reached. The base cases are simple enough to be solved straightforwardly.
  3. Combine: Combine the solutions of the subproblems to obtain the solution to the original problem. This step may involve merging, aggregating, or modifying the solutions of the subproblems.
• Key characteristics 
  1. Recursion: Divide and Conquer algorithms often use recursion to solve subproblems. The algorithm calls itself with smaller instances of the same problem until it reaches the base case.
  2. Parallelism: The Divide and Conquer approach is well-suited for parallel processing, as subproblems can be solved independently, and their solutions can then be combined.
  3. Efficiency: In many cases, Divide and Conquer algorithms can provide efficient solutions to complex problems. For example, some sorting algorithms like Merge Sort and Quick Sort, as well as algorithms for fast exponentiation and matrix multiplication, use this paradigm.
• Example of algorthms based on Divdied and Conquer approach
  • Merge Sort
  • Quick Sort
  • Binary Search
  • Karatsub Algorithm