Divide and Conquer

Divide and Conquer Strategy

Divide and Conquer is a problem-solving strategy in which a large and complex problem is divided into smaller problems, each smaller problem is solved separately, and then the solutions are combined to obtain the solution to the original problem.

Simple idea

“Break a big problem into smaller problems, solve them, and combine the answers.”

This strategy is especially important in algorithm design because many difficult problems become easier when we work with smaller pieces.

---

The Three Steps

Divide and Conquer generally has three stages:

1. Divide

Break the original problem into smaller sub-problems.

The smaller problems should be easier to handle and usually have the same nature as the original problem.

Example:
Suppose we have 1,000 books to organize.

Instead of organizing all 1,000 books together:

1000 Books
     ↓
 ┌───┼────┐
 ↓   ↓    ↓
Fiction  Non-fiction  Reference

We have divided one large problem into smaller problems.

---

2. Conquer

Solve each of the smaller problems independently.

The sub-problems can themselves be divided further if necessary.

For example:

Fiction
   ↓
 ┌──────────────┐
 ↓              ↓
Science       Historical
Fiction       Fiction

Continue dividing until the problem becomes small enough to solve easily.

For example:

10 books
   ↓
5 books + 5 books
   ↓
2 + 3     2 + 3

Very small groups can then be organized directly.

---

3. Combine

After solving all the smaller problems, combine their solutions to obtain the solution to the original problem.

For example:

Science Fiction → Organized
Historical      → Organized
Biographies     → Organized
Reference       → Organized
        ↓
Combine
        ↓
Complete organized library

---

Programming Example: Merge Sort

A very good programming example for first-year students is Merge Sort.

Suppose we want to sort:

[38, 27, 43, 3, 9, 82, 10]

Divide

Split the array into smaller arrays:

[38, 27, 43, 3]     [9, 82, 10]

Divide again:

[38, 27] [43, 3]     [9, 82] [10]

Continue until individual elements remain:

[38] [27] [43] [3] [9] [82] [10]

Conquer

Sort the small groups:

[38] [27] → [27, 38]

[43] [3] → [3, 43]

[9] [82] → [9, 82]

Combine

Merge the sorted groups:

[27, 38] + [3, 43]
       ↓
[3, 27, 38, 43]

[9, 82] + [10]
       ↓
[9, 10, 82]

Finally:

[3, 27, 38, 43] + [9, 10, 82]
              ↓
[3, 9, 10, 27, 38, 43, 82]

Thus, the original large sorting problem is solved by dividing it into smaller sorting problems and combining their results.

---

Divide and Conquer in Software Development

Consider developing a college management system.

Instead of developing the entire system at once, divide it into modules:

College Management System
          ↓
 ┌────────┼───────────┐
 ↓        ↓           ↓
Student  Faculty    Examination
Module   Module       Module

These can be further divided:

Student Module
      ↓
 ┌────┼─────┐
 ↓    ↓     ↓
Admission Attendance Results

Each module can be developed and tested independently and then integrated into the complete system.

---

Why Is Divide and Conquer Useful?

1. Reduces complexity

A large problem becomes a collection of smaller, easier problems.

2. Makes problem solving easier

We can concentrate on one sub-problem at a time.

3. Supports recursion

Many Divide and Conquer algorithms naturally use recursion.

4. Can improve efficiency

Some algorithms become significantly faster when a large problem is divided intelligently.

5. Easier testing

Individual sub-problems can be tested independently.

---

Divide and Conquer vs Brute Force

This is a useful comparison for students:

Strategy	Basic Idea
Brute Force	Try all possible solutions
Divide and Conquer	Divide a large problem into smaller problems
Heuristic	Use a practical shortcut
Backtracking	Try a choice and undo it if it fails

For example, when sorting a large list:

Brute Force:
Try many possible arrangements and find the sorted one.

Divide and Conquer:
Divide the list into smaller lists, sort them, and combine them.

