Introduction to Algorithm

Algorithm : Finite sequence of steps / instructions to solve a

problem.
To design a better program, you require Algorithms.
Characteristics of an Algorithm
Input : We can say an Algorithm can have zero or more well -
defined inputs.
Output : Algorithm should have at least one output. May be more
than one output can be there.
Unambiguous / Definiteness : Every instruction must be clear, there
should be no ambiguity in those instructions.
Suppose if you are writing “read” that is if you are writing an
algorithm for sum of two numbers and you are writing statement
“read” means what, what are you reading?
This is what Unambiguous statement. It is having multiple meanings
and if you will write.
read a  It means this statement “read a” is having a clear meaning.
read b  It means this statement “read b” is having a clear meaning.

That is , we are reading a value for variable a. We are reading another value for
another variable b.

So, every statement must have a single meaning that is only one meaning. It
means every statement must be unambiguous. There should be no ambiguity, it
should be very clear.

Every instruction must be clear and precise, there should be no ambiguity.

Finiteness : Every algorithm must contains finite number of steps,

means the steps must be countable.
It’s not like thill say while at you’re writing steps infinite steps are
there, that is there is no end.

Like, if you are writing a program and if you will say while(1) and if
you here print something, then this while(1) is always true.

So, this would be an infinite loop

while (1)
{
……
……
}

It is not going to end, until you forcefully terminate it.

Every algorithm must have finite number of steps and every

instruction within that algorithm must take finite amount of time for
execution.

So, algorithm must terminate after a finite number of steps.

Effectiveness : It should perform that task for which you have written
that algorithm. It should be effective.

It should not contain any unnecessary statements.

Example : Take sum of 2 numbers and here you will write sum = a +
b and here you can print sum.

Start
Read a
Read b
Sum = a + b
Print Sum
Stop
Output of this algorithm would be obviously the sum of these 2
numbers. That means, it is effective and it is not containing any
unnecessary statements, like here

Start
Read a
Read b
Read c
Sum = a + b
Print Sum
Stop

I am not writing here “Read c”, because I am not using c anywhere.

Every statement or every instruction in that algorithm must be
feasible, it should not be imaginary.

Algorithm Specification : Algorithm can be described in 3 ways.

Natural Language Like English : You can specify each instruction

which is in simple sentences in English.

So, let us consider an example, if you want to store 4 subject marks

and then you want to sum it up and then you want to find if that
average is less than 50 you can say it as a “Fail”, otherwise print it as
“Pass”. So, for this problem how to write an algorithm like in Natural
Like English.

1. Input set of 4 numbers

2. Calculate their average by summing and dividing by 4.
3. If average is below 50 is “Fail” otherwise “Pass”

Graphic Representation called Flowchart

Here also you are specifying the problem solution in a sequential

steps , but additionally with graphical diagrams like Graphical
representations.
 Start/Stop

Input / Output

Calculation

Decision

Flow lines
 Start

Input m1,
m2, m3, m4

Total = m1 + m2 + m3 + m4

Average = Total / 4

True False
If Average < 50

Print “Fail”
Print “Pass”

Stop

