Learn Divide & Conquer Algorithm

Hello, good people! Are you ready to dive into the exciting world of the Divide & Conquer Algorithm? Let's get started!

What is Divide and Conquer Algorithm?

Divide and conquer is an algorithm design paradigm which works by recursively breaking down a problem into subproblem of similar types, until these become simple enough to be solved directly. The solutions to the subproblems are then combined to give a solution to the original problem.

Example: Developing a website

Website -

• Module 1

  • Sub module 1

    • Function 1

    • Function 2

    • Function 3

    • Function 4

  • Sub module 2

    • Function 1

    • Function 2

    • Function 3

    • Function 4

• Module 2

  • Sub module 3

• Module 3

  • Sub module 4

  • Sub module 5

The idea is dividing a problem until we can't get any smaller. The we solve the small problems and combine them together.

Optimal Substructure: If a problem's overall optimal solution can be built from the optimal solutions of its subproblems, then this problem has an optimal substructure. It is very effective when the problem has optimal substructure property.

Example: Fib(n) = Fib(n-1) + Fib(n-2)

How to solve Fibonacci Series using Divide and Conquer approach?

Definition: A series of numbers in which each number is the sum of the two preceding numbers. First two numbers by definition are 0 and 1.

Example: 0,1,1,2,3,5,8,13,21,34,55...

Pseudocode for Fibonacci:

The 3 conditions are the base condition for Fibonacci. I'm not going to write the code here, because this is very easy, you can write the code using this pseudocode.

Number factor

Problem: Given N, find the number of ways expressing N as a sum of 1, 3 and 4. (you can use this numbers multiple times)

Example 1:

• N = 4

• Number of ways = 4

• Explanation: There are 4 ways can express N, {4}, {1,3}, {3,1}, {1,1,1,1}

Example 2:

• N = 5

• Number of ways = 6

• Explanation: There are 5 ways can express N, {4,1}, {1,4}, {1,3,1}, {3,1,1}, {1,1,3}, {1,1,1,1,1}

Now, we are going to find number of ways for 5 by solving sub problems.

So, to find the sub problems, we need to find the n-1 problems of the given numbers.

As you can see here, we are dividing the problems into subproblem then combining to get the global solution.

Number factor in Python

def numberFactor(n): 
    if n in (0,1,2): 
        return 1 
    elif n == 3: 
        return 2 
    else: 
        subP1 = numberFactor(n-1)
        subP2 = numberFactor(n-3) 
        subP3 = numberFactor(n-4) 
        return subP1 + subP2 + subP3 
