Divide and Conquer Algorithm in Python

Divide and Conquer is an algorithm design paradigm that works by recursively breaking down a problem into subproblems of similar type until they become simple enough to solve directly.

The solutions of the subproblems are then combined to give a solution to the original problem. Divide and Conquer algorithms use recursive functions.

A divide and conquer algorithm uses the following approach to solve a problem:

• Break the problem into smaller sub-problems.
• Solve the sub-problems.
• Combine the solutions to the sub-problems and obtain the solution to the original problem.

The divide and conquer is based on the following steps:

• Divide: Divide the original problem into sub-problems using recursion.
• Conquer: Solve the smaller sub-problems using recursion. If the subproblem is simple enough, then solve it directly.
• Combine: Combine the solutions of the sub-problems to solve the actual problem.

In the previous articles, we have performed some operations that use the divide and conquer algorithm approach. They are:

• Merge Sort
• Quick Sort

Fibonacci Series

The Fibonacci Series is a series of numbers in which each number is the sum of the preceding two numbers. By definition, the first two numbers are 0 and 1.

Example: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,…….
Fibonacci(N) = Fibonacci(N-1) + Fibonacci(N-2)

Implementation of Fibonacci Series using Divide and Conquer Algorithm

Fibonacci Series can be implemented using the Divide and Conquer Algorithm using the following steps:

• Declare the function and take the number whose Fibonacci Series is to be printed as parameter.
• If the number N is less than 1, return an error message.
• If N equals 1, return 0. If N equals 2, return 1.
• Else, recursively call the function for the preceeding ttwo numbers, N-1 and N-2.

#Function to implement Fibonacci Series
def Fibonacci(N):
   if N <= 1:
       return N
   else:
       return(Fibonacci(N-1) + Fibonacci(N-2))

#Number of terms to be printed
number = 10
if number <= 0:
   print("Plese enter a positive integer")
else:
   print("Fibonacci sequence:")
   for i in range(number):
       print(Fibonacci(i))

Time and Space Complexity

The time complexity for implementing Fibonacci Series is (2^n) as we use recursion. The space complexity is O(1) as no additional memory is required.

Number Factor

We are given a number N. Find the number of ways of expressing N as a sum 1, 3, and 4.

Example:
– N = 5
– Number of ways = 6
– Explanation: There are 6 ways to express N. {4,1}, {1,4}, {1,3,1}, {3,1,1}, {1,1,3}, {1,1,1,1,1}

Implementation of Number Factor using Divide and Conquer Algorithm

Number Factor problem can be implemented using the Divide and Conquer Algorithm using the following steps:

• Declare the function and take the number whose Number Factor is to be printed as parameter.
• If the number is 0, 1, or 2, return 1.
• Else, if the number is 3, return 2.
• Else, recursively call the function for three sub-parts N-1, N-3, N-4.
• Return the sum of the three sub-parts as output.

#Function to solve Number Factor Problem
def numberFactor(n):
    if n in (0,1,2):
        return 1
    elif n == 3:
        return 2
    else:
        subPart1 = numberFactor(n-1)
        subPart2 = numberFactor(n-3)
        subPart3 = numberFactor(n-4)
        return subPart1+subPart2+subPart3

print(numberFactor(5))

#Output
6

House Robber

We are given N number of houses along a street, each having some amount of money. A thief can not steal from adjacent houses. Find the maximum amount that can be stolen.

Example:

Answer:
– Maximum amount = 41
– Houses Stolen = 7, 30, 4

Implementation of House Robber using Divide and Conquer Algorithm

House Robber problem can be implemented using the Divide and Conquer Algorithm using the following steps:

• Declare the function and take the houses and current index as parameters.
• If the currentIndex is greater than the length of the list of houses, return 0.
• Then, we create two lists – stealFirstHouse and skipFirstHouse.
• We recursively call the function for each variable by incrementing the index.
• Finally, the max value between the two sets is returned as the output.

#Function to solve House Robber Problem
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(houses, 0))

#Output 
41

Convert String

We are given two strings S1 and S2. Convert S2 to S1 using delete, insert or replace operations. Find the minimum number of edit operations

