## Algorithms Notes

Algorithm Basics

Divide And Conquer

Greedy Algorithm

Dynamic Programming

Shortest Path

Backtracking

Minimum Spanning Tree

Maximum Flow

Complexity Classes

# Heading

Q

1

Explain the general equation of divide and conquer.

Ans

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.

Q

2

What is the divide and conquer strategy? discuss its fundamentals .

Ans

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.

Q

3

Explain with example the max-min problem in divide and conquer technique .

Ans

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:

Q

4

Explain with example merge sort in divide and conquer technique .

.

Ans

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;

}

Q

5

Explain with example the binary search in divide and conquer technique.

Ans

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;

}

Q

6

Analyse best, worst and average cases of binary search.

Ans

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).

Q

7

Explain with example the tower of hanoi in divide and conquer technique.

Ans

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;

}

Q

8

Explain with example the strassens matrix multiplication in divide and conquer technique.

Ans

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 ]

Q

9

What is the advantage of strassens matrix multiplication over ordinary matrix multiplication?

Ans

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.