0
8.5kviews
Explain the general procedure of divide and conquer method.
1 Answer
3
879views

General Procedure of Divide-and-Conquer Method

  • In simple words, Divide-and-Conquer break down the main problem into small sub-problems. Then solve that sub-problem independently, and at last combine the solutions of small sub-problems as a solution for the main problem.
  • Divide-and-Conquer creates at least two sub-problems, a divide-and-conquer algorithm makes multiple recursive calls.
  • Some divide-and-conquer algorithms create more than two sub-problems also.
  • Divide-and-Conquer solve sub-problems recursively, each sub-problem must be smaller than the original problem, and there must be a base case for sub-problems.
  • Divide-and-Conquer algorithms have three parts as follows:
    • Divide the problem into a number of sub-problems that are small instances of the main problem.
    • Conquer the sub-problems by solving them recursively. If they are small enough, solve the sub-problems as base cases.
    • Combine the solutions of the sub-problems as one complete solution for the main problem.

Diagrammatic Representation of General procedure of Divide-and-Conquer Method:

Divide-and-Conquer

The problem with more recursive steps looks as follows:

Divde-and-Conquer BIG

Benefits of Divide-and-Conquer:

  • Easily solve large problems faster than other algorithms.
  • It solves simple sub-problems within the cache memory instead of accessing the slower main memory.
  • It supports parallelism because sub-problems are solved independently.
  • Hence, the algorithm made using this approach runs on the multiprocessor system.

Drawback of Divide and Conquer:

  • It uses recursion therefore sometimes memory management is a very difficult task.
  • An explicit stack may overuse the space.
  • It may crash the system if the recursion is carried out rigorously greater than the stack present in the CPU.

Applications of Divide and Conquer:

There are lots of applications of this divide-and-conquer approach as follows:

  • Merge Sort
  • Quick Sort
  • Binary Search
  • Tower of Hanoi
  • Closest Pair of Points
  • Karatsuba Algorithm
  • Strassen's Matrix multiplication
  • Cooley-Tukey Fast Fourier Transform (FFT) algorithm
  • Finding the maximum and minimum of a sequence of numbers
Please log in to add an answer.