---

Easy Way to Remember

Students can remember Divide and Conquer using:

DIVIDE → CONQUER → COMBINE

             LARGE PROBLEM
                   ↓
                DIVIDE
             ↙          ↘
       Small Problem   Small Problem
            ↓               ↓
         CONQUER         CONQUER
            ↓               ↓
             ↘             ↙
                COMBINE
                   ↓
             FINAL SOLUTION

One-line definition 

Divide and Conquer is a problem-solving strategy in which a large problem is divided into smaller sub-problems, each sub-problem is solved independently, and their solutions are combined to obtain the solution to the original problem.

Example: Merge Sort Visualization

Here’s how Merge Sort would work on an array [11, 6, 3, 24, 46, 22, 7]:

1. Divide:

   • Split the array into [11, 6, 3, 24] and [46, 22, 7].
   • Further divide [[11, 6, 3, 24] into [11, 6] and [3,24], and [46, 22, 7] into [46,22] and [7].
   • Continue dividing until you have sub-arrays of single elements: [11], [6], [3], [24], [46], [22], [7].

2. Conquer:

   • Merge [11] and [6] to get [6, 11].
   • Merge [3] and [24] to get [3, 24].
   • Merge [46] and [22] to get [22,46].
   • Now, you have [6, 11], [3, 24], [22, 46],[7]

3. Combine:

   • Merge [6, 11] and [3, 24] to get [3, 6, 11, 24].
   • Merge [22,46] and [7] to get [7,22,46].
   • Finally, merge [3,6,11,24] and [7,22,46] to get the fully sorted array [3, 6, 7, 11, 22, 24,46].

Python code for Merge Sort- Divide and conquer method

def merge_sort(arr):

    # Base case: if the array has 1 or 0 elements, it is already sorted

    if len(arr) > 1:

        # Divide the array into two halves

        mid = len(arr) // 2  # Find the middle of the array

        left_half = arr[:mid]  # Left sub-array

        right_half = arr[mid:]  # Right sub-array

        # Conquer: Recursively apply merge_sort to both halves

        merge_sort(left_half)

        merge_sort(right_half)

        # Combine: Merge the two halves

        i = j = k = 0

        # Merge data from left_half and right_half into the original array

        while i < len(left_half) and j < len(right_half):

            if left_half[i] < right_half[j]:

                arr[k] = left_half[i]

                i += 1

            else:

                arr[k] = right_half[j]

                j += 1

            k += 1

        # Check if any elements were left in left_half

        while i < len(left_half):

            arr[k] = left_half[i]

            i += 1

            k += 1

        # Check if any elements were left in right_half

        while j < len(right_half):

            arr[k] = right_half[j]

            j += 1

            k += 1

# Example usage:

arr = [11, 6, 3, 24, 46, 22, 7]

print("Original array:", arr)

merge_sort(arr)

print("Sorted array:", arr)

Output

Original array: [11, 6, 3, 24, 46, 22, 7]

Sorted array: [3, 6, 7, 11, 22, 24, 46]

Example: ( University Question)

Finding the Maximum Element in an Array

Given an array of integers, find the maximum value in the array.

Step-by-Step Solution

1. Initial Setup:

Begin with the entire array and determine the range to process. Initially, this range includes the entire array from the first element to the last element.

2.Divide

If the array contains more than one element, split it into two approximately equal halves. This splitting continues recursively until each subarray has only one element.

3. Conquer:

    • For subarrays with only one element, that element is trivially the maximum for that subarray.

    • For larger subarrays, recursively apply the same process to each half of the subarray.

4. Combine:

After finding the maximum element in each of the smaller subarrays, combine the results by comparing the maximum values from each half. Return the largest of these values as the maximum for the original array.

Python Implementation

def find_max(arr, left, right):

    # Base case: If the array segment has only one element

    if left == right:

        return arr[left]

    # Divide: Find the middle point of the current segment

    mid = (left + right) // 2

    """ Conquer: Recursively find the maximum in the left and

    right halves """

    # Maximum in the left half

    max_left = find_max(arr, left, mid)

    # Maximum in the right half

    max_right = find_max(arr, mid + 1, right)

    # Combine: Return the maximum of the two halves

    return max(max_left, max_right)

# Example usage

array = [3, 6, 2, 8, 7, 5, 1]

result = find_max(array, 0, len(array) - 1)

print("Maximum element:", result)

# Output: Maximum element: 8

Example: ( University Question)

you are working as a financial analyst for a bank.the bank has received a list of loan interest rates from multiple branches, and you need to identify the two lowest rates to recommend the most cost-effective options to customers. The rates are provided as an array of positive integers and your task is to develop an efficient algorithm using the divide and conquer approach to find the sum of the two smallest rates/ explain with suitable example

To solve the problem using a divide and conquer approach, we can break the problem into smaller sub problems, solve them, and combine the results to find the two smallest loan interest rates efficiently.

---

Algorithm

Steps:

1. Divide the Array:

   • Split the array into two halves until each subarray contains only one or two elements.

2. Conquer (Find Two Smallest in Each Subarray):

   • For each subarray, determine the two smallest numbers directly if the size is $\leq 2$.
   • Otherwise, recursively solve for the two smallest numbers in each half.

3. Combine the Results:

   • Merge the results from the two halves by selecting the two smallest numbers among the four candidates (two from each half).

4. Return the Sum:

• Add the two smallest numbers obtained.

Explanation with Example

Input:

arr = [5, 2, 8, 6, 3, 1]

Steps:

1. Divide the Array:

   • Split the array recursively until each subarray has 1 or 2 elements:

     
     [5, 2, 8, 6, 3, 1]
     -> [5, 2, 8] and [6, 3, 1]
     -> [5, 2] and [8] for the first half; [6, 3] and [1] for the second half.
     

2. Conquer:

   • Find two smallest numbers in each subarray:

     
     [5, 2] -> (2, 5)
     [8] -> (8, ∞)
     [6, 3] -> (3, 6)
     [1] -> (1, ∞)
     

3. Combine Results:

   • Merge the results:

     
     First half ([2, 5], [8, ∞]) -> [2, 5, 8, ∞] -> (2, 5)
     Second half ([3, 6], [1, ∞]) -> [3, 6, 1, ∞] -> (1, 3)
     

   • Combine the two halves:

     
     [2, 5] and [1, 3] -> [2, 5, 1, 3] -> (1, 2)
     

4. Result:

   • Smallest: $1$
     
   • Second Smallest: $2$
     
   • Sum: $1 + 2 = 3$
     

Output:

Sum of two smallest rates: 3

Python Implementation

def find_two_smallest(arr):

    # Base case: If the array has only one element, return the element and infinity

    if len(arr) == 1:

        return arr[0], float('inf')

    # Base case: If the array has two elements, return the smallest and the second smallest

    if len(arr) == 2:

        return (min(arr[0], arr[1]), max(arr[0], arr[1]))

    # Divide the array into two halves

    mid = len(arr) // 2

    left_smallest, left_second = find_two_smallest(arr[:mid])

    right_smallest, right_second = find_two_smallest(arr[mid:])

    # Combine results from the two halves

    candidates = [left_smallest, left_second, right_smallest, right_second]

    candidates.sort()  # Sort to find the two smallest numbers

    return candidates[0], candidates[1]  # Return the two smallest numbers

def sum_two_smallest(arr):

    smallest, second_smallest = find_two_smallest(arr)

    return smallest + second_smallest

# Example Usage

rates = [5, 2, 8, 6, 3, 1]

result = sum_two_smallest(rates)

print("Sum of the two smallest rates:", result)

Output:

Sum of the two smallest rates: 3