Example:
– S1 = “table”
– S2 = “tbres”
– Output = 3
– Explanation: Insert “a” to second position, replace “r” with “l”, and delete “s”.

Implementation of String Convert using Divide and Conquer Algorithm

String Convert problem can be implemented using the Divide and Conquer Algorithm using the following steps:

• Declare the function and take the strings s1 and s2, along with their starting indices as parameters.
• If s1 or s2 are empty strings, return the differnece between the empty string and the other string as output.
• If they have the same length, recursively invoke the function by incementing the index.
• Else, recursively invoke the function for each seperate operation by incrementing the value of the indices.
• Return the minimum of the three values as output.

#Function to solve String Convert Problem
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+1, index2+1)
    else:
        deleteOp = 1 + findMinOperation(s1, s2, index1, index2+1)
        insertOp = 1 + findMinOperation(s1, s2, index1+1, index2)
        replaceOp = 1 + findMinOperation(s1, s2, index1+1, index2+1)
        return min (deleteOp, insertOp, replaceOp)

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

#Output
3

Zero One Knapsack Problem

We are given the weights and profits of N items. Find the maximum profit if we are given the knapsack capacity C. Items cannot be broken and must be added fully.

Example:

Answer:
Max profit is achieved by the following combination:
Apple(W: 1, P: 26) + Banana(W: 5, P: 72) = W: 6, P: 98

Implementation of Zero One Knapsack Problem using Divide and Conquer Algorithm

For the implementation of the Zero Knapsack Problem, we first create the Item where each object holds two variables – weight and profit.

Zero One Knapsack Problem can be implemented using the Divide and Conquer Algorithm using the following steps:

• Declare the function and take the items, capacity and current index as parameters.
• If capacity is less than 0, currentIndex is less than 0, or currentIndex is greater than length of the list, return 0.
• Else, if the total weight is less than the capacity, create two profits for checking adajacent items. This is achieved by recursively calling the function with different parameters.
• Return the maximum out of these two profits.

#Function to solve Zero One Knapsack Problem
class Item:
    def __init__(self, profit, weight):
        self.profit = profit
        self.weight = weight

def zeroKnapsack(items, capacity, currentIndex):
    if capacity <=0 or currentIndex < 0 or currentIndex >= len(items):
        return 0
    elif items[currentIndex].weight <= capacity:
        profit1 = items[currentIndex].profit + zeroKnapsack(items, capacity-items[currentIndex].weight, currentIndex+1)
        profit2 = zeroKnapsack(items, capacity, currentIndex+1)
        return max(profit1, profit2)
    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(zeroKnapsack(items, 7, 0))

#Output
98

Longest Common Subsequence (LCS)

We are given two strings S1 and S2. Find the length of the longest subsequence common to both the strings.

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing their order.

Example:
– S1 = “elephant”
– S2 = “erepat”
– Output = 5
– Explanation: Longest common subsequence = “eepat”

Implementation of Longest Common Subsequence using Divide and Conquer Algorithm

The Longest Common Subsequence problem can be implemented using the Divide and Conquer Algorithm using the following steps:

• Declare the function and take the strings s1 and s2, along with their starting indices as parameters.
• If any of the indices of the strings is equal to its respective length, return 0.
• If the characters at the indices of the respective elements are same, recursively provoke the function by incrementing the indices by 1. Return its value + 1.
• Else, create two variables op1 and op2.
• Recursively call the function by incrementing the index of s1 and assign it to op1.
• Recursively call the function by incrementing the index of s2 and assign it to op2.
• Return the maximum of the two variables op1 and op2.

#Function to solve Longest Common Subsequence Problem
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(findLCS("elephant", "eretpat", 0, 0))

#Output
5

Longest Palindromic Subsequence(LPS)

We are given a string. Find the longest palindromic sequence. A palindrome is a string that reads the same backward as well as forward.

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing their order.

Example:
– S = “ELRMENMET”
– Output = 5
– Explanation: Longest palindromic subsequence = “EMEME”

Implementation of Longest Palindromic Subsequence using Divide and Conquer Algorithm

