Table of contents
- What is Divide and Conquer Algorithm?
- How to solve Fibonacci Series using Divide and Conquer approach?
- Number factor
- Number factor in Python
- House robber
- House Robber Problem in Python
- Convert one string to another
- Convert one string to another in Python
- Zero One knapsack problem
- Zero One knapsack problem in Python
- Longest Common sequence problem
- Longest Common sequence problem in Python
- Longest Palindromic Subsequence problem
- Longest Palindromic Subsequence in Python
- Minimum cost to reach the Last cell problem
- Minimum cost to reach the Last cell in 2D array using Python
- Number of Ways to reach the last cell with given cost
- Number of Ways to reach the last cell with given cost in Python
- End.
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:
Weight | Profit | |
Mango | 3 | 31 |
Apple | 1 | 26 |
Orange | 2 | 17 |
Banana | 5 | 72 |
Answer combinations:
Mango + Apple + Orange : weight 6; profit 74
Orange + banana : weight 7; profit 89
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:
Option 1 = 31 + f(2,3,4) [1st items' profit]
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)
Option 1 = 1 + f(2 (2nd char of s1), 8(length of s1) : 2(2nd char of s2), 7(length of s2))
Option 2 = 0 (they are not matching) + f(3,8 : 2,7)
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:
Option 1 = 2 + f(2,8)
If the characters at the two ends of the current substring (i.e.,
S[i]
andS[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).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 excludingS[i]
. This gives the subproblemf(i+1, j)
.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 excludingS[j]
. This gives the subproblemf(i, j-1)
.Max(option1, option2, option3)
These three options cover all possible cases:
Option 1 considers the case where both the first and last characters can be part of the LPS.
Option 2 considers the case where the first character is excluded.
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:
Option 1 = y + 9 + 3 f(4, 3)
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:
Option 1 = y + 2 = 22 f(3,4,22)
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))