Heading

The divide and conquer algorithm is used to break down a complex problem into simpler sub-problems to solve them easily. The complexity of the divide and conquer algorithm can be determined using the recurrence relation.
The recurrence relation of the divide and conquer algorithm is given by the following formula:
f(n) = a*f(n/b) + g(n) where,
f(n) 🡪 the number of operations to be performed to solve a problem of size 'n'
g(n) 🡪 the additional computations required to combine the sub-problem solutions. (or) the cost of the combinations performed.
b 🡪size of the sub problem
a 🡪 number of recursive calls

As the given problem is divided into 'b' sub-problems, the complexity will be a scalar multiple of f(n/b) in addition to the cost of the combination.

The main objective of the divide and conquer strategy is to break down a complex problem into sub-problems until it becomes simple enough to solve it easily. Then, the solutions of the sub-problems are combined to solve the original complex problem. There are three steps in solving a problem using the divide and conquer strategy. They are:
a. Divide
This step involves breaking down a complex problem into sub-problems of the same type.
b. Conquer
This step involves conquering the sub-problems by solving them using recursion.
c. Combine
Finally, the solutions of the sub-problems are combined to get the solution of the given complex problem.
The Divide and conquer algorithm can be used to solve a complicated problem if and only if the problem is divisible into sub-problems of the same type.

The max-min problem
Find the maximum and minimum values in a given array.
Solution using Divide and Conquer Technique
a. Divide the array into two halves
b. Find the maximum and minimum elements in both the halves.
c. Return the maximum of the two maxima calculated in each half.
d. Return the minimum of the two minima calculated in each half.
Algorithm
if y-x <=1 then
return (max(numbers[x], numbers[y], min((numbers[x], numbers[y]))
else
(max1, min1):= maxmin(x, ((x+y)/2))
(max2, min2):= maxmin(((x+y)/2 + 1),y)
Return (max(max1, max2), min(min1, min2))
Example
Find the maximum element of the given array using divide and conquer strategy
29, 14, 15, 1, 6, 10, 32, 12
The solution to the given problem is explained using the diagram given below:

Merge sort divides the given array into two equal halves and then combines them after sorting both the halves. If the sub-array is empty or has only one element, it is considered as sorted. Else, the sub-array is split into two halves and merge sort is invoked recursively on both the halves.
Algorithm:
MergeSort(A, p, r):
if p > r
return
q = (p+r)/2
mergeSort(A, p, q)
mergeSort(A, q+1, r)
merge(A, p, q, r)
Example:
Sort the following array in ascending order.
26, 10, 50, 7, 18, 111, 9, 34

C Code
#include <stdio.h>
#include <stdlib.h>

void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];

for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];

i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}

while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

void mergeSort(int arr[], int l, int r)
{
if (l < r) {
int m = l + (r - l) / 2;

mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);

merge(arr, l, m, r);
}
}

void printArray(int A[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}

int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);

printf("Given array is \n");
printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}

The binary search algorithm can be applied for searching an element in a pre-sorted array.
In binary search, the target value is first compared with the middle element of the given sorted array.
1. If the mid element is equal to the target value, the search is complete.
2.If the mid element is greater than the target value, the target element cannot lie in the lower half of the array. So, the search is done in the upper half of the array.
3.If the mid element is smaller than the target value, the target element cannot lie in the upper half of the array. Hence, the search is continued in the lower half of the array.
4.The above steps 1) 2) and 3) are repeated until the target element is found.
5.If the array becomes empty before the target value is found, then the target value does not exist in the array.

The mid value is calculated using the following formula:
Mid = (low+high)/2 Algorithm

Procedure BinarySearch
low=0
high=n-1
while(low<=high)
{
mid=(high+low)/2;
if(A[mid] == data)
return mid;
if(A[mid] < data)
low=mid+1;
if(A[mid] >data)
high=mid-1;
}

Best Case
Best case in binary search occurs when the item to be searched in the mid element of the given array.
Time Complexity of binary search in the best case is O(1).
Average Case
The average case of binary search occurs when the target element is not the mid element of the array. The average case time complexity is O(logn).
Worst Case
The worst case in binary search occurs if the element searched is not in the array.
The worst case time complexity of binary search is O(logn).

