Analysis of Algorithm Introduction

Chapter-1. Introduction

What is Algorithm
Finite set of steps to solve a problem is call algorithm.
Analysing is a process of comparing two algorithms w.r.t time and space.
In computer science, the analysis of algorithms is the process of finding the computational
complexity of algorithms – the amount of time, storage, or other resources needed to execute them.

Initially the solution to problem is written in natural language known as algorithm then this
algorithm is converted into code.
If algorithm is correct then program should produce correct output on valid input otherwise it
should generate an appropriate error message.
An algorithm is said to be efficient when this function's values are small, or grow slowly compared
to a growth in the size of the input.
Different inputs of the same length may cause the algorithm to have different behaviour, so best,
worst and average case.

➢ A good algorithm should have following properties and characteristics:

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 1
 Analysis of Algorithm Introduction

(i) Input:
The range of input for which algorithm work and there should be clear indication for the range of
inputs for which the algorithm may fail.
(ii) Output:
Algorithm reads input, processes it and produce at least one output.
(iii) Definiteness:
Each of the statement in the algorithm must be clear and precise. There should not be ambiguity in
any of the statement.
(iv) Finiteness:
Algorithm should be finite i.e there should not be infinite condition leading to a never-ending
procedure and hence never completing the task.
(v) Effectiveness:
It should produce the result as fast as possible or efficiently.

How to write algorithm

• Algorithm Basically consist of two-part Head, Body
• Head Consist of algorithm name, description of problem, input and expected output.
• Body Consist of description of functionality.
1. Algorithm should start with keyword followed by name of algorithm
“Algorithm Find_Sum(A, B)”
2. Use left arrow for assignment: C  A + B
3. Input and Output are performed using read and write statement
Read(A) or Read “A”
Write(A) or Write “A” or Print “A”
4. Control Statements
If (Condition) then Statement end

If (Condition) then Statement1 else statement2 end

5. Loop Statement
a. While (condition) do
Do Some Work
end
b. For index  Start to end do
Do some work
End

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 2
 Analysis of Algorithm Introduction

Example: Write an algorithm for finding the factorial of a number n.

Algorithm Factorial(n)
// Description: Find factorial of given number
// Input: Number n whose factorial is to be computed.
// Output: Factorial of n = n × (n – 1) × …. × 2 × 1

If (n ==1) then
return 1
else
return n * Factorial(n – 1)

Performance Analysis
• Efficiency:
Efficiency of algorithm is it should take less space in memory and also require less time for
giving the output.
The various parameters required to be considered for the efficiency of an algorithm are:
1. Space Complexity
2. Time Complexity

1. Space Complexity
The amount of memory requires to solve given problem is called space complexity of the
algorithm.

➢ Space complexity controlled by two Components:

1. Fixed size component

Programming part whose memory requirement does not alter on program execution.

e.g., Variables, Constant, arrays

2. Variable size component

Programming part whose size depends on program being solved.
e.g., size of loop, linked list.
We use notation s(n) to specify the space complexity.
Where n is treated as size of input.

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 3
 Analysis of Algorithm Introduction

Example: Addition of two scalar variables.

Algorithm ADD_SCALAR(A,B)
// Description: Perform arithmetic addition of two numbers
// Input: Two scalar variables A and B
// Output: variable C, which holds the addition of A and B
C←A+B
return C

The addition of two scalar numbers required one extra memory location to hold the result. Thus
the space complexity of this algorithm is constant, hence S(n) = O(1).

Example: Addition of two Arrays.

Algorithm ADD_ARRAY(A, B)
// Description: Performa element-wise arithmetic addition of two arrays
// Input: Two number arrays A and B
// Output: Array C holding the element-wise sum of array A and B
for i ← 1 to n do
C[i] ← A[i] + B[i]
end
return C

Addition corresponding elements of two arrays, each of size n requires extra n memory locations
to hold the result. As input size n increases, required space to hold the result also grows in the linear order
of input. Thus, the space complexity of above code segment would be S(n) = O(n).

Example: Sum of elements of Arrays.

Algorithm SUM_ARRAY_ELEMENTS(A)
// Description: Add all elements of array A
// Input: Array A of size n
// Output: Variable Sum which holds the addition of array elements
Sum ← 0
for i ← 1 to n do

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 4
 Analysis of Algorithm Introduction

Sum ← Sum + A[i]

end
return Sum

The addition of all array elements requires only one extra variable denoted as sum, this is independt
of array size.
So space complexity of algorithm is S(n)=O(1)

2. Time Complexity
The Time required by the algorithm to solve given problem is called complexity of the algorithm.
Time complexity is not measured in physical clock tricks, rather it is most frequent operation in
algorithm.
We use notation T(n) to symbolise time complexity

Example: Addition of two scalar variables.

Algorithm ADD_SCALAR(A, B)
// Description: Perform arithmetic addition of two numbers
// Input: Two scalar variable A and B
// Output: Variable C, which holds the addition of A and B
C←A+B
return C

The sum of two scalar numbers requires one addition operation. Thus the time complexity of this
algotithm is constant, so T(n) = O(1).

Example: Perform addition of two Arrays.

Algorithm ADD_ARRAY(A, B)
// Description : Perform element wise arithmetic addition of two arrays
// Input : Two number arrays A and B of length
// Output : Array C holding the element wise sum of array A and B
for i ← to n do
c[i] ← A[i] + B[i]
end
return C

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 5
 Analysis of Algorithm Introduction

As it can be observed from above code, addition array elements required iterating loop n times.
Variable i is initialized once, the relation between control variable i and n are checked n times, and i is
incremented n times. With the loop, addition and assignment operations are performed n time.
Thus, the total time of algorithm is measured as
T(n) = f(initialization) + n(comparison+ increment +addition + assignment)
= 1 + 4n
While doing efficiency analysis of the algorithm, we are interested in the order of complexity in term
of input size n.
So, all multiplicative and divisive constants should be dropped. Thus, for given algorithm T(n) = O(n).

Example: Sum of elements of array.

Algorithm SUM_ARRAY_ELEMENTS(A)
// Description: Add all elements of array A
// Input: Array A of size n
// Output: Variable Sum which holds the addition of array elements
Sum ← 0
for i ← 1 to n do
Sum ← Sum + A[i]
end