The Longest Palindromic Subsequence problem can be implemented using the Divide and Conquer Algorithm using the following steps:

• Declare the function and take the strings s and the start and end indices as parameters.
• If the startIndex is greater than endIndex, return 0.
• Else, if the startIndex is equal to endIndex, return 1.
• If the characters at the start and end indices of the string are same, recursively provoke the function by incrementing the start index by 1 and decrementing the end index by 1. Return its value + 2
• Else, create two variables op1 and op2.
• Recursively call the function by incrementing the start index and assign it to op2.
• Recursively call the function by decrementing the end index and assign it to op1.
• Return the maximum of the two variables op1 and op2.

#Function to solve Longest Palindromic Subsequence Problem
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))

#Output
5

Minimum Cost

We are given a 2D Matrix. Each cell of the given matrix has a cost associated with it. We need to start from (0, 0) cell and go till (n-1, n-1) cell.

We can only move in the right or downward direction while traversing the cells. Find the minimum cost it will take to reach the destination from the source.

Example:

Solution:
– Min Cost = 36

Implementation of Minimum Cost Problem using Divide and Conquer Algorithm

The Minimum Cost problem can be implemented using the Divide and Conquer Algorithm using the following steps:

• Declare the function and take the matrix, number of rows, and the number of columns as parameters.
• If row or col equals to -1, return an infinite float value.
• If row or col equals to 0, return the intital element of the matrix (tempArray[0][0]).
• Else, create two variables op1 and op2.
• Recursively call the function by decrementing row and assign it to op1.
• Recursively call the function by decrementing col and assign it to op2.
• Return the current element plus the minimum of the two variables op1 and op2.

#Function to solve Minimum Cost Problem
def findMinCost(tempArray, row, col):
    if row == -1 or col == -1:
        return float('inf')
    elif row == 0 and col == 0:
        return tempArray[0][0]
    else:
        op1 = findMinCost(tempArray, row-1, col)
        op2 = findMinCost(tempArray, row, col-1)
        return tempArray[row][col] + min(op1,op2)

tempList = [[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(tempList, 4,4))

#Output
36

Number of Ways

We are given a 2D Matrix. Each cell of the given matrix has a cost associated with it. We need to start from (0, 0) cell and go till (n-1, n-1) cell.

We can only move in the right or downward direction while traversing the cells. We are given the total cost to reach the last cell. Find the number of ways to reach the last cell within the given “total cost”.

Example:
– Total cost = 25

Solution:
– There are 2 paths to reach the last cell within the given cost. Both the paths cost 22.

Implementation of Number of Ways Problem using Divide and Conquer Algorithm

The Number of Ways problem can be implemented using the Divide and Conquer Algorithm using the following steps:

• Declare the function and take the matrix, number of rows, number of columns, and the total cost as parameters.
• If cost < 0, return 0.
• If row or col equals to 0, check whether the difference between the initial element and cost is equal to 0. If yes, return 1.
• Else, return 0.
• Else, if row equals to 0, recursively call the function by passing row as 0, decrementing col, and decrementing the cost.
• Else, if col equals to 0, recursively call the function by passing col as 0, decrementing row, and decrementing the cost.
• Else, create two variables op1 and op2.
• Recursively call the function by decrementing row and cost and assign it to op1.
• Recursively call the function by decrementing col and cost and assign it to op2.
• Return the sum of the two variables op1 and op2.

#Function to solve Number of Ways Problem
def numberOfWays(twoDArray, row, col, cost):
    if cost < 0:
        return 0
    elif row == 0 and col == 0:
        if twoDArray[0][0] - cost == 0:
            return 1
        else:
            return 0
    elif row == 0:
        return numberOfWays(twoDArray, 0, col-1, cost - twoDArray[row][col])
    elif col == 0:
        return numberOfWays(twoDArray, row-1, 0, cost - twoDArray[row][col])
    else:
        op1 = numberOfWays(twoDArray, row - 1, col, cost - twoDArray[row][col])
        op2 = numberOfWays(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(numberOfWays(TwoDList, 3, 3, 25))

#Output
2