Let’s explore divide and Conquer : Data Structures and Algorithms

The “Divide and Conquer” strategy is widely recognized as a fundamental approach to algorithmic problem-solving by programmers across industries. Its simplicity and practicality make it a popular technique for tackling complex problems. In this article, et’s explore divide and Conquer strategy, exploring its key principles and demonstrating its effectiveness in addressing real-world problems.

A divide-and-conquer strategy recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

wikipedia.org

Understanding the divide-and-conquer strategy

• In simple terms, the divide-and-conquer method involves breaking down (dividing) the complex problem into simple, solvable sub-problems.
• These sub-problems will be solved independently. If sub-problems are large enough, then these will be further broken down into sub-problems.
• The generated sub-problems are usually of the same type as the original problem; hence, recursion is used in the divide-and-conquer strategy.

Control Abstraction of Divide-and-conquer strategy

Algorithm DandC(P){
  if( isSmall(P))
    return P;
  else{
    Divide P into no. of instances: P1,P2,P3...,Pk;
    Apply DandC(P1), DandC(P2), DandC(P3),...,DandC(Pk);
    return Combine(DandC(P1), DandC(P2), DandC(P3),...,DandC(Pk));
  }
}

Computing time for this can be given by recurrence relation:

Applications of Divide-and-Conquer Strategy

• Finding Maximum-Subarray Sum
• Binary Search
• Quick Sort
• Merge Sort
• Starssens Matrix Multiplication

Let’s explore divide and Conquer !