The addition of all array elements requires n additions (we shall omit ṭhe number of comparisons,
assignment, initialization etc. to avoid the multiplicative or additive constants. A number of additions
depend on the size of the array. It grows in the linear order of imput size. Thus the time complexity of
above code is T(n) = O(n).

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 6
 Analysis of Algorithm Introduction

Growth Function
Growth functions are used to estimate the number of steps an algorithm uses as its input
grows.
Order of growth indicates how quickly the time required by algorithm grows with respect to
input size.
The largest number of steps needed to solve the given problem using an algorithm on input
of specified size is worst-case complexity.

➢ Efficiency classes are categories into different classes:

Efficiency Order of Example

Class Growth Rate
Delete the first node from linked list

1 Remove the largest element from max heap

Constant
Add two numbers

Binary search
Logarithmic log n
Insert / delete element from binary search tree

Linear search

n Insert node at the end of linked list

Linear
Find minimum / maximum element from array

Merge sort
Binary search
n log n n log n
Quick sort
Heap sort

Selection sort
Bubble sort
Quadratic n2
Input 2D array
Find maximum element from 2D matrix

n3 Matrix multiplication
Cubic
Find power set of any set

2n Find optimal solution for knapsack problem

Exponential
Solve TSP using dynamic programming

These are widely used classes, there exist many other classes.
Algorithm having exponential or factorial running time are unacceptable for practical use.

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 7
 Analysis of Algorithm Introduction

Asymptotic Notation
Asymptotic notations are mathematical tool to find time and space complexity of an algorithm
without implementing it in a programming language.
It is way of describing cost of algorithm.
Asymptotic notation does analysis of algorithm independent of processor speed, ram, memory.
For example: In bubble sort, when the input array is already sorted, the time taken by the algorithm
is linear i.e., the best case.
But, when the input array is in reverse condition, the algorithm takes the maximum time (quadratic)
to sort the elements i.e., the worst case.
When the input array is neither sorted nor in reverse order, then it takes average time. These
durations are denoted using asymptotic notations.
➢ There are mainly three asymptotic notations:
• Big-O notation
• Omega notation
• Theta notation
1. Big oh
The notation is denoted by ‘O’ and pronounced as Big oh
It means running time of algorithm cannot be more than its
asymptotic upper bound.

• Big oh (o) (Upper Bound)

f(n) = O(g(n))
f(n) <= c.g(n)
In this f(n) lies on or below c.g(n)

2. Big Omega
This notation is denoted by ‘Ω’ and pronounced as Big
omega
It defines lower bound for the algorithm.
It means running time of algorithm cannot be less than its
asymptotic lower bound.

• Omega(o) (Lower Bound)

f(n) = Ω(g(n))
f (n) >= c.g(n)
In this f (n) lies on or above c.g(n).

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 8
 Analysis of Algorithm Introduction

3. Big Theta
This notation is denoted by ‘𝜃’ and pronounced as Big
theta
It defines lower bound for the algorithm.
It means running time of algorithm cannot be less or
greater than its asymptotic tight bound.

• Theta(o) (between order)

f(n) = 𝜃(g(n))
c1.g(n) <= f(n) <= c2.g(n)
In this f(n) lies between c1.g(n) and c2.g(n)

Example: Represent the following function using Big oh, Omega and Theta Notations.
(i) (n) = 3n + 2 (ii) T(n) = 10n2 + 2n + 1
Solution:
(A) Big oh (upper bound)
(i) T(n) = 3n + 2
To Find upper bound of f(n), we have to find c and n0 such that 0 ≤ f(n) ≤ c . g(n) for all n ≥
n0
0 ≤ f(n) ≤ c . g (n)
0 ≤ 3n + 2 ≤ c . g (n)
0 ≤ 3n + 2 ≤ 3n + 2n, for all n ≥ 1 (there can be such infinite possibilities)
0 ≤ 3n + 2 ≤ 5n
So, c = 5 and g(n) = n, n0 = 1

(ii) T(n) = 10n2 + 2n + 1

To find upper bound of f(n), we have to find c and n0 such that 0 ≤ f(n) ≤ c . g (n) for all n ≥
n0
0 ≤ f(n) ≤ c . g (n)
0 ≤ 10n2 + 2n + 1 ≤ 10n2 + 2 n2 + n2 for all n ≥ 1
0 ≤ 10n2 + 2n + 1 ≤ 13n2
So, c = 13, g(n) = n2 and n0 = 1

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 9
 Analysis of Algorithm Introduction

(A) Lower bound

(i) T(n) = 3n + 2
To Find lower bound of f(n), we have to find c and n0 such that 0 ≤ c . g(n) ≤ f(n) for all n ≥
n0
0 ≤ c . g(n) ≤ f(n)
0 ≤ c . g(n) ≤ 3n + 2
0 ≤ 3n ≤ 3n + 2 → true, for all n ≥ n0
f(n) = Ω (g(n)) = Ω(n) for c = 3, n0 = 1

(ii) T(n) = 10n2 + 2n + 1

To find lower bound of f(n), we have to find c and n0 such that 0 ≤ c . g (n) ≤ f(n) for all n ≥
n0
0 ≤ c . g (n) ≤ f(n)
0 ≤ c . g (n) ≤ 10n2 + 2n + 1
0 ≤ 10n2 ≤ 10n2 + 2n + 1 → true, for all n ≥ 1
So, c = 13, g(n) = n2 and n0 = 1
f(n) = Ω (g(n)) = Ω(n2) for c = 3, n0 = 1

(A) Tight bound

(i) T(n) = 3n + 2
To Find tight bound of f(n), we have to find c1, c2 and n0 such that 0 ≤ c1 . g(n) ≤ c2 . g(n) for
all n ≥ n0
0 ≤ c1 . g(n) ≤ 3n + 2 ≤ c . g(n)
0 ≤ 3n ≤ 3n + 2 ≤ 5n, for all n ≥ 1
Above inequality is true and there exists such infinite inequalities.
So, f(n) = θ(g(n)) = θ(n) for c1 = 3, c2 = 5, n0 = 1

(ii) T(n) = 10n2 + 2n + 1

To Find tight bound of f(n), we have to find c1, c2 and n0 such that 0 ≤ c1 . g(n) ≤ f(n) ≤ c2 .
g(n) for all n ≥ n0
0 ≤ c1 . g(n) ≤ 10n2 + 2n + 1 ≤ c2 . g(n)
0 ≤ 10n2 ≤ 10n2 + 2n + 1 ≤ 5n, for all n ≥ 1
Above inequality is true and there exists such infinite inequalities.
So, f(n) = θ(g(n)) = θ(n2) for c1 = 10, c2 = 13, n0 = 1

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 10
 Analysis of Algorithm Introduction

P, NP, NP Hard and NP Complete

➢ Problem can be classified in one of the following categories,

1. Problem cannot be defined in a proper way

2. Problem which can be defined but cannot be solved.
3. Problem which can be solved but computationally they are not feasible algorithm takes long
time to solve such a problem.

Intractable: - Problem is called intractable if it takes too long time to solve.

4. Problem which can be solved theoretically and practically in reasonable amount of time

Tractable: - If the problem is solvable in polynomial time, it is called tractable such a

problem is denoted by P

Polynomial Time Exponential time

• Linear Search O(n) Traveling Salesman 2n

• Binary Search O(logn) su-do-ku 2n
• Inserting element O(n) Scheduling 2n
• Selection sort O(n2)

1. P- Polynomial time solving.

Problems which can be solved in polynomial time is known as P class problem (Sorting/
Searching), which take time like O(n), O(n2), O(n3).

E.g.,: finding maximum element in an array or to check whether a string is palindrome or not. So there
are many problems which can be solved in polynomial time.

P: problems are quick to solve

2. NP- Non deterministic Polynomial time solving.

Problem which can't be solved in polynomial time but can be verified in polynomial time like
TSP( travelling salesman problem) , su-do-ku

But NP problems are checkable in polynomial time means that given a solution of a problem, we can
check that whether the solution is correct or not in polynomial time.

NP : Problems are quick to verify but slow to solve

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 11
 Analysis of Algorithm Introduction

P is subset of NP

Take two problems A and B both are NP problems.

Reducibility- If we can convert one instance of a problem A into problem B (NP problem) then it means
that A is reducible to B.

NP-hard—Problem is NP-Hard if every problem in NP can be polynomially reduced to it.

Now suppose we found that A is reducible to B, then it means that B is at least as hard as A.

NP Hard: Problems are slow to verify, slow to solve and can be reduced to any other problem.

NP-Complete -- The group of problems which are both in NP and NP-hard are known as NP-Complete
problem.

NP-complete problems are the hardest problems in NP set.

Now suppose we have a NP-Complete problem R and it is reducible to Q then Q is at least as hard as R
and since R is an NP-hard problem. Therefore Q will also be at least NP-hard, it may be NP-complete also.

NP Complete: Problems are also quick to verify, slow to solve and can be reduced to any other problem.

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 12
 Analysis of Algorithm Divide and Conquer Approach

Chapter-2. Divide and Conquer Approach

Introduction
• The technique of diving large problems into smaller subproblems, solving subproblems and
combining them to get solution of original large problem.
• Divide and Conquer is a recursive problem-solving
approach which break a problem into smaller
subproblems.
1. Divide: This involves dividing the problem into some sub
problem.
2. Conquer: Sub problems are solved independently.
3. Combine: The Sub problem combine so that we will get
find problem solution.

Applications
Many computer science problems are effectively solved using divide and conquer.
• Finding exponential of the number
• Multiplying large numbers.
• Multiplying matrices.
• Sorting elements (Quick sort and Merge Sort )
• Searching elements from the list (Binary Search)
• Discreate Fourier Transform.
• Max-Min Problem.

General Method (Control Abstraction)

• Divide and conquer approach works in three stages.
1. Recursively divide the problem into smaller subproblems.
2. Subproblems are solved independently.
3. Combine solutions of subproblems in-order to derive solution of the original big-problem.
• Each subproblem in divide and conquer are independent and hence subsystem may be solved
independent times.

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 1
 Analysis of Algorithm Divide and Conquer Approach

Master Method

➢ Time Complexity :-
n
T(n) = aT (b) + f(n)

• n is the size of the problem

• a is number of subproblems in the recursion
• n/b is the size of each sub problem
• F(n) is cost of the work done other than recursive calls like
• Cost of dividing the problem
• Cost of merging solution

Explain Binary Search using divide and Conquer

• Searching is the problem of finding element from given set of data.

• Binary search uses divide and conquer approach.
• Algorithm divides the list into two halves and check if element to be searched is on upper or lower
half of the array.
• If element is found in middle then algorithm returns otherwise it continues.

Binary Search

0 1 2 3 4 5 6 7 8 9
Search 23 2 5 8 12 16 23 38 56 72 91
L=0 1 2 3 M=4 5 6 7 8 H=9
23 > 16
Take 2nd half
2 5 8 12 16 23 38 56 72 91

0 1 2 3 4 L=5 6 M=7 8 H=9

23 > 56
Take 1st half
2 5 8 12 16 23 38 56 72 91

0 1 2 3 4 L=5, M=5 H=6 7 8 9

Found 23
Return 5
2 5 8 12 16 23 38 56 72 91

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 2
 Analysis of Algorithm Divide and Conquer Approach

Algorithm

Algorithm BINARY-SEARCH(A, Key)

//Description: Perform Binary Search on Array A.
//Input: Sorted Array A of size n and Key to be Searched
//Output: Data found or not found.
Start1
End n
if start <= end
middle = floor((start+end)/2)
if A[middle]==x
return middle
if A[middle]>x
return BINARY-SEARCH(A, start, middle-1, x)
if A[middle]<x
return BINARY-SEARCH(A, middle+1, end, x)
return FALSE // in case, element is not in the array

Merge Sort
• Merge Sort Uses divide and Conquer approach.
• In Merge Sort, we divide array into two halves, sort the two halves recursively, and then merge the
sorted halves.

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 3
 Analysis of Algorithm Divide and Conquer Approach

void mergesort(int a[], in i, int j) {

int mid;
if (i < j) {
mid = (i + j)/2;
mergesort(a, i, mid); //left recurssion
mergesort(a, mid+1, j); //right recurssion
merge (a, i, mid, mid+1, j); //merging of two sorted sub-array
}

void merge(int a[ ],int i1,int j1,int i2,int j2)

{
int temp[50]; //array used for merging
int i,j,k;
i=i1; //beginning of the first list
j-i2; //beginning of the second list
while(i<=j1 && j<=j2) //while elements in both lists
{
if(a[i]<a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
while(i<=j1) //copy remaining elements of the first list
temp[k++] = a[i++];
while(j <= j2) //copy remaining elements of the sec
temp[k++] = a[j++];
//Transfer elements from temp[ ] back to a[ ]
for(i = i1, j = 0; i <= j2; i++, j++)
a[i]=temp[j];

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 4
 Analysis of Algorithm Divide and Conquer Approach

Algorithm for merge sort is described below.

Algorithm MERGE_SORT(A,B)
// Description: Sort elements of array A using Merge sort
// Input: Array of size n, low ← 1 and high ← n
// Output: Sorted array B
if low < high then Recursively sort first sub list
mid ← floor (low + high) / 2
MERGE_SORT(A, low, mid) Recursively sort second sub list
MERGE_SORT(A, mid+1, high)
COMBINE(A, low, mid, high) // merge two sorted sublists
end

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 5
 Analysis of Algorithm Divide and Conquer Approach

Procedure COMBINE performs a two way merge to produce a sorted array of size n from two
sorted arrays of size n/2. The subroutine works as follow:

COMBINE (A, low, mid, high)

l1 ← mid – lwo + 1 // size of 1st array
l2 ← high – mid // size of 2nd array
for i ← 1 to l1 do
LEFT [i] ← A [low + i – 1] // copy 1st sub list in array
LEFT
end
for j ← 1 to l2 do
RIGHT [i] ← A [mid + j] // copy 2nd sub list in array
RIGHT
end
// insert sentinel symbol at the end of each array
LEFT [l1 + 1] ← ∞
RIGHT [l2 + 1] ← ∞

// Start two-way merge process

i ← 1, j ← 1 Two-way merge

for k ← low to high do // perform 2-way merge on LEFT & RIGHT

if LEFT[i] ≤ RIGHT[j] then
//smaller element is in LEFT sub list, so copy it in B
B[k] ← LEFT[i]
i←i+1
else
// smaller element is in RIGHT sub list, so copy it in B
B
B[k] ← RIGHT[i]
j←j+1
end
end

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 6
 Analysis of Algorithm Divide and Conquer Approach

Quick Sort
• It is divided and conquer based approach.
• It select one element as a pivot and moves pivot to correct location.
• Fixing the pivot to correct location divides the list into two sub list.
• Each sub lists is solved recursively.

Procedure:

- Scan array from left to right until an element greater than pivot is found.

- Scan array from right to left until an element equal or smaller than pivot is found.

- After finding such elements,

✓ If low < high, then exchange A[low] and A[high].

✓ If low ≥ high, then exchange A[pivot] and A[high], which will split the list into two sub-
lists. Solve them recursively.

Algorithm for quick sort is shown below:

Algorithm QUICKSORT(A, low, high)

// Description: Sort array A using Quick sort
// Input: Unsorted array A of size n, low = 0, high = n – 1
// Output: Sorted array A
if low ≤ high then Find pivot index to split the list

q ← PARTITION (a, low, high)

Sort left sub list
QUICKSORT(A, low, q – 1)
Sort right sub list
QUICKSORT(A, q + 1, high)
end

The pseudo code of PARTITION subroutine is given below:

PARTITION (A, low, High)

x ← A[high] // x is pivot element i.e. last element of list

i ← low – 1
for j ← low to high – 1 do
if A[j] ≤ x then
i←i+1
swap (A[i], A[j])
This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 7
 Analysis of Algorithm Divide and Conquer Approach
end
end
swap (A[i + 1], A[High])
return (i + 1) // Correct index of pivot after sorting

Min- Max Problem

• It is used to find min and max element from given array.
• In traditional approach the maximum and minimum element can be found by comparing each
element. This approach is simple but it require n – 1 comparison.
• Using divide and conquer approach, we can reduce the number of comparison.
• If a1 is the only element in array, a1 is maximum and minimum.
• If the array contains only two element a1 and a2 then the single comparison between two elements
can decide minimum and maximum two elements.
• If there are more than two elements, algorithm divides the array from middle and crate two
subproblems.
• Both subproblems are treated as an independent problem and same recursive process is applied.
• The division continues until subproblem size becomes one or two.
• After solving two subproblems, their minimum and maximum numbers are compared two build the
solution of large problem.
• This process continues in bottom up fashion to build solution of parent problem.

Algorithm DC_MAXMIN (A, low, High)

//Description: Find minimum and maximum element from array using
divide and conquer approach
//Input: Array A of length n, and indces low = 0 and high = n – 1
//Output: (min, max) variables holding minimum and maximum element of
array
if n == 1 then
return (A[1], A[1])
else if n == 2 then
if A[1] < A[2] then
return (A[1], A[2])
else
return (A[2], A[1])
else
mid ← (low + high)/2
This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 8
 Analysis of Algorithm Divide and Conquer Approach
[LMin, LMax] = DC_MAXMIN(A, low, mid)
[RMin, RMax] = DC_MAXMIN(A, mid + 1, high)

if LMax > RMax then //Combine solution

max ← LMax
else
max ← RMax
if LMin > RMin then //Combine solution
min ← LMin
else
min ← RMin
else
return (min, max)
end

Strassen’s matrix multiplication

• The strassens algorithm, named after Volker Strassen, is algorithm for matrix multiplication.
• It is faster than the standard matrix multiplication algorithm.

• It takes less number of multiplication compare to this traditional way of matrix multiplication.

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 9
 Analysis of Algorithm Greedy method Approach

Chapter-3. Greedy Method Approach

Introduction
• Greedy Method find out the best method/option out of many present ways
• Greedy algorithm is optimization technique, it tries to find an optimal solution from the set of
feasible solutions.
• Greedy algorithm derive solution step by step, by looking at information available at current
moment. It does not look at future prospects.
• Decisions are completely locally optimal.

➢ Steps for achieving a Greedy Algorithm are

• Feasible:
Choice should satisfy problem constraint.
• Local Optimal Choice:
Best Solution from all feasible solution at current stage should be selected.
• Unalterable:

- Once the choice is made it cannot be altered at any subsequence stages.

- The choice made under greedy solution procedure are irrevocable, means once we have selected
solution the local best solution it cannot be backtracked.

Algorithm GREEDY_APPROACH(L, n)
//Description: Solve the given problem using greedy approach.
//Input: L: List of possble choices, n: size of solution
//Output: Set Solution containing solution of given problem

Solution  ∅
for i  1 to n do
Choice  Select(L)
if (feasible(Choice ∪ Solution)) then
Solution  Choice ∪ Solution
end
end
return Solution

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 1
 Analysis of Algorithm Greedy method Approach

Dijkstra's Algorithm
• It is a greedy algorithm that solves the single-source shortest path problem.
• Single-Source means that only one source is given, and we have to find the shortest path from the
source to all the nodes.
• Dijkstra's Algorithm maintains a set S of vertices whose final shortest - path weights from the
source s have already been determined.

Example:

Let's understand the working of Dijkstra's algorithm. Consider the below graph.

First, we have to consider any vertex as a source vertex. Suppose we consider vertex 0 as a source
vertex.

Here we assume that 0 as a source vertex, and distance to all the other vertices is infinity. Initially,
we do not know the distances. First, we will find out the vertices which are directly connected to the vertex
0. As we can observe in the above graph that two vertices are directly connected to vertex 0.

Let's assume that the vertex 0 is represented by 'x' and the vertex 1 is represented by 'y'. The distance
between the vertices can be calculated by using the below formula:

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 2
 Analysis of Algorithm Greedy method Approach

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (0 + 4) < ∞
3. = 4 < ∞

Since 4<∞ so we will update d(v) from ∞ to 4.

Therefore, we come to the conclusion that the formula for calculating the distance between the
vertices:

1. {if( d(u) + c(u, v) < d(v))

2. d(v) = d(u) +c(u, v) }

Now we consider vertex 0 same as 'x' and vertex 4 as 'y'.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (0 + 8) < ∞
3. = 8 < ∞

Therefore, the value of d(y) is 8. We replace the infinity value of vertices 1 and 4 with the values
4 and 8 respectively. Now, we have found the shortest path from the vertex 0 to 1 and 0 to 4. Therefore,
vertex 0 is selected. Now, we will compare all the vertices except the vertex 0. Since vertex 1 has the
lowest value, i.e., 4; therefore, vertex 1 is selected.

Since vertex 1 is selected, so we consider the path from 1 to 2, and 1 to 4. We will not consider the
path from 1 to 0 as the vertex 0 is already selected.

First, we calculate the distance between the vertex 1 and 2. Consider the vertex 1 as 'x', and the
vertex 2 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (4 + 8) < ∞
= 12 < ∞
Since 12<∞ so we will update d(2) from ∞ to 12.
Now, we calculate the distance between the vertex 1 and vertex 4. Consider the vertex 1 as 'x' and
the vertex 4 as 'y'.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (4 + 11) < 8
3. = 15 < 8

Since 15 is not less than 8, we will not update the value d(4) from 8 to 12.

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 3
 Analysis of Algorithm Greedy method Approach

Till now, two nodes have been selected, i.e., 0 and 1. Now we have to compare the nodes except
the node 0 and 1. The node 4 has the minimum distance, i.e., 8. Therefore, vertex 4 is selected.

Since vertex 4 is selected, so we will consider all the direct paths from the vertex 4. The direct paths
from vertex 4 are 4 to 0, 4 to 1, 4 to 8, and 4 to 5. Since the vertices 0 and 1 have already been selected so
we will not consider the vertices 0 and 1. We will consider only two vertices, i.e., 8 and 5.

First, we consider the vertex 8. First, we calculate the distance between the vertex 4 and 8. Consider
the vertex 4 as 'x', and the vertex 8 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (8 + 7) < ∞
= 15 < ∞

Since 15 is less than the infinity so we update d(8) from infinity to 15.

Now, we consider the vertex 5. First, we calculate the distance between the vertex 4 and 5. Consider
the vertex 4 as 'x', and the vertex 5 as 'y'.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (8 + 1) < ∞
3. = 9 < ∞

Since 5 is less than the infinity, we update d(5) from infinity to 9.

Till now, three nodes have been selected, i.e., 0, 1, and 4. Now we have to compare the nodes
except the nodes 0, 1 and 4. The node 5 has the minimum value, i.e., 9. Therefore, vertex 5 is selected.

Since the vertex 5 is selected, so we will consider all the direct paths from vertex 5. The direct paths
from vertex 5 are 5 to 8, and 5 to 6.

First, we consider the vertex 8. First, we calculate the distance between the vertex 5 and 8. Consider
the vertex 5 as 'x', and the vertex 8 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (9 + 15) < 15
= 24 < 15

Since 24 is not less than 15 so we will not update the value d(8) from 15 to 24.

Now, we consider the vertex 6. First, we calculate the distance between the vertex 5 and 6. Consider
the vertex 5 as 'x', and the vertex 6 as 'y'.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (9 + 2) < ∞</p>
3. = 11 < ∞

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 4
 Analysis of Algorithm Greedy method Approach

Since 11 is less than infinity, we update d(6) from infinity to 11.

Till now, nodes 0, 1, 4 and 5 have been selected. We will compare the nodes except the selected
nodes. The node 6 has the lowest value as compared to other nodes. Therefore, vertex 6 is selected.

Since vertex 6 is selected, we consider all the direct paths from vertex 6. The direct paths from
vertex 6 are 6 to 2, 6 to 3, and 6 to 7.

First, we consider the vertex 2. Consider the vertex 6 as 'x', and the vertex 2 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (11 + 4) < 12
= 15 < 12

Since 15 is not less than 12, we will not update d(2) from 12 to 15

Now we consider the vertex 3. Consider the vertex 6 as 'x', and the vertex 3 as 'y'.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (11 + 14) < ∞
3. = 25 < ∞

Since 25 is less than ∞, so we will update d(3) from ∞ to 25.

Now we consider the vertex 7. Consider the vertex 6 as 'x', and the vertex 7 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (11 + 10) < ∞
= 22 < ∞

Since 22 is less than ∞ so, we will update d(7) from ∞ to 22.

Till now, nodes 0, 1, 4, 5, and 6 have been selected. Now we have to compare all the unvisited
nodes, i.e., 2, 3, 7, and 8. Since node 2 has the minimum value, i.e., 12 among all the other unvisited nodes.
Therefore, node 2 is selected.

Since node 2 is selected, so we consider all the direct paths from node 2. The direct paths from
node 2 are 2 to 8, 2 to 6, and 2 to 3.

First, we consider the vertex 8. Consider the vertex 2 as 'x' and 8 as 'y'.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (12 + 2) < 15
3. = 14 < 15

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 5
 Analysis of Algorithm Greedy method Approach

Since 14 is less than 15, we will update d(8) from 15 to 14.

Now, we consider the vertex 6. Consider the vertex 2 as 'x' and 6 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (12 + 4) < 11
= 16 < 11

Since 16 is not less than 11 so we will not update d(6) from 11 to 16.

Now, we consider the vertex 3. Consider the vertex 2 as 'x' and 3 as 'y'.

1. d(x, y) = d(x) + c(x, y) < d(y)

2. = (12 + 7) < 25
3. = 19 < 25

Since 19 is less than 25, we will update d(3) from 25 to 19.

Till now, nodes 0, 1, 2, 4, 5, and 6 have been selected. We compare all the unvisited nodes, i.e., 3,
7, and 8. Among nodes 3, 7, and 8, node 8 has the minimum value. The nodes which are directly connected
to node 8 are 2, 4, and 5. Since all the directly connected nodes are selected so we will not consider any
node for the updation.

The unvisited nodes are 3 and 7. Among the nodes 3 and 7, node 3 has the minimum value, i.e., 19.
Therefore, the node 3 is selected. The nodes which are directly connected to the node 3 are 2, 6, and 7.
Since the nodes 2 and 6 have been selected so we will consider these two nodes.

Now, we consider the vertex 7. Consider the vertex 3 as 'x' and 7 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (19 + 9) < 21
= 28 < 21

Since 28 is not less than 21, so we will not update d(7) from 28 to 21.

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 6
 Analysis of Algorithm Greedy method Approach

Shortest path from s

Vertex T Y X Z
S 10 5 00 00

Vertex T Y X Z
S-> y 8 - 14 7

Vertex T Y X Z
S-> y->t - - 9 7

Vertex T Y X Z
S-> y->t->z - - 9 -

• Thus we get all shortest path vertex as

- Weight from s to y is 5

- Weight from s to z is 7

- Weight from s to t is 8

- Weight from s to x is 9

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 7
 Analysis of Algorithm Greedy method Approach

Knapsack Problem

• The Greedy algorithm could be understood very well with a well-known problem referred to as
Knapsack problem.
• Let M is the capacity of knapsack i.e. knapsack can not hold item having collective weight more
than M.
• Knapsack problem is problem of filling knapsack using item in x such that it maximizes the profit
such that total weight item should not cross the knapsack capacity.
• 0/1 knapsack
• Fractional Knapsack

Example:
Solve following using 0/1 knapsack method.

Item (I) Values (vi) Weight (wi)

1 18 3
2 25 5
3 27 4
4 10 3
5 15 6

Knapsack capacity M = 12.

Solution:

If items are selected according to decreasing order of profit to weight ratio using fractional
knapsack strategy, then algorithm always finds the optimal solution. First arrange items in decreasing order
of profit density. Items are labeled as X = (3, 1, 2, 4, 5), have profit V = (27, 18, 25, 10, 15) an weight W
= (4, 3, 5, 3, 6).

Item Values (vi) Weight (wi) Pi = ci / wi

3 27 4 6.75
1 18 3 6
2 25 5 5
4 10 3 3.33
5 15 6 2.5

We shall select one by one item from above table. If the inclusion of an item does not cross the
knapsack capacity, then add it. Otherwise, break the current item and select only the portion of item
equivalent to remaining knapsack capacity. Select the profit accordingly. We should stop when knapsack
is full or all items are scanned.
Initialize, Weight of selected items, SW = 0, Profit of selected items, SP=0,

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 8
 Analysis of Algorithm Greedy method Approach

Set of selected items, S = { }.

Here, Knapsack capacity M = 12.
Iteration 1: SW= (SW+w3) = 0 + 4 = 4
SW ≤ M, so select item 3
S = {3}, SW = 4, SP = 0 + 27 = 27
Iteration 2: SW = (SW + w1) = 4 + 3 = 7
SW ≤ M, so select item 1
S = {3, 1}, SW = 7, SP = 27 + 18 = 45
Iteration 3: SW (SW + w2) = 7 + 5 = 12
SW ≤ M, so select item 2
S = (3, 1, 2), SW = 12, SP = 45 + 25 = 70

- Knapsack is full, no more items can be added to knapsack. Selected items are (3, 1, 2), which gives
the profit of 70.

Job Sequencing
- Schedule jobs out of set of N jobs on a single processor which maximizes profit as much as possible.

- Each job is taking unit time for execution and having some profit and deadline associated with it.

- The job is feasible only if it can be finished on or before its deadline.

- Greedy approach produces an optimal result in fairly less time as each job takes same amount of time

- Uniprocessor System: - One Processor is going to work on it.

- No Preemption :- if we start one job we should complete it without assigning any other

- 1 Unit of Time: 1 hr, 1Day, 1Month ….

Job J1 J2 J3 J4

Profit 50 15 10 25

Deadline 2 1 2 1

Algorithm JOB SCHEDULING(J, D, P)

//Description: Schedule the jobs using greedy approach which maximizes the profit
//Input: J: Array of N jobs
D: Array of deadline for each job
P: Array of profit associated with each job
Sort all jobs in J in decreasing order of profit If job does not miss its
deadline

S← ∅ //S is set of scheduled jobs, initially it is empty

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 9
 Analysis of Algorithm Greedy method Approach
SP← 0 //Sum is the profit earned

Add job to solution set

for i ← 1 to N do
if Job J[i] is feasible then
Schedule the job in latest possible free slot meeting its deadline.
S ← S ∪ J[i]
Add respective profit
SP ← SP + P[i]

end
end

Example:
Let n = 4, (P1, P2, P3, P4)= (100, 10, 15, 27) and (d1, d2, d3, d4) = (2, 1, 2, 1). Find feasible solutions,
using job sequencing with deadlines.
Soln.:
Sort all jobs in descending order of profit.
So, P=(100, 27, 15, 10), J = (J1, J4, J3, J2) and D = (2, 1, 2, 1). We shall select one by one job from
the list of sorted jobs, and check if it satisfies the deadline. If so, schedule the job in the latest free slot. If
no such slot is found, skip the current job and process the next one.
Initially,
S
0 1 2 3 4
Profit of scheduled jobs, SP = 0
Iteration 1
Deadline for job J1 is 2. Slot 2(t = 1 to t = 2) is free, so schedule it in slot 2.
Solution set S = {J1}, and Profit SP = {100}
S J1
0 1 2 3 4
Iteration 2
Deadline for job J4 is 1. Slot 1(t = 0 to t = 1) is free, so schedule it in slot 1.
Solution set S = {J1, J4}, and Profit SP = {100, 27}
S J4 J1
0 1 2 3 4
Iteration 3
Job J3 is not feasible because first two slots are already occupied and if we schedule J3 any time
later t = 2, it cannot be finished before its deadline 2. So job J3 is discarded.
Solution set S = (J1, J4), and Profit SP = {100, 27}

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 10
 Analysis of Algorithm Greedy method Approach

Iteration 4
Job J2 is not feasible because first two slots are already occupied and if we schedule J2 any time
later t = 2, it cannot be finished before its deadline 1. So job J2 is discarded,
Solution set S = {J1, J4), and Profit SP= (100, 27) With the greedy approach, we will be able to
schedule two jobs (J1, J4), which gives a profit of 100 + 27 = 127 units..

Minimum spanning tree

• A connected Subgraph ‘s’ of graph G(V, E) is said to be spanning if
- ‘s’ should contain all vertices of ‘G’
- ‘s’ should contain (|v|-1) Edges.
• Spanning tree with minimum cost is called as minimal spanning tree.
• Application of MST
- MST is used in network design
It is used to implement efficient routing algorithm
- It is used to solve traveling salesman Problem
• Prims and Kruskal algorithm.

Prims algorithm
Refer class notes
Kruskal algorithm
Refer class notes

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 11
 Analysis of Algorithm BackTracking And Branch and Bound

Chapter-4. BackTracking And Branch and

Bound

General Method
• Backtracking is a technique based on algorithm to solve problem.
• In backtracking problem, the algorithm tries to find a sequence path
to the solution which has some small checkpoints from where the
problem can backtrack if no feasible solution is found for the
problem.
• Solutions to many problem can be viewed as a making sequence of
decisions.
• Backtracking is an intelligent way of gradually building solution.
• Typically it is applied to problems like sudoku, crossword, 8-queen puzzels, chess and many others
• Backtracking builds the solutions incrementally. Partial solutions which do not satisfy the
constraint are abandon.
• Backtracking limits the search by eliminating the candidates that do not satisfy certain constraints.

4 Queens Problem
• 4 – Queens’ problem is to place 4 – queens on a 4 x 4 chessboard in such a

manner that no queens attack each other by being in the same row, column, or

diagonal.

• Here we have to place 4 queens say Q1, Q2, Q3, Q4 on the 4 x 4

chessboard such that no 2 queens attack each other.

The solver starts by placing the first queen in the upper left corner.

After this first step, only the white squares are still available to place the three remaining queens. The
process of excluding some squares is what is called propagation.

The second step starts with the solver trying to place a second queen. It does so in the first available

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 1
 Analysis of Algorithm BackTracking And Branch and Bound

square from the top in the second column.

Now, we have a failure as there is no possibility to place a third queen in the third column: there simply
can not be a solution with this configuration. The solver has to backtrack!

First, the square with the red cross is removed because of the positive diagonal constraint. This leaves
only one possibility to place a queen in the fourth column.

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 2
 Analysis of Algorithm BackTracking And Branch and Bound

The “no two queen on the same row” constraint removes one more square in the third column, leaving
only one square to place the last remaining queen

8-Queen Problem
• Problem: - 8X8 chess board Arrange 8 queen in a way such that no two queen attack each other.
• Two queen are attacking each other if they are in same row, column or diagonal.
• 8 Queen Problem has 64c8= 4,42,61,65,368 different arrangements out of which only 12 are
fundamental solution.
1 2 3 4 5 6 7 8 Solution Vector

1 Q1

2 Q2 1 2 3 4 5 6 7 8

3 Q3 4 6 8 2 7 1 3 5

4 Q4
5 Q5
6 Q6
7 Q7

8 Q8

Sum of subsets
• Given set of positive integers, find the combination of numbers that sum to given value is M.
• Find subset whose sum of subset is M.
• Set (10,20,30,40)
• M=50 (sum)

❖ Boundary Function :
Q) n = 4 W = {2, 7, 8, 15} M = 17

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 3
 Analysis of Algorithm BackTracking And Branch and Bound

x1, x2, x3, x4

Q) w[1 : 6] = {5, 10, 12, 13, 15, 18} n = 6 m = 30

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 4
 Analysis of Algorithm BackTracking And Branch and Bound

x 1 1 0 0 1 0
1 2 3 4 5 6

∑ wi xi + wk+1 ≤ m
i=1
k n

∑ wi xi + ∑ wi > m
i=1 i=k+1

Graph Coloring
• Graph colouring is the problem of colouring vertices of a graph in such a way that no two
adjacent vertices of same color.

• We have given a chromatic number m which is the least number of colors needed to color graph.

1 2 3 4 5

R G R G B

M=5

R, G, B

Colors needed to color graph.

Example:

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 5
 Analysis of Algorithm BackTracking And Branch and Bound

Branch and Bound

• Method by which we can solve problem.
• It also uses state space tree for solving problem.
• It is similar to backtracking approach.

15 Puzzle problem
• In this puzzle solution of the 8 puzzle problem is discussed.
• Given a 3×3 board with 8 tiles (every tile has one number from 1 to
8) and one empty space.
• The objective is to place the numbers on tiles to match the final
configuration using the empty space.
• We can slide four adjacent (left, right, above, and below) tiles into
the empty space.

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 6
 Analysis of Algorithm BackTracking And Branch and Bound

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 7
 Analysis of Algorithm String Matching Algo

Chapter-5. String Matching Algo

String matching
• String matching is core part in many text processing application
• Objective of string matching is to find pattern P from given set of text T.
• String matching is used in compilers and text editors.

 Consider the following example:

1 2 3 4 5 6 7 8 9 10 11 12

Text T H O W A R E Y O U ?

Pattern P s=4 A R E

1 2 3
Pattern matching in Text T
 In this example, pattern P = ARE is found in text T after four shifts.
 Classical application of string matching algorithm is to find particular protein pattern in DNA
sequence.

Naïve string matching algorithm

• This is simple and inefficient brut force approach
• It compares first character of pattern with searchable text
 If match is found pointer in both text are incremented.
 If match is not found , pointer of text is incremented and pointer of pattern is reset. This
process continues till end of text.
• Given T and P, it directly start comparing both string character by character.
• After each comparison it shifts pattern string one position right.

 Following example illustrates the working of naive string matching algorithm.

Here,
T=PLANINGANDANALYASIS and P = AND
Here, ti and pj are indices of text and pattern respectively

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 1
 Analysis of Algorithm String Matching Algo

 Step 1 : T[1] ≠ P[1], advance text pointer, i.e. t i ++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
P L A N I N G A N D A N A L Y S I S

A N D
1 2 3

 Step 2 : T[2] ≠ P[1], advance text pointer, i.e. t i ++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
P L A N I N G A N D A N A L Y S I S

A N D
1 2 3

 Step 3 : T[3] = P[1], advance text pointers, i.e. ti ++, pj ++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
P L A N I N G A N D A N A L Y S I S

A N D
1 2 3

 Step 4 : T[4] = P[2], advance text pointers, i.e. t i ++, pj ++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
P L A N I N G A N D A N A L Y S I S

A N D
1 2 3

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 2
 Analysis of Algorithm String Matching Algo

 Step 5 : T[5] ≠ P[3], advance text pointer and reset pattern pointer, i.e. t i ++, pj = 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
P L A N I N G A N D A N A L Y S I S

A N D
1 2 3

 Step 6 : T[6] ≠ P[1], so advance text pointer, i.e. t i ++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
P L A N I N G A N D A N A L Y S I S

A N D
1 2 3

 Step 7 : T[7] ≠ P[1], so advance text pointer, i.e. t i ++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
P L A N I N G A N D A N A L Y S I S

A N D
1 2 3

 Step 8 : T[8] = P[1], so advance both pointer, i.e. t i ++, pj ++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
P L A N I N G A N D A N A L Y S I S

A N D
1 2 3

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 3
 Analysis of Algorithm String Matching Algo

 Step 9 : T[9] = P[2], so advance both pointers, i.e. t i ++, pj ++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
P L A N I N G A N D A N A L Y S I S

A N D
1 2 3

 Step 10 : T[10] = P[3], so advance both pointers, i.e. t i ++, pj ++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
P L A N I N G A N D A N A L Y S I S

A N D Match found
1 2 3

This process continues till the end of text string.

Algorithm for naïve string matching approach is described below:

Algorithm NAIVE_STRING_MATCHING(T, P)
//T is the text string of length n
//P is the pattern of length m
for i ← 0 to n – m do
if P[l .... m] = = T[i + l ...... i + m] then
print “Match Found”
end
end

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 4
 Analysis of Algorithm String Matching Algo

The rabin karp algorithm

• Comparing number is easier and cheaper than comparing string.

• Rabin karp algorithm represents strings in number.
• Rabin karp is based on hashing technique, it first compute hash value of p and t.
• If hash values are same we check equality of inverse hash similar to native method.
• If hash values are not same no need to compare actual string.
• However same hash value does not ensure the string match, two different string can have same
hash value.
• We need to compare them character by character.
• Rabin-Karp algorithm is an algorithm used for searching/matching patterns in the text using a hash
function
• Unlike Naive string matching algorithm, it does not travel through every character in the initial
phase rather it filters the characters that do not match and then performs the comparison.
• A sequence of characters is taken and checked for the possibility of the presence of the required
string. If the possibility is found then, character matching is performed.

1. Let the text be:

And the string to be searched in the above text be:

2. We have taken first ten alphabets only (i.e. A to J).

3. m be the length of the pattern and n be the length of the text. Here

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 5
 Analysis of Algorithm String Matching Algo

Knuth-Morris-Pratt (KMP) Algorithm

• This algorithm is also known as KMP algorithm

• It utilizes concept of naïve approach is some different way.
• This approach keeps track of matched part of pattern and reducing useless shifts
performed in naïve approach.

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 6
 Analysis of Algorithm Dynamic Programming Approach

Chapter-6. Dynamic programming approach

Introduction

• Dynamic Programming Approach is similar to divide and conquer in breaking down the problem
into smaller and yet smaller possible sub-problems. But unlike, divide and conquer, these sub-
problems are not solved independently. Rather, results of these smaller sub-problems are
remembered and used for similar or overlapping sub-problems.
• Dynamic programming is used where we have problems, which can be divided into similar sub-
problems, so that their results can be re-used.
• Dynamic programming is used where we have problems, which can be divided into similar sub-
problems, so that their results can be re-used.
• Dynamic programming can be used in both top-down and bottom-up manner.

Applications of dynamic programming

1. 0/1 knapsack problem

2. Mathematical optimization problem
3. All pair Shortest path problem
4. Reliability design problem
5. Longest common subsequence (LCS)
6. Flight control and robotics control
7. Time-sharing: It schedules the job to maximize CPU usage

Multistage Graph

• A multistage graph G = (V, E) is a directed graph, weighted graph

• The multistage graph problem is finding
the path with minimum cost from
source to sink destination.
• A Multistage graph is a directed graph
in which the nodes can be divided into a
set of stages such that all edges are from
a stage to next stage only

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 1
 Analysis of Algorithm Dynamic Programming Approach

Single source shortest path

• The single source shortest path algorithm (for arbitrary weight positive or negative) is also known
Bellman-Ford algorithm is used to find minimum distance from source vertex to any other vertex.
• It is slower compared to Dijkstra algorithm but it can handle negative weight.
• Bellman-ford algorithm is used to find the shortest path from the source vertex to remaining all
vertex in the weighted graph.
• If graph contain negative weight cycle, it is not possible to find the minimum path because on every
iteration gives better cycle.

Floyd Warshall Algorithm

• Floyd-Warshall Algorithm is an algorithm for finding the shortest path between all the pairs of
vertices in a weighted graph.
• This algorithm works for both the directed and undirected weighted graphs. But, it does not work
for the graphs with negative cycles (where the sum of the edges in a cycle is negative).

Assembly-line scheduling Problem

• Assembly-line scheduling is a manufacturing problem.

• Assembly lines are used to transfer parts from one station to another.
• We know that in automobile industry, automobiles are produced using assembly lines. There are
multiple lines that are working together to produce products. Then a finished auto exits at the end
of the line.
• The problem is that which line we should choose next from any station that will give best time
utilization for company for one auto.
• The main goal of assembly line scheduling is to give best route or can say fastest from all assembly
line.

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 2
 Analysis of Algorithm Dynamic Programming Approach

Traveling Salesman problem

Longest common subsequence

• It is problem of finding maximum length common sequence from given two strings A and B.
• A subsequence of a string is a new string generated from the original string with some characters
(can be none) deleted without changing the relative order of the remaining characters.
• For example, "ace" is a subsequence of "abcde"
• A common subsequence of two strings is a subsequence that is common to both strings.

This document is property of RKDEMY and cannot be used, disclosed or duplicated without the prior written consent of RKDEMY pg.1- 3