Scribd
Upload
5 views11 pages

Divide and Conquer Algorithm Overview

The document outlines the Divide and Conquer algorithm, which involves breaking a larger problem into smaller subproblems, solving them independently, and combining their solutions. It describes the three main steps: Divide, Conquer, and Merge, along with examples such as maximum and minimum problem, binary search, and sorting algorithms. Additionally, it mentions the general recurrence relation and the Master theorem for analyzing divide and conquer recurrences.

Uploaded by

sss.081960z
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views11 pages

Divide and Conquer Algorithm Overview

The document outlines the Divide and Conquer algorithm, which involves breaking a larger problem into smaller subproblems, solving them independently, and combining their solutions. It describes the three main steps: Divide, Conquer, and Merge, along with examples such as maximum and minimum problem, binary search, and sorting algorithms. Additionally, it mentions the general recurrence relation and the Master theorem for analyzing divide and conquer recurrences.

Uploaded by

sss.081960z
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Design and Analysis of Algorithms

MODULE-2
Dr. Shivanna K,
Associate Professor,
Computer Science and Engineering,
Sahyadri College of Engineering and Management,
Adyar, Mangalore-575007.
Email: shivannak4phd@[Link]
Mobile: +91-9686194749
1
Divide and Conquer (General Procedure)
 Divide and Conquer Algorithm involves breaking a larger problem
into smaller subproblems, solving them independently, and then
combining their solutions to solve the original problem.
 The basic idea is to recursively divide the problem into smaller
subproblems until they become simple enough to be solved directly.
 Once the solutions to the subproblems are obtained, they are then
combined to produce the overall solution.
Working of Divide and Conquer Algorithm:
1. Divide:
• Break down the original problem into smaller subproblems.
• Each subproblem should represent a part of the overall problem.
• The goal is to divide the problem until no further division is possible.
2
2. Conquer:
• Solve each of the smaller subproblems individually.
• If a subproblem is small enough (often referred to as the “base
case”), we solve it directly without further recursion.
• The goal is to find solutions for these subproblems independently.
3. Merge:
• Combine the sub-problems to get the final solution of the whole
problem.
• Once the smaller subproblems are solved, we recursively combine
their solutions to get the solution of larger problem.
• The goal is to formulate a solution for the original problem by
merging the results from the subproblems.
3
4
5
Examples of Divide and Conquer Algorithm:
1. Maximum and Minimum Problem
2. Binary Search
3. Sorting (merge sort, quick sort)
4. Tower of Hanoi.

6
General divide-and-conquer recurrence relation

7
Master theorem for divide and conquer recurrences

8
9
10
11

You might also like