Here, you can see each instruction is specified in some block which is
also we call it as a graphical representation.
Pseudo - Code Method : In this method, we should typically
describe Algorithm as programs which resembles language like C. So,
we should typically describe algorithms like, why we are writing this
algorithm. Simply, in the next step we want to implement it as a
program.
Now, how the programming will be there. So, if you see how the
program is, then according to that if you make the algorithm as a
sequence of steps, then it is easy in the next step to implement it as a
program.
Pseudocode Conventions : Pseudocode convention means, how you
can represent the algorithm. What are the rules are there in the
Pseudocode convention.
1. Comments begin with forward slash [//] and continue until the
end of the line.
If you want to write any comment like in C – Language. There
are Single – Line Comments and Multi – Line Comments.
For Single – Line Comments you will use two forward slash [//].
For Multi – Line Comment you will use /* Multi – Line
Comment*/.

2. Blocks are indicated with matching braces { and }. So, now if

you see any programming, so any block or any function you can
start with opening brace and you need to end with close brace.

3. An identifier begins with a letter. The data types of the variables

are not explicitly declared. If you take any variable declaration,
it must start with an alphabet definitely it should not start with
any digit or with some special symbol.

Examples of Variable declaration

1. S1  Valid Variable declaration.
2. Sample  Valid Variable declaration.
3. 1S  Invalid Variable declaration.
Note, while declaring the variable, the first letter must be an
alphabet.
4. Assignment of values to variables is done using the
assignment statement.
<variable> := <expression>;
You want to assign one value, you can use this variable
whatever you want to, see left side you should have only one
variable not more than that because you are assigning
whatever the expression value to the left hand side, that is a
variable.

Examples of Assigning values to variables

1. C := a + b
The values of a and b are added and the resultant value is
stored in variable named C. That is, the resultant value is
assigned to the variable C.
2. Sample := S1

The value that is available in S1 variable is assigned to the

variable Sample. Here you need to write assignment
statement with colon followed by equal to i.e. :

5. There are two Boolean values ‘TRUE’ and ‘FALSE’.

Logical Operators  AND, OR, NOT
Relational Operators  < <= > >= == ≠
You need to specify if the answer is the Boolean value is
‘TRUE’ you need to specify it in upper case.
If it is false, you need to specify it in upper case ‘FALSE’.
6. The following loop statements are employed while, for and
repeat – until.
 while loop
Syntax of while loop :
while <condition> do
{
<statement 1>
.
.
<statement n>
}
While loop is similar to while loop in your python or C –
Language. while keyword and then you need to write the
condition and additional here you need to write one word that
is ‘do’. After while condition then do then open the opening
brace whatever the statement that you want to write you can
write it. If the condition is ‘TRUE’, then these block of
statements will be executed.
for loop : Syntax of for loop is
for variable := value 1 to value 2 step
step – value do
{
<statement 1>
.
.
<statement n>
}
In for loop, we have 3 properties in that line. That is for what is a
variable value 1 is the first value or initial value and the value 2 is the
last value or final value and how you want to do that is whether to
increment or decrement.
So, for variable you want to do value 1 to value 2 you need to write
step and then step value how much you want to increment or
decrement and then keyword do. If this is ‘TRUE’, till then the block
of statements inside the for loop will be executed.

Example on for loop

1. for I := 1 to 10 step 2 do
{
}
I = 1, 3, 5, 7, 9

2. for I := 1 to 10 do
{
}
I = 1,2,3,4,5,6,7,8,9,10

Initially, the value of 1 is 1, it will execute whatever the block of

statements will be here. Then i value will be step 2 that means it will
be incremented by 2. That is, the next value of I becomes 3 and then
the next value of I becomes 5, next value of I becomes 7, and then
next value of I becomes 9. After I = 9, then I = 11, but what is the last
value in this case, it is 10, so that’s why it will come out of the loop.

It will never take the value 11 with the loop.

In the second example, for i := 1 to 10 do now I am not writing step.

So, what happens if you don’t write like this, that means, if you don’t
write by default the step value will be incremented by 1. Now, if you
see i = 1, what is the next i value definitely it will be 2 because by
default next 3 up to 10.

repeat – until : Syntax of repeat – Until.

repeat
<statement 1>
…………….
<statement n>
until <condition>

This is similar to do … while loop in your C – language. So, in C –

language you will write do then block of statements and then while
condition. Now here, you will write repeat so you want to start
statement 1, 2 up to n statements until condition is True. It will be
repeated until this condition is True. This loop is also called Exit –
Controlled loop. That means, all the statements will be executed then
it is checking for the condition. Whereas in while loop first the
condition is tested then only block of statements will be executed.
This while loop is called Entry – Controlled loop.

A conditional statements has the following forms.

if <condition> then <statement>
if <condition> then <statement – 1>
else <statement – 2>

If condition then statement will be executed.

If this is not true else statement will be executed.

Case Statement

Case
{
: <condition 1> : <statement 1>
.
.
: <condition n> : <statement n>
else : <statement n+1>
}

In C – Language, we have switch … case, but here you have case

statement like case you need to write what is a condition – 1 statement
will be executed, condition 2 up to condition n .

In switch case statement, none of the case labels are satisfied there
you’ll write default statement. Here you will write else statement
n + 1 is executed and the case statement is exited. The else clause is
optional.

Input and Output are done using the instructions read and write . No
format is used to specify the size of input or output quantities.

There is only one type of procedure, Algorithm.

An Algorithm consists of heading and a body. The heading takes the
form.

Algorithm Name (<parameter list>)

Where Name is the Name of the procedure and (<parameter list>) is a

listing of the procedure parameters.

The body has one or more [simple or compound] statements enclosed

within the braces { and }. An algorithm may or may not return any
values. Simple variables to procedures are passed by value. Arrays
and records are passed by reference. An array name or record name is
treated as a pointer to the respective data type.

Elements of multidimensional arrays are accessed using [ and ]. For

example , if A is a two dimensional array, the (i, j) th element of the
array is denoted as A[i, j] . Array indices start at 0.

Example : Algorithm finds and returns the maximum of n given

numbers.

Algorithm Max (A , n)
//A is an array of size n
{
Result := A[1];
for i := 2 to n do
if A[i] > Result then
Result := A[i];
return Result;
}
In this algorithm named max, A and n are procedural parameters .
Result and i are local variables.

Recursive Algorithm : Recursive algorithm is defined as an

algorithm which is invoked within its body.

Types of Recursion : There are 2 types of Recursive algorithms.

Direct Recursive and Indirect Recursive.

Direct Recursive : An algorithm A is said to be Direct Recursive if it

calls itself.

Indirect Recursive : An algorithm A is said to be Indirect Recursive,

if it calls another algorithm which in turn calls A.

Example : A is an algorithm which calls an algorithm B where B

itself again calls an algorithm A and A is termed as Indirect Recursive
algorithm.

Every Recursive algorithm has 2 elements Base Case and General

Case.

Base Case General Case

This statement solves a particular General Case reduces the size of
part of a problem the problem.
Every Recursive function must The rest of the function is known
have a Base Case as the General Case

Designing a Recursive Algorithm :

Initially, determine the Base Case. Determine the General Case.

Finally, combine the Base Case and General Case into an algorithm.
Recursive Algorithm for Factorial of a Number:

Base Case : Factorial (0) = 1

General Case : Factorial (n) = n * Factorial(n – 1);

Example : 4! Can be written as 4 * 3!

Algorithm Factorial(n)
{
if (n == 0)
return 1;
else
return (n * Factorial(n – 1));
}

Performance Analysis of an Algorithm

We can analyse the Performance of the Algorithm by using 2 ways :

1. Time Complexity
2. Space Complexity

Time Complexity : The amount of time that an algorithm requires for

its execution is known as “Time Complexity”.

How much time that an algorithm requires for its execution is nothing
but Time Complexity.

There are mainly 3 types of Time Complexity.

Best Case Time Complexity
Worst Case Time Complexity
Average Case Time Complexity

Best Case Time Complexity : If an algorithm requires minimum

amount of time for its execution, then it is known as Best Case Time
Complexity.
Worst Case Time Complexity : If an algorithm requires maximum
amount of time for its execution, then it is known as Worst Case Time
Complexity.

Average Case Time Complexity : If an algorithm requires average

amount of time for its execution, then it is known as Average Case
Time Complexity.

Linear Search : Searching the elements of the list 1 – by – 1 until the

key element is found or the array is completely exhausted.

Let the elements of the list are :

10 20 30 40 50

Key Element : 40

First, we have to compare 10 with 40, so it did not match.

Compare 20 with 40, it did not match.
Compare 30 with 40, it did not match.
Compare 40 with 40, it matches and we can say that the key element
is found.

Now the elements of the list are :

10 20 30 40 50

Key Element : 100

First, compare 10 with 100 it did not match.

Compare 20 with 100 it did not match.
Compare 30 with 100 it did not match.
Compare 40 with 100 it did not match.
Compare 50 with 100 it did not match.

As the array is exhausted, so we can say that here the Key Element is
not found. While searching an element using Linear Search, if the key
element is found at first position, so this is nothing but Best Case
Time Complexity. Here, the algorithm requires one unit of time for
comparing the element.

Example of Worst Case Time Complexity :

While searching an element using Linear Search if the Key Element

requires maximum amount of time. That means, if the Key Element
found at last position, then it is called as Worst Case Time
Complexity.

List of Elements : 10 20 30 40 50
Key Element : 50

Example of Average Case Time Complexity :

Average Case means if the key element found at some 2 nd place or 3rd
place or 4th place then we can say that it is Average Case Time
Complexity.

List of Elements : 10 20 30 40 50
Key Element : 30

In order to calculate Time Complexity, we have 2 approaches.

Frequency Count or Step Count

Asymptotic Notations

Space Complexity : The amount of space that an algorithm requires

for its execution.

Frequency Count or Step Count : In order to calculate Time

Complexity, we use Frequency Count or Step Count.

Frequency Count specifies the number of times a statement is to be

executed. How many corresponding statement is executed, that is
nothing but Frequency Count.
Here, we can give the count value depends upon the statements :

Here we have 4 steps:

For comments, declarations step count is 0. As we know that

comments are not executed, only for understanding purpose we these
comments.

Declarations also not necessary while writing the algorithm. So,

declaration of variables are needed only while writing a program. In
algorithm, there is no need of declaration.

return statement, assignment statement count is 1.

By using return statement we can return a value. By using assignment

statement we assign a value to a variable.

Ignore lower order exponents when higher order exponents are

present.

Let the Time Complexity of an algorithm is like this.

3n4 + 4n3 + 10n2 + n + 100

Now, we have to consider only higher order exponents and ignore

lower order exponents. In this case, we need to consider only 3n 4 and
we have to ignore these 4n3 + 10n2 + n + 100.

Ignore constant multipliers.

3n4 + 4n3 + 10n2 + n + 100

Here, the multiplier is 3n4 is 3, so we have to ignore this 3. The Time

Complexity of this algorithm becomes O(n4).
Let the Time Complexity of the algorithm is 10n8 . Hence we have
only 1 term, so the Time Complexity will be O(n8) because in that
case there are no other exponents.

Example :

int sum(int a[], int n)

{
s = 0;
for(i=0;i<n;i++)
s = s + a[i];
return s;
}

Now, let us calculate the Time Complexity for the above algorithm.

Algorithm Frequency Count or Step Count

int sum(int a[], int n)
{
s = 0; //Assignment Statement 1
for(i=0;i<n;i++) n+1
s = s + a[i]; n
return s; //return statement 1
}

Now, let us consider the for loop, how many times the condition will
be executed.

Let n = 3
Initial value of i = 0; 0 < 3 [True] . So, Step Count is 1.
Next i value is 1 ; 1 < 3 [True]. So, Step Count is 2.
Next i value is 2 ; 2 < 3 [True]. So, Step Count is 3.
Next i value is 3 ; 3 < 3 [False]. So, Step Count is 4.

Since n = 3, and the condition i < n will be executed for 4 times i.e.,
n + 1 times.
How many times the body of the loop will be executed? The body of
the loop will be executed for n times.

Now, we have to add all the step count values. This gives us
1 + n + 1 + n + 1 = 2n + 3.

Here, the higher order exponent is n.

So, the Time Complexity for the above algorithm is O(n).

Likewise, let us calculate the Space Complexity for the above

algorithm.

int sum(int a[], int n)

{
s = 0; //Assignment Statement
for(i=0;i<n;i++)
s = s + a[i];
return s; //return statement
}

For calculating the Space Complexity we need to calculate the Space

Complexity for each variable.

Here, a is an array and the size of the array is n elements. a occupies n

elements or words.

n is the number of elements. It occupies only 1 element. It may either

1 or 2 or 3 or 100 like that.

s is also a normal variable which occupies only 1 word or 1 element.

i is also a normal variable it also occupies only 1 word.

So, the variables in the above algorithm are:

an
n1
s1
i1

We need to add all the above terms. So, it will come to n + 3.

The Space Complexity for the above algorithm is O(n).

Example :

void mat_add(int a[][], int b[][])

{
int c[][];
for (i = 0;i < n; i++)
{
for (j = 0;j < n;j++)
{
c[i][j] = a[i][j] + b[i][j];
}
}
}

Now, we have to calculate the Time and Space Complexity for the
above algorithm.

Let us calculate the Time Complexity

Algorithm Frequency Count or Step Count
void mat_add(int a[][], int b[][])
{
int c[][];
for (i = 0;i < n; i++) n+1
{
for (j = 0;j < n;j++) n * (n + 1)
{
c[i][j] = a[i][j] + b[i][j]; n * n
}
}
}
By adding all these, we get 2n2 + 2n + 1.

So, we have to consider only the higher order exponent that is n 2 and
we need to ignore the constant multiplier. The Time Complexity for
the above algorithm is O(n2).

For Space Complexity, the following are the variables.

a  n2
b  n2
c  n2
i1
j1

By adding all these terms we will get 3n2 + 3.

Here, we have to consider the higher order exponents that is 3n 2 and

we need to ignore the constant multipliers i.e., ignore 3.

So, the Space Complexity for the above algorithm is O(n2).

Asymptotic Notations
Asymptotic Notations are mainly useful to calculate Time Complexity
of an algorithm.
By using Asymptotic Notations we can calculate
Best Case Time Complexity
Worst Case Time Complexity
Average Case Time Complexity
There are 5 types of Asymptotic Notations as follows:
1. Big Oh Notation
2. Big Omega Notation
 3. Theta Notation
4. Little oh Notation
5. Little Omega Notation
Big Oh Notation
Big Oh notation is represented by O.
Big Oh notation mainly represents the Upper bound of algorithm’s
running time.
By using Big Oh notation we can calculate maximum amount of time
that an algorithm requires for its execution.
Big Oh notation is mainly useful in order to calculate the Worst Case
Time Complexity of an algorithm.
Definition of Big Oh notation
Let f(n), g(n) be two non – negative functions then f(n) = O(g(n)) if
there exists two positive constants c, n0 such that f(n) <= c * g(n), for
all n > n0.
X – axis represents n where n is the number of elements.
Y – axis represents t where t is the time.
If n > n0 then we can say that f(n) <= c *g(n) before that it may be
either less than or greater than c * g(n).
Example :
Let f(n) = 3n + 2 ; g(n) = n then we have to prove f(n) = O(g(n)).
So, in order to prove f(n) = O(g(n)) we have to satisfy this condition
f(n) <= c * g(n), for all n > n0.
3n + 2 <= c * n
Let n = 1; c =3
By Substituting the values we get
3 + 2 <= 3 * 1
5 <= 3 [False]
So, n should be greater than 3.
Let n0 = 1; c= 4, then n is represented as n0.
By substituting the values, we get
5 <= 4 [False]
Let n0 = 2; c= 4 then 8 <= 8 [True]
Let n0 = 3; c= 4 then 11 <= 12 [True].
n0 value should be greater than 2 ie n0 > 2.
So, we can say that this condition is true f(n) <= c * g(n), for all n > 2
and c = 4
Prove that 2n2 = O(n3) where f(n) = 2n2 and g(n) = n3.
f(n) <= c * g(n)
2n2 <= c * n3
Divide n2 on both sides, we get
2 <= c*n
n = 1 ; c =2
Big Omega Notation :
Big Omega Notation is represented by Ὼ.
Big Omega notation mainly represents lower bound of algorithm’s
running time.
It mainly represents minimum amount of time that an algorithm
requires for its execution.
Big Omega notation is mainly useful in order to calculate Best Case
Time Complexity of an algorithm.
Definition of Big Omega Notation
Let f(n), g(n) be two non – negative functions then f(n) = Ὼ(g(n)) if
there exists two positive constants c, n0 such that f(n) >= c * g(n), for
all n > n0.
Graphical Representation of Big Omega Notation
If n > n0 then we can say that f(n) > c * g(n) before that f(n) value
may be less than c * g(n) or greater than c * g(n).
Example : f(n) = 3n + 2 ; g(n) = n we have to prove f(n) = Ὼ(g(n)).
In order to prove the above, we have to prove f(n) >= c * g(n) for all n
> n0.
By substituting the values of f(n) and g(n) we get
3n + 2 >= c * n
Let c= 1 then we get 3n + 2 >= n
Let n0 = 1, c = 1, then 5 >= 1 [True]
Let n0 = 2, c = 1, then 8 >= 2 [True]
So we can say that , n0 >= 1
Theta Notation :
Theta notation is represented as ɵ.
Theta notation mainly represents the Average Bound of algorithm’s
running time.
By using Theta notation we can calculate the Average amount of time
that an algorithm requires for its execution.
By using Theta notation we can calculate Average Case Time
Complexity.
Definition of Theta Notation
Let f(n), g(n) be two non – negative functions , then f(n) = ɵ(g(n)) if
there exists three positive constants c1, c2, n0 such that
c1 * g(n) <= f(n) <= c2 * g(n), for all n > n0.
Graphical Representation of Theta Notation

Example : f(n) = 3n + 2 ; g(n) = n we have to prove f(n) = ɵ(g(n)).

In order to prove the above we have to satisfy the condition
c1 * g(n) <= f(n) <= c2 * g(n)
c1 = 1; c2 = 4 as we have already done Big Oh notation and Big
Omega notation
In Big Oh notation f(n) <= c * g(n)
Where c = 4; c2 = 4
In Big Omega notation f(n) >= c * g(n)
Where c = 1; c1 = 1
1 * n <= 3n + 2 <= 4 * n
Let n0 =1 ; 1<=5<=4 [False]
Let n0 = 2; 2<=8<=8[True]
Let n0 = 3; 3 <= 11 <= 12 [True]
n0 >= 2
so, we can say that f(n) = ɵ(g(n)).
Little oh notation
Little oh notation is represented by o.
Definition of Little oh notation
Let f(n), g(n) be two non – negative functions then f(n) = o(g(n)) such
that
Lt (f(n)/g(n)) = 0
nI
where I stands for infinite.
Little Omega notation
Little Omega notation is represented by ώ.
Definition of Little Omega notation
Let f(n), g(n) be two non – negative functions then f(n) = ώ(g(n)) such
that .
Lt (g(n) / f(n)) = 0 or
nI
Where I stands for Infintity.
Lt (f(n) / g(n)) = I
nI
Where I stands for Infintity.
Note :
We write O(1) to mean a computing time that is a constant.
O(n) is called linear.
O(n2) is called quadratic.
O(n3) is called cubic.
O(2n) is called exponential.
If an algorithm takes time O(log n), it is faster for sufficiently large n,
than if it had taken O(n).
Similarly O(nlogn) is better than O(n2), but not as good as O(n).
The algorithms can be classified as follows from the best – to – worst
performance.
1. A logarithmic algorithm – O(log n).
Runtime grows logarithmically in proportion to n.

2. A linear algorithm – O(n).

Runtime grows directly in proportion to n.

3. A Super linear algorithm – O(nlogn).

Runtime grows in proportion to n.

4. A polynomial algorithm – O(nc).

Runtime grows quicker than previous all based on n.

5. A Exponential algorithm – O(cn).

Runtime grows even faster than polynomial algorithm based on
n.

6. A factorial algorithm – O(n!).

 Runtime grows the fastest and becomes quickly unusable for
even small values of n.

Algorithmic Examples of Runtime Analysis

Some of the examples of all those types of algorithms [in worst –
case scenarios] are mentioned below:
1. Logarithmic Algorithm – O(log n) – Binary Search.
2. Linear Algorithm – O(n) – Linear Search.
3. Super linear Algorithm – O(nlogn) – Heapsort, Merge sort
4. Polynomial Algorithm – O(nc) – Strassen’s Matrix
Multiplication, Bubble Sort, Selection Sort, Insertion Sort,
Bucket Sort.
5. Exponential Algorithm – O(cn) – Tower of Hanoi
6. Factorial Algorithm – O(n!) – Determinant Expansion by
minors, Brute – Force Search algorithm for Travelling
Salesperson problem.

Divide and Conquer

This topic is related to a strategy for solving a problem.
Strategy is a approach or design for solving a problem.
If a problem of some size is given. Let us say size is n. this size is the
size of the input for a problem . So, if a problem P is there of some
size and if we say that this problem is large, then you can break this
problem into smaller sub – problems P1, P2, P3 goes on as many
problems as possible, that depends on the user.
 P
P1 P2 P3 . . .. …. Pk
Let us say k is a sub – problem, now the large problem is broken
down into smaller sub – problems. As the size was larger, so we’ve
broken into smaller size problems.
Now these sub – problems can be solved to obtain their solutions s1,
s2, s3, …., sk.
P
P1 P2 P3 . . .. …. Pk
s1 s2 s3 sk
s1, s2, s3,…., sk are solutions. All these sub – problems are solved
individually.
Now, once you have the solutions for these you can combine these
solutions to get a solution for a main problem.
P
P1 P2 P3 . . .. …. Pk
s1 s2 s3 sk

S
So, if a problem is large divide the problem into sub – problems and
solve those sub – problems and combine the solutions of sub –
problems to get the solution for main problem.
That means, if a problem cannot be solved if it is too big break it into
sub – problems and solve it.
If a sub – problem is also large , then do the same thing, apply Divide
and Conquer strategy on sub – problems also. If it is large again do
the same thing, break it into sub – problems and find a solution and
then combine the solution.
Whatever the problem is , the sub – problems be same as that
problem.
For example, if a problem is to Sort then the sub – problems should
also be Sort. Each and every sub – problem should be sort only. It
cannot convert into some other problem.
General Method for Divide and Conquer Strategy
DAC(P)
{
if (small(P))
{
S(P);
}
else
{
Divide P into P1, P2, … , Pk
Apply DAC(P1), DAC(P2),…
Combine(DAC(P1), DAC(P2),….)
}
}
Divide and Conquer upon a problem P. If the problem is small then
directly solve it. Yes, definitely there must be a solution for small
problem.
If it is large, divide the problem P into sub – problems P1, P2, … , Pk
and apply Divide and Conquer on each. This is recursive.
Then, whatever the solutions you get, you combine these solutions of
the results of Divide And Conquer(P1), DAC(P2) and so on, combine
them together to get the solution for the main problem.
In the above example, we can see that it is having a recursive property
so the procedures are recursive, the algorithms are recursive.

Binary Search : The requirement of this Binary Search algorithm is ,

the array should be in sorted manner.

Example :

0 1 2 3 4 5 6 7 8 9
5 9 17 23 25 45 59 63 71 89

In the above example, the data in that array is sorted. If the data is not
sorted then you cannot apply Binary Search on that array. You have to
first the array then you can apply Binary Search for searching.

0 1 2 3 4 5 6 7 8 9
5 9 17 23 25 45 59 63 71 89

Key element = 59

Search for that data. Is this Key element = 59, present in this array or
not.

If present, your code should return where this 59 is present. That is,
the index at which this 59 is present.
Binary Search algorithm uses Divide and Conquer strategy. That
means, it is going to divide the array into two halves. That is, it
recursively Divide the array.

In this case, we’re going to find out the Middle element of the array.
So, we’re going to take two variables. First is left variable and left
variable is going to point to the start position of the array. Next is
right variable and right variable will be pointing to the last position of
the array.

0 1 2 3 4 5 6 7 8 9
5 9 17 23 25 45 59 63 71 89
L R
Left = 0 Right = 9

In this algorithm, we’re going to find out the mid position of the
array. From where, we’re going to divide the array into 2 halves.

How to find mid? Mid = Floor [(l + r) / 2] and we’re going to take the
floor value.

Mid = Floor [(0 + 9) / 2 ] = Floor [4.5] = 4

Left Right Mid

0 9 4

0 1 2 3 4 5 6 7 8 9
5 9 17 23 25 45 59 63 71 89
L R
Left = 0 Mid Right = 9

Here are three cases.

The data you want to find out is equal to the data at the mid position.
The data is less than the data which is at mid position.

The data you want to find out is greater than the data which is at mid
position.

Case 1 : data == a[mid]

Case 2 : data < a[mid]
Case 3 : data > a[mid]

Key element = 59 and Mid = 4. What is the value of a[4]?

a[4] = 25 ; data > a[mid]
59 > 25

So, now we can say that the data is present to the right of this mid.

0 1 2 3 4 5 6 7 8 9
5 9 17 23 25 45 59 63 71 89
L R
Left = 0 Mid Right = 9

Now, we’ve divided the array into 2 parts. How you can say that 59 is
present to the right of this mid? Because we know that the array is
sorted. If array is sorted, then all the data which is greater than 25
must be present to the right of this 2.

Now, we’re going to see in the right sub – array. We’ve divided our
search space.

In the beginning our search space is from 0 to 9. After 1 st comparison

we’ve divided into half. Now we’re going to search from 5 to 9.

If data > a[mid], then the left variable should be moved to index 5 .
That is to the right of the mid.
 0 1 2 3 4 5 6 7 8 9
5 9 17 23 2545 59 63 71 89
L R
Mid Left=5 Right = 9
Our L = mid + 1. As ,we are going to work in the right sub – array
only.

Mid = Floor [(5 + 9) / 2 ] = Floor [7] = 7

Left Right Mid

0 9 4
5 9 7

0 1 2 3 4 5 6 7 8 9
5 9 17 23 25 45 59 63 71 89
L R
Left=5 Mid Right = 9

Again, 3 cases can be there.

Case 1 : data == a[mid]

Case 2 : data < a[mid]
Case 3 : data > a[mid]

Now, check data = 59; Mid = 63; data < a[Mid]; 59 < 63

First, it will check data is equal to Mid. It is False. Here, the data is
less than the Mid value.

Now, we can say that data is present to the left of 63. If the data is
present to the left of mid, in that case left would be as it is i.e., L = 5.
The Right, R would be moved towards this side. Now, R = Mid – 1.
 0 1 2 3 4 5 6 7 8 9
5 9 17 23 25 45 59 63 71 89
L R
Left=5 Mid Right=6
We again divide the array into two parts. That is why we recursively
divide the array into 2 parts until you find the element.

Mid = Floor [(5 + 6) / 2 ] = Floor [5.5] = 5

Left Right Mid

0 9 4
5 9 7
5 6 5

Now, L = 5; Mid = 5. Check now.

Is data = 59 same a[mid] = False.

59 > a[mid] . That is 59 > 45.

That means data = 59 is present to the right of mid. Means L becomes

Mid + 1.

0 1 2 3 4 5 6 7 8 9
5 9 17 23 25 45 59 63 71 89
L R
Left=6 Mid Right=6
Mid = Floor [(6 + 6) / 2 ] = Floor [6] = 6

Left Right Mid

0 9 4
5 9 7
5 6 5
6 6 6

If Left and Right is pointing at the same index, it means we have

only 1element.
Now, check, if data = a[mid] that is 59 = a[mid]  True. Now, this is
the stopping condition, we found the data.

So, now we’re going to stop and you’re going to return mid. Return
Mid means you are going to return the index 6 where the data is
present.

If data is not present in the array. In that case, when you are going to
stop searching.

0 1 2 3 4 5 6 7 8 9
5 9 17 23 25 45 59 63 71 89
L R
Left = 0 Right = 9

Key element = 60

Mid = Floor [(0 + 9) / 2 ] = Floor [4.5] = 4

Left Right Mid

0 9 4
At index 4, we have the value is 25, which is the mid value.

This mid value is not equal to the data = 60

0 1 2 3 4 5 6 7 8 9
5 9 17 23 25 45 59 63 71 89
L R
Left = 0 Mid Right = 9

As, 60 > 25, so data is present to the right of 25. Then we are going to
move this left L, Left = Mid + 1.

0 1 2 3 4 5 6 7 8 9
5 9 17 23 25 45 59 63 71 89
L R
Mid Left=5 Right = 9
 Left Right Mid
0 9 4
5 9 7

0 1 2 3 4 5 6 7 8 9
5 9 17 23 25 45 59 63 71 89
L R
Left=5 Mid Right = 9
Now, check is 60 != 63 [False]. 60 < 63 [True] .

Since the data < a[mid] then the data is present to the left of 63. In
that case, R = Mid – 1.

Mid = Floor [(5 + 6) / 2 ] = Floor [5.5] = 5

Left Right Mid

0 9 4
5 9 7
5 6 5

0 1 2 3 4 5 6 7 8 9
5 9 17 23 25 45 59 63 71 89
L R
Left=5 Mid Right=6
Now, check if data = a[mid], that is 60 != 45 [False].

60 > 45, then data would be to the right of mid. In that case, left L
will be moving to the right of the array. L = Mid + 1.

Mid = Floor [(6 + 6) / 2 ] = Floor [6] = 6

Left Right Mid

0 9 4
5 9 7
5 6 5
6 6 6
 0 1 2 3 4 5 6 7 8 9
5 9 17 23 25 45 59 63 71 89
L R
Left=6 Mid Right=6
60 != 59 [False].

60 > 59 [True], it means that data is present to the right of that mid
element. Then we are going to move this L = Mid +1.

Left Right Mid

0 9 4
5 9 7
5 6 5
6 6 6
7 6

If L value becomes greater than R value, it means data is not present.

We’re going to repeat these steps.

Case 1 : data == a[mid]
Case 2 : data < a[mid]
Case 3 : data > a[mid]

int BinarySearch(a, n, data)

{
l = 0, r = n – 1
while (l < r)
{
mid = (l + r) / 2
if (data == a[mid])
return mid;
else if (data < a[mid])
 r = mid – 1;
else
l = mid + 1;
}
return -1;
}
Quick Sort
Sorting the elements that are available in an ascending or descending
order.
Example
0 1 2 3 4 5 6
10 15 1 2 9 16 11

In this algorithm, we are going to choose one element known as key

element or pivot element.
You can choose this first element as pivot element or key element, the
last element of the array as pivot element or key element or you can
say the median element as pivot element.
There are many techniques to get this pivot or key element.
Now, for the above example we will consider the first element as key
or pivot element.
0 1 2 3 4 5 6
10 15 1 2 9 16 11

Pivot = 10
Quick sort algorithm is based on the Divide and Conquer technique.
In Divide and Conquer technique, this complete array would be
divided into sub – arrays, and dividing this array into sub – arrays is
known as partitioning.
That partition method of this array that process is known as the
backbone of the quick sort.
0 1 2 3 4 5 6
10 15 1 2 9 16 11

Pivot = 10
We are going to partition this array in a way such that all the elements
less than this pivot element would be on the left side of the pivot
element and all the elements greater than this pivot element would be
to the right side of this element.
If any element which is equal to this pivot element that element can
go either ways i.e. either to the left side of the array or to the right
side of the array.
0 1 2 3 4 5 6
10 15 1 2 9 16 11

Pivot = 10
Key
Partition 1 Pivot Partition 2
Values < Pivot Values > Pivot
Now, that we have found out the proper place for one element, and
now the above array is divided into 2 arrays.
 Key
Partition 1 Pivot Partition 2
Values < Pivot Values > Pivot

One is called “Partition 1” i.e. the values less than the pivot element.
The other is all the elements greater than the pivot element are on the
right – side and is called as “Partition 2”.
In “Partition 1” we cannot say that values are in sorted order but the
main thing is that all the values to the left side are less than the pivot
element.
All the values to the right side i.e. “Partition 2” would be greater than
this pivot element.
We are going to choose pivot element on the left – side of the array
i.e. “Partition 1” again into two parts.
We are going to choose pivot element on the right – side of the array
i.e “ Partition 2” again into two parts and we are going to continue
this until we only one element left out.
2, 1, 9 or 9,1,2 10 15, 11, 16 or 16, 11,
15

0 1 2 3 4 5 6
2 1 9 10 15 11 16

The value 10 is at the position 3, so this pivot element is at its

appropriate place, no need to sort the pivot element 10 now.
We are going to apply the same procedure from index 0 – 2 and from
index 4 – 6.
Finding out the proper place for pivot element and partitioning the
array into two parts is known as “Partition Method”.

Example
0 1 2 3 4 5 6 7 8
7 6 10 5 9 2 1 15 7

In the above array, it contains 9 elements and name of the array A and
index is from 0 – 8.
0 1 2 3 4 5 6 7 8
7 6 10 5 9 2 1 15 7
lb
ub
Pivot = a[0] = 7
Where lb is Lower bound of this array
ub is Upper bound of this array
Now, we have to find out the proper place for the pivot element such
that all the elements less than pivot element i.e. 7 should be on the left
side of the array and all the elements greater than pivot element i.e. 7
should be on the right side of the array.
0 1 2 3 4 5 6 7 8
7 6 10 5 9 2 1 15 7
start
end
start variable will be moving from left to right.
end variable will be moving from right to left.
If you find any element which is greater than this pivot element at that
element we are going to stop the ‘start’ variable otherwise we are
going to increment start variable.
Or
If you find any element which is less than or equal to this pivot
element, then we are going to increment start variable until we found
element greater than pivot element.
0 1 2 3 4 5 6 7 8
7 6 10 5 9 2 1 15 7
start
end
Pivot = 7 (7 <= 7 True)
0 1 2 3 4 5 6 7 8
7 6 10 5 9 2 1 15 7
start
end
(6 < = 7 True)
0 1 2 3 4 5 6 7 8
7 6 10 5 9 2 1 15 7
start
end
(10 <= 7 False)
0 1 2 3 4 5 6 7 8
7 6 7 5 9 2 1 15 10
 start
end
0 1 2 3 4 5 6 7 8
7 6 7 5 9 2 1 15 10
start
end
(5 <= 7 True)
0 1 2 3 4 5 6 7 8
7 6 7 5 9 2 1 15 10
start
end
(9 <= 7 False)
0 1 2 3 4 5 6 7 8
7 6 7 5 9 2 1 15 10
start
end
(10 > 7 True)
0 1 2 3 4 5 6 7 8
7 6 7 5 9 2 1 15 10
start end
(15 > 7 True)
0 1 2 3 4 5 6 7 8
7 6 7 5 9 2 1 15 10
start end
(1 > 7 False)
Now, we are going to swap the elements 9 and 1. After swapping the
array would be.
0 1 2 3 4 5 6 7
8
7 6 7 5 1 2 9 15 10
start end
a[start] <= Pivot
(1 <= 7 True)
0 1 2 3 4 5 6 7
8
7 6 7 5 1 2 9 15 10
start end
a[start] <= Pivot
(2 <= 7 True)
0 1 2 3 4 5 6 7 8
7 6 7 5 1 2 9 15 10
start end
a[start] <= Pivot
(9 <= 7 False, We are going to stop here)
0 1 2 3 4 5 6 7 8
7 6 7 5 1 2 9 15 10
start end
a[end] > Pivot
(9 > 7 True, Decrement the end variable)
 0 1 2 3 4 5 6 7
8
7 6 7 5 1 2 9 15 10
end start
a[end] > Pivot
(2 > 7 False, then we are going to stop here)
After that, we have to swap the elements, but we are not going to
swap the elements. Why ?
Because ‘start’ variable has crossed the ‘end’ variable so we are not
going to swap the elements.
We are going to follow the procedure swapping and all until we have
‘start’ is less than ‘end’.
At the point we got ‘start’ is greater than ‘end’ then we are not going
to swap.
Now, next step is we are going to swap this pivot element with the
element where end variable is available.
After swapping the array would be :
0 1 2 3 4 5 6 7
8
2 6 7 5 1 7 9 15 10

Location of the pivot element is at 5.

Now, you can check all the elements which are less than or equal to
the pivot element (7) are to the left and all the elements which are
greater than the pivot element (7) are to the right.
Now, pivot element (7) is at its position. Now, we are going to apply
the same procedure for partition 1 and partition 2.
Quick sort is also known as Partition – Exchange sort.
Time Complexity for the Quick Sort algorithm is, in the worst case
O(n2), but in average case or in best case O(n log n).

Quick Sort Algorithm

Partition (A, lb, ub)
{
Pivot = a[lb];
start = lb;
end = ub ;
while (start < end)
{
while (a[start] <= Pivot)
{
start ++;
}
while (a[end] > Pivot)
 {
end --;
}
if (start < end)
{
swap(a[start], a[end]);
}
swap(a[lb], a[end]);
return end;
}
Quicksort(A, lb, ub)
{
if (lb < ub)
{
loc = Partition(A, lb, ub);
Quicksort(A, lb, loc – 1);
Quicksort(A, loc + 1, ub);
}
}
Merge Sort
This sorting technique also works on divide and conquer technique.
In this case, the complete list is divided into sub – list or you can say
the complete list is divided into n sub – lists and each sub – list is
having one element or you can say we will keep on dividing the list
into sub – list until we get the sub – list having one element only.
After that we are going to merge the sub – list and we will keep on
merging the sub – list.
Two adjacent sub – list you can say to produce a new sorted sub – list
and will keep on merging the sub – list until we get 1 complete sub –
list and that sub – list would be sorted sub – list.
The first step is dividing the given list into sub – list.
Second step is merging of those sub – list to get one complete sorted
list.
Example
0 1 2 3 4 5 6 7 8
15 5 24 8 1 3 16 10 20

Now, we are going to apply merge sort to sort these elements.

First divide the list into 2 equal sub – lists.
Equal subarrays means we have to find out the mid position, then you
are going to divide this array from that mid – position.
Finding out the mid – position
(lb + ub)/2
Where lb is Lower Bound and ub is Upper Bound.
0 1 2 3 4 5 6 7 8
15 5 24 8 1 3 16 10 20
lb ub
mid = (0 + 8)/2 = 8/2 = 4
Till index 0 to 4 one sub – list and from 5 to 8 one other sub – list.
0 1 2 3 4 5 6 7 8
15 5 24 8 1 3 16 10 20

0 1 2 3 4 5 6 7 8
15 5 24 8 1 3 16 10 20
0 1 2
15 5 24 8 1
3 16 10 20

15 5 24
8 1 3 16 10
20
15 5

Now, we cannot further divide the sub – lists because each sub – list
is having 1 element.
Algorithm
Mergesort(A, lb, ub)
{
if (lb < ub)
{
mid = (lb + ub) / 2
Mergesort(A, lb, mid);
Mergesort(A, mid + 1, ub);
 Merge(A, lb, mid, ub);
}
}
Merge(A, lb, mid, ub)
{
i = lb;
j = mid + 1;
k = lb;
while ((i <= mid) && (j <= ub))
{
if(a[i] <= a[j])
{
b[k] = a[i];
i++;
}
else
{
b[k] = a[j];
j ++;
}
k++;
}
 if (i > mid)
{
while(j <= ub)
{
b[k] = a[j];
j++;
k++;
}
}
else
{
while (i <= mid)
{
b[k] = a[i];
i++;
k++;
}
}
for (k = lb; k <= ub; k++)
{
a[k] = b[k];
}
}
Example
5 15

5 15 24

1 5 8 15 24 3 10 16 20

0 1 2 3 4 5 6 7 8
1 3 5 8 10 15 16 20 24

k = m + n elements.
Time complexity for this merging formation is Theta(m + n).
Where m denotes no. of elements in one sorted sub – list.
n denotes no. of elements in another sorted sub – list.
Finding Maximum and Minimum element using Divide and
Conquer

Divide and Conquer algorithm is implemented in 3 steps. Divide,

Conquer, Combine.

Divide : In this step, given array is divided into 2 parts.

Conquer : In this step, each sub – problem or each sub – list is solved
recursively.

Combine : In this step, the solutions of the sub – problems or sub –

lists are merged or combined.

Example : An array which contains n elements .

Size of the array contains 7 elements.
0 1 2 3 4 5 6
7 10 13 71 32 83 2
Low high

The first element is treated as low value, whereas the last element is
treated as high value. If n = 7, then high = n – 1, as we have taken
starting index as 0 in the above example. So, Low = 0; high = 6

The first step is to divide. In divide step, the given array is divided
into 2 parts. We can divide the array into 2 parts by calculating the
mid value.

mid = (low + high) / 2 ; here low = 0; high = 6

mid = (0 + 6) / 2 = 6 / 2 = 3

So, now we can have 2 lists for the above array.

0 1 2 3 4 5 6
7 10 13 71 32 83 2

7 10 13 71
List 1

32 83 2
List 2
List 1 ranges from low to this mid value. That is, low = 0; Mid = 3, so
it ranges from 0 to 3.
Whereas List 2 ranges from (Mid + 1) to high value. That is, Mid + 1
= 3 + 1 = 4; high = 6, so it ranges from 4 to 6.
Again, we have to solve the List 1 and List 2 recursively. Now, we
need to calculate the Mid value.
Mid = Floor [(0 + 3) / 2] = [3/2] = 1

0 1 2 3 4 5 6
7 10 13 71 32 83 2

7 10 13 71

32 83 2
7 10

13 71 32 83

So, here List 1 contains the elements from 0 to 1. Whereas List 2

contains the elements from Mid + 1 to high.
List 1 contains the values that are at indexes 0 and 1. List 2 contains
the values that are at indexes 2 and 3.
We have to solve each list recursively as long as the list contains
either 1 or 2 elements.
In the above example, List 1 contains 2 elements and List 2 contains 2
elements.
Whereas in List 2 also it is divided into 2. Here, List 1 contains 2
elements and List 2 contains 1 element. So, we have to stop the
conquer process. For how long, we have to continue this conquer
process? We have to solve this problem as long as the list contains
either 1 or 2 elements.

0 1 2 3 4 5 6
7 10 13 71 32 83 2

7 10 13 71

32 83 2
7 10

13 71 32 83

Now, compare the elements in the list.

Compare 7 and 10 and tell which is minimum and maximum value?
Maximum = 10; Minimum = 7
Now, compare 13 and 71 and tell which is the maximum value and
minimum value. Maximum = 71; Minimum = 13
The last step is to Combine. Combine means doing the comparisons
and finding which is the maximum element and which is the
minimum element. So, Combine the solutions of the sub – problems.
Here, Combining means comparing the Maximum and Minimum
element.

0 1 2 3 4 5 6
7 10 13 71 32 83 2

7 10 13 71

32 83 2
7 10
Min = 7; Max = 10
13 71 32 83
Min = 13; Max = 71
Min = 32; Max = 83
2
Min = 7; Max = 71
Max = Min = 2

Min = 2; Max = 83
Now, compare 10 and 71 which one is maximum, Max = 71.
Compare 7 and 13, which one is minimum, Min = 7. Compare 83 and
2 which one is maximum, Max = 83. Compare 32 and 2 which is
minimum, Min = 2.
That’s why in Conquer step, we are solving the problem recursively
as long as the list contains 1 or 2 elements.
If there are 2 elements, then 1 element will become maximum
element and the other element will become minimum element.
Whereas if the list contains only 1 element then that element solely
will becomes both maximum and minimum.
0 1 2 3 4 5 6
7 10 13 71 32 83 2

7 10 13 71

32 83 2
7 10
Min = 7; Max = 10
13 71 32 83
Min = 13; Max = 71
Min = 32; Max = 83
2
Min = 7; Max = 71
Max = Min = 2

Min = 2; Max = 83

Max = 83; Min = 2

Algorithm Maxmin(low, high, Max, Min)
{
if (low == high)
{
Max = Min = a[low];
}
else if (low == high – 1)
{
if (a[low] > a[high])
{
Max = a[low];
Min = a[high];
}
else
{
Max = a[high];
Min = a[low];
}
Mid = (low + high) / 2;
Maxmin(low, Mid, Max, Min);
Maxmin(Mid + 1, high, max1, min1);
if (max1 > max)
max = max1;
if (min1 < min)
 min = min1;
}
}
if (low == high) means, if the list contains only 1 element, then that
element will become both maximum element and minimum element.
So, that’s why the statement max = min = a[low] or we can write as
max = min = a[high]. Here, a means array name.
Else if (low == high – 1) means if the list contains 2 elements for
example, the following are the elements 10, 20 . Low = 0; High = 1.
So this statements inside that condition will be executed.
If the list contains two elements, then we’ve to compare those two
elements. The maximum element will be stored in Max variable and
minimum element will be stored in Min. variable.
if a[low] is greater than a[high] means the first element is the biggest
element, whereas the second element is the smallest element.
So, max = a[low] that is max = 20 and min = a[high] that is min = 10.
Else if a[low] is less than a[high]  10 is less than 20 becomes True.
So, max = a[high] that is max = 20 and min =10.
Else if the list contains more than two elements then we will be using
Divide and Conquer algorithm.
We know that Divide and Conquer algorithm is implemented using 3
steps :
1. Divide Mid = (Mid = (low + high) / 2
2. Conquer means list 1 and list 2 are to be solved recursively.
list 1 contains the elements which ranges from low to mid.
Whereas list 2 contains the elements from mid + 1 to high.
So the statement Maxmin(low, mid, max, min) is for list 1
conquer step, in order to solve list 1 recursively we’re using the
above statement.

Next, solving list 2 recursively, we have to solve list 2

recursively, list 2 contains the elements which ranges from mid
+ 1 to high. That is, the statement Maxmin(Mid + 1, high,
Max1, Min1).

Next we have to perform ‘Combine’. After executing this

function call Maxmin(low, mid, max, min);

Maximum value is available in Max variable.

Minimum value is available in Min variable.

Likewise after solving this list 2 maximum value is available in

Max1 variable. Minimum value is available in Min1 variable.

Here, combining means combining the solutions of these two

lists. That is, making the comparison between Max and Max1;
Min and Min1.

So, if Max1 is greater than Max that means Max1 is having

higher value. We have to store Max1 in Max variable, that is
Max = Max1. So, now Maximum is available in Max variable.

List1 minimum value is stored in min variable. Whereas list2

minimum value is stored in Min1 variable. So, compare Min1
and Min element.

Suppose if Min1 is less than Min then Min = Min1.

To find out the Time Complexity for finding the Minimum and
Maximum value.
0 𝑖𝑓 𝑛 = 1
𝑇(𝑛) = {
1 𝑖𝑓 𝑛 = 2
𝑛
T(n) = 2𝑇 ( ) + 2 if n > 2
2

T(n) means Time Complexity for an array of n elements.

If the list contains only one element, that means if n = 1 then zero
comparisons because that element will become both maximum and
minimum element.
If the list contains two elements that means if n = 2 then we require
one comparison.
Let the list contains 2 elements 10, 30 then we have to make
comparison between 10 and 30. So, we need one comparison.
If the list contains more than two elements that means if n is greater
than 2 then the recurrence relation is.
We have the following elements 10 30 40 50. Here, we have to divide
the list into 2 parts. Elements 10 and 30 belongs to one part and
elements 40 and 50 belong to the other part.
𝑛
Here the recurrence relation is 2𝑇 ( ) + 2.
2

Why we have taken this 2? Because we have taken two parts.

Since we are dividing the list into two parts, where each part contains
n/2 elements.
Let us the following elements.
10, 20, 30, 40, 50, 60, 70, 80  8 Elements.
So, we have to divide this list into two parts. List 1 contains the
elements 10, 20, 30, 40 and List 2 contains 50, 60, 70, 80.
𝑛
List 1 contains the elements 10, 20, 30, 40 and it is 𝑇 ( ) .
2

𝑛
List 2 contains the elements 50, 60, 70, 80 and it is 𝑇 ( ).
2

Since we have 8 elements. Now, the List 1 contains 8/2 = 4 elements.

Whereas List 2 contains 8/2 = 4 elements.
Let us calculate the Time Complexity based on the recurrence
relation.
𝑛
T(n) = 2𝑇 ( ) + 2.
2

𝑛
= 2 [2𝑇 ( ) + 2] + 2.
4

𝑛
= 4𝑇 ( ) + 4 + 2.
4

𝑛
= 4 (2𝑇 ( ) + 2] + 4 + 2.
8

𝑛
= 8𝑇 ( ) + 8 + 4 + 2
8

𝑛
= 23 𝑇 ( 3 ) + 2 3 + 22 + 21
2

𝑛
= 22𝑇 ( 2 ) + 22 + 21
2

. . .
𝑛
T(n) = 2 k - 1𝑇 ( )+ ∑𝑘−1
𝑖=1 2
𝑖
2𝑘−1

m–n m–n 𝑎𝑚
This is in the form of a . So, a =
𝑎𝑛

2𝑘 2𝑛
T(n) = ( ) 𝑇 ( 𝑘 ) + ∑𝑘−1
𝑖=1 2
𝑖
2 2
Let 2k = n
𝑛 2𝑛
T(n) = 𝑇 ( ) + ∑𝑘−1
𝑖=1 2
𝑖
2 𝑛

∑𝑘−1 𝑖
𝑖=1 2 is nothing but Geometrical Progression.

𝑛 2𝑛
T(n) = 𝑇 ( ) + 2k – 2
2 𝑛

𝑛 2𝑛
= 𝑇( ) + n– 2
2 𝑛
𝑛
= 𝑇(2) + n – 2
2
𝑛
= +𝑛 −2
2
3𝑛
= −2
2
3𝑛
This is the Time Complexity is −2
2

In order to calculate the Time Complexity, we have to ignore the

constant multipliers as well as we need to consider higher exponent.
ɵ(n) is the Best, Worst and Average case Time Complexity.
Selection Sort
Example
0 1 2 3 4 5
7 4 10 8 3 1
In this case, one array is there and this array would be divided into
two sub – arrays.
1. Sorted Sub – Array
2. Unsorted Sub – Array
Initially, the Sorted sub – array or sorted sub – list is empty. That is,
no element is available.
From this unsorted sub – array or sub – list we will find out the
minimum element and that minimum element would be swapped with
the element which is at the starting position in this unsorted sub –
array.
In the above example, the minimum element is 1, so this element 1
would be swapped with at the starting position of this unsorted sub –
array. So, the element 1 would be swapped with element 7.
First, we need to find out the minimum element in the unsorted sub –
array or sub – list.
By some method, we have found out the 1 is the minimum element.
Next step is this element 1 would be swapped with the element which
is at the starting of the unsorted sub – array.
Initially the array is.
0 1 2 3 4 5
7 4 10 8 3 1

After swapping the array is:

Pass 1:
0 1 2 3 4 5
1 4 10 8 3 7

This index 0 is sorted sub – array and unsorted sub – array is from
index 1 to 5.
Next step, from the unsorted sub – array find the minimum element.
So, the minimum element is 3 and swap this minimum element 3 with
the element which is at the beginning of the unsorted sub – array.
Pass 2:
0 1 2 3 4 5
1 3 10 8 4 7

From index 0 to 1 is sorted sub – array, and, from index 2 to 5 is

unsorted sub – array.
In Pass 3, find out the minimum element from the unsorted sub –
array. Minimum element is 4 and swap this minimum element with
the element which is at the beginning of this unsorted sub – array.
Pass 3:
0 1 2 3 4 5
1 3 4 8 10 7

From, index 0 to 2 is sorted sub – array. In Pass 4, find out the

minimum element from the unsorted sub – array. Minimum element is
7 and swap this minimum element with the element which is at the
beginning of this unsorted sub – array.
Pass 4:
0 1 2 3 4 5
1 3 4 7 10 8

From, index 0 to 3 is sorted sub – array. In Pass 5, find out the

minimum element from the unsorted sub – array. Minimum element is
8 and swap this minimum element with the element which is at the
beginning of this unsorted sub – array.
Pass 5:
 0 1 2 3 4 5
1 3 4 7 8 10

From index 0 to 4 is sorted sub – array. In unsorted sub – array, there

is only one element and there is no need to sort, because if one
element is there, obviously that is always sorted.
So, you can say that if 6 elements are there, now we have sorted 5
elements. So, automatically 6th element would be at its appropriate
place.
In this example, there are 6 elements and the number of passes
required are 5. That means, (n – 1) passes.
for(i = 0; i < n – 1; i++)
{
int min = i;
for (j = i + 1; j < n; j++)
{
if (a[j] < a[min])
{
min = j;
}
if (min != i)
{
swap(a[i], a[min]);
}
}
Time Complexity for Selection Sort is O(n2) both in worst case and
best case.
Strassen’s Matrix Multiplication
Let’s start with Matrix Multiplication is
𝑎11 𝑎12 𝑏11 𝑏12
A=[ ] B=[ ]`
𝑎21 𝑎22 𝑏21 𝑏22

𝑐11 𝑐12
C=[ ]
𝑐21 𝑐22

I have taken two matrices A and B . Where Matrix A contains some

elements and the order of this matrix is 2 X 2 . Matrix B contains
some elements and the order of this matrix is 2 X 2.
When you multiply 2 matrices, they can be multiplied if the number
of columns of the first matrix are equal to the number of rows of
second matrix. The resultant matrix will be 2 X 2.
Any term of that C matrix Cij = ∑𝑛𝑘=1 𝐴𝑖𝑘 * Bkj
The above is the general form for multiplying 2 matrices of any
dimensions.
Here, we’re just taking an example of 2 X 2 matrix. Whether you
want to multiply these 2 matrices and get the resultant matrix that is C
matrix. If I use the general formula and write down the algorithm or a
piece of code for multiplying two matrices . Let us see how the code
looks like. For preparing C matrix I will take the loops.
for (i = 0;i < n ; i++)
{
 for (j = 0;j < m ;j++)
{
c[i][j] = 0;
for (k = 0; k < n; k++)
{
c[i][j] += a[i][k] * b[k][j];
}
}
If we write simple algorithm for multiplying two matrices then it will
be written using three for loops as shown above.
For accessing all the elements of any matrix we actually require two
for loops. Then, here, for finding the product of each element C11
will be obtained by multiplying all the elements of a row with all the
elements of a column. So, for that we require one more loop.
What will be the Time Complexity if three for loops? O(n3).
Now, let us try to adapt Divide and Conquer strategy for solving the
matrix multiplication.
So, let us observe what we can do such that we can apply Divide and
Conquer strategy.
In Divide and Conquer strategy we say that if a problem is large, we
break the problem into sub – problems and solve these sub –
problems, combine the solutions of the sub – problems to get the
solution for main problem.
Now, when you say the problem is large, then you should also define
what is this small problem. If it is a small problem, we will directly
solve it.
That’s why first of all define a small problem.
In Divide and Conquer strategy which size matrix we should say is
small , so, we will say 2 X 2 matrix is small.
If the matrix is of 2 X 2 then we will directly solve them. If there are
bigger than that, that is if the dimensions are 4 X 4 or 8 X 8 then we
apply Divide and Conquer strategy. That is, we break the problem
into sub – problems.
Let us see how to solve this 2 X 2 matrix.
𝑎11 𝑎12 𝑏11 𝑏12 𝑐11 𝑐12
A=[ ] B=[ ] C=[ ]
𝑎21 𝑎22 𝑏21 𝑏22 𝑐21 𝑐22
We have to get the resultant matrix after multiplying them.
How can we get the terms of C matrix?
C11 = a11 * b11 + a12 * b21
C12 = a11 * b12 + a12 * b22
C21 = a21 * b11 + a22 * b21
C22 = a21 * b12 + a22 * b22
Here, if the matrices of order 2 X 2 of 2 matrices, then we can
multiply them by directly using the above formulas. Here, for
multiplying 2 X 2 matrix I am not using three for loops, but I am
directly using the formula.
So, if I say the time taken by this. How much time it is taking?
If I consider each statement is taking one unit of time, so, total time is
four unit of time. That is constant.
If I say, no multiplications are there you count them then total 8
multiplications are there, that is also a constant.
Anyhow the above four formulas are constant. Now this is defined as
a small problem. If you want to reduce the size and say if it is 1 X 1
matrix then they will be having just 1 element and just single product
will be there.
That is, imagine there is only one element.
A = [a11]; B = [b11] ;C = [a11 * b11]
So, I can say that if the dimensions are less than or equal to 2 then it is
a small problem. If it is 2 X 2 then the above 4 formulas will be used.
If it is 1 X 1 matrix, then I will use the above formula C = [a11 * b11]
direct multiplication is there.
Now what if it is greater than 2 X 2?
Then, I have to divide the problem into sub – problems and solve
them.
One important thing is, as it is 2 X 2 we assume that the matrices are
having the dimensions in powers of 2 only, like 2 X 2 or 4 X 4 or 8 X
8 or 16 X 16. So, the dimensions are in the powers of 2, so that will
be divide and divide we may reach to the size of 2 X 2 or if you
further divide, then you may go until 1 X 1. If it not of power 2 X 2
then you cancel zeros and you make it square matrix of powers of 2 X
2.
Now if it is 4 X 4 how we will apply Divide and Conquer strategy.
A 4X4 B
a11 a12 a13 a14
a21 a22 a23 a24
a31 a32 a33 a34
a41 a42 a43 a44
 b11 b12 b13 b14
b21 b22 b23 b24
b31 b32 b33 b34
b41 b42 b43 b44
4X4
In the above, we are having two 4 X 4 matrices and I say that this
problem is large. Then, we have to divide the problem into sub –
problem and then solve these sub – problems and combine the
solutions.
The above is a 4 X 4 matrix, if you see the dimension there are 4 rows
and 4 columns. Rows are starting from 1 and ending at 4. Columns
are starting from 1 and ending at 4.
Now, we say that this dimensions are 4 X 4 must be divided by 2, that
is (4 / 2) X (4 / 2).
Now, we will get 4 matrices of size 2 X 2. Now we will consider this
matrix.
𝑎11 𝑎12 𝑏11 𝑏12
A11 = [ ] B11 = [ ]
𝑎21 𝑎22 𝑏21 𝑏22
𝑎13 𝑎14 𝑏13 𝑏14
A12 = [ ] B12 = [ ]
𝑎23 𝑎24 𝑏23 𝑏24
𝑎31 𝑎32 𝑏31 𝑏32
A21 = [ ] B21 = [ ]
𝑎41 𝑎42 𝑏41 𝑏42
𝑎33 𝑎34 𝑏33 𝑏34
A22 = [ ] B22 = [ ]
𝑎43 𝑎44 𝑏43 𝑏44
𝑎11 𝑎12
Now, if I consider this matrix A11 = [ ] as single element,
𝑎21 𝑎22
then now this become a 2 X 2 matrix.
𝐴11 ∗ 𝐵11 + 𝐴12 ∗ 𝐵21 𝐴11 ∗ 𝐵12 + 𝐴12 ∗ 𝐵22
[ ]
𝐴21 ∗ 𝐵21 + 𝐴22 ∗ 𝐵21 𝐴21 ∗ 𝐵12 + 𝐴22 ∗ 𝐵22
We will follow the same formulas even for multiplying these
matrices. We treat the matrix as a single element.
Algorithm of Divide and Conquer for Matrix Multiplication
Algorithm mm(A, B, n)
{
if (n <= 2)
{
C11 = 𝐴11 ∗ 𝐵11 + 𝐴12 ∗ 𝐵21
C12 = 𝐴11 ∗ 𝐵12 + 𝐴12 ∗ 𝐵22
C21 = 𝐴21 ∗ 𝐵21 + 𝐴22 ∗ 𝐵21
C22 = 𝐴21 ∗ 𝐵12 + 𝐴22 ∗ 𝐵22
}
else
{
mid = (n / 2);
mm(A11, B11, (n/2)) + mm (A12, B21, (n/2))
mm(A11, B12, (n/2)) + mm (A12, B22, (n/2))
mm(A21, B11, (n/2)) + mm(A22, B21, (n/2))
mm(A21, B12, (n/2)) + mm(A21, B22, (n/2))
}
}
Now, what will be the Time Complexity of this algorithm?
This algorithm is using Divide and Conquer strategy, so, this is a
recursive algorithm we can see that the function is calling to itself ,
that is a function is called to itself 8 times.
Now let us prepare the recurrence relation for the above algorithm?
Recurrence relation will be:
 1 𝑛≤2
𝑇(𝑛) = { 𝑛 2 n>2
8𝑇 ( ) + 𝑛
2

What is the work done for combining? This addition, I said that those
are not normal scalar value additions, those are matrix additions.
How much time it will take for adding two matrices?
Each element should be added with the corresponding element, so
there are n2 elements.
Time taken for adding is n2.
So, the time for combining is n2 .
1 𝑛≤2
𝑇(𝑛) = { 𝑛 2 n>2
8𝑇 ( ) + 𝑛
2

If we apply master’s theorem on the above recurrence relation a = 8; b

=2 and the function f(n) = n2.
logb a = log2 8 = 3
nk = n2 = 2. That is k = 2.
So, logb a is greater than k.
What will be the Time Complexity? ɵ(n3).
But the Divide and Conquer algorithm is recursive. Internally uses a
stack that will be consuming extra space. In terms of space, if we see
then the algorithm with just three for loops is better than Divide and
Conquer algorithm.
Now, as this is taking more time compared to other algorithm. Is there
any chance of reducing the Time Complexity of the algorithm?
Now, let us talk about Strassen.
We have seen 4 formulas for multiplying 2 matrices and those
formulas are being utilized in the form of functions [recursive
function]. In this, we can see that there are total 8 multiplications.
What Strassen has done is the major work in matrix multiplication is
multiplication only.
So, if we can reduce the number of multiplications then that will make
the algorithm faster.
So, 4 formulas with eight multiplications, he has given different
formulas instead of following those 4 formulas. He has given different
formulas with 7 multiplications which will reduce the Time
Complexity of the algorithm little bit, little less than n3.
So, let us see what Strassen has given? The 4 formulas for directly
multiplying 2 matrices.
C11 = 𝐴11 ∗ 𝐵11 + 𝐴12 ∗ 𝐵21
C12 = 𝐴11 ∗ 𝐵12 + 𝐴12 ∗ 𝐵22
C21 = 𝐴21 ∗ 𝐵21 + 𝐴22 ∗ 𝐵21
C22 = 𝐴21 ∗ 𝐵12 + 𝐴22 ∗ 𝐵22
With 8 multiplications.
These may be simple elements or these may be matrices.
Strassen has reduced the number of multiplications and this additions
are also there [4 additions].
Addition or Subtraction will take less time compared to
multiplication.
Strassen’s formula if you see the number of multiplications are
reduced. Additions and Subtractions has increased.
The following are the formulas.
P = (A11 + A22) (B11 + B22)
Q = (A21 + A22) B11
R = A11(B12 – B22)
S = A22(B21 – B11)
T = (A11 + A12)B22
U = (A21 – A11)(B11 + B12)
V = (A12 – A22)(B21 + B22)
C11 = P + S – T + V
C12 = R + T
C21 = Q + S
C22 = P + R – Q + U
Find out these formulas P, Q, R, S, T, U, V and that is involving these
elements A and B.
So, he has given 7 formulas named as P to V with 7 multiplications.
Those formulas are utilized to get the elements C11 to C22.
Number of formulas has increased and addition and subtraction has
increased but the number of multiplications has reduced.
If you apply Divide and Conquer strategy then the algorithm will be
calling itself multiple times but total only 7 times instead of 8 times.
So, what will be the recurrence relation for this.
1 𝑛≤2
𝑇(𝑛) = { 𝑛 2 n>2
7𝑇 ( ) + 𝑛
2

Log2 7 = 2.81 ; k = 2
Strassen has reduce the Time Complexity and the Time Complexity
will be O(n2.81) that is a little lesser than O(n3).

THE GREEDY METHOD

Introduction
Greedy Method is one of the strategy for solving problems, just like
Divide and Conquer and other strategies.
Greedy method is also one of the approach for solving the problem or
a design we can adopt for solving similar problem. The problems
which fits into this one, we can solve all of them.
This method is used for solving Optimization problems. What is
Optimization problem? A problem which demands or which requires
either minimum result or maximum result.
Example :
Suppose there is a problem P and the problem is P : A  B; I want to
travel from one location A to location B. I have to cover this journey,
that is the problem. For any problem, I am taking one example it can
be any problem of similar type.
Now, for this problem, there may be more than one solution. Let us
say I can travel this by Walk [Solution 1] or I can take a Bike
[Solution 2] or I can take a Car [Solution 3] or I can go by Train
[Solution 4] or I can go by Flight [Solution 5] and there may be more
solutions.
P:AB
 S1 S2 S3 S4 S5 ……..
Where S1, S2, S3, S4, S5, …. are solutions 1, 2, 3, 4, 5,…..
So, my problem is to travel from location A to location B and there
are many locations. But there is a constraint in a problem. I say that I
have to cover this journey within 12 hours. This is a Constraint.
Suppose I cannot cover it if I go by Walk, by Car and so, I can cover
it only if I go by Train or Flight.
Now, for a problem there are many solutions, but these solutions
which are satisfying the condition given in the problem, then these
types of solution becomes Feasible Solution.
A solution which is satisfying the condition given in the problem is
Feasible Solution. Though for a given problem there may be many
solutions. This is Feasible Solution satisfying the constraint.
Commonly, we can use the term whether it is Feasible or not. Feasible
in the sense satisfying our constraints or not, limitations or not.
If I say that I want to cover this journey in minimum cost, that means
I want to spend as much as less possible, then this becomes a
minimization problem. So, now as the problem demands or result
should be minimum then it is a minimization problem.
Out of these two solutions, i.e. S4 and S5, one of the solution may be
taking minimum cost.
Suppose by Train if I go this is the minimum cost, then, this is called
as Optimal Solution.
A Solution which is already feasible and also giving me minimum
cost that is best results. That is best for the minimum is the best for
me then that solution is called Optimal Solution and definitely for any
problem there can be only one Optimal Solution, there cannot be
multiple Optimal Solutions. That means there can be only one
minimum cost, minimum can only be one.
There can be more than one solution, there can be more than one
feasible solution but there will be definitely only one Optimal
Solution.
This problem requires minimum result, some others may require
maximum result. So, if a problem requires either minimum or
maximum results then we call that type of problem as Optimization
problem.
Optimization problem is one which requires either minimum result or
maximum result.
Feasible solution means a solution which is satisfying some
constraint.
Optimal solution which is achieving the objective of a problem, that is
satisfying the objective of a problem that is either minimum result or
maximum result.
A problem which requires a minimum or maximum result is a
Optimization problem.
So, Greedy method is used for solving Optimization problems.
These are the strategies used for solving Optimization problems.
1. Greedy method
2. Dynamic Programming
3. Branch and Bound
But the approach is different, and every problem whichever requires
optimal results, some may be suitable in Greedy method, some may
be suitable in Dynamic Programming.
This strategy can apply on it or some Branch and Bound strategy can
be applied. For some problems all these strategies can be applied on
them.

General Method of Greedy

Algorithm Greedy(a, n)
{
for i = 1 to n do
{
x = select(a);
if feasible(x) then
solution = solution + x
}
}
I have written an algorithm. Now, see Greedy method says that a
problem should be solved in stages, in each stage we will consider
one input from a given problem and if that input is feasible then we
will include it in the solution, so by including all those feasible inputs
we will get an Optimal solution.
So, in stage we will each time we’ll pick up our input and we consider
it and we fished it’s feasible we will include it and like this if we
follow this procedure we will get the Optimal solution.
So, here a general method is given, if a problem is given and that
problem is having a input of some size and n is the size and it is
having some data some values input values.
Now, it will go through all those input values from 1 to n and each
time it will select something from a and call it as x. If that x if
feasible, that is one input one by one it will pick up the input and that
input if it is feasible it will include in the solution.

Knapsack Problem using Greedy method

Let us assume that we have n objects, here each object is having a
profit, where profit is represented by Pi . So P1 means first object
profit, P2 means second object profit and each object will have
corresponding weight also.
Weight is represented with the help of Wi.
We have a Knapsack here, Knapsack is nothing but a bag whose
weight is represented with the help of m.
Assume that the size of the Knapsack, that is the capacity of the bag is
20 kgs.
The main objective of Knapsack problem is to place the
corresponding objects in the bag with the minimum profit. That is, we
have to place all the objects in the Knapsack with the maximum
profit.
Here, an Optimal solution [Optimal solution means the best solution]
is represented with the help of Knapsack Vector and Knapsack Vector
is represented with the help of Xi.
Here, the value of Xi ranges from 0 to 1 i.e., 0 <= Xi <= 1. That
means, minimum value is 0 and maximum value is 1 and in between
we can have some fractional values also.
If the object is placed in the Knapsack, then we can say that X i = 1,
whereas if an object is not placed in the Knapsack, then we say that Xi
= 0.
Let Knapsack contains some space, but in the space it is not possible
to place the object. Let here the remaining size of the bag is 10 kgs,
whereas our object size is 30 kgs. So, we can’t place 30 kg of object
in 10kg of the bag. Then Xi can be calculated as.

𝑅𝑒𝑚𝑎𝑖𝑛𝑖𝑛𝑔 𝑆𝑖𝑧𝑒 𝑜𝑓 𝐾𝑛𝑎𝑝𝑠𝑎𝑐𝑘

𝑋𝑖 =
𝐴𝑐𝑡𝑢𝑎𝑙 𝑊𝑒𝑖𝑔ℎ𝑡 𝑜𝑓 𝑡ℎ𝑒 𝑂𝑏𝑗𝑒𝑐𝑡
The value of Xi may be 1 or 0 or some fraction value.
Objects 1 2 3 4 5 6 7
Profit 5 10 15 7 8 9 4
[P]
Weight 1 3 5 4 1 3 2
[W]

Weight = 15 ; n = 7
In the above problem we have 7 objects, with their Profits and
Weights. Total Weight, W = 15 kgs. Total objects n = 7.
We can assume that, we have one bag having weight 15 kgs or one
container having capacity 15 kgs.
Now, you have to select item such that you will get the maximum
profit. We cannot select all the items , because if you total the weight
of all the items then it would be greater than 15.
There are 3 approaches that we select the items where you will get the
maximum profit.
1. We can select the item first which is having maximum profit.
In the above problem, the maximum profit is 15, so that we can select
the item, then we will select 10 and so on.
2. We will select items having maximum weight, so that we can
select more and more items.
3. May be I can say that I will find out the ratio of profit by weight
and then I will select the items having maximum profit by
weight ratio as well.
In the above problem, the profit of item 3 is 15 you can say maximum
profit, but this profit is for 5 kgs, it is not for 1 kg. If you find out the
15
profit for 1kg, then profit would be = 3. So, for 1 kg it is 3.
5

So, the best approach is to find out the ratio profit by weight and then
select the item which is having the maximum profit by weight ratio.
Now, we will see all the three approaches and then we will compare
all the three approaches.
1. Select the item according to the maximum profit.
2. According to the minimum weight.
3. According to the maximum profit by weight ratio.
Approach 1: Select the items according to the maximum profit.
Total weight is 15 kgs.
Objects Profit [P] Weight [W] Remaining
Weight
3 15 5 15 – 5 = 10
2 10 3 10 – 3 = 7
6 9 3 7–3=4
5 8 1 4–1=3
4 3
7X =
21
= 3 3–3=0
4 4
5.25
Total Profit = 47.25
Now, check out which item is having maximum profit which is 15 in
this case. Then Object is 3; Profit = 15; Weight = 5; Remaining
Weight = 15 – 5 =10.
Next, maximum profit Object = 2; Profit = 10; Weight = 3;
Remaining Weight = 10 – 3 = 7.
Next, maximum profit Object = 6; Profit = 9; Weight = 3; Remaining
Weight = 7 – 3 = 4.

Next, maximum profit Object = 5; Profit = 8; Weight = 1; Remaining

Weight = 4 – 1 = 3.
Next, maximum profit Object = 4 ; Profit = 7; Weight = 4
In this, Remaining Weight = 3, so we cannot select the complete
object, we cannot pick the complete object.
As we have to use Fractional Knapsack problem, so, we have to select
fraction of the object.
For example, suppose we have 4 kg of apple then you will select 3 kg
of apple, the remaining capacity is only 3.
So, out of 4 the weight you will select is 3. The profit would be
according to this 3, because we have selected this 3 and this Profit = 7
for Weight = 4 kgs.
So, you have to find out profit for 3 kgs and that profit would be 7 X
3 21
= = 5.25. Now, Remaining Weight = 3 – 3 = 0. So, Remaining
4 4
Weight = 0 in the last.
Check out what is the total profit, here the total profit is 47.25
Approach 2 : Choose the item according to their Minimum Weight.
Total Weight is 15 kgs
 Objects Profit [P] Weight [W] Remaining
Weight
1 5 1 15 – 1 = 14
5 8 1 14 – 1 = 13
7 4 2 13 – 2 = 11
2 10 3 11 – 3 = 8
6 9 3 8–3=5
4 7 4 5–4=1
3 1
15 x = 3 1 1–1=0
5
Total Profit = 46

Min. Weight = 1; Object = 1; Profit = 5; Weight = 1; Remaining

Weight = 15 - 1 = 14
Min. Weight = 1; Object = 5; Profit = 8; Weight = 1; Remaining
Weight = 14 - 1 = 13
Min. Weight = 2; Object = 7; Profit = 4; Weight = 2; Remaining
Weight = 13 - 2 = 11
Min. Weight = 3; Object = 2; Profit = 10; Weight = 3; Remaining
Weight = 11 - 3 = 8
Min. Weight = 3; Object = 6; Profit = 9; Weight = 3; Remaining
Weight = 8 - 3 = 5
Min. Weight = 4; Object = 4; Profit = 7; Weight = 4; Remaining
Weight = 5 - 4 = 1
Min. Weight = 5; Object = 3; Now, Remaining Weight = 1 and the
Total Weight = 5, so, we cannot select the complete object.
1
You will select the fraction of this object is 3 that is , so, we will
5
1
select only 1 kg out of 5 kgs and this Profit is 15 x = 3; Remaining
5
Weight = 1 – 1 = 0.
Finally, Remaining Weight = 0 and we cannot select any more item.
Total Profit is 46.
Approach 3 : We will find out the ratio of Profit by Weight and then
we will select the maximum Profit by Weight ratio.
Objects 1 2 3 4 5 6 7
Profit 5 10 15 7 8 9 4
[P]
Weight 1 3 5 4 1 3 2
[W]
P/W 5 3.3 3 1.75 8 3 2

We have to find out the Profit divided by Weight ratio.

For 1kg you will find out the Profit.
Profit = 5; Weight = 1; Profit / Weight = 5 [As it is for 1 kg]
Profit = 10; Weight = 3; Profit / Weight = 3.3 [As it is for 3 kg for 1
kg then Profit is 10 / 3 = 3.33]
Profit = 15; Weight = 5; Profit / Weight = 15 / 5 = 3
Profit = 7; Weight = 4; Profit / Weight = 7 / 4 = 1.75
Profit = 8; Weight = 1; Profit / Weight = 8 / 1 = 8
Profit = 9; Weight = 3; Profit / Weight = 9 / 3 = 3
Profit = 4; Weight = 2; Profit / Weight = 4 / 2 = 2
Now, we will select the items according to the maximum Profit
divided by Weight ratio.
Objects Profit [P] Weight [W] Remaining
Weight
5 8 1 15 – 1 = 14
1 5 1 14 – 1 = 13
2 10 3 13 – 3 = 10
3 15 5 10 – 5 = 5
6 9 3 5–3=2
 7 4 2 2–2=0
Total Profit = 51

Max. Profit = 8; Object = 5; Profit = 8; Weight = 1;Remaining Weight

= 15 – 1 = 14
Max. Profit = 5; Object = 1; Profit = 5;Weight = 1; Remaining Weight
= 14 – 1 = 13

Max. Profit = 3.3; Object = 2; Profit = 10;Weight = 3; Remaining

Weight = 13 – 3 = 10
Max. Profit = 3; Object = 3; Profit = 15;Weight = 5; Remaining
Weight = 10 – 5 = 5
Max. Profit = 3; Object = 6; Profit = 9;Weight = 3; Remaining Weight
=5–3=2
Max. Profit = 2; Object = 7; Profit = 4;Weight = 2; Remaining Weight
=2–2=0
So, the Total Max. Profit = 51 and we have got this Max. Profit in 3 rd
approach. So, Profit divided by Weight ratio is the best one.
In, fractional Knapsack problem you will find out the Optimal result
when you apply Greedy Method.
But in 0 / 1 Knapsack problem it is better to use Dynamic
Programming.
Job Sequencing with Deadline
We are going to solve this using Greedy method. Assumes, we have n
jobs where each job is having a Profit [Pi] as well as each job has a
deadline [di].
P1 and d1 are the profits and deadlines of the first job.
P2 and d2 are the profits and deadlines of the second job and so on.
If we complete a job in a particular deadline, then we will earn the
corresponding profit. If we can’t complete the job by its deadline then
we can’t earn the profit.
So, we can earn profit if and only if we have completed the job by its
deadline. Here, in order to complete the job execution we have two
constraints .
a) We have only one machine in order to execute all the jobs.
Suppose if there are multiple machines, then multiple machines can
execute multiple jobs simultaneously. But here the constraint is we
have only one machine, so, with the help of this machine only we
need to execute all the jobs.
b) Here, the machine requires one unit of time in order to complete
the execution of the job.
So, in order to complete the first job execution, the machine
requires one unit of time. In order to complete the second job
execution, the machine requires one unit of time and so on.
Here, our objective is to complete all these jobs with the maximum
profit by its deadline. So, by its deadline we have to complete all
the jobs or some subset of the jobs with the maximum profit.
Algorithm or Procedure in order to implement this approach
Step 1 : Arrange all the jobs in descending or decreasing order based
on the profit values.
So, highest value will be arranged first, whereas the lowest value will
be written last.
Step 2 : Select the first job and execute it by assigning a slot, so, what
is a slot? Here, let the deadline is 3, then we have three slots such as
we can have slot 0 to 1, slot 1 to 2 and slot 2 to 3.
Let us assume that , here the process deadline is r, if a process
deadline is r then we have to execute the process by assigning the slot
[r – 1, r].
Let the process deadline is 3, then we have to assign slot [2, 3] <-- [r -
1, r]. First, we have to assign the slot [2, 3].
Suppose if this slot [2, 3] is already occupied then we have to arrange
the slot [r – 2, r – 1].
Since, r = 3, [r -2, r – 1]  [1, 2], next we have to assign the slot [1,
2]. Suppose this slot [1, 2] is also occupied then we have to arrange
the slot [r – 3, r – 2].
As, r = 3; [r – 3, r – 2] = [0, 1] . Likewise we have to arrange the slot.
In order to execute the job the machine requires only 1 slot. That
means, the machine requires only 1 unit of time.
Step 3 : Likewise, we have to execute all the processes one – by –
one.
With the above algorithm, our objective is to find out the Optimal
solution.
Example : Assume that we have 5 jobs
Profits  [P1, P2, P3, P4, P5] = [100, 19, 38, 27, 52]
Deadlines  [d1, d2, d3, d4, d5] = [2, 1, 2, 1, 3]
Now, we have to find the Optimal solution with the maximum profit,
we need to execute all these jobs or some subset of the jobs.
Solution :
We have to arrange all the jobs in descending order based on the
profit values.
In the above example, the higher profit is 100, so, the first process is
P1. Next, that is second highest is 52, the last process which is P5.
Next the third highest is 38, the process which is P3. Next fourth
highest is 27, the process which is P4. Next, last job profit is 19, the
process which is P2.
(P1, P5, P3, P4, P2) = (100, 52, 38, 27, 19)
According to that we have to write the deadlines also.
(d1, d2, d3, d4, d5) = (2, 3, 2, 1, 1)
Now, we have to assign all the job to the corresponding machine. So,
machine assigns a slot to them and executes one – by – one.
For that we have to draw the table. This table consists of 4 columns.
Assigned Slot Job Selected Action Profit

Initially, there is no slot allocated, so we have to write it as None.

None indicates that initially no process is allocated to any slot.
Next is job selection, in this case job J1 will be selected first. Action
means which slot should be allocated.
Check the maximum slot, in this case the maximum slot is 3. So, 3
means we will be having 3 slots.

0 1 2 3
0 to 1 means first slot.
1 to 2 means second slot.
2 to 3 means third slot.
In the example, the first job deadline is 2. So, here we can assign
either 0 to 1 slot or 1 to 2 slot. It is our choice.
Here the formula is [r-1, r]. r is nothing but the deadline.
[2 – 1, 2] = [1, 2]
So, we need to assign the slot [1, 2] . Now, slot [1, 2] is free, so we
place J1 in that slot.

Assigned Slot Job Selected Action Profit

None J1 [1, 2] 100

100 is the profit of the first job.

Already, we have assigned [1, 2] slot.
Next, job is 52, means the profit of J5, so the job selected is J5. So,
for J5 which we will have to allocate. Here J5 the deadline is 3. So,
the formula is [r – 1, r] = [3 – 1, 3] = [2, 3].
Here, slot [2, 3] is completely free, so, we can assign the slot [2, 3].
Suppose if slot [2, 3] is already occupied then we have to use the
formula [r – 2, r -1]. That means, [1, 2], likewise we have to check
one – by – one.
As slot [2, 3] is free, we have to assign job J5 and 52 is the profit of
second job.
Assigned Slot Job Selected Action Profit
None J1 [1, 2] 100
[1, 2] J5 [2, 3] 152

Now, assigned slots are [1, 2] as well as [2, 3] . So, two slots are
already allocated.
Next, highest profit is 38 which is the profit of the third job. So, the
next job is J3. Which slot should be allocated?
Here the formula is [r – 1, r] = [2 – 1, 2] = [1, 2].
So, we have to allocate [1, 2] but it is already occupied. Then we have
to use the formula [r – 2, r – 1] = [2 – 2, 2 – 1] = [0, 1] or we can
directly assign [0, 1] or [1, 2]. As slot [1, 2] is already occupied so we
have to assign the slot [0, 1] to the corresponding job. So, J3 should
be allocated to [0, 1] slot.
Assigned Slot Job Selected Action Profit
None J1 [1, 2] 100
[1, 2] J5 [2, 3] 152
[1, 2], [2, 3] J3 [0, 1] 190

Next, job profit is 27, which is the profit of the fourth job. So, the
deadline of J4 is 1. 1 means we have to assign [0, 1] but slot [0, 1] is
completely occupied. Here, the ‘Action’ is ‘Reject’, as we can’t place
the corresponding job in the corresponding slot. Before slot [0, 1] we
don’t have any other slot. Profit is 190 only.
Assigned Slot Job Selected Action Profit
None J1 [1, 2] 100
[1, 2] J5 [2, 3] 152
[1, 2], [2, 3] J3 [0, 1] 190
[0, 1], [1, 2], J4 Reject 190
[2, 3]

The last job is J2 and the profit is 19. So, here the assigned slots are
[0, 1], [1, 2], [2, 3]. Deadline of job J2 is 1, so, 1 means we can
allocate to [0, 1] slot, but [0, 1] slot is already allocated for J3.
Assigned Slot Job Selected Action Profit
None J1 [1, 2] 100
[1, 2] J5 [2, 3] 152
[1, 2], [2, 3] J3 [0, 1] 190
[0, 1], [1, 2], J4 Reject 190
[2, 3]
[0, 1], [1, 2], J2 Reject 190
[2, 3]

So, ‘Reject’ as it is not possible to place that in a particular slot. Profit

will not be changed. Same profit 190 only, because we can’t execute
J4 as well as J2, so Profit won’t changes.
Here we can say that the job sequence is [J1, J5, J3]. That means the
machine executes the jobs in this order [J1, J5, J3] with a Profit of
190.
Algorithm for Job Sequencing with Deadlines
Algorithm GreedyJob(d, j, n)
// J is a set of jobs that can be completed by their deadlines
{
j = {1}
for i = 2 to n do
{
if (all jobs in j U {i} can be completed by their deadlines) then
j = j U {i}
}
}
Optimal Storage on Tapes
There are n programs that are to be stored on a computer tape. So, let
us assume that we have n programs and we need to store all those
programs on a computer tape. Let the length of each program is
denoted by li .
So, length of the first program will become l1. Length of second
program will become l2 and so on.
Tape is nothing but Magnetic Tape. Magnetic Tape provides
sequential access that means we can retrieve the programs, we can
access the programs one – by – one. We can access the first program
directly, but, if you want to access the second program, before the
second program we must access first program. If you want to retrieve
fifth program then we must retrieve all the programs before the fifth
program, so, before fifth program we must retrieve first program,
second program, third program, fourth program and then fifth
program. After retrieving each record the corresponding pointer will
be placed at the first position only, so, if you want to access the last
program then before that we need to access all the programs from first
program to last but one program, that is the property of the tape or
magnetic tape.
Our main aim is we have to store all the programs on a Computer tape
with minimum retrieval time.
Example :
Consider n = 3, that means the number of programs are 3 and lengths
are (l1, l2, l3) = (5, 10, 3). Find the Optimal Storage order. That
means in which order if you store the program then the retrieval time
is minimum. Number of tapes is 1.
Sol :
For these 3 programs the possible solutions or the orderings are n!.
In this case it is going to be 3! that is 6 orderings . The following are
the ordering in tabular format.
 Ordering Number Program Order
1 1 2 3
2 1 3 2
3 2 1 3
4 2 3 1
5 3 1 2
6 3 2 1

Program order 1 2 3 means first program will be accessed first

followed by second program followed by third program. In the similar
manner the remaining programs will be accessed.
Now, we will see how much time is required for each ordering.
Ordering Program Order d(I)
Number
1 1 2 3 5 + (5 + 10) (5 + 10 + 3) = 38
2 1 3 2 5 + (5 + 3) (5 + 3 + 10) = 31
3 2 1 3 10 + (10 + 5) + (10 + 5 + 3) = 43
4 2 3 1 10 + (10 + 3) + (10 + 3 + 5) = 41
5 3 1 2 3 + (3 + 5) (3 + 5 + 10) = 29
6 3 2 1 3 + (3 + 10) (3 + 10 + 5) = 34

Consider if the programs are stored in the order of 1 2 3 the time

required to read the first program will be the length of the first
program which is 5, the time required to retrieve the second program
is, length of the first program and length of the second program which
is (5 + 10). The time required to retrieve the third program is 1 + 2 + 3
or (5 + 10 + 3).
(1 + 2 + 3) is nothing but length of the first program, length of the
second program and length of the third program. So, total time
required is 38.
 If we will go for the order 2 3 1, the time required for second program
is 10, so, time required for this third program will be (10 + 3) and the
time required for the first program will be (10 + 3 + 5). So, total time
is 41.
In this manner we have calculated the times for every combination.
Now, we have to calculate the minimum time taken to retrieve the
programs is as follows.

Ordering Program d(I) Mean Retrieval

Number Order Time[MRT]
1 1 2 3 5 + (5 + 10) (5 + 10 + 38 / 3 = 12.66
3) = 38
2 1 3 2 5 + (5 + 3) (5 + 3 31 / 3 = 10.33
+ 10) = 31
3 2 1 3 10 + (10 + 5) + (10 + 43 / 3 = 14.33
5 + 3) = 43
4 2 3 1 10 + (10 + 3) + (10 + 41 / 3 = 13.33
3 + 5) = 41
5 3 1 2 3 + (3 + 5) (3 + 5 + 29 / 3 = 9.66
10) = 29
6 3 2 1 3 + (3 + 10) (3 + 10 + 34 / 3 = 11.33
5) = 34

As we have calculated the Mean Retrieval Time [MRT], now, we

have to find the Optimal solution which is 9.66.
If we will store the program in the ordering of 3 1 2 we are getting
this d(I) = 29 and MRT = 9.66.
Approach to Obtain Optimal Solution
Find all the permutations of the programs and find Optimal solution
[Minimum MRT].
Drawback
For the large value of n, time will be high to find all possible
permutations.
What can be the other approach which will save you time? Greedy
approach to obtain the solution.

Greedy Approach to obtain Optimal Solution

If you have observed which Optimal which ordering you have given
the Optimal solution. It is nothing but, store the programs in
increasing order of their lengths using any sorted order.
Time required for sorting is nlogn.
That is in the above example increasing order of the lengths are 3, 5,
10 and then we have seen that this ordering 3 1 2 and the time
required is always less.
The approach is that arrange at an increasing order of the length and
then find out its Mean Retrieval Time[MRT].
Example 2
Let n = 10, that means totally there are 10 programs and lengths are
(L1, L2, L3, L4, L5, L6, L7, L8, L9, L10) = (10, 20, 45, 70, 1, 3, 7,
54, 23, 67)
L1 means length of the first program, L2 means length of the second
program, likewise L10 means length of the tenth program.
Here, first we have to arrange all the elements in ascending order of
length of the program.
Ascending Order : 1, 3, 7, 10, 20, 23, 45, 54, 67, 70
Let us assume that we have 3 tapes i.e.,
Tape 0 : First Tape
Tape 1: Second Tape
Tape 2 : Third Tape
The first three elements are 1, 3, 7. Here, we are assigning 1 to Tape
0, 3 to Tape 1 and 7 to Tape 2.
Depending upon the number of tapes we have to store the lengths in
the tapes.
Next, 10 is stored on Tape 0; 20 is assigned to Tape 1, 23 is assigned
to Tape 2. Next, 45, is stored in Tape 0, 54 is stored in Tape 1, 67 is
stored in Tape 2, next , 70 is stored in Tape 0.
The following are the storage of lengths of the programs on Tapes.
Tape 0 1 10 45 70 1 + (1 + 10) + (1 + 10 + 45) + (1 + 10 + 45 + 70) =
194
Tape 1 3 20 54 3 + (3 + 20) + (3 + 20 + 54) = 103
Tape 2 7 23 67 7 + (7 + 23) + (7 + 23 + 67) = 134

We can access this 1 directly, that is we can retrieve the first record
length directly. We can access the second program only after
accessing the first program. That is 1 + (1 +10). Next, we can retrieve
the third program only after retrieving the first two programs. That is
1 + (1 + 10) + (1 + 10 + 45). Next, we can retrieve the last program,
only after retrieving the first three programs.
That is, 1 + (1 + 10) + (1 + 10 + 45) + (1 + 10 + 45 + 70) = 194.
Total retrieval time is calculated by adding the Retrieval time of Tape
0, Retrieval time of Tape 1, Retrieval time of Tape 2.
Total Retrieval Time = 194 + 103 + 134 = 431
Means Retrieval Time, means Average Retrieval Time is 431 / 3 =
143.67
Minimum Cost Spanning Trees
Spanning Tree : A Spanning Tree is a sub – graph of a given graph.
A Spanning Tree must satisfy these 3 properties.
1. It should contain all the vertices of the graph.
Suppose if a graph contains 5 vertices, then the Spanning Tree
should contain 5 vertices. If the graph contains 3 vertices, then the
Spanning Tree should contain 3 vertices.
2. If the graph contains n vertices then the Spanning Tree should
contain n – 1 edges.
3. Spanning Tree should not contain any cycle.
Graph can be represented G(V, E), that means this Graph G contains
n number of vertices and n number of edges.
Example: The following is a graph, which contains 5 vertices and 4
edges.

2 5

3 4
G’ is the Spanning Tree for the above graph, that Spanning Tree
would contain G’(V’, E’).
V’  Number of Vertices
E’  Number of Edges
in that Spanning Tree.
What is the relation between V’ and V as well as E’ and E?
Mathematically, we can write V’ = V. That means, in a Spanning Tree
of a given graph, all the vertices in that Spanning Tree would be same
as in that graph.
V’ would be same as V. There is a difference in number of edges.
Number of edges E’ in a Spanning Tree would be subset of the
number of edges in this original graph. We can write E’ ⸦ E or
E = |V| - 1
Number of edges in a Spanning Tree would be number of Vertices in
a graph minus 1 always.
Spanning Tree would contain same number of vertices of the graph.
Number of edges in a Spanning Tree would be |V| - 1 [Number of
Vertices in the graph minus 1].
Suppose this is a graph

2 5

3 4
You are supposed to construct or draw a Spanning Tree for the graph.
A graph can have more than one Spanning Trees.
Spanning Tree contains same number of vertices as graph. It looks
like this.
Many Spanning Trees can be drawn from the above graph.

2 5

3 4

2 5

3 4
 1

2 5

3 4

2 5

3 4

Minimum Spanning Tree

1
1 3

2 5

4 2

3 4
5
Suppose this graph is having some edge weights. Now, out of the
above Spanning Trees, the Spanning Tree whose total of these edge
weights is minimum. That would be the Minimum Spanning Tree
[MST].
Let us suppose, we have constructed the following Spanning Tree.

1
1

2 5

4 12 2

3 4
5

What is the cost of this Spanning Tree? 1 + 4 + 5 + 2 = 12

Total edge weight of this Spanning Tree is 12.

1
3

2 5

4 14 2

3 4
 5
Total edge weight of this Spanning Tree is 3 + 2 + 5 + 4 = 14.

1
1 3

2 5

11 2

3 4
5
Total edge weight of the Spanning Tree is 1 + 3 + 2 + 5 = 11.

1
1 3

2 5

4 10 2

3 4

Total edge weight of the Spanning Tree is 1 + 3 + 4 + 2 = 10.

Tree is the Minimum Spanning Tree [MST] of the above graph.
Spanning Tree should not contain any cycle.
This Spanning Tree should not be disconnected. Suppose let us say,
for the following Spanning Tree.

1
1

2 5
 4 2

3 4

Suppose we remove the edge from Vertex 3 to Vertex 4, this is not a

Spanning Tree, as Spanning Tree cannot be disconnected.
If you give one more edge for the Spanning Tree like this.

1
1 3

2 5

4 2

3 4
5
This is also not Spanning Tree, as this Spanning Tree contains a
cycle.
So, Spanning Tree should not contain a cycle and the Spanning Tree
should not be disconnected.
Properties of Spanning Tree
Removing an edge from the Spanning Tree will make it disconnected.
Adding one edge to the Spanning Tree will create a loop.
If each edge has distinct weight then there will be only one and
unique MST.
 – 2
A complete undirected graph can have nn number of Spanning
Trees.
Every connected and undirected graph has at least one Spanning Tree.
Disconnected graph does not have Spanning Tree.
From a complete graph by removing max(e – n + 1) edges we can
construct a Spanning Tree.
Example :

We have removed only one edge from a Spanning Tree.

Number of edges, e, for the above graph is 3.
Number of vertices, n, for the above graph is 3.
max(e – n + 1) = max(3 – 3 + 1) = 1.
So, we can remove a maximum of one edge.
If we remove two edges from a Spanning Tree.

This is not a Spanning Tree because Spanning Tree cannot be

disconnected.
A complete graph having 4 vertices.

A complete graph is nothing but every vertex is connected with

another vertex.
Draw the Spanning Tree, for the above complete graph.

nn-2 = 44-2 = 16 possible Spanning Trees

(6 – 4 + 1) = 3
Maximum you can remove 3 edges from this complete graph.
Prim’s Algorithm : This algorithm is used to find out Minimum
Spanning Tree.
8
7 B 6 D 5
A 3 4 2 F 1
8 2
C E
3
In Prim’s algorithm, remove all the loops and parallel edges.
Loops means the incoming and outgoing to the same vertex. In the
above graph we only 1 loop, so remove that loop.
8
7 B 6 D 5
A 3 4 2 F

8 2
C E
3
No need to check its cost, although it is having edge cost or weight 1
that is minimum, but that doesn’t matter. You have to remove that
loop.
Next, is remove parallel edges. In the above graph, from vertex B to
vertex D we have two edges which are parallel. So, these type of
edges are known as parallel edges.
How many ever parallel edges we have in this graph, we have to
remove those edges. In this graph, we have only one parallel edge.
Which edge has to be removed? Check out the edge weight one is 6
and another is 8.
You’re supposed to keep that edge which is having minimum weight
or cost. Since, 6 is minimum we will retain it as it is and we will
remove the edge weight 8.

7 B 6 D 5
A 3 4 2 F

8 2
C E
3
All the loops and parallel edges are removed.
Next, choose any arbitrary vertex as a root node. Suppose, if you
choose A as the root node, check out all the outgoing edges from
vertex A or incident edges from vertex A.
Two edges are there, one is with edge weight 7 and another is with
edge weight 8. You have to choose one edge that is minimum weight.
So, out of edge weights 7 and 8, we will choose this edge weight 7,
and this will go up to vertex B.

B
7
A
We have reached to vertex B, you have to choose all the outgoing
edges or you can say the incident edges from vertex B as well as from
vertex A.
It is not like that , since we have reached to vertex B we will be
checking edges only from vertex B.
There are 2 outgoing edges from vertex B and the edge weight is 3
and 6. But, still we are having one more edge with edge weight 8, we
have to compare this edge weight 8 also.
Out of 8, 3, 6 which one is having minimum edge weight? 3 is the
minimum edge weight, so we will choose this 3 which is going from
vertex B to vertex C.

B
7
A 3
C

We have 3 vertices in this minimum Spanning Tree A, B and C. Now,

check all the incident or outgoing edges from vertex B, vertex C, and
vertex A. We can choose that one which is having minimum weight.
From vertex C we have to vertex E with edge weight 3 and from
vertex C to vertex D with edge weight 4. But still there is one more
edge from vertex B to vertex D that is 6, and we are also having the
edge from vertex A to vertex C with edge weight 8.
Out of 8, 6, 3, 4 which edge is minimum one? 3 is the minimum edge
weight from vertex C to vertex E.

B
7
A
 3
C E
3

Check out all the outgoing edges from vertex E , vertex C, vertex B,
vertex A. From vertex E, what are the incident edges? One is from
vertex E to vertex F with edge weight 2, vertex E to vertex D with
edge weight 2, from vertex C, we are having one edge weight 4.
From vertex B, we are having one incident edge with edge weight 6.
From vertex A we are having one incident edge with edge weight 8.
Out of edge weights 8, 6, 2, 2, 4 which is having minimum weight ?
Minimum weight is 2 and 2, so we can choose any one of the edge
weight. Suppose, you have chosen this vertex F, then minimum
Spanning Tree would be

B
7 F

A 3 2
C E
3
We have one another vertex, that is vertex F.
Still one vertex is left, that is vertex D in the graph. Now, choose the
vertex with minimum edge weight ? From vertex F, we have only one
outgoing edge left that is edge weight 5.
It’s not like that we have reached vertex F, just choose it and draw the
minimum Spanning Tree.
From vertex E, incident edges are 2, 3, 2. Edge weight 2 has been
chosen, edge weight 3 has been chosen, so one edge weight 2 has
been left.
That is, from vertex C we have this edge weight 4, from vertex B one
is left that is edge weight 6, from vertex A one edge weight is 8.
out of 8, 6, 4, 2, 5 which edge is having minimum edge weight? That
is, 2 is the minimum edge weight from vertex E to vertex D.

B D
7 2 F

A 3 2
C E
3
This is the minimum Spanning Tree [MST] for the above given graph,
using Prim’s algorithm.
If you want to verify, minimum Spanning Tree [MST] or Spanning
Tree of any graph would contain the same number of vertices as that
graph contains.
There are 6 vertices in the graph and Spanning Tree also contains 6
vertices. The edges would be the subset of that edges that the graph
contains.
G(V, E) and G(V’, E’)
V = V’ and E’ ⸦ E
E’ should contain |V| - 1, where V means number of vertices in the
graph, so, E’ = |V| - 1 = 6 – 1 = 5.
So, there are 5 edges in the Spanning Tree that was constructed.
One more condition of Minimum Spanning Tree [MST] that total
edge weight of these edges should be minimum.
A graph can have more than one Spanning Tree.
Algorithm
Algorithm Prim(E, cost, n, t)
// E is the set of edges in G. cost[1:n, 1:n] is the cost adjacency matrix
// of an n vertex such that cost[i, j] is either a positive number or
//infinity if no edge(i, j) exists
//A minimum Spanning Tree is computed and stored as a set of edges
// in the array t[1 : n -1, 1:2], (t[i, 1], t[i, 2]) is an edge in the minimum
// cost spanning tree. The find cost is returned.
{
Let (k, l) be an edge of minimum cost in E;
mincost := cost[k, l];
t[l, 1] := k;
t[1, 2] := l;
for i := 1 to n do // initialize near
if (cost[i, l] < cost [i, k]) then near[i] := l;
else near[i] := k;
near[k] := near[l] := 0;
for i := 2 to n -1 do
{
//find n – 2 additional edges for t
 Let j be an index such that near[j] not equal to 0 and
cost[j, near[j]] is minimum;
t[i, 1] : = j;
t[i, 2] : = near[j];
mincost = mincost + cost[j, near[j]];
near[j] := 0;
for k := 1 to n do // update near[]
if (near[k] != 0) and (cost[k, near[k]] > cost[k, j])) then
near[k] := j;
}
return mincost;
}
Kruskal’s Algorithm
The following is the graph:
10
7 A 5 B 4
F 3 6 2 E

8 2
C D
3
First step is to remove all the loops and parallel edges from the above
graph. Parallel edges means from one vertex to another vertex, two
edges are there in parallel.
In the above graph, from vertex A to vertex B one edge is having edge
weight 5 and another edge is having edge weight 10. Since, we have 2
edges, these are known as parallel edges. We’re supposed to remove
any of these edges.
Loops means an edge that is created to the same vertex, that means
both source vertex and destination vertex are same. For parallel edge,
you’ll keep that edge having minimum weight.
From edge weights 5 and 10, which edge weight is minimum?5 is the
minimum edge weight. So, you’ll remove the edge with edge weight
10.

7 A 5 B 4
F 3 6 2 E

8 2
C D
3
In Kruskal’s algorithm, you’ll arrange all the edges according to their
edge weights, all are arranged in increasing order of their edge
weights.
Out of all edge weights we are having 2 and 2 as the minimum edge
weight.
BD = 2; DE = 2 . In any order you can write, either DE or BD.
Next, minimum edge weight is 3 and for edge weight 3 is also
containing 2 edges AC = 3; CD = 3.
Next, BE = 4; AB = 5; BC = 6; AF = 7; FC = 8; BD = 2; DE = 2; AC
= 3; CD = 3; BE = 4; AB = 5; BC = 6; AF = 7; FC = 8
In the next step, you will choose minimum edge weight from the
above set.

B
2

B
2 E

D 2

A B

3 2 E

C D 2

Next BE = 4, where we cannot connect this edge from vertex B to

vertex E, as you will not connect this edge from vertex B to vertex E
as this will form a cycle.
The property of a Minimum Spanning Tree [MST] is that it does not
contain any cycle. So, you cannot connect an edge which forms a
cycle in Minimum Spanning Tree [MST].
 Next, AB, where we cannot connect this edge as this will form a
cycle. BC also cannot be connected, because it contains a cycle.

A B

3 2 E

C D 2
3

7 B
A

3 2 E
F
C D 2
3
Next is FC, we cannot connect FC as it will form a cycle.
If the given graph is having n number of vertices then MST must
contain same number of vertices.
Suppose, there are n number of vertices, then Minimum Spanning
Tree [MST] will contain n vertices and (n – 1) edges.
Minimum Spanning Tree would contain 6 vertices, but you will be
having 6 – 1 = 5 edges.
In MST, the total cost of this tree would be minimum.
Early form of MST algorithm due to Kruskal
t := 0;
while ((t has less than n – 1 edges) and (E != 0)) do
{
choose an edge (v, w) from E of lowest cost;
Delete (v, w) from E;
If (v, w) does not create a cycle in t then add (v, w) to t;
else
discard(v, w);
}
Kruskal’s Algorithm
Algorithm Kruskal(E, cost, n, t)
// E is the set of edges in G. G has n vertices
//cost[u, v] is the cost of edge (u, v)
//t is the set of edges in MST. The final cost is returned.
{
Construct a heap out of the edge costs using heapify;
for i := 1 to n do
parent [i] := -1;
//Each vertex is in a different set
i := 0; mincost := 0.0;
 while ((i<n -1) and (heap not empty)) do
{
Delete a minimum cost edge (u, v) from the heap and heapify
using Adjust;

j := find(u); k := find(v);
if (j != k) then
{
i := i + 1;
t[i, 1] := u; t[i, 2] := v;
mincost := mincost + cost[u, v];
union(j, k);
}
}
if (i != (n – 1)) then write (“No Spanning Tree”);
else
return mincost;
}
Dijkstra’s Algorithm
Single Source Shortest Path Problem

8 7 9
1 2 3

4 11 2 4 14
7
0
8

4
 8 7 6 10

5 6

1 2

In this algorithm one source is given we’re supposed to find out the
shortest path may be and you’re supposed consider 0 as a source
vertex and from 0 we are supposed to find out the shortest path to all
the vertices.
May be you’re supposed to vertex 2 as the source vertex and we are
supposed to find out the shortest path from 2 to 1, 2 to 4, 2 to 8, 2 to
5, 2 to 6 and so on to all other vertices.
From one source we are supposed to find out the shortest path to all
other vertices.
Working Principle of Dijkstra’s Algorithm
8 7 9
1 2 3

4 11 2 4 14
7
0
8
8 7 6 10

4 5 6

1 2

Suppose the graph is given above and we’re supposed to find out the
shortest path and source vertex that is given to is 0.
Or
May be we can consider 5 as a source vertex and start the algorithm.
But for now we’re considering vertex 0 as source.
Distance of source vertex to source vertex is 0. The distance of all
other vertices would be infinity and is represented as I that is we don’t
know what is the shortest path .

I 8 I 7 I 9
1 2 3

4 11 2 4 14 I
7
0 0 8 I

8 7 6 10

4 5 6

I 1 I 2 I

I  Infinity

From 0 to how many vertices are directly connected. We can find out
the distance from vertex 0 to vertex 1 and from vertex 0 to vertex 4.
How the distance is calculated?
Suppose we are considering from 0 to 1, now we need to calculate
this distance. We will consider vertex 0 as u and vertex 1 as v.
As we need to find out the distance from vertex 0 to vertex 1 . At the
beginning we don’t know the distance of v, hence d(v) is infinity (I).
We will update the infinity value and replace it with the newly
calculated value.
d(u) + c(u, v) < d(v)
0+4<I=4<I
Suppose we are considering from 0 to 4, now we need to calculate
this distance. We will consider vertex 0 as u and vertex 4 as v.
0+8<I=8<I
If (d(u) + c(u, v) < d(v))
d(v) = d(u) + c(u, v)

4 8 12 7 I 9
1 2 3

4 11 2 4 14 I
7
0 0 8 I

8 7 6 10

4 5 6

8 1 I 2 I

The source vertex is 0 is known as selected vertex or visited vertex.

Now as from vertex 0 we have already find out the shortest path from
0 to 1 and from 0 to 4.
Just leave the selected vertex or visited vertex.
Now check out all the remaining distances.
Select the shortest distance out of the newly calculated distances from
vertex 0.
Since 4 is the shortest distance select vertex 1 as the source vertex.
From vertex 1 we can update the distance from vertex 1 to 2 and we
can update the distance from vertex 1 to vertex 4 and we can update
vertex 1 to vertex 0 but we will not update the distance from vertex 1
to vertex 0 because vertex 0 is already a selected vertex.
So once a vertex is already a visited vertex or selected vertex we will
not update the distance of that vertex.
So from vertex 1, we will update the distance from vertex 1 to 4 and
vertex 1 to 2.
Now find out the distance from vertex 1 to 2.
d(u) + c(u,v) < d(v)
4 + 8 < I = 12 < I
Now find out the distance from vertex 1 to 4.
d(u) + c(u,v) < d(v)
4 + 11 < 8 = 15 < 8 (False)
Now, vertex 0 and 1 are already selected vertices or visited vertices.
Now out of the remaining nodes which node is having the shortest
distance. 8 is the shortest distance ie vertex 4
From vertex 4, we can update the distance of vertex 4 to 5 , vertex 4
to 8 But we cannot update the distances of vertex 4 to 1 & vertex 4 to
0.
Now find out the distance from vertex 4 to 5
8 + 1 < I = 9 < I (True)
Now find out the distance from vertex 4 to 8
8 + 7 < I = 15 < I (True)

4 8 12 7 I 9
1 2 3

8
 4 11 2 4 14 I
7
0 0 15

8 7 6 10

5 6

8 1 9 2 I

Vertices 0, 1, 4 are selected vertices or visited vertices, so you’ve to

leave the nodes 0, 1, 4.
Out of these remaining vertices 2, 8, 5, 3, 6, 7 which vertex is having
the shortest distance. 9 is the shortest distance, so, we will select this
vertex 5.
From vertex 5, we can update vertex 5 to vertex 6, vertex 5 to vertex
8. We will not update vertex 5 to vertex 4 because vertex 4 is already
selected.
Find out the distance from vertex 5 to vertex 6?
vertex 5  u; vertex 6  v; 9 + 2 < I ; 11 < I.

4 8 12 7 I 9
1 2 3

4 11 2 4 14 I
7
0 0 8 15

8 7 6 10

4 5 6

8 1 9 2 11

Find out the distance from vertex 5 to vertex 8?

9 + 6 < 15 ; 15 < 15 . No, need to change.
Leave the selected nodes or vertices 0, 1, 4, 5 .
Out of these unvisited vertices 8, 2, 6, 3, 7 which one is having
minimum distance?
11 is the shortest distance, so, select vertex 6.
From vertex 6, we can update distance of those nodes or vertices
which are directly connected.
Vertex 6 to vertex 7, 3, 2. From vertex 6 to vertex 7.
11 + 10 < I; 21 < I; Update the distance with 21.

4 8 12 7 I 9
1 2 3

4 11 2 4 14 21
7
0 0 8 15

8 7 6 10

4 5 6

8 1 9 2 11

From vertex 6 to vertex 3; 11 + 14 < I; 25 < I.

4 8 12 7 25 9
1 2 3

4 11 2 4 14 21
7
0 0 8 15

8 7 6 10

4 5 6

8 1 9 2 11

From, vertex 6 to vertex 2; 11 + 4 < 12 ; 15 < 12.

We will not update this distance. We will leave it as it is.
Out of these unvisited vertices 2, 8, 3, 7 which one is having
minimum distance?
12 is the minimum distance, so, select vertex 2.
From vertex 2 we can update this vertices 3 and 8. We cannot update
vertex 6 and vertex 1 because vertex 6 and vertex 1 is already
selected.
Find out the distance from vertex 2 to vertex 8? 12 + 2 < 15; 14 < 15
We will update this distance 15 with 14.

4 8 12 7 25 9
1 2 3

4 11 2 4 14 21
7
0 0 8 14

8 7 6 10

4 5 6

8 1 9 2 11

Find out the distance from vertex 2 to vertex 3? 12 + 7 < 25 ; 19 < 25.
We will update 19 with 25.

4 8 12 7 19 9
1 2 3

4 11 2 4 14 21
7
0 0 8 14

8 7 6 10

4 5 6
 8 1 9 2 11

Out of these 3 vertices 8, 3, 7 which is having shortest distance.

Vertex 8 is having 14, vertex 3 is having 19, vertex 7 is having 21.
We will select vertex 8, as this is having shortest distance. From
vertex 8, how many nodes are directly connected to vertices 5, 4, 2.
But we will not update these vertices 5, 4, 2 as those are selected
vertices.
Out of vertices 3 and 7. Vertex 3 is selected as it is having the
minimum shortest distance factor. We can update the distance from
vertex 3 to vertex 7.
19 + 9 < 21; 28 < 21 [False]. So, we will not update the distance.
Only one vertex 7, that will be selected and the distance is 21.
What is the shortest distance from vertex 0 to vertex 3?
19 is the shortest distance.
What is the shortest distance from vertex 0 to vertex 8?
14 is the shortest distance.
What is the shortest distance from vertex 0 to vertex 6?
11 is the shortest distance.
What is the shortest distance from vertex 0 to vertex 7?
21 is the shortest distance.
What is the shortest distance from vertex 0 to vertex 5?
9 is the shortest distance.
What is the shortest distance from vertex 0 to vertex 4?
8 is the shortest distance.
What is the shortest distance from vertex 0 to vertex 1?
4 is the shortest distance.
What is the shortest distance from vertex 0 to vertex 2?
12 is the shortest distance.

Example of a Directed Graph using Dijkstra Algorithm

1
B D
10
A
2 3 9 6
5 C E

Let us see the above graph, which one is directed and weighted. We
are supposed to find out the shortest distance from the source vertex
to all other vertices.
Let us suppose A is the source vertex. In the case of a directed graph,
we will update in table.
In tabular format, the source vertex must be written at the beginning
only. Here, we have considered source vertex as A.
A B C D E
A 0 I I I I
10
Distance of source vertex to source vertex is 0. For all the remaining
vertices it would be infinity [I]. Out of the distances that are listed in
tabular format which one is having the minimum distance factor. 0 is
the minimum distance factor.
So, we will select this 0 and the vertex is A.
From, vertex A to how many vertices you can find out the distance.
That is, from vertex A to vertex B and vertex A to vertex C. There is
no edge from vertex A to vertex E. The edge that is shown in the
graph will be from vertex E to vertex A. So, we cannot update from
vertex A to vertex E. We can update only from vertex A to vertex B
and vertex A to vertex C.
Find out distance from vertex A to vertex B?
Distance of A is 0.
Formula is :
If (d(u) + cost(u, v) < d(v)) then
d(v) = d(u) + cost(u, v)
0 + 10 < I ; 10 < I . We will update the table at vertex B, the distance
is 10.
0 + 5 < I; 5 < I, we, will update the table at vertex C, the distance is 5.
A B C D E
A 0 I I I I
C 10 5 I I
Since, vertex A is already selected, we will not update this in the
table.
Out of the vertices B, C, D, E which one is having the shortest
distance factor?
The minimum distance factor is 5 which is at vertex C, so, vertex C is
selected.
From vertex C we can update distance of vertex C to vertex B and
vertex C to vertex D and vertex C to vertex E.
Now, find out the distance from vertex C to vertex B?
5 + 3 < 10 ; 8 < 10; we will update the distance of vertex B which is
8.
Next, from vertex C to vertex D. 5 + 9 < I ; 14 < I. We can update the
distance of D that is 14.
Next, from vertex C to vertex E. 5 + 2 < I; 7 < I . We can update the
distance of E, that is 7.
We will not write this vertex C value 5 again, because we have
already selected vertex C.

A B C D E
A 0 I I I I
C 10 5 I I
E 8 14 7

Out of these, 3 distances which one is having the minimum distance

factor? That is , 7 vertex E, so, Vertex E would be selected.
From vertex E, we can update the distance of vertex D and vertex A.
we will not update the distance of vertex A, because vertex A is
already selected / visited / marked.
We can update the distance from vertex E to vertex D. Now, find out
the distance from vertex E to vertex D?
7 + 6 < 14; 13 < 14. So, we will update the distance of vertex D with
13.
We cannot update the vertex from E to B, as there is no edge. Then in
the table we will write as it is.
A B C D E
A 0 I I I I
C 10 5 I I
E 8 14 7
B 8 13

Now, we have only two vertices which are unvisited. Out of these two
vertices B and D which one is having minimum distance? We will
select this 8 which is the distance factor of vertex B. Vertex B would
be selected.
Then, from vertex B we can update only the distance from vertex B to
vertex D. 8 + 1 < 13; 9 < 13, then we will update the distance at
vertex D.
A B C D E
A 0 I I I I
C 10 5 I I
E 8 14 7
B 8 13
D 9

What is the shortest distance from A to D?

9 is the shortest distance.
What is the shortest distance from A to E?
7 is the shortest distance.
What is the shortest distance from A to C?
5 is the shortest distance.
What is the shortest distance from A to B?
8 is the shortest distance.
If you want to find out the path, we’re supposed to find out the
shortest distance from vertex A to vertex D plus the path, may be
there would not be the direct edge from vertex A to vertex D. Shortest
distance is 9.
Path : A  C  B  D ; 5 + 3 + 1 = 9.