Tower of Hanoi Problem
The Tower of Hanoi is a mathematical puzzle in which three rods are given. Disks of different sizes are placed one over the other on one of the three rods (or poles) in ascending order. Our aim is to find the number of moves and the order in which the disks have to be moved, to move all the given disks from the first rod(source) to the third rod(destination) in the same order. The only condition is that a disk cannot be placed over another disk that is smaller than itself.
Recursive Solution
The movement of ‘n’ disks from source to destination can be divided into sub-problems by considering the largest disk as one part and the remaining ‘n-1’ disks as the other part. We keep on dividing the problem into sub-problems until the number of disks becomes 1. We apply these steps in the recursive way to all the disks.
Steps
a. Move n-1 disks from the first pole (source) to the auxillary pole
b. Move nth disk from the source to the destination pole.
c. Move n-1 disks from the auxillary pole to the destination pole.

Algorithm
Procedure Tower_of_Hanoi (disk, source, dest, aux)
If no_of_disks ==1:
Move disk from source to destination
Else:
Tower_of_Hanoi ( disk-1, source, aux, dest)
Move disk from source to dest
Tower_of_Hanoi ( disk-1, aux, dest, source)
End Procedure

C Code
#include <stdio.h>
void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod)
{
if (n == 1)
{
printf("\n Move disk 1 from rod %c to rod %c", from_rod, to_rod);
return;
}
towerOfHanoi(n-1, from_rod, aux_rod, to_rod);
printf("\n Move disk %d from rod %c to rod %c", n, from_rod, to_rod);
towerOfHanoi(n-1, aux_rod, to_rod, from_rod);
}

int main()
{
int n = 4; // Number of disks
towerOfHanoi(n, 'A', 'C', 'B'); // A, B and C are names of rods
return 0;
}

Strassen's matrix multiplication gives us a simple method to multiply two 2x2 matrices.
Some formulas are used to find the product of two 2x2 matrices. By using these formulas the time complexity of matrix
multiplication can be greatly reduced. The time complexity is reduced because,
by the using the strassen's formulas, the number of multiplication operations performed is reduced.
To use the Strassen's method for matrix multiplication, both the multiplier and multiplicand matrices have an order of power of 2.
The Strass's matrix multiplication formulas involve 7 multiplications and 18 addition-subtraction operations.
Steps
Divide the given matrix recursively till we get the matrix of order 2*2.
Carry out the 2x2 multiplication using the formulas given below.
Combine the results of the two matrixes to find the final result.

Formulae
Multiplication formulas
D1 = (a11 + a22) (b11 + b22)
D2 = (a21 + a22).b11
D3 = (b12 – b22).a11
D4 = (b21 – b11).a22
D5 = (a11 + a12).b22
D6 = (a21 – a11) . (b11 + b12)
D7 = (a12 – a22) . (b21 + b22)

Addition, subtraction formulas
C11 = d1 + d4 – d5 + d7
C12 = d3 + d5
C21 = d2 + d4
C22 = d1 + d3 – d2 + d6

Algorithm
Procedure Strassen (a, b, d, n)
BEGIN
If n = threshold then compute
C = a * b is a conventional matrix.
Else
Partition a into 4 sub matrices 🡪 a11, a12, a21, a22.
Partition b into 4 sub matrices 🡪 b11, b12, b21, b22.
Strassen ( n/2, a11 + a22, b11 + b22, d1)
Strassen ( n/2, a21 + a22, b11, d2)
Strassen ( n/2, a11, b12 – b22, d3)
Strassen ( n/2, a22, b21 – b11, d4)
Strassen ( n/2, a11 + a12, b22, d5)
Strassen (n/2, a21 – a11, b11 + b22, d6)
Strassen (n/2, a12 – a22, b21 + b22, d7)

C = d1+d4-d5+d7 d3+d5
d2+d4 d1+d3-d2-d6

end if

return (C)
END
Example
A= [1 2 3 4 ] B= [4 3 2 2 ]
D1 = (1+4)*(4+2) = 30
D2 = (3+4)*4 = 28
D3 = 1*(3-2) = 1
D4 = 4*(2-4) = -8
D5 = (1+2)*2 = 6
D6 = (3-1)*(4+3) = 14
D7 = (2-4)*(2+2) = -8
C11 = 30-8-6-8 = 8
C12 = 1+6 = 7
C21 = 28-8 = 20
C22 = 30+1-28+14 = 17

The final answer is
C=A*B= [7 7 20 17 ]

Strassen's Matrix Multiplication is better than the Naive matrix multiplication method because it has a time complexity of n2.81, but the latter has the time complexity of n3.

We use some formulas to find the product of two 2x2 matrices in Strassen's matrix multiplication method. By using these formulas the time complexity of matrix multiplication can be greatly reduced. The normal matrix multiplication method requires 8 multiplications and 4 additions. But, Strassen's method requires only 7 multiplications and 18 additions.

The time complexity is low because, by using Strassen's formulas, the number of multiplication operations performed is decreased.