print(numberFactor(5)

House robber

Imagine you are a professional robber and you want to rob a house. But the problems are :

• Given N number of houses along the street with some amount of money

• Adjacent houses cannot be stolen

• Find the maximum amount that can be stolen

If there are 6 houses in a street, and you rob the 1st house, you can't rob the 2nd house. If you rob the 3rd house, you can't rob the 4th house. This pattern continues. You can start from either the 1st or the 2nd house; it's up to you.

If you start from the 2nd house, Answer:

• Maximum amount = 41 million

• Houses that are stolen: 7, 30, 4

With this method, adjacent houses are never robbed, so the police cannot catch you, and you achieve the maximum value.

Now let's see how we can solve this problem using a divide and conquer algorithm. To apply divide and conquer, we first need to check if we can break the problem into smaller subproblems.

If we start from the 1st house, then the 2nd house will be excluded, leaving the remaining 5 houses available.

Option 1: 6 + f(5)

The second option is to not start from the first house, leaving all 6 houses available to rob.

Option 2: 0 + f(6)

With this, you can see we have divided our problem into two subproblems.

By solving these two options, we can find our maximum value: Max(option1, option2)

This is the recursion tree:

And the pseudocode:

House Robber Problem in Python

This problem becomes very simple when we use divide and conquer approach.

def houseRobber(houses, currentIndex): 
    if currentIndex >= len(houses): 
        return 0 
    else: 
        stealFirstHouse = houses[currentIndex] + houseRobber(houses, currentIndex + 2) 
        skipFirstHouse = houseRobber(houses, currentIndex +1)
        return max(stealFirstHouse, skipFirstHouse)

houses = [6,7,1,30,8,2,4] 
print(houseRobber(house,0))

Convert one string to another

Problem statement:

• S1, S2 are given string

• Convert S2 to S1 using delete, insert, or replace operation

• Find the minimum count of edit operations

Example 1

• S1 = "catch"

• S2 = "carch"

• Output = 1 (number of operations performed)

• Explanation: Replacing "r" with "t"

Example 2

• S1 = "table"

• S2 = "tbres"

• Output = 3 (number of operations performed)

• Explanation: Insert "a" to 2nd posotion, replace "r" with "i" and delete "s"

Example:

• S1 = "table"

• S2 = "tgable"

  Delete → f(2,3) [2 refers 2nd character of S1, 2 refers 3rd character of S2]

• S1 = "table"

• S2 = "tble"

  Insert → f(3,2) [3 refers 2nd character of S1, 2 refers 2nd character of S2]

• S1 = "table"

• S2 = "tcble"

  Replace → f(3,3) [3 refers 3rd character of S1, 3 refers 3rd character of S2]

Convert one string to another in Python

def findMinOperation(s1, s2, index1, index2): 
    if index1 == len(s1): 
        return len(s2) - index2 
    if index2 == len(s2): 
        return len(s1) - index1 
    if s1[index1] == s2[index2]: 
        return findMinOperation(s1, s2, index1, index2)
    else: 
        deleteOp = 1 + findMinOperation(s1, s2, index1, index2)
        insertOp = 1 + findMinOperation(s1, s2, index1, index2)
        replaceOp = 1 + findMinOperation(s1, s2, index1, index2)
        return min (deleteOp, insertOp, replaceOp) 

print(findMinOperation("table", "tbrles", 0 , 0)

Zero One knapsack problem

Problem statement:

• Given the weights and profits of N items

• Find the maximum profit within given capacity of C

• Items cannot be broken

What is the zero-one knapsack problem? We have items with weights and profits. We need to put these items in a knapsack with a capacity of C. Unlike the fractional knapsack problem, we can't break items into smaller units. Our goal is to find the maximum profit from the items in the knapsack.

Example:

Answer combinations:

1. Mango + Apple + Orange : weight 6; profit 74

2. Orange + banana : weight 7; profit 89

3. Apple + banana : weight 6, profit 98

Option 3 has the max profit. Now the question is, how do we get the answers? Here, we can divide the problem into two sub problems.

Subproblems:

1. Option 1 = 31 + f(2,3,4) [1st items' profit]

2. Option 2 = 0 + f(2,3,4) [skipping the 1st item]

Now it will be like max(option1, option2)

Zero One knapsack problem in Python

def Item: 
    def __init__(self, profit, weight): 
        self.profit = profit 
        self.weight = weight 

def zoKnapsack(items, capacity, currentIndex): 
    if capacity <= 0 or currentIndex < 0 or currentIndex >= len(items): 
        return 0
    elif items[currentIndex].weight <= capacity: 
        profit1 = items[currentIndex].profit + zoKnapsack(items, capacity-items[currentIndex].weight, currentIndex+1)
        profit2 = zoKnapsack(items, capacity, currentIndex+1)
    else: 
        return 0 
mango = Item(31, 3) 
apple = Item(26, 1) 
orange = Item(17, 2) 
banana = Item(72, 5)
items = [mango, apple, orange, banana) 
print(zoKnapsack(items, 7, 0))

Longest Common sequence problem

Problem statement:

• S1 and S2 are given strings

• Find the length of the longest subsequence which is common to both strings

• Subsequence: a sequence that can be driven from another sequence by deleting some elements without changing the order of them

Example:

• s1 - "elephant"

• s2 - "erepat"

• Output - 5

• Longest string - "eepat"

• Explanation - The first character is the same, so we take it. The second character isn't the same, so we skip it. The third and fourth characters are the same. That's how we find the longest common string.

Subproblems: f(char1 ,length1 : char2, length2)

1. Option 1 = 1 + f(2 (2nd char of s1), 8(length of s1) : 2(2nd char of s2), 7(length of s2))

2. Option 2 = 0 (they are not matching) + f(3,8 : 2,7)

3. Option 3 = 0 + f(2,8 : 3,7)

Now it will be like max(option1, option2, option3)

Longest Common sequence problem in Python

def findLCS(s1, s2, index1, index2): 
    if index1 == len(s1) or index2 == len(s2): 
        return 0 
    if s1[index1] == s2[index2]: 
        return 1 + findLCS(s1, s2, index1+1, index2+1)
    else: 
        op1 = findLCS(s1,s2,index1, index2+1) 
        op2 = findLCS(s1,s2,index1+1, index2)
        return max(op1, op2) 
print("elephant", "eretpat", 0 , 0)

Longest Palindromic Subsequence problem

Problem statement:

• S is given string

• Find the longest palindromic subsequence (LPS)

• Subsequence: a sequence that can be driven from another sequence by deleting some elements without changing the order of them

• Palindrome is a string that reads the same backwards well as forward (MADAM, NUN)

Example 1:

• S = "ELRMENMET"

• Output = 5

• LPS: 'EMEME"

Subproblems:

1. Option 1 = 2 + f(2,8)

   If the characters at the two ends of the current substring (i.e., S[i] and S[j]) are the same, then they could be part of the LPS. f(i+1, j-1) (the LPS within the substring excluding these two characters).

2. Option 2 = 0 + f(1,8)

   If you decide not to include S[i] (the first character of the current substring), you solve the problem for the substring excluding S[i]. This gives the subproblem f(i+1, j).

3. Option 3 = 0 + f(2,9)

   Similarly, if you decide not to include S[j] (the last character of the current substring), you solve the problem for the substring excluding S[j]. This gives the subproblem f(i, j-1).

   Max(option1, option2, option3)

These three options cover all possible cases:

1. Option 1 considers the case where both the first and last characters can be part of the LPS.

2. Option 2 considers the case where the first character is excluded.

3. Option 3 considers the case where the last character is excluded.

Example 2:

• S = "AMEEWMEA"

• Output = 6

• LPS: 'AMEEMA"

Longest Palindromic Subsequence in Python

def findLPS(s, startIndex, endIndex): 
    if startIndex > endIndex: 
        return 0 
    elif startIndex == endIndex: 
        return 1
    elif s[startIndex] == s[endIndex]: 
        return 2+ findLPS(s, startIndex +1, endIndex-1)
    else: 
        op1 = findLPS(s, startIndex, endIndex-1) 
        op2 = findLPS(s, startIndex+1, endIndex) 
        return max(op1,op2)
print(findLPS("ELRMENMET", 0 , 8)

Minimum cost to reach the Last cell problem

Problem statement:

• 2D matrix is given

• Each cell has a cost associated with it for accessing

• We need to start from (0,0) cell and go till (n-1, n-1) cell

• We can go only right or down cell from current cell

• Find the way in which the cost is minimum

Min cost: 36

Subproblems:

1. Option 1 = y + 9 + 3 f(4, 3)

2. Option 2 = z + 7 + 3 f(3, 4)

   Min(option1, option2)

Minimum cost to reach the Last cell in 2D array using Python

def findMinCost(twoDArray, row, col): 
    if row == -1 or col == -1: 
        return float("inf") 
    elif row == 0 and col == 0: 
        return twoDArray[0][0]
    else: 
        op1 = findMinCost(twoDArray, row-1, col)
        op2 = findMinCost(twoDArray, row, col-1)
        return twoDArray[row][col] + min(op1, op2)

TwoDList = [[4,7,8,6,4], 
            [6,7,3,9,2], 
            [3,8,1,2,4], 
            [7,1,7,3,7], 
            [2,9,8,9,3]
            ]
print(findMinCost(twoDList, 4,4))

Number of Ways to reach the last cell with given cost

Problem Statement:

• 2D matrix is given

• Each cell has a cost associated with it for accessing

• We need to start from (0,0) cell and go till (n-1,n-1) cell

• We can go only to right or down cell from current cell

• We are given total cost to reach the last cell

• Find the number of ways to reach at the end of the matrix with given "total cost"

The given cost is - 25

Subproblems:

1. Option 1 = y + 2 = 22 f(3,4,22)

2. Option 2 = z + 6 = 22 f(4,3,22)

   sum(option1, option2)

Number of Ways to reach the last cell with given cost in Python

def numberOfPaths(twoDArray, row, col, cost): 
    if cost < 0: 
        return 0 
    elif row == 0 and col == 0: 
        if cost == twoDArray[0][0]: 
            return 1 
        else: 
            return 0 
    elif row == 0: 
        return numberOfPaths(twoDArray, 0, col-1, cost - twoDArray[row][col]) 
    elif col == 0: 
        return numberOfPaths(twoDArray, row-1, 0, cost - twoDArray[row][col])
    else: #recursive callm
        op1 = numberOfPaths(twoDArray, row-1, col, cost - twoDArray[row][col]) 
        op2 = numberOfPaths(twoDArray, row, col-1, cost - twoDArray[row][col]) 
        return op1 + op2 

TwoDList = [
    [4, 7, 1, 6], 
    [5, 7, 3, 9], 
    [3, 2, 1, 2], 
    [7, 1, 6, 3]
]

print(numberOfPaths(TwoDList, 3, 3, 25))

End.