Data Structure

Department of Computer Science & Engineering
UIT-RGPV
Topic: Introduction to Data Structures

[Part-1]
Course: Data Structures (CS303)
By:
Mr. Praveen Yadav
Assistant Professor
UIT-RGPV, Bhopal
Outline
➢Introduction
➢Basic Terminology
➢Types of Data Structures
➢Advantages of Data Structures
Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 2

Introduction
• Definition: Data Structure can be defined as the
group of data elements which provides an efficient
way of storing and organizing data in the computer so
that it can be used efficiently.
• Data may be organized in many different ways.
• Data Structure refers to logical or mathematical
model of a particular organization of data.

Introduction Cont…
• The choice of a particular data model depends on two
considerations:
1. It must be rich enough in structure to mirror the
actual relationships of the data in the real world.
2. The structure should be simple enough that one can
effectively process the data when necessary.

Examples of Data Structures
• Some examples of Data Structures are:
✓ Arrays
✓ Linked List
✓ Stack
✓ Queue
✓ Trees
✓ Graphs
• Data Structures are widely used in almost every aspect
of Computer Science i.e. Operating System, Compiler
Design, Artificial intelligence and many more.

Basic Terminology
Following terminology is used as far as data structures are
concerned:
• Data: Data can be defined as an elementary value or the
collection of values, for example, student's name and its id are
the data about the student.
• Group Items: Data items which have subordinate data items
are called Group item, for example, name of a student can
have first name and the last name.
• Record: Record can be defined as the collection of various
data items, for example, if we talk about the student entity,
then its name, address, course and marks can be grouped
together to form the record for the student.

Basic Terminology cont…
• File: A File is a collection of various records of one
type of entity.
• Attribute and Entity: An entity represents the class
of certain objects. It contains various attributes. Each
attribute represents the particular property of that
entity.
• Field: Field is a single elementary unit of information
representing the attribute of an entity.

Types of Data Structures

Advantages of Data Structures
✓ Efficiency
✓ Reusability
✓ Abstraction
I. Efficiency: Efficiency of a program depends upon the choice
of data structures.
For example: Suppose, we have some data and we need to
perform the search for a particular record.
• In that case, if we organize our data in an array, we will have
to search sequentially element by element. Hence, using array
may not be very efficient here.
• There are better data structures which can make the search
process efficient like ordered array, binary search tree or hash
tables.
Advantages of Data Structures cont…
II. Reusability: Data structures are reusable, i.e. once we
have implemented a particular data structure, we can use it at
any other place.
• Implementation of data structures can be compiled into
libraries which can be used by different clients.
III. Abstraction: Data structure is specified by the ADT

which provides a level of abstraction.
• The client program uses the data structure through interface
only, without getting into the implementation details.

Thank You
Data Structures By Asst. Prof. Praveen

11
Yadav, DoCSE, UIT-RGPV
UIT-RGPV
Topic: Introduction to Data Structures

[Part-2]
By:
Mr. Praveen Yadav
Assistant Professor
UIT-RGPV, Bhopal
Outline
• Data Structure Classifications
• Operations on Data Structure

Data Structure Classifications
Characteristic Description
Linear In Linear data structures, the data items are arranged in a
linear sequence. Example: Array, Linked List, Queue
Non-Linear In Non-Linear data structures, the data items are not in
sequence. Example: Tree, Graph
Homogeneous In homogeneous data structures, all the elements are of
same type. Example: Array
Non-Homogeneous In Non-Homogeneous data structure, the elements may or
may not be of the same type. Example: Structures, Class
Static Static data structures are those whose sizes and structures
associated memory locations are fixed, at compile time.
Example: Array
Dynamic Dynamic structures are those which expand or shrink
depending upon the program need and its execution. Also,
their associated memory locations changes.
Example: Linked List created using pointers
Data Structure Classifications Cont…
I. Linear Data Structures: A data structure is called linear
if all of its elements are arranged in the linear order.
• Types of Linear Data Structures are given below:
1. Arrays: An array is a collection of similar type of data
items and each data item is called an element of the
array.
• The data type of the element may be any valid data
type like char, int, float or double.
• Example, the individual elements of the array
marks[100] are:
marks[0], marks[1], marks[2], marks[3],.........
marks[98], marks [99].
2. Linked List: Linked list is a linear data structure which is used to maintain a
list in the memory. It can be seen as the collection of nodes stored at non-
contiguous memory locations. Each node of the list contains a pointer to
its adjacent node.
3. Stack: Stack is a linear list in which insertion and deletions are allowed only
at one end, called top.
• A stack is an abstract data type (ADT), can be implemented in most of the
programming languages. It is named as stack because it behaves like a
real-world stack, for example: - piles of plates or deck of cards etc.
4. Queue: Queue is a linear list in which elements can be inserted only at one
end called rear and deleted only at the other end called front.
• It is an abstract data structure, similar to stack. Queue is opened at both
end therefore it follows First-In-First-Out (FIFO) methodology for storing
the data items.
II. Non Linear Data Structures: This data structure does not form a sequence i.e. each
item or element is connected with two or more other items in a non-linear
arrangement. The data elements are not arranged in sequential structure.
Types of Non Linear Data Structures are given below:
1. Trees: Trees are multilevel data structures with a hierarchical relationship
among its elements known as nodes.
• The bottommost nodes in the hierarchy are called leaf node while the
topmost node is called root node. Each node contains pointers to point
adjacent nodes.
• Tree data structure is based on the parent-child relationship among the
nodes. Each node in the tree can have more than one children except the
leaf nodes whereas each node can have at most one parent except the
root node.
2. Graphs: Graphs can be defined as the pictorial representation of the set of
elements (represented by vertices) connected by the links known as
edges. A graph is different from tree in the sense that a graph can have
cycle while the tree cannot have the one.

Operations on Data Structure
1. Traversing: Every data structure contains the set of data elements. Traversing
the data structure means visiting each element of the data structure in order to
perform some specific operation like searching or sorting.
• Example: If we need to calculate the average of the marks obtained by a student in
6 different subject, we need to traverse the complete array of marks and calculate
the total sum, then we will divide that sum by the number of subjects i.e. 6, in
order to find the average.
2. Insertion: Insertion can be defined as the process of adding the elements to the
data structure at any location.
3. Deletion: The process of removing an element from the data structure is called
Deletion. We can delete an element from the data structure at any random
location.
• If we try to delete an element from an empty data structure
then underflow occurs.

Operations on Data Structure Cont…
4. Searching: The process of finding the location of an element within the
data structure is called Searching. There are two algorithms to perform
searching, Linear Search and Binary Search. We will discuss each one of
them later in this tutorial.
5. Sorting: The process of arranging the data structure in a specific order is
known as Sorting. There are many algorithms that can be used to perform
sorting, for example, insertion sort, selection sort, bubble sort, etc.
6. Merging: When two lists List A and List B of size M and N respectively, of
similar type of elements, clubbed or joined to produce the third list, List C
of size (M+N), then this process is called merging.

Advantages of Data Structures
I. Efficiency: Efficiency of a program depends upon the choice of data structures.
For example: suppose, we have some data and we need to perform the search for a
particular record. In that case, if we organize our data in an array, we will have to
search sequentially element by element. Hence, using array may not be very
efficient here.
There are better data structures which can make the search process efficient like
ordered array, binary search tree or hash tables.
II. Reusability: Data structures are reusable, i.e. once we have implemented a
particular data structure, we can use it at any other place. Implementation of data
structures can be compiled into libraries which can be used by different clients.
III. Abstraction: Data structure is specified by the ADT which provides a level of
abstraction. The client program uses the data structure through interface only,
without getting into the implementation details
Thank You

10
UIT-RGPV

Topic: Array
By:
Mr. Praveen Yadav
Assistant Professor
UIT-RGPV, Bhopal
Outline
Introduction
Terms used for Array
Array Memory Representation
Need of an Array
Types of Arrays
Basic Operations performed on an Array
Advantages of Arrays
Disadvantages of Arrays

Introduction
• Definition: An array is a collection of homogeneous
(same type) data items stored in contiguous memory
locations.
• For example: If an array is of type “int”, it can only
store integer elements and cannot allow the
elements of other types such as double, float, char
etc.

Terms used for Array
Following are the important terms to understand
the concept of Array.
• Element: Each item stored in an array is called an
element.
• Index: Each location of an element in an array has
a numerical index, which is used to identify the
element.
• Array Length: The length of an array is defined
based on the number of elements an array can
store.
Array Memory Representation
• The following diagram represents an integer

array that has 12 elements. The index of the
array starts with 0, so the array having 12
elements has indexes from 0 to 11.

Need of an Array
• Array is particularly useful when we are dealing
with lot of variables of the same type.
• For example: let’s say I need to store the marks in
“Data Structures” subject of 100 students. To
solve this particular problem:
Solution-1: I have to create the 100 variables of
int type.
Solution-2: Create an array of int type with the
size 100. Example: int marks[100];
Note: Obviously the solution-2 is best.

Types of Arrays
The various types of arrays are as follows.

• One Dimensional Array
• Multi-Dimensional Array

One-Dimensional Array
• A one-dimensional array is also called a single

dimensional array where the elements will be
accessed in sequential order. This type
of array will be accessed by the subscript of
either a column or row index.

Array Declaration, Initialization & Display
#include <stdio.h>
int main () {
int A[ 5 ]; /* A[] is an array of 5 integers */
int i, j;
/* initialize elements of array */
for ( i = 0; i < 5; i++ )
{
A[ i ] = i + 100; /* set element at location i to i + 100 */
}
/* output each array element's value */
for (j = 0; j < 5; j++ )
{
printf("A[%d] = %d\n", j, A[j] );
}
return 0;
}
Multi-Dimensional Array
• When the number of dimensions specified is more

than one, then it is called as a multi-
dimensional array. Multidimensional arrays include
2D arrays and 3D arrays.
• A Two-Dimensional Array will be accessed by using
the subscript of row and column index. For traversing
the two-dimensional array, the value of the rows and
columns will be considered.

Two-Dimensional Array
• In the two-dimensional array Arr2D[3] [4], the first index specifies

the number of rows and the second index specifies the number of
columns and the array can hold 12 elements (3 * 4).
• Similarly, in a three-dimensional array, there will be three
dimensions. The array Arr3D[5] [10] [15] can hold 750 elements (5
* 10 * 15).
Basic Operations performed on an Array
1. Traverse: print all the array elements one by

one.
2. Insertion: Adds an element at the given index.
3. Deletion: Deletes an element at the given index.
4. Search: Searches an element using the given
index or by the value.
5. Update: Updates an element at the given index.

Advantages of Arrays
1.Reading an array element is simple and efficient:
In an Array any element can be instantly read
using indexes (base address calculation behind
the scene) without traversing the whole array.
2.Array is a foundation of other data structures: For
example other data structures such as Linked-List,
Stack, Queue etc. are implemented using array.
3.All the elements of an array can be accessed using
a single name (array name) along with the index,
which is readable, user-friendly and efficient
rather than storing those elements in different-
different variables.
Disadvantages of Arrays
1.While using array, we must need to make the decision

of the size of the array in the beginning, so if we are not
aware how many elements we are going to store in
array, it would make the task difficult.
2.The size of the array is fixed so if at later point, if we
need to store more elements in it then it can’t be done.
On the other hand, if we store less number of elements
than the declared size, the remaining allocated memory
is wasted.
3.Insertion and deletion are quite difficult in an array as
the elements are stored in
consecutive memory locations and the shifting
operation is costly.
Thank You

UIT-RGPV
Topic: Address Calculation in an Array
By:
Mr. Praveen Yadav
Assistant Professor
UIT-RGPV, Bhopal
Outline
Address Calculation in One Dimensional Array

Address Calculation in Two Dimensional Array
Numerical Examples

Address Calculation in One Dimensional Array

Cont…
• Address of an element of an array say “A[ I ]” is
calculated using the following formula:
• Address of A [ I ] = B + W * ( I – LB )
Where,
• B = Base address
• W = Storage Size of one element stored in the array (in
byte)
• I = Subscript of element whose address is to be found
• LB = Lower limit / Lower Bound of subscript, if not
specified assume 0 (zero).

Examples
Example-1:
• Given the base address of an array
A[1300 : 1900] as 1020 and size of each
element is 2 bytes in the memory. Find the
address of A[1700].

Examples
Example-1:
• Given the base address of an array A[1300 : 1900] as 1020 and size
of each element is 2 bytes in the memory. Find the address of
A[1700].
Solution: The given values are:
• Base Address, B = 1020
• Lower Bound, LB = 1300
• Size of an element, W = 2 Bytes
• Index position whose address is to be found, I = 1700
Address of A [ I ] = B + W * ( I – LB )
= 1020 + 2 * (1700 – 1300)
= 1020 + 2 * 400
= 1020 + 800
= 1820 [Ans]

Examples
Example-2:
• Given the base address of an array A[0 : 40] as 1000 and size of each
element is 2 bytes in the memory. Find the address of A[25].
Note: A[X : Y] indicates that A is a 1-Dimentional array with lower
bound X and upper bound Y.
Solution: The given values are:
• Base Address, B = 1000
• Lower Bound, LB = 0
• Size of an element, W = 2 Bytes
• Index position whose address is to be found, I = 25
Address of A [ I ] = B + W * ( I – LB )
= 1000 + 2 * (25 – 0)
= 1000 + 2 * 25
= 1000 + 50
= 1050 [Ans]

Address Calculation in Two Dimensional Array
• Address of an element of any array say “A[ I ][ J ]” is
calculated in two forms as given:
1. Row Major System.
2. Column Major System

Cont…
1.Row Major System:
The address of a location in Row Major System is calculated using the following
formula:
Address of A [ I ][ J ] = B + W * [ N * ( I – Lr ) + ( J – Lc ) ]
Where,
B = Base address
I = Row subscript of element whose address is to be found
J = Column subscript of element whose address is to be found
W = Storage Size of one element stored in the array (in byte)
Lr = Lower limit of row/start row index of matrix, if not given assume 0 (zero)
Lc = Lower limit of column/start column index of matrix, if not given assume 0
(zero)
N = Number of column of the given matrix

Cont…
2. Column Major System:
The address of a location in Column Major System is calculated using
the following formula:
Address of A [ I ][ J ] = B + W * [( I – Lr ) + M * ( J – Lc )]
Where,
B = Base address
I = Row subscript of element whose address is to be found
J = Column subscript of element whose address is to be found
W = Storage Size of one element stored in the array (in byte)
Lr = Lower limit of row/start row index of matrix, if not given assume 0 (zero)
Lc = Lower limit of column/start column index of matrix, if not given assume 0
(zero)
M = Number of row of the given matrix.

Numerical Examples
• Important: Usually number of rows and columns of a
matrix are given ( like A[20][30] or A[40][60] ) but if it is
given as A[Lr- – – – – Ur, Lc- – – – – Uc].
• In this case number of rows and columns are calculated
using the following methods:
• Number of rows (M) will be calculated as = (Ur – Lr) + 1
• Number of columns (N) will be calculated as = (Uc – Lc)
+1
• And rest of the process will remain same as per
requirement (Row Major Wise or Column Major Wise).

Cont…
• Question: An array X [-15……….10, 15……………40]
requires one byte of storage for an element. If
beginning location is 1500 determine the location of X
[15][20].
• Solution: As you see here the number of rows and columns are
not given in the question. So they are calculated as:
Number of rows say M = (Ur – Lr) + 1 = [10 - (- 15)] +1
= 26
Number of columns say N = (Uc - Lc) + 1 = [40 – 15)] +1
= 26
Cont…
(i). Row Major Wise Calculation of above equation
• The given values are: B = 1500, W = 1 byte, I = 15, J = 20, Lr = -15,
Lc = 15, N = 26
• Address of A [ I ][ J ] = B + W * [ N * ( I – Lr ) + ( J – Lc ) ]
= 1500 + 1* [26 * (15 – (-15))) + (20 – 15)]
= 1500 + 1 * [26 * 30 + 5]
= 1500 + 1 * [780 + 5]
= 1500 + 785
= 2285 [Ans]

Cont…
(ii). Column Major Wise Calculation of above equation
• The given values are: B = 1500, W = 1 byte, I = 15, J = 20, Lr = -
15, Lc = 15, M = 26
• Address of A [ I ][ J ] = B + W * [ ( I – Lr ) + M * ( J – Lc ) ]
= 1500 + 1 * [(15 – (-15)) + 26 * (20 – 15)]
= 1500 + 1 * [30 + 26 * 5]
= 1500 + 1 * [160]
= 1660 [Ans]

Practice Questions
Q.1. Given an array, arr[1………10][1………15] with base
value 100 and the size of each element is 1 Byte in
memory. Find the address of arr[8][6] with the help
of row-major order.
Q.2. Given an array arr[1………10][1………15] with base

value 100 and the size of each element is 1 Byte in
memory find the address of arr[8][6] with the help of
column-major order.

Solutions
Q.1. Given an array, arr[1………10][1………15] with base value 100 and the size of
each element is 1 Byte in memory. Find the address of arr[8][6] with the help
of row-major order?
Solution: - Given:
• Base address B = 100
• Storage size of one element store in any array W = 1 Bytes
• Row Subset of an element whose address to be found I = 8
• Column Subset of an element whose address to be found J = 6
• Lower Limit of row/start row index of matrix LR = 1
• Lower Limit of column/start column index of matrix = 1
• Number of column given in the matrix
N = Upper Bound – Lower Bound + 1
=15–1+1
= 15

Cont…
• Formula:
Address of A[I][J] = B + W * (N*(I – Lr) + (J – Lc))
• Address of A[8][6] = 100 + 1 * [15*(8 – 1) + (6 – 1)]

= 100 + 1 * [15*(7) + (5)]
= 100 + 1 * 110
= 210
Ans: Address of A[8][6] = 210

Solutions
Q.2. Given an array, arr[1………10][1………15] with base value 100 and the size of
each element is 1 Byte in memory. Find the address of arr[8][6] with the help
of column-major order.
Solution: - Given:
• Base address B = 100
• Storage size of one element store in any array W = 1 Bytes
• Row Subset of an element whose address to be found I = 8
• Column Subset of an element whose address to be found J = 6
• Lower Limit of row/start row index of matrix LR = 1
• Lower Limit of column/start column index of matrix = 1
• Number of rows given in the matrix, M = Upper Bound – Lower Bound + 1
= 10 – 1 + 1
= 10

Cont…
• Formula:
Address of A[I][J] = B + W * [(I – LR) + M*(J – LC)]
• Address of A[8][6] = 100 + 1 * [(8 – 1) + 10*(6 – 1)]

= 100 + 1 * [7 + 10*(5)]
= 100 + 1 * 57
= 157
Ans: Address of A[8][6] = 157

Thank You

UIT-RGPV
Topic: Tower of Hanoi
By:
Mr. Praveen Yadav
Assistant Professor
UIT-RGPV, Bhopal
Outline
Tower of Hanoi – Introduction

Objective & Rules
Tower Of Hanoi Problem With 3-Disks
Recursive Procedure for Tower of Hanoi
Problem for N-Disks
Example: Recursive solution for Tower of
Hanoi problem for 4-disks.

Tower of Hanoi
• The puzzle was invented by
the French mathematician Edouard Lucas in 1883.
• Tower of Hanoi, is a mathematical puzzle which
consists of three towers (pegs) and more than one
rings is as depicted :

Objective & Rules
Objective: The objective is to move all the disks to
some another tower without violating the
sequence of arrangement.
• A few rules to be followed for Tower of Hanoi are:

1.Only one disk can be moved among the towers
at any given time.
2.Only the "top" disk can be removed.
3.No large disk can sit over a small disk.
TOWER OF HANOI PROBLEM WITH 3-DISKS
Given: Initial Condition of Tower of Hanoi Puzzle for n = 3
(i.e. Three Disks)

• General Formula: Number of steps required to move n-
disks from source peg to destination peg = 2n−1 steps.
• Therefore, Number of steps required to move 3-disks from

source peg to destination peg = 23−1 = 7 steps.
• Following is the step by step solution for n =3:

Step-1: Move the top disk from source peg to destination peg.
Step-2: Move the top disk from source peg to auxiliary peg.
Step-3: Move the top disk from destination peg to auxiliary peg.
Step-5: Move the top disk from auxiliary peg to source peg
Step-6: Move the top disk from auxiliary peg to destination peg.

Solution Steps

Recursive procedure for Tower of
Hanoi problem for N disks
Note: In the above procedure BEG is used for Source Peg, AUX is used for Auxiliary
Peg and END is used for Destination Peg.
9
Solution for, TOWER (N, BEG, AUX, END )
The solution for General notation, TOWER (N, BEG,

AUX, END ) be reduce to the solution of the
following three sub-problems
1. TOWER ( N-1, BEG, END, AUX )
2. TOWER ( 1, BEG, AUX, END ) or BEG →END
3. TOWER ( N-1, AUX, BEG, END )

10
For Example: Recursive solution for Tower of
Hanoi problem for 4-disks.
• Recursive solution for TOWER ( 4, BEG, AUX,

END ) is given in next slide:
• Number of steps required = 2n−1 steps.
= 24-1
= 15

11
12
Thank You

UIT-RGPV

Topic: Asymptotic Notations
By:
Mr. Praveen Yadav
Assistant Professor
DoCSE, UIT-RGPV
Bhopal
Outline
Introduction
Asymptotic Analysis
Types of Asymptotic Notations

Introduction
• Asymptotic Notations are mathematical tools/
expressions to represent time complexity of
algorithms for Asymptotic Analysis.

Asymptotic Analysis
• The main idea of asymptotic analysis is to have a
measure of efficiency of algorithms that doesn’t
depend on machine specific constants, and doesn’t
require algorithms to be implemented.
• There are three types of analysis that we perform on
a particular algorithm.
1. Best Case
2. Worst Case
3. Average Case

Asymptotic Analysis Cont…
1. Best Case: In which we analyze the performance of
an algorithm for the input, for which the algorithm
takes less time or space.
2. Worst Case: In which we analyze the performance
of an algorithm for the input, for which the
algorithm takes long time or space.
3.Average Case: In which we analyze the
performance of an algorithm for the input, for which
the algorithm takes time or space that lies between
best and worst case.

Types of Asymptotic Notation
The following 3 asymptotic notations are mostly used
to represent time complexity of algorithms.
1. Big-O Notation (Ο) – Big O notation specifically
describes worst case scenario.
2. Omega Notation (Ω) – Omega(Ω) notation
specifically describes best case scenario.
3. Theta Notation (θ) – This notation represents the
average complexity of an algorithm.

Big-O Notation (Ο)
• Big O notation specifically describes worst case
scenario. It represents the upper bound running time
complexity of an algorithm.
f(n) <= c*g(n) , for all n >= n0

Ω (Omega) Notation
Just as Big O notation provides an asymptotic upper
bound on a function, Ω notation provides an
asymptotic lower bound.
f(n) >= c*g(n), for all n >= n0

Θ (Theta) Notation
The theta notation bounds a functions from

above and below, so it defines exact asymptotic
behavior.
c1*g(n) <= f(n) <= c2*g(n), for all n >= n0

Thank You

UIT-RGPV

Topic: Time Complexity
By:
Mr. Praveen Yadav
Assistant Professor
DoCSE, UIT-RGPV
Bhopal
Time Complexity Computation
1. Substitution Method
2. Master Method

1. Substitution Method

Time Complexity Calculation by Substitution Method
• Example-1: Find time complexity of the following
recurrence relation:
T(n) = T(n − 1) + 1 ,for n > 1
and T(n) = 1, for n = 1
Solution:
T(n) = T(n − 1) + 1 ----------------given equation-1
Put n = n - 1
T(n-1) = T(n-2) + 1
now put value of T(n-1) in equation-1
T(n) = T(n-2) + 1 + 1
T(n) = T(n-2) +2 --------------equation-2
Now put n = n-2 in given equation-1 to get T(n-2)
T(n-2) = T(n-3) + 1
Now put value of T(n-2) in equation-2, we get
T(n) = T(n-3) + 2 + 1
T(n) = T(n-3) + 3 --------------equation-3
Now, We can write general solution in terms of k
T(n) = T(n-k) + k
When k = n-1 we get T(1) = 1

Put k = n-1 in above general equation we get
T(n) = T(n – (n-1)) + n-1
T(n) = T(1) + n-1
T(n) = 1 + n - 1
T(n) = n
Hence T(n) = Θ(n)
Ans: Time Complexity is: Θ(n)

Example-2: Find time complexity of the following
recurrence relation:
T(n) = T(n/2) + O(1), for n > 1
and T(1) = 1
Solution:
T(n) = T(n/2) + O(1) --------------given equation-1
Put n = n/2
T(n/2) = T(n/4) + O(1) put this value in equation-1
We get
T(n) = T(n/4) + O(1) + O(1)
T(n) = T(n/22) + 2*O(1) -------------- equation-2

Now put n = n/4 in equation-1
T(n/4) = T(n/8) + O(1) put this value in equation-1
We get
T(n) = T(n/8) + 2*O(1) + O(1)
T(n) = T(n/23) + 3*O(1) -------------- equation-3
Similarly we can write general solution for k-steps
T(n) = T(n/2K) + K*O(1) -------------- equation-4
When
n/2K = 1
n = 2K
K = log2(n)

Now put K = log2(n) in equation-4
T(n) = T(1) + log2(n) *O(1)
T(n) = 1 + log2(n)
We know that
log2(n) ≤ 1 + log2(n) ≤ 2 log2(n) ∀ n ≥ 2.
Hence
T(n) = Θ(log2n )
Ans: Time Complexity is: Θ(log2n )

2. Master Method

Master Method

Relation Between h(n) and u(n)
h(n) u(n)
1 O ( nr ) , r < 0 O (1)
2 Θ ( ( log n)i) , i >= 0 Θ ( log n)i + 1 / (i + 1) )
3 Ω ( nr ) , r > 0 Θ ( h(n) )

Master Method
Example-1: Find out the time complexity of the given function T(n):
T(n) = 2 T(n/2) + n ; if n > 1
And T(1) = 2
Solution:
Where, a= 2 , b = 2, F(n) = n and T(1) = 2
Put all values, solution becomes:

From table we get,
u(n) = θ (log n)
Put into equation –(1) i.e.
T(n) = n (θ (log n) + 2)
T(n) = n θ(log n) + 2n
Hence Time Complexity is: θ(n log n)

Master Method
Example-2: Find Time Complexity:

T(n) = 7 T(n/2) + 18n2 ; if n > 1
And T(1) = 1
Answer:

Thank You

UIT-RGPV
Topic: Recursion
By:
Mr. Praveen Yadav
Assistant Professor
UIT-RGPV, Bhopal
Outline
Definition of Recursion
Base Condition in Recursion
Types of Recursion (Direct & Indirect)
Types of Direct Recursion

Recursion
Definition: The process in which a function calls itself
directly or indirectly is called recursion and the
corresponding function is called as recursive function.
• In recursion, a function or method has the ability of calling

itself to solve the problem.
• Using recursive algorithm, certain problems can be solved
quite easily.
• Examples of such problems are Towers of Hanoi (TOH),
Different Types of Tree Traversals, DFS of Graph, etc.
• Note: The process of recursion involves solving a problem
by turning it into smaller varieties of itself.
Base Condition in Recursion
• In the recursive program, the solution to the base case is
provided and the solution of the bigger problem is
expressed in terms of smaller problems.
• For Example:
int fact(int n)
{
if (n < = 1) // base case
return 1;
else
return n*fact(n-1);
}
Types of Recursion
1. Direct Recursion
2. Indirect Recursion

Direct Recursion
• If a function calls itself from within itself, it’s known as

direct recursion.
• This result in a one-step recursive call: the function
makes a recursive call inside its own function body.
• For Example:
void Fun()
{
// some code...
Fun();
// some code...
}

Types of Direct Recursion
Direct Recursion can be further categorized

into four types:
1. Tail Recursion
2. Head Recursion
3. Tree Recursion
4. Nested Recursion

1. Tail Recursion
If a recursive function calling itself and that recursive call is the last
statement in the function then it’s known as Tail Recursion.
• After that call the recursive function performs nothing.
• The function has to process or perform any operation at the time of calling and it does
nothing at returning time.
• Example:
// Code Showing Tail Recursion // Driver Code

#include <stdio.h> int main()
// Recursion function {
void fun(int n) int x = 3;
{ fun(x);
if (n > 0) { return 0;
printf("%d ", n); }
// Last statement in the function
fun(n - 1);
}
}

2. Head Recursion
If a recursive function calling itself and that recursive call is the first
statement in the function then it’s known as Head Recursion.
• There’s no statement, no operation before the call.
• The function doesn’t have to process or perform any operation at the time
of calling and all operations are done at returning time.
Example:
// Code Showing Head Recursion // Driver code
#include <stdio.h> int main()
{
// Recursive function
int x = 3;
void fun(int n) fun(x);
{ return 0;
if (n > 0) { }
// First statement in the function
fun(n - 1);
printf("%d ", n);
}
}
Indirect Recursion
In this recursion, there may be more than one
function and they are calling one another in a
circular manner.
From the above diagram:

fun(A) is calling for fun(B), fun(B) is calling for fun(C) and
fun(C) is calling for fun(A) and thus it makes a cycle.
Thank You

UIT-RGPV
Topic: Sparse Matrix
By:
Mr. Praveen Yadav
Assistant Professor
UIT-RGPV, Bhopal
Outline
➢Definition
➢Reason to use Sparse Matrix
➢Sparse Matrix Representations

Definition
• A matrix is a two-dimensional data object, made of
m-rows and n-columns, therefore having total m x n
values. If most of the elements of the matrix have 0
values, then it is called a sparse matrix.
• For Example:
0 0 3 0 4
0 0 5 7 0
0 0 0 0 0
0 2 6 0 0
4x5

Reason to use Sparse Matrix instead of Simple
Matrix
1. Storage: There are lesser non-zero elements than zeros and
thus lesser memory can be used to store only those
elements.
2. Computing Time: Computing time can be saved by logically
designing a data structure traversing only non-zero
elements.
Note:
• Representing a sparse matrix by a 2D-array leads to wastage
of lots of memory as zeroes in the matrix are of no use in
most of the cases.
• So, instead of storing zeroes with non-zero elements, we
only store non-zero elements.
• This means storing non-zero elements with triples- (Row,
Column, Value).

Sparse Matrix Representations
• Sparse Matrix Representations can be done in

many ways following are two common
representations:
1. Array Representation
2. Linked List Representation

Method 1:
Array Representation of Sparse Matrix

Method 1: Array representation of Sparse Matrix
➢ 2D-array is used to represent a sparse matrix in

which there are three rows named as:
• Row: Index of row, where non-zero element is
located.
• Column: Index of column, where non-zero element
is located.
• Value: Value of the non zero element located at
index – (row, column).

Array representation Cont…

Method 2:
Linked list Representation of Sparse Matrix

Method 2: Linked list Representation of Sparse Matrix
➢In linked list, each node has four fields. These

four fields are defined as:
• Row: Index of row, where non-zero element
is located.
• Column: Index of column, where non-zero
element is located.
• Value: Value of the non zero element located
at index – (row, column).
• Next: Address of the next node
Linked list Representation of Sparse Matrix cont…
• Node Structure in Linked List:

Example: Linked list Representation of Sparse Matrix

Thank You

UIT-RGPV

Topic: Linked List
By:
Mr. Praveen Yadav
Assistant Professor
UIT-RGPV, Bhopal
Linked List
• A Linked List or one-way list, is a linear collection of
data elements, called Nodes, Where the linear order
is given by means of pointers.
• Each node is divided into two parts
1. First Part: It contains the information of the
elements
2. Second Part: It contains the address of the next
node in the list.
Note:
• First Part is also called Data Field or Information Field
• Second part is also called Link field or next-pointer field.
Single Node of Linked List

Example: Linked List with 6-Nodes

Key Terms
• List Pointer (External Pointer) (START or NAME): It
contain the address of the first node in the list.
• Null Pointer: It is used to indicate the end of the list.
It is denoted by or NULL = 0
• Null List (Empty List): The list that has no nodes is
called Null List. It is denoted by the null pointer in
the variable START.

Representation of Linked List in Memory
A Linked List in Memory
where each node of the list
contains a single character.
Note: LIST require two

linear Arrays i.e. INFO & LINK

• We can obtain the actual list of characters or in other
words the string as follows:

Node Creation
struct Node {
int data;
struct Node* next;
};
// creating start pointer to hold address of first node

struct Node* start = NULL;
// allocate node in the heap
start = (struct Node*)malloc(sizeof(struct Node));

Thank You

UIT-RGPV
Topic: Operations Performed on Linked List
By:
Mr. Praveen Yadav
Assistant Professor
UIT-RGPV, Bhopal
Operations Performed on Linked List
Basic Operations performed on Linked List are:
• Node Creation
• Insertion
• Deletion
• Traversing
• Searching

Node Creation
struct Node {
int data;
struct Node* next;
};


Why use Linked List over Array?
• Linked list is the data structure which can overcome
all the limitations of an array.
 Array contains following limitations:
• The size of array must be known in advance before
using it in the program.
• Increasing size of the array is a time taking process. It
is almost impossible to expand the size of the array
at run time.
• All the elements in the array need to be contiguously
stored in the memory. Inserting any element in the
array needs shifting of all its predecessors.
Advantages of Linked List
1. Dynamic in size
2. Ease of insertion/deletion of a Node.

Disadvantages of Linked List
1. Random access is not allowed. We have to access
elements sequentially starting from the first node.
So we cannot do binary search with linked lists
efficiently with its default implementation.
2. Extra memory space for a pointer is required with
each element of the list.
3. Not cache friendly. Since array elements are
contiguous locations, there is locality of reference
which is not there in case of linked lists.

Thank You

UIT-RGPV

Topic: Insertion Operations Performed on
Linked List
By:
Mr. Praveen Yadav
Assistant Professor
UIT-RGPV, Bhopal
Operations Performed on Linked List
• Node Creation
• Insertion
• Deletion
• Traversing
• Searching

Node Creation
struct Node {
int data;
struct Node* next;
};


Inserting a Node
To insert a Node into Linked List, the following

three things should be done:
1. Allocating a Node
2. Assigning the Data
3. Adjusting the Pointers/Addresses

Inserting a Node
at the
Beginning

Inserting a Node at the Beginning of Linked List

Linked List after Insertion of New Node 40

Algorithm to Inserting a Node at the Beginning of
Linked List

C-Code to Implement Algorithm

Inserting a Node
at the
END

Inserting a Node at the END of Linked List

Process to Insert a Node at the END of Linked List

Inserting a Node at the END of Linked List

Algorithm to Inserting a Node at the END of
Linked List

C-Code to Implement Algorithm

Inserting a Node
at
Specified Position

Inserting a Node at Specified Position in the
Linked List

Thank You

UIT-RGPV
Topic: Types of Linked List
By:
Mr. Praveen Yadav
Assistant Professor
UIT-RGPV, Bhopal
Types of Linked List
• Following are the types of Linked List
1. Singly Linked List
2. Doubly Linked List (Two-Way Linked List)
3. Circular Linked List
4. Circular Doubly Linked List
5. Header Linked List (Grounded Header List and
Circular Header List)
6. Two-Way Header List & Two-Way Circular Header
List

Singly Linked List
• Each node has a single link to another node is called Singly Linked
List.
• It requires a reference (Start pointer) to the first node to store a
single linked list.
• Singly Linked List does not store any pointer any reference to the
previous node.
• Each node stores the contents of the node (Data Field) and a
reference to the next node (Next Field) in the list.
• In a singly linked list, last node has a pointer which indicates that it
is the last node (reference to next node is NULL).
• It has successor and predecessor. First node does not have
predecessor while last node does not have successor.
• In this type of linked list, only forward sequential movement is
possible,
• No direct access of the node allowed.

Singly Linked List
The address of the first node is always store in a

reference pointer known as Start or Head.
Reference part of the last node must be null.

Doubly (Two-way ) Linked List
• Each Node of Doubly Linked List is Consisting of three field/
parts.
• Link-1 field stores the address of the previous node and Link-2
field stores the address of the next node.
• The Data Item field stores the actual value of that node.

Doubly Linked List
• Doubly linked list is a sequence of elements in which
every node has link to its previous node (predecessor
node) and next node (Successor node).
• Traversing can be done in both directions (Forward and
Backward Direction).
• First node is always pointed by head. In doubly linked
list, previous field of the first node is always NULL (it
must be NULL) and the next field of the last must be
NULL.

Example of Doubly Linked List

Advantages & Disadvantages of Doubly Linked List
Advantages:
• Doubly linked list can be traversed in both forward and
backward directions.
• To delete a node in singly linked list, the previous node is
required, while in doubly linked list, we can get the
previous node using previous pointer.
• It is very convenient than singly linked list. Doubly linked list
maintains the links for bidirectional traversing.
Disadvantages:
• In doubly linked list, each node requires extra space for
previous pointer.
• All operations such as Insert, Delete, Traverse etc. require
extra previous pointer to be maintained.

Circular Linked List
• Circular linked list is similar to singly linked list. The only
difference is that in circular linked list, the last node points to the
first node in the list.

Circular Linked List
• It is a sequence of elements in which every element has
link to its next element in the sequence and has a link to
the first element in the sequence.
• A singly linked list can be converted into circular linked
list by simply storing the address of very first node in the
link field of the last node.

Advantages & Disadvantages of Circular Linked List
Advantages:
1.If we are at a node, then we can go to any node. But in linear
linked list it is not possible to go to previous node.
2.It saves time when we have to go to the first node from the last
node. It can be done in single step because there is no need to
traverse the in between nodes. But in double linked list, we will
have to go through in between nodes.
Disadvantages:
1.It is not easy to reverse the linked list.
2.If proper care is not taken, then the problem of infinite loop can
occur.
3.If we at a node and go back to the previous node, then we can
not do it in single step. Instead we have to complete the entire
circle by going through the in between nodes and then we will
reach the required node.
Circular Doubly Linked List
• Circular doubly linked list is a linked data
structure which consists of a set of sequentially
linked records called nodes.
• In doubly circular linked list, the previous link of
the first node points to the last node and the next
link of the last node points to the first node.
• In Circular doubly linked list, each node contains
three fields one data field and two link fields .
• Two link fields are used to represent references
to the previous and the next node in the
sequence of nodes.

Example of Circular Doubly Linked List

Header Linked List
• A Header Linked List is a linked list which always
contains a special node, called the Header Node, at
the beginning of the list.
• This special node can be used to store additional
information like number of nodes present in the
linked list.
• We can use header node to store meta data.
• The following are the two kind of widely used
header lists:
1. Grounded Header List
2. Circular Header List
Grounded Header List
• A grounded header list is a header list where
the last node contains the null pointer.

Circular Header List
• A circular header list is a header list where last
node points back to the header node.

Two-Way Header List

Two-Way Circular Header List

Applications of Linked List
• Implementation of Stacks and Queues
• Implementation of Trees and Graphs
• Dynamic memory allocation
• Represent & Manipulate Polynomials by storing
non-zero coefficients and exponents in the node
of linked list
• Representing Sparse Matrices

Represent & Manipulate Polynomials
• Polynomials are the expressions containing number of
terms with non-zero coefficient and exponents.
P(x) = an xn + an-1 xn-1 + … + a1 x1 + a0
• In linked list representation of polynomials, each node is

considered as a node. Each node is consisting of three
fields:
1. Coefficient field
2. Exponent field
3. Link field

Linked List Representation of Polynomials
P(x) = 5x3 + 2x2 + 10x + 6
Q(x) = 21x4 + 16x3 + 4x2 + 5x + 10

Addition of Polynomials
P(x) = 5x3 + 2x2 + 10x + 6
Q(x) = 21x4 + 16x3 + 4x2 + 5x + 10
Result: R(x) = P(x) + Q(x)
= 21x4 + 21x3 + 6x2 + 15x + 16

Addition of Polynomials
Result: R(x) = P(x) + Q(x)
= 21x4 + 21x3 + 6x2 + 15x + 16

Thank You

UIT-RGPV
Topic: Stack Data Structure
By:
Mr. Praveen Yadav
Assistant Professor
UIT-RGPV, Bhopal
Stack Data Structure
• A stack is a list of elements in which an element
may be inserted or deleted only at one end,
called the TOP of the stack.
• A Stack is a linear Data Structure.
• Stacks are also called Last-In-First-Out (LIFO).
• Elements are removed from a stack in the reverse
order of that in which the were inserted into the
stack.
• Stack is said to be in Overflow state when it is
completely full and is said to be
in Underflow state if it is completely empty.
Basic Operations Associated with Stack
• Two Basic Operations are:
1. PUSH Operation
2. POP Operation
PUSH Operation: It is used to insert an element

into a stack.
POP Operation: It is used to delete an element

from a stack.
Procedure Insert an Item into Stack

Insertion (PUSH Operation)
• Suppose the following 5 elements are
pushed, in order, onto an empty stack:
• A, B, C, D, E

Insertion (PUSH Operation)
• After Insertion of all 5 elements stack
becomes:

Procedure to delete an Item from Stack

Deletion (POP Operation)
• Delete an element from the stack

Implementation of Stack
• Stack can be easily implemented using an
Array or a Linked List.
1. Implement Stack using array.
2. Implement Stack using Linked List.
• Arrays are quick, but are limited in size.
• Linked List requires overhead to allocate, link,
unlink, and deallocate, but is not limited in
size.

Implement Stack using array
• Already study in previous slides

Implement Stack using Linked List
• Linked Stack: Linked Stack is a stack that is
implemented using a singly linked list.
• The INFO field of the node hold the element
of the stack.
• LINK fields hold address of the next element in
the stack.
• The START pointer of the linked list behaves as
the TOP pointer variable of the stack.
• NULL pointer of the last node in the list signal
the bottom of stack.
Linked Representation of Stack

PUSH Operation into STACK
• PUSH “WWW” into Stack (Inserting a Node).

POP Operation into STACK
• Deleting a Node from Stack.
• Delete a Node from Stack.

Applications of Stack
• Stack Frames (Used in Recursion).
• Reversing a String.
• Parsing (Used in Compiler).
• Arithmetic Expression Conversion(Conversion
of Infix to Prefix and Postfix Expressions) and
Expression Evaluation.

Thank You

UIT-RGPV
Topic: Applications of Stack
By:
Mr. Praveen Yadav
Assistant Professor
UIT-RGPV, Bhopal
• Calculation of Postfix Expression.

Evaluation of a Postfix Expression

Evaluation of a Postfix Expression cont…
Example: Given Postfix Expression
P = 5, 6, 2, +, *, 12, 4, /, -
Solution:
First Add “)” at the end of P (Postfix expression)
P = 5, 6, 2, +, *, 12, 4, /, -, )

Evaluation of a Postfix Expression cont…
Symbol Scanned STACK Operation performed
5 5 Push 5
6 5, 6 Push 6
2 5, 6, 2 Push 2
+ 5, 8 Pop 6 & 2 and perform operation 6+2 = 8 then Push 8
* 40 Pop 8 & 5 and perform operation 8*5 = 40 then Push 40
12 40, 12 Push 12
4 40, 12, 4 Push 4
/ 40, 3 Pop 4 & 12 and perform operation 12/3 = 4 then Push 3

- 37 Pop 3 & 40 and perform operation 40-3 = 37 then Push 37
) Pop 37 and Announce Result = 37

Thank You

UIT-RGPV
Topic: Implementation of Stack using

Linked List
By:
Mr. Praveen Yadav
Assistant Professor
UIT-RGPV, Bhopal
Implementation of Stack using Linked List
• Linked Stack: Linked Stack is a stack that is
implemented using a singly linked list.
• A Node of Linked List:
OR

Terms used in Implementation of Stack using
Linked List
• Node:
• INFO field: The INFO field hold the element of
the stack.
• LINK fields: The LINK fields hold address of the
next element in the stack.
• START Pointer: The START pointer of the linked
list behaves as the TOP pointer variable of the
stack.
• NULL pointer: The NULL pointer of the last
node in the list signal the bottom of stack.


PUSH Operation into STACK
• PUSH “WWW” into Stack (Inserting a Node).

POP Operation into STACK
• Deleting a Node from Stack.
• Delete a Node from Stack.

• Arithmetic Expression Conversion(Conversion
of Infix to Prefix and Postfix Expressions) and
Expression Evaluation.

Thank You

UIT-RGPV
Topic: Types of Notations for

Mathematical Expression
By:
Mr. Praveen Yadav
Assistant Professor
UIT-RGPV, Bhopal
Types of Notations for an Mathematical Expression
1. Infix Notation
2. Prefix Notation (Polish Notation)
3. Postfix Notation (Reverse Polish Notation)

Infix Notation
The Operator symbol is placed between its two
operands
For Example:
• A+B
• C-D
• E*F
• G/H

Infix Notation
Example: A + B * C
Here, we must distinguish between
1. (A + B) * C
2. A + (B * C)
By using Parentheses or some Operator-
Precedence Conventions.
Highest: Exponentiation (↑)
Next Highest: Multiplication (*)and Division (/)
Lowest: Addition (+) and Subtraction (-)
Infix Notation
• Operator-Precedence Conventions.
Highest: Exponentiation (↑)
Next Highest: Multiplication (*)and Division (/)
Lowest: Addition (+) and Subtraction (-)

Prefix Notation (Polish Notation)
The Operator symbol is placed before its two
operands
For Example:
• +AB
• -CD
• *EF
• /GH

Infix to Prefix Conversion
Example-1:
Example-2:
Example-3:

Postfix Notation (Reverse Polish Notation)
The Operator symbol is placed after its two
operands
For Example:
• AB+
• CD-
• EF*
• GH/

Thank You

UIT-RGPV
Topic: Types of Queue
By:
Mr. Praveen Yadav
Assistant Professor
UIT-RGPV, Bhopal
Types of Queue
• There are four types of Queue:
1. Simple Queue
2. Circular Queue
3. DEQUE (Double Ended Queue)
4. Priority Queue

DEQUE (Double Ended Queue)
• A Deque is a linear list in which elements can
be added or removed at either end but not in
the middle.

Types of DEQUE
There are two types of DEQUE
1. Input-Restricted DEQUE
2. Output-Restricted DEQUE

• Input-Restricted DEQUE: It allows insertion at
only one end of the list but allows deletion at
both ends of the list.
• Output-Restricted DEQUE: It allows deletion at

only one end of the list but allows insertion at
both ends of the list.

Priority Queue
• A Priority Queue is a collection of elements such that
each element has been assigned a priority.
• The Order in which elements are deleted and
processed comes from the following rules:
1. An element of higher priority is processed before
any element of lower priority.
2. The two elements with same priority are
processed according to the order in which they
where added to the Queue.

Types of Priority Queue
• There can be two Types of Priority Queue:
1. Ascending Priority Queue.
2. Descending Priority Queue.
• Implementation of Priority Queue:

1. Linked List Implementation
2. Array Implementation

Ascending Priority Queue
Linked List Implementation

Descending Priority Queue
Linked List Implementation

Array Representation of Priority Queue
• A Two-Dimensional Array is use to implement Priority Queue.
• A separate Queue for each level of priority (Priority Number)
• Each Queue is a Circular Array.
• Use two pair of Pointers FRONT and REAR.

Linked List Representation

Thank You

UIT-RGPV
Topic:Trees Data Structure & Tree

Terminology
By: Asst. Prof. Praveen Yadav,

DoCSE, UIT-RGPV, BHOPAL
Trees
 Tree is a Non-Linear Data Structure.
 Trees are used to represent hierarchical relationship
existing between elements (Data Items or Nodes).
 Tree is a finite set of one or more data items (Nodes)
such that:
 1.There is a special node called the root of the tree.
 2. And its remaining nodes are partitioned into number of
mutually exclusive (i.e. disjoint) subsets, each of which is
itself a tree.And they are called subtrees.
2 Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV, Bhopal

Trees
 For Example:

Tree Terminology
 There are number of terms associated with the trees
which are listed bellow:
1. Root 9. Terminal Nodes (Leaf
2. Node Nodes)
3. Edge 10. Level
4. Parent Node 11. Height
5. Child Nodes 12. Depth
6. Siblings 13. Subtree
7. Degree
14. Forest
8. None Terminal Nodes
(Internal Nodes) 15. Path
4 Data Structures By Asst. Prof. Praveen

Yadav, DoCSE, UIT-RGPV, Bhopal
Tree Terminology
1. Root:
 The first node from where the tree originates is called as
a root node.
 In any tree, there must be only one root node.
 We can never have multiple root nodes in a tree data
structure.

Tree Terminology
2. Node:
 Each data item (element) in a tree is called a Node.
 It is the basic structure in a tree.
 It specifies the data information and links (branches) to
other Nodes.

Tree Terminology
3. Edge:-
 The connecting link between any two nodes is called as
an edge.
 In a tree with n number of nodes, there are exactly (n-1)
number of edges.

Tree Terminology
4. Parent Node:-
 The node which has a branch from it to any other node is
called as a parent node.
 In other words, the node which has one or more children
is called as a parent node.
 In a tree, a parent node can have any number of child
nodes.
 Node A is the parent of nodes B and C
 Node B is the parent of nodes D, E and F
 Node C is the parent of nodes G and H
 Node E is the parent of nodes I and J
 Node G is the parent of node K

Tree Terminology
5. Child Nodes:-
 The node which is a descendant of some node is called as
a child node.
 All the nodes except root node are child nodes.
 Nodes B and C are the children of node A

 Nodes D, E and F are the children of node B
 Nodes G and H are the children of node C
 Nodes I and J are the children of node E
 Node K is the child of node G

Tree Terminology
6. Siblings:-
 Nodes which belong to the same parent are called
as siblings.
 In other words, nodes with the same parent are sibling
nodes.
 Nodes B and C are siblings

 Nodes D, E and F are siblings
 Nodes G and H are siblings
 Nodes I and J are sibling

Tree Terminology
7. Degree:-
 Degree of a node is the total number of children of that node.
 Degree of a tree is the highest degree of a node among all the nodes in
the tree.
 Degree of node A = 2
 Degree of node B = 3
 Degree of node C = 2
 Degree of node D = 0
 Degree of node E = 2
 Degree of node F = 0
 Degree of node G = 1
 Degree of node H = 0
 Degree of node I = 0
 Degree of node J = 0
 Degree of node K = 0

Tree Terminology
8. Internal Node:-
 The node which has at least one child is called as an internal
node.
 Internal nodes are also called as non-terminal nodes.
 Every non-leaf node is an internal node.
 Here, nodes A, B, C, E and G

are internal nodes.

Tree Terminology
9. Leaf Node:-
 The node which does not have any child is called as a leaf
node.
 Leaf nodes are also called as external nodes or terminal
nodes.
 Here, nodes D, I, J, F, K and H

are leaf nodes.

Tree Terminology
10. Level:-
 In a tree, each step from top to bottom is called as level
of a tree.
 The level count starts with 0 and increments by 1 at each
level or step.

Tree Terminology
11. Height:-
 Total number of edges that lies on the longest path from any leaf node to a
particular node is called as height of that node.
 Height of a tree is the height of root node.
 Height of all leaf nodes = 0
 Here,
 Height of node A = 3
 Height of node B = 2
 Height of node C = 2
 Height of node D = 0
 Height of node E = 1
 Height of node F = 0
 Height of node G = 1
 Height of node H = 0
 Height of node I = 0
 Height of node J = 0
 Height of node K = 0

Tree Terminology
12. Depth:-
 Total number of edges from root node to a particular node is called as depth of that
node.
 Depth of a tree is the total number of edges from root node to a leaf node in the
longest path.
 Depth of the root node = 0
 The terms “level” and “depth” are used interchangeably.
 Here,
 Depth of node A = 0
 Depth of node B = 1
 Depth of node C = 1
 Depth of node D = 2
 Depth of node E = 2
 Depth of node F = 2
 Depth of node G = 2
 Depth of node H = 2
 Depth of node I = 3
 Depth of node J = 3
 Depth of node K = 3

Tree Terminology
13. Subtree:-
 In a tree, each child from a node forms a subtree recursively.
 Every child node forms a subtree on its parent node.

Tree Terminology
14. Forest:-
 A forest is a set of disjoint trees.

Tree Terminology
15. Path:-
 It is sequence of consecutive edges from the source node
to the destination node.
 The path between A and J is given by the node pairs
(edges): (A, B), (B, E) and (E, J)

Thank You

UIT-RGPV
Topic: Binary Trees

Binary Trees
 A Binary Tree T is defined as a finite set of elements called
Nodes, such that:
(a) T is empty (called the Null Tree or Empty Tree), or
(b) T contains a distinguished Node R, called the Root of
the T, and the remaining nodes of T form an ordered
pair of disjoint binary trees T1 and T2
Note:
 In Binary Tree, a node may have at most 2 child nodes
(i.e. Zero or One or Two Child nodes are allowed).
 In a Binary Tree Maximum degree of any node is at
most two.

Binary Trees
 If binary tree T does contain a root node R, then two
trees T1 and T2 are called respectively the left and right
subtrees of R.

Left and Right Successor/Child Node
 Left Successor/Child of Root Node (A) is Node B
 Right Successor/Child of Root Node (A) is Node C
 Left Subtree of Root Node(A) consists of following
nodes: B, D, E, H, I, J and K.
 Right Subtree of Root Node(A) consists of following
nodes: C, F, G and L

Binary Tree: Example
 In a binary tree, each node has either 0-child or 1-child
or 2-children.

Unlabeled Binary Tree-
 A binary tree is unlabeled if its nodes are not assigned
any label.

Example: Number of binary trees possible
with 3 unlabeled nodes.
Number of binary trees possible with 3 unlabeled nodes
= 2 x 3C3 / (3 + 1)
= 6C3 / 4 = 6!/(6-3)!*3!*4 = (6 * 5 * 4 * 3!)/(3!*3! *4)
=5
 With 3 unlabeled nodes, 5 unlabeled binary trees are
possible.
 These unlabeled binary trees are as follows-

Labeled Binary Tree
 A binary tree is labeled if all its nodes are assigned a label.

Example: Number of binary trees possible
with 3 labeled nodes
Number of binary trees possible with 3 labeled nodes
= { 2 x 3C3 / (3 + 1) } x 3!
= { 6C3 / 4 } x 6
=5x6
= 30
Thus,
 With 3 labeled nodes, 30 different labeled binary trees
are possible.
 Each unlabeled structure gives rise to 3! = 6 different
labeled structures.
Each unlabeled structure gives rise to 3! = 6
different labeled structures.

Types of Binary Trees
1. Rooted Binary Tree
2. Full Binary Tree / Strictly Binary Tree
3. Complete Binary Tree
4. Perfect Binary Tree
5. Extended Binary Tree
6. Skewed Binary Tree

1. Rooted Binary Tree
A rooted binary tree is a binary tree that satisfies the
following 2 properties-
1. It has a root node.
2. Each node has at most 2 children.
 Example

2. Full Binary Tree (Strictly Binary Tree)
 A full binary tree is a tree in which every node other than the
leaves has two children.
 Full binary tree is used to represent mathematical expressions.
 Example:

3. Complete Binary Tree-
A complete binary tree is a binary tree in which every level,
except possibly the last, is completely filled, and all nodes are as
far left as possible.
Example-

4. Perfect Binary Tree-
A Binary tree is a Perfect Binary Tree in which all the internal
nodes have two children and all leaf nodes are at the same level.
Example-

5. Extended Binary Tree (2-Tree)
Extended binary tree is a type of binary tree in which all the null sub
tree of the original tree are replaced with special nodes called
external nodes whereas other nodes are called internal nodes
Example-

6. Skewed Binary Tree
 A skewed binary tree is a binary tree of n nodes such that
its depth is (n-1).
 Example-

Thank You

UIT-RGPV
Topic:Traversing Binary Trees

Traversing Binary Trees
 Traversal is a process to visit all the nodes of a tree and
may print their values too.
 Because, all nodes are connected via edges (links) we
always start from the root (head) node. That is, we cannot
randomly access a node in a tree.
 There are three ways which we use to traverse a tree:
1. In-Order Traversal
2. Pre-Order Traversal
3. Post-Order Traversal
 Note: Generally, we traverse a tree to search or locate a
given item or key in the tree or to print all the values it
contains.

1. In-Order Traversal

In-Order Traversal
 In this traversal method, the left subtree is visited first,
then the root and later the right sub-tree.
 We should always remember that every node may
represent a subtree itself.
 Note: Left-Subtree, Root, Right-Subtree

In-Order Traversal Algorithm
Algorithm Inorder(tree) :
Step-1: Recursively traverse left subtree. (i.e., call
Inorder(left-subtree) )
Step-2: Visit root node.
Step-3: Recursively traverse right subtree.( i.e., call
Inorder(right-subtree))

In-Order Traversal
 We start from A, and following in-order traversal, we move to

its left subtree B. B is also traversed in-order. The process
goes on until all the nodes are visited.
 The output of Inorder traversal of this tree will be −
D → B → E →A → F → C → G
2. Pre-Order Traversal

Pre-Order Traversal
 In this traversal method, the root node is visited first,
then the left subtree and finally the right subtree.
 Note: Root, Left-Subtree, Right-Subtree

Pre-Order Traversal Algorithm
Algorithm Preorder(tree) :
Step-2: Recursively traverse left subtree. (i.e. call
Preorder(left-subtree))
Step-3: Recursively traverse right subtree. (i.e. call
Preorder(right-subtree) )

Traversing Binary Trees
 We start from A, and following pre-order traversal, we first visit A itself and
then move to its left subtree B. B is also traversed pre-order.
 The process goes on until all the nodes are visited.
 The output of pre-order traversal of this tree will be:
A→B→D→E→C→F→G

3. Post-Order Traversal

Post-Order Traversal
 In Post-Order traversal method, the root node is visited
last, hence the name.
 First we traverse the left subtree, then the right subtree
and finally the root node.
 Note: Left-Subtree, Right-Subtree, Root

Post-Order Traversal Algorithm
Algorithm Postorder(tree):
Step-1: Recursively traverse left subtree. (i.e., call
Postorder(left-subtree))
Step-2: Recursively traverse right subtree. (i.e., call
Postorder(right-subtree))

Post-Order Traversal
 We start from A, and following Post-order traversal, we first visit the left
subtree B. B is also traversed post-order.
 The process goes on until all the nodes are visited.
 The output of post-order traversal of this tree will be −
D → E → B → F → G → C →A

Example
Write:
1. Inorder Traversal:
2. Preorder Traversal:
3. Postorder Traversal:

Solution
Write:
1. Inorder Traversal: 4, 2, 5, 1, 3
2. Preorder Traversal: 1, 2, 4, 5, 3
3. Postorder Traversal: 4, 5, 2, 3, 1

Construction of Binary Tree
Using Inorder & Preorder Traversals
 Example:
 Inorder traversal = {4, 2, 5, 1, 3, 6}
 Preorder traversal = {1, 2, 4, 5, 3, 6}
 Given: Inorder and Preorder traversals of a binary tree,
Construct binary tree and Find Postorder traversal.
 Solution: Postorder traversal is {4, 5, 2, 6, 3, 1}

 Binary tree:

Construction of Binary Tree
Using Inorder & Postorder Traversals
 Example:
 Inorder traversal = {4, 2, 5, 1, 3, 6}
 Postorder traversal = {4, 5, 2, 6, 3, 1}
 Given: Inorder and Postorder traversals of a binary tree,
Construct binary tree and Find Preorder traversal.
 Solution: Preorder traversal is {1, 2, 4, 5, 3, 6}

 Binary tree:

Thank You

UIT-RGPV
Topic: Representation of Binary Trees

in Memory

Representation of Binary Trees in
Memory
1. Sequential/Array Representation of Binary Trees
2. Linked Representation of Binary Trees

Sequential/Array Representation of
Binary Trees

Binary Trees
 Let us consider that we have a tree T.
 let our tree T is a binary tree that is complete binary tree.
Then there is an efficient way of representing T in the
memory called the sequential representation or array
representation of T.
 This representation uses only a linear array TREE as follows:
 The root N of T is stored in TREE [1].
 If a node occupies TREE [k] then its left child is stored
in TREE [2 * k] and its right child is stored into TREE
[2 * k + 1].
Note: Parent node of node k is at location:


4
└ ┘k/2
Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV, Bhopal
Binary Trees
 Maximum Number of nodes at level “i” = 2i
 Maximum Number of Nodes possible in a Complete Binary
Tree
=
Where n is maximum Level number.

 In a full complete binary tree of height 'h' there are 2(h+1) - 1
nodes.

Binary Trees
 Example-1:
 sequential representation is as follow:

Binary Trees
 Example-2:
 sequential representation is as follow:

Linked Representation of Binary Trees

 To represent a binary tree, each Node of a Linked List is
consisting of three fields:
1. Data Field
2. Left Link Field (For Left Child)
3. Right Link Field (For Right Child)

The Logical representation of the
node is C-Code
struct node
{
int data;
struct node *left_Child;
struct node *right_Child;
};

Example-1:
Consider the following Binary Tree:


Example-2:

Thank You

UIT-RGPV
Topic: Binary Search Tree (BST)

Binary Search Tree (BST)
A Binary Search Tree (BST) is a tree in which all the nodes
follow the following properties:
1. The value of the key of the left sub-tree is less than the
value of its parent (root) node's key.
2. The value of the key of the right sub-tree is greater
than or equal to the value of its parent (root) node's
key.
 Thus, in BST relation between key values of node and its
left sub-tree and the right sub-tree can be defined as:
left_subtree (keys) < node (key) ≤ right_subtree (keys)

Binary Search Tree: Example
The root node key (27) has all less-valued keys on the left
sub-tree and the higher valued keys on the right sub-
tree.

Advantages of using Binary Search Tree
I. Searching become very efficient in a binary search tree
since, we get a hint at each step, about which sub-tree
contains the desired element.
II. Searching an element in a binary search tree takes
O(log2n) time. In worst case, the time it takes to search
an element is O(n).
III. It also speed up the insertion and deletion operations as
compare to that in array and linked list.

Basic Operations Performed on
Binary Search Tree
Following are the basic operations performed on BST:
 Searching: Searches an element in a BST.
 Insertion: Inserts an element in a BST.
 Deletion: Delete an element from BST
 Pre-order Traversal: Traverses a BST in a pre-order manner.
 In-order Traversal: Traverses a BST in an in-order manner.
 Post-order Traversal: Traverses a BST in a post-order manner.

Searching and Inserting in Binary
Search Trees

Binary Search Tree Before Insertion
Insert an ITEM = 20 in given BST.

Binary Search Tree Before Insertion
Insert an ITEM = 20 in given BST.
Apply Insertion Algorithm:

Binary Search Tree After Insertion
BST after inserting ITEM = 20

Inserting Data Elements into an
Empty Binary Search Tree
OR
Construction of Binary Search Tree

Construction of Binary Search Tree

Deleting an Element in a Binary
Search Tree

Search Tree

Search Tree
Example:
Case-1: Delete: 44

Search Tree
BST after deletion of 44

Search Tree
Example:
Case-1I: Delete: 75

Search Tree

Search Tree
Example:
Case-III: Delete: 25

Search Tree

Thank You

UIT-RGPV
Topic: Construction of BST using

Preorder/Postorder Traversals

Construction of BST using
Preorder Traversal

BST Construction using Preorder
Traversal
Example: Given Preorder Traversal:
10, 9, 23,15, 27, 25, 50, 40, 29, 95, 60
Construct BST and also find Postorder Traversal.
Solution:
 In Preorder Traversal first Node is the Root Node
 Start scanning from left to right in case of Preorder
Traversal..

BST Construction using Preorder
Traversal

Find Postorder Traversal
Postorder Traversal: 9, 15, 25, 29, 40, 60, 95, 50, 27, 23, 10

Construction of BST using
Postorder Traversal

BST Construction using Postorder
Traversal
Example: Given Postorder Traversal:
10, 9, 23, 27, 25, 15, 50, 95, 60, 40, 29
Construct BST and also find Preorder Traversal.
Solution:
 In Postorder Traversal last Node is the Root Node
 Start scanning from right to left if Postorder Traversal is
given.

BST using Postorder Traversal

Preorder Traversal
Preorder Traversal: 29, 15, 9, 10, 25, 23, 27, 40, 60, 50, 95
Note: In BST, Inorder Traversal gives Sorted List:
9, 10, 15, 23, 25, 27, 29, 40, 50, 60, 95

Thank You

UIT-RGPV
Topic: AVL Search Trees

Drawback of Skewed Binary Search
Tree
Drawback of Skewed Binary Search Tree is that the worst
case time complexity of a search is O(n).
For Example:

Overcome the Drawback of Skewed
Binary Search Tree
 Therefore there arises the need of the binary search tree
to be of balanced height.
 By balancing the height, it is possible to obtain a searching
time complexity of O(log n) in the worst case.

AVL Tree
(Named after inventors
Adelson-Velsky & Landis)

AVL Tree
 AVL tree can be defined as follows:
1. An empty binary tree is an AVL tree.
2. A non empty binary tree T is an AVL tree iff the balance
factor at each node can be either -1, 0 or 1.
Balance Factor:
 Let TL and TR be the left and right subtrees of T and
h(TL) and h(TR) be the heights of subtrees TL and TR
respectively then
Balance Factor = h(TL) - h(TR)
NOTE: For AVL Tree |h(TL) - h(TR)| <= 1

AVL Tree
Example:

AVL Search Tree

AVL Search Tree
An AVL search tree is a binary search tree which holds the
properties of an AVL tree.

Insertion in AVL Search Tree
1. Inserting an element in AVL search tree is similar to that
of binary search tree.
2. If after insertion balance factor of any node in the tree
is affected so as to render the binary search tree
unbalanced, we resort to techniques called Rotations.
Pivot Node: It is the first node (near to newly inserted
node) in the search path of newly inserted node whose
balance factor becomes ± 2 after insertion.

Rotations
 Single Rotations:
1. LL Rotation: Inserted node is in the left subtree of left
child of pivot node A.
2. RR Rotation: Inserted node is in the right subtree of
right child of pivot node A.
 Double Rotations:
1. LR Rotation: Inserted node is in the right subtree of
left child of pivot node A.
2. RL Rotation: Inserted node is in the left subtree of
right child of pivot node A.

Single Rotations

1. LL Rotation
Balancing of AVL Search Tree through LL Rotation:

Example of LL-Rotation

2. RR-Rotation

Example of RR-Rotation

Double Rotations

1. LR Rotation

Example of LR-Rotation

Thank You

UIT-RGPV
Topic: Deletion in AVL Search Trees

Deletion in AVL Search Trees
 On deletion of node X from AVL search tree, let A be the
closest ancestor node on the path from X to the root node,
with balance factor +2 or -2)
 Note: A is Pivot node.
 Depending on the value of Balance Factor(B),where B is the
root of the left or right subtree of A, Following Rotations can
be apply:
 R0 Rotation
 R1 Rotation
 R-1 Rotation
 L0 Rotation
 L1 Rotation
 L-1 Rotation

R0 Rotation

Example: R0 Rotation

R1 Rotation

Example: R1 Rotation

R-1 Rotation

Example: R-1 Rotation

Thank You

UIT-RGPV
Topic: M-Way Search Trees

M-Way Search Tree
Definition:
• An m-way search tree T may be an empty tree.
• If T is non empty, then it satisfies the following properties:
1. A node is consisting of key values and child nodes pointer.
2. Each node has at most m-child nodes (i.e. order of tree).
3. If a node has k-child nodes, where k <= m, then the node can
have only (k-1) keys, k1 , k2 , … , kk-1 such that ki < ki+1
4. For a node P0, (k1, P1), (k2, P2), … , (km-1, Pm-1)
(a). All key values in the subtree pointed to by Pi are
less than the key ki+1 where 0<= i <= m-2.
(b). All key values in the subtree pointed to by Pm-1 are
greater than key km-1
5. Each subtrees are also m-way search tree.
M-Way Search Tree
IMP Points:
 In a m-way search tree, a node can have:
 Maximum number of child nodes = m
 Maximum number of keys = m-1
 Order of tree = m
NOTE: Height “h” of m-way search tree is:
logm(n+1) ≤ h ≤ n
Where n is number of keys and m is the order
of tree.
M-Way Search Tree (Example)

Searching, Insertion and Deletion
in M-Way Search Tree

Searching in M-Way Search Tree

Insertion in M-Way Search Tree
Given 5-way search tree
 Insert 6 and 146

Deletion in M-Way Search Tree
Delete 262 from given m-way search tree.

Deletion in M-Way Search Tree
After Deletion of 262

Construction of M-Way Search
Tree

Construction of M-Way Search Tree
Example-1: A 3-way search tree constructed out of an
empty search tree with the following keys:
D, K, P, V, A, G

Example-2:Construct 3-way search tree for the
following list of keys:
List A: 10, 15, 20, 25, 30, 35, 40, 45
List B: 20, 35, 40, 10, 15, 25, 30, 45
NOTE: Height h of m-way search tree is:
logm(n+1) ≤ h ≤ n
Where n is number of keys and m is the order
of tree.

Construction of 3-Way Search Tree
List A: 10, 15, 20, 25, 30, 35, 40, 45
3-Way Search Tree for List A:

List B: 20, 35, 40, 10, 15, 25, 30, 45
This m-way search is height balanced (i.e. height is

close to logm(n+1)).
IMP Points (M-Way Search Tree)
IMP Points :
 M-way search tree have the advantage of
minimizing file accesses due to their restricted
height.
 However it is essential that the height of the tree be
kept as low as possible(i.e close to logm(n+1)) and
therefore there arises the need to maintain balanced
m-way search tree.
 Such balanced m-way search tree is called B-Tree.

Thank You

UIT-RGPV
Topic: B-Trees

B-Tree (Definition)

Example of B-Tree
B-Tree of order-5

Searching and Insertion
in B-Tree

Searching in B-Tree
 Searching for a key in a B-tree is similar to the one
on an m-way search tree.
 The number of accesses depends on the height h of
the B-tree.

Insertion in B-Tree (Example)
 Insert following elements into empty B-tree of order 3.
5, 10, 12, 13, 14, 1, 2, 3, 4
Solution:

Insertion in B-Tree (Example) Cont…





Practice Questions

Practice Question-1
 Consider the B-tree of order 5 as shown bellow.
 Insert the elements 4, 5, 58, 6 in the order given.

Given B-Tree

Construction of B-Tree

Example: Construct a B-tree of order 3 (2-3 tree) by
inserting the following keys in the order
(given bellow) into an empty B-tree:
M, Q, A, N, P, W, X, T, G, E, J

Step-1: Insert M, A, Q

Step-2: Insert N, P

Step-3: Insert W, X

Step-4: Insert T

Step-5: Insert G, E, J

Homework: Construct a B-Tree of order 5 for the
following order of elements:
1, 12, 8, 2, 25, 6, 14, 28, 17, 7, 52, 16, 48,
68, 3, 26, 29, 53, 55, 45
Solution: B-Tree of order-5 is:

Thank You

UIT-RGPV
Topic: Huffman’s Coding

Huffman’s Coding
 Huffman coding is lossless data compression algorithm.
 In this algorithm a variable-length code is assigned to
input different characters.
 The code length is related with how frequently characters
are used.
 Most frequent characters have smallest codes, and longer
codes for least frequent characters.

Huffman’s Coding
 There are mainly two major parts in Huffman Coding
1) Build a Huffman Tree.
2) Traverse the Huffman Tree and assign codes to each
data item/element/file.

Huffman’s Tree
 Objective: To determine the optimal way to pair-wise
merge n-sorted files.
 Objective Function:
 Where:
 P is weighted path length (we want minimize it)
 Wi and Li denotes respectively the weight and path length
of an external node Ni.

Huffman’s Tree

Huffman’s Algorithm

Huffman’s Algorithm

Huffman’s Tree

Huffman’s Tree

Huffman’s Tree

Huffman’s Coding
Variable length coding:

Huffman’s Coding
Example-2: Suppose we want to encode a text with the

characters a, b, c, d, e, f, g occurring with the following
frequency.

Huffman’s Coding

Huffman’s Coding

Huffman’s Coding

Huffman’s Coding

Huffman’s Coding

Huffman’s Coding

Huffman’s Coding

Huffman’s Coding

Huffman’s Coding

Huffman’s Coding

Huffman’s Coding

Huffman’s Coding

Huffman’s Coding

Huffman’s Coding

Huffman’s Coding

Huffman’s Coding

Huffman’s Coding

Huffman’s Coding

Huffman’s Coding

Thank You

UIT-RGPV
Topic: Searching Techniques

Searching
 Searching is an operation or a technique that helps to
finds the place of a given element or value in the list.
 Any search is said to be successful or unsuccessful
depending upon whether the element that is being
searched is found or not.
 Some of the standard searching technique that is
being followed in the data structure are listed below:
1. Linear Search or Sequential Search
2. Binary Search

1. Linear Search
or
Sequential Search

Linear Search or Sequential Search
 This is the simplest method for searching.
 In this technique of searching, the element is searched
sequentially in the list.
 This method can be performed on a sorted or an
unsorted list (usually Arrays).
 Example: Search 35 in given List: 10, 5, 15, 20, 25, 35.

Linear Search or Sequential Search
 In case of a sorted list searching starts from 0th element
and continues until the element is found from the list or
the element whose value is greater than (assuming the list
is sorted in ascending order), the value being searched is
reached.
 As against this, searching in case of unsorted list also
begins from the 0th element and continues until the
element found or the end of the list is reached.

Linear Search Algorithm

Linear Search Algorithm
Example:
Array DATA: 11, 40, 44, 55, 22, 30, 33, 60, 77, 88, 99, 80
Search an ITEM = 99
Solution:
 Apply Sequential Search
 Compare each array element with ITEM till
element found.
 ITEM is found at LOC = 11

Time Complexity of Linear Search Algorithm
 Time Complexity of Linear Search is: O(n)

 Where n is number elements in given list.

2. Binary Search

Binary Search
 Binary search is a very fast and efficient searching technique.
 It requires the list to be in sorted order.
 In this method, to search an element you can compare it with
the present element at the center of the list. If it matches, then
the search is successful otherwise the list is divided into two
halves: one from the 0th element to the middle element which
is the center element (first half) another from the center
element to the last element (which is the 2nd half) where all
values are greater than the center element.
 The searching mechanism proceeds from either of the two
halves depending upon whether the target element is greater
or smaller than the central element. If the element is smaller
than the central element, then searching is done in the first
half, otherwise searching is done in the second half.

Binary Search Algorithm

Example:
Given sorted List of 13 data elements:
Array DATA: 11, 22, 30, 33, 40, 44, 55, 60, 66, 77, 80, 88, 99
Search an ITEM = 40.
Solution: To Search ITEM = 40 we apply the Binary Search

Algorithm.

Time Complexity of Binary Search Algorithm
 Time Complexity of Binary Search is: O(log2n)

 Where n is number elements in given list.

Thank You

UIT-RGPV
Topic: Sorting Techniques (Part-1)

Sorting
 Sorting refers to the operation or technique of arranging
and rearranging sets of data in some specific order.
 A collection of records called a list where every record
has one or more fields. The fields which contain a unique
value for each record is termed as the key field.
 Sorting is the operation performed to arrange the
records of a table or list in some order according to
some specific ordering criterion. Sorting is performed
according to some key value of each record.
 The records are either sorted either numerically or
alphanumerically. The records are then arranged in
ascending or descending order depending on the
numerical value of the key.
Categories of Sorting
 The techniques of sorting can be divided into two
categories.These are:
1. Internal Sorting
2. External Sorting
 Internal Sorting: If all the data that is to be sorted can be
adjusted at a time in the main memory, the internal sorting
method is being performed.
 External Sorting: When the data that is to be sorted
cannot be accommodated in the memory at the same time
and some has to be kept in auxiliary memory such as hard
disk, floppy disk, magnetic tapes etc, then external sorting
methods are performed.
The Complexity of sorting algorithm
 The complexity of sorting algorithm calculates the
running time of a function in which 'n' number of items
are to be sorted.
 The choice for which sorting method is suitable for a
problem depends on several dependency configurations
for different problems. The most noteworthy of these
considerations are:
1. The length of time spent by the programmer in
programming a specific sorting program
2. Amount of machine time necessary for running the
program
3. The amount of memory necessary for running the
program
Efficiency of Sorting Techniques
 To get the amount of time required to sort an array of 'n'
elements by a particular method, the normal approach is
to analyze the method to find the number of comparisons
(or exchanges) required by it.
 Most of the sorting techniques are data sensitive, and so
the metrics for them depends on the order in which they
appear in an input array.
 Various sorting techniques are analyzed in various cases
and named these cases as follows:
1. Best case
2. Worst case
3. Average case

Types of Sorting
 Insertion Sort
 Selection Sort
 Bubble Sort
 Radix sort
 Merge Sort
 Quick Sort
 Heap Sort

1. Insertion Sort

Insertion Sort
 Insertion sort is a simple sorting algorithm that works
similar to the way you sort playing cards in your hands.
 The array is virtually split into a sorted and an unsorted
part.
 Values from the unsorted part are picked and placed at
the correct position in the sorted part.
 Note: Insertion sort is frequently used when number of
elements (i.e. n) are small.

Insertion Sort Procedure

Insertion Sort Algorithm

Insertion Sort: Example

Time Complexity of Insertion Sort

2. Selection Sort

Selection Sort

Selection Sort: Example

Selection Sort: Algorithm

Time Complexity of Selection Sort

3. Bubble Sort

Selection Sort: Algorithm

Bubble Sort: Example
 Bubble Sort is the simplest sorting algorithm that works
by repeatedly swapping the adjacent elements if they are
in wrong order.
 Example: Given array elements: 5 1 4 2 8
 First Pass:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares
the first two elements, and swaps since 5 > 1.
(1 5 4 2 8 ) –> (1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are
already in order (8 > 5), algorithm does not swap them.

Bubble Sort
 Second Pass:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does
not know if it is completed. The algorithm needs
one whole pass without any swap to know it is sorted.

Bubble Sort
 Third Pass:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Forth Pass:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) No Change List is sorted.
Note: Bubble sort take (n-1) passes to sort a list of n elements.

Time Complexity of Bubble Sort

Thank You

UIT-RGPV
Topic: Sorting Techniques (Part-2)

Types of Sorting
 Insertion Sort
 Selection Sort
 Bubble Sort
 Radix sort
 Merge Sort
 Quick Sort
 Heap Sort

4. Radix sort

Radix sort: Example

Pass: 2

Pass: 3
After Third Pass we get sorted list:

128, 143, 321, 348, 361, 366, 423, 538, 543

Explanation

Radix sort

5. Merge Sort

Merge Sort

Merge Sort

Thank You

UIT-RGPV
Topic: Collision Resolution Techniques

(in Hashing)

Collision

Collision
 Collision is a situation in which the hash function returns
the same hash key for more than one record.
 Suppose we want to add a new record R with key k to
our file F, but suppose the memory location address H(k)
is already occupied.This situation is called collision.
 Sometimes when we are going to resolve the collision it
may lead to a overflow condition and this overflow and
collision condition makes the poor hash function.

Collision Resolution
Techniques

Collision Resolution Techniques
 If there is a problem of collision occurs then it can be
handled by apply some technique. These techniques are
called as collision resolution techniques.
 There are generally four techniques which are described
below:
1. Chaining
2. Linear Probing
3. Quadratic Probing
4. Double Hashing

1. Chaining

Chaining
 Chaining is a method in which additional field with data
i.e. chain is introduced.
 A chain is maintained at the home bucket.
 In this when a collision occurs then a linked list is
maintained for colliding data.

Chaining: Example
 Example: Let us consider a hash table of size 10 and we apply a
hash function of H(key)= key % size of table. Let us take the
records to be inserted are 31, 33, 77, 61.
 Solution:
In this diagram we can see at
same bucket 1 there are two
records which are maintained
by linked list or we can say
by chaining method.

2. Linear Probing

Linear Probing
 It is very easy and simple method to resolve or to handle
the collision.
 In this collision can be solved by placing the second
record linearly down, whenever the empty place is found.
 Drawback: In this method there is a problem of clustering
which means at some place block of a data is formed in a
hash table.

Linear Probing (Example)
 Example:
Let us consider a hash table of size 10 and hash function
is defined as H(key) = key % table size.
Consider that following keys are to be inserted that are:
56, 64, 36, 71.

Linear Probing: Example
Solution:
In this diagram we can see that 56 and 36
need to be placed at same bucket but
by linear probing technique the records
linearly placed downward if place is
empty i.e. it can be seen 36 is placed
at index 7.

3. Quadratic Probing

Quadratic Probing
 This is a method gives solution of clustering problem
which is occur in linear probing.
 In this method the hash function is defined by the
H(key)= (key % table size) = h
 if collision is occur for address h then instead of searching
locations with addresses h, h+1, h+2, …. (in linear way)
we search locations with addresses: h, h+1, h+4, h+9,
h+16,……, h+i2 (i.e. put i = 0, 1, 2….).

Quadratic Probing: Example
 Example: Let us consider we have to insert following
elements that are: 67, 90, 55,17, 49.
 Solution: In this we can see if we insert
67, 90, and 55 it can be inserted
easily but at case of 17
hash function is used in such a
manner that :
 H(17) = 17%10 = 7 now collision is
Occur then search locations 7+0,
7+1, 7+4……. Hence we place
it at location 8.
4. Double Hashing

Double Hashing
 It is a technique in which two hash function are used when
there is an occurrence of collision. In this method first
hash function is simple as same as division method. But
for the second hash function there are two important rules
which are
1. It must never evaluate to zero.
2. Must sure about the buckets, that they are probed.
 The hash functions for this technique are:
 H1(key) = key % table size
 H2(key) = P-(key mod P)
 Where, p is a prime number which should be taken
smaller than the size of a hash table.

Double Hashing: Example
 Example: Let us consider we have to insert 67, 90, 55, 17, 49.
 Solution:
In this we can see 67, 90 and 55 can be inserted
in a hash table by using first hash function but
in case of 17 again the bucket is full and in this
case we have to use the second hash function
which is H2(key) = P - (key mode P) here p is
a prime number which should be taken smaller
than the hash table so value of p will be the 7.
i.e. H2(17)=7 - (17%7) = 7 - 3 = 4
that means we have to take 4 jumps for placing
the 17.
Therefore 17 will be placed at index 1.
Thank You

UIT-RGPV
Topic: Heap and Heap Sort

Heap
 Heap is a binary tree data structure which satisfies two
additional properties:
1. Shape Property: Heap is a Complete binary tree.
2. Heap Property: Each node value is greater than or
equal to each of its child node value.
OR
Each node value is less than or equal to each of its child
node value.

Heap
 A complete binary tree is a special binary tree in which
have following properties:
 Every level, except possibly the last, is completely filled.
 All the nodes are as far left as possible.
For Example:

Types of Heap
 Heap can be classified on the basis of heap property as:
1. Max Heap
2. Min Heap
 Max Heap: The value at node N is greater then or equal

to the value of children/s of N.
 Min Heap: The value at node N is less then or equal to

the value of children/s of N.

Max Heap
 The value at node N is greater then or equal to the value
of children/s of N.

Min Heap
 The value at node N is less then or equal to the value of
children/s of N.

Inserting an Element into Heap

Inserting into Heap
Example-1: Suppose H is a heap with N elements, and
suppose an ITEM of information is given.
We insert ITEM into heap H as follows:
1. First add ITEM at the end of heap H so that H is still a
complete binary tree, but not necessarily a heap.
2. Then let ITEM rise to its “appropriate place” in H so
that H is finally a heap (This process is called
Heapify/Reheaping).

Example-1: Insert 70 into given Max Heap

 First we add 70 as the next element in the complete binary tree;
that is, we set TREE[21] = 70.
 Then 70 is the right child of TREE[10]=48.
 The path from 70 to root of H is shown below:
 Now Heapify/Reheaping: Compare 70 with its parent and place it
to its correct position.

 Finally we get Max Heap, after insertion of 70.

Construction of Heap

Example-2: Construction of Heap
Example-2: Suppose we want to build a max heap H from the
following list of numbers:
44,30, 50, 22, 60, 55, 77, 55
Solution: First add element as next node of complete binary tree.
Then apply Heapify process to reconstruct heap.
Steps:

Example-2: Construction of Heap cont…

Example-2: Construction of Heap cont…
Finally we get Max Heap.

Deleting the Root of a Heap

Deleting the Root of a Heap
Suppose H is a heap with N elements and we want to delete the root
R of H. This is accomplished as follows:
1. Assign the root R to some variable ITEM.
2. Replace the deleted node R by the last node L of H, so that H is
still a complete binary tree, but not necessarily a heap.
3. (Reheap) Let L sink (go downwards) to its appropriate place in H
so that H is finally a Heap.

Deleting the Root of a Heap cont…
Example: Consider the following Max Heap H, and we want to
delete root node R = 95.

Solution:
 First identify the last element L = 22 in the Heap.
 Delete Root node R=95 and Place L=22 at root position.
 Apply Heapify/Reheaping process.


Heap Sort

Heap Sort
 Heap sort processes the elements by creating the min heap or
max heap using the elements of the given array.
 Min heap or max heap represents the ordering of the array in
which root element represents the minimum or maximum
element of the array.
 At each step, the root element of the heap gets deleted and
stored into the sorted array and the heap will again be heapified.

Heap Sort Algorithm
 The heap sort algorithm is consisting of two phases and
recursively performs two main operations.
 Phase-1 Operation: Build a heap H, using the elements of
Array.
 Phase-2 Operation: Repeatedly delete the root element of the
heap formed in phase-1.

Heap Sort
Example: Sort the following Array using Heap Sort:
Array[N] = 8, 3, 11, 5, 4, 15
Solution:
Step-1: Construct Max Heap for given Array.
Step-2: Assign the root R to some variable ITEM and set A[N+1] =
ITEM.
Step-3: Replace the deleted node R by the last node L of H, so that H
is still a complete binary tree, but not necessarily a heap.
Step-4: (Reheap) Let L sink (go downwards) to its appropriate place
in H so that H is finally a Heap.
Step-5: Repeat step-1 to step-4 till Heap contain only one element.

Heap Sort

Heap Sort

Heap Sort

Heap Sort
Now Array A = 15, 5, 11, 3, 4, 8

Heap Sort
Now, Perform Heap Sort on Array[1 to 6].
After this condition of Array: A = 11, 5, 8, 3, 4, , 15

Heap Sort
Again Apply Heap Sort on Array[1 to 5].
After this condition of Array: A = 8, 5, 4, 3, , 11 , 15

Heap Sort
After this condition of Array: A = 5, 3, 4, , 8 , 11 , 15

Heap Sort
After this condition of Array: A = 4, 3, , 5, 8, 11, 15

Heap Sort
After this condition of Array: A = 3, , 4, 5, 8, 11, 15

Heap Sort
Now one Heap contain only element, delete it from heap root and
place it at Array[2].
After this condition of Array: A = , 3, 4, 5, 8, 11, 15

Now Array is Sorted.

Time Complexity of Heap Sort
 Heap Sort time complexity is O(n log2 n)

Thank You

UIT-RGPV
Topic: Hashing

Hashing
 There are many possibilities for representing the
dictionary and one of the best methods for representing
is hashing.
 Hashing is also called Hash Addressing.
 Hashing is independent of number of entries/records (n).
 Hashing is a technique which uses less key comparisons
and searches the element in O(n) time in the worst case
and in an average case it will be done in O(1) time.
 This method generally used the hash functions to map the
keys into a table, which is called a hash table.

Hash table
 Hash table is a type of data structure which is used for
storing and accessing data very quickly.
 Insertion of data in a table is based on a key value.
 Hence every entry in the hash table is defined with some
key.
 By using this key, data can be searched in the hash table
by few key comparisons and then searching time is
dependent upon the size of the hash table.

Hash function
 Hash function is a function which is applied on a key by which
it produces an integer, which can be used as an address (index)
of hash table.
H: K → L
 Where H represent Hash Function or Hashing Function, K is a

set of Keys and L is set of Memory Address/Locations.
 Hash function gives mapping from K to L.
 Hence one can use the same hash function for accessing the
data from the hash table.
 In this the integer returned by the hash function is called hash
key.

Principal Criteria to Select Hash Function
The two principal criteria used in selecting a hash function

H: K → L are as follows:
1. The function H should be very easy and quick to
compute.
2. The function H should, as for as possible, uniformly
distribute the hash addresses throughout the set L, so
that there are a minimum number of collisions.
Note: There is no guarantee that the second condition can
be completely fulfilled without actually knowing the
keys and addresses.

Types of Hash Function
There are various types of hash function which are used to
place the data in a hash table.
1. Division Method
2. Mid Square Method
3. Digit Folding Method

1. Division Method

1. Division Method
 Choose a number m larger than the number n of keys in K.
(Number m is usually chosen to be a prime number since
this minimize number of collisions)
 The Hash Function H is defined by:
H(k) = k (mod m)
or
H(k) = k (mod m) + 1
 Here k(mod m) denotes the remainder when k is divided
by m.
 The second formula is used when we want hash addresses
(indexes) to range from 1 to m rather than from 0 to m-1.
Division Method: Example
 For example: If the records are: 52, 68, 99, 84 is to be
placed in a hash table and let us take the table size is 10.
 Then use Hash Function: H(k) = k(mod m)
 We use m = 10 (i.e. table size)
 H(k) = record % table size
H(52) = 52%10 = 2
H(68) = 68%10 = 8
H(99) = 99%10 = 9
H(84) = 84%10 = 4


 In this method firstly key is squared and then mid part of
the result is taken as the index.
H(k) = l
 Where l is obtained by deleting digits from both ends of k2
 For example: consider that if we want to place a record of
3101 and the size of table is 1000.
 So 3101*3101=9616201
 i.e. H (3101) = 162 (middle 3 digit)


 In this method the key is divided into separate parts (two
or more) and by using some simple operations these parts
are combined to produce a hash key.
For example-1: consider a record of 12465512 then it will
be divided into parts i.e. 124, 655, 12. After dividing the
parts combine these parts by adding them.
 H(key) = H(12465512) = 124 + 655 + 12 = 791
Example-2: Chopping the key into two parts and adding
yield the following addresses:
 H(key) = H(3205) = 32 + 05 = 37
 H(7148) = 71 + 48 = 19

Characteristics of
Good Hashing Function

Characteristics of Good Hashing Function
1. The hash function should generate different hash values
for the similar string.
2. The hash function is easy to understand and simple to
compute.
3. The hash function should produce the keys which will
get distributed, uniformly over an array.
4. A number of collisions should be less while placing the
data in the hash table.
5. The hash function is a perfect hash function when it
uses all the input data.

Thank You

UIT-RGPV
Topic: Sequential Representations

of Graph

Sequential Representations of Graph
 Graphs are commonly represented in two ways:
1. Adjacency Matrix
2. Adjacency List (Linked Representation)

Adjacency Matrix Representation
 An adjacency matrix is a VxV binary matrix A. Where V is
number of vertices/Nodes in Graph G.
 In adjacency matrix, value of an element Ai,j is 1 if there is
an edge from vertex i to vertex j else Ai,j is 0.
 Note: A binary matrix is a matrix in which the cells can
have only one of two possible values - either 0 or 1.
 In an undirected graph, if Ai,j = 1, then Aj,i = 1. In a directed
graph, if Ai,j = 1, then Aj,i may or may not be 1.

Adjacency Matrix Representation
 Adjacency matrix provides constant time access (O(1) ) to
determine if there is an edge between two nodes.
 Space complexity of the adjacency matrix is O(V2).

Example-1: Adjacency Matrix for Directed Graph

Example-2: Adjacency Matrix for Undirected Graph
The adjacency matrix for an undirected graph:

Adjacency List Representation
of Graph

Example: Adjacency List Representation of Graph
 Adjacency List Representation is more efficient as

compared to adjacency matrix representation.
 For a given graph G with n vertices and e edges,
adjacency list opens n head nodes corresponding to
the n vertices of graph G, each of which points to a
singly linked list of nodes, which are adjacent to the
vertex representing the head node
 For Example: See next slide.

Example-1: Adjacency List Representation of
Directed Graph

Example-2: Adjacency List Representation of
Undirected Graph

Thank You

UIT-RGPV
Topic: BFS (Breadth First Search)

Graph Traversal Technique

Graph Traversal
 Graph Traversal (also known as Graph Search) refers
to the process of visiting each vertex in a graph.
 Such traversals are classified by the order in which the
vertices are visited.
 Tree traversal is a special case of graph traversal.

Graph Traversal Techniques
 There are two graph traversal techniques/algorithms:
1. BFS (Breadth First Search)
2. DFS (Depth First Search)
 During the execution of algorithms, each node N of graph G will

be in one of three states, called the status of node N, as follows:
❑ STATUS = 1: (Ready state) The initial state of the node N.
❑ STATUS = 2: (Waiting state) The node N is on the queue or
stack, waiting to be processed.
❑ STATUS = 3: (Processed state) The node N has been
processed.

BFS (Breadth First Search)

BFS (Breadth First Search)
 The general idea behind BFS, beginning at a starting node
A is as follows:
 First we examine the starting node A.
 Then we examine all the neighbors of A.
 Then we examine all the neighbors of the neighbors of A.
 And so on...
Note:
 We need to keep record of neighbors of a node.
 No node is processed more than once.
 A queue is used to hold nodes that are waiting to be
processed and by using a field STATUS which tells us the
current status of any node.
Breadth First Search Algorithm

BFS: Example
 Traverse the given graph using BFS. Start from Node: 2

First Construct Adjacency List, Initialize
Visited Table and Queue

Step-1

Step-2:

Step-3:

Step-4:

Step-5:

Step-6:

Step-7:

Step-8:

Step-9:

Step-10:

Step-11:

Application of BFS

Example

Solution

Example

Thank You

UIT-RGPV
Topic: DFS (Depth First Search)

Graph Traversal Technique

DFS (Depth First Search) Algorithm
The general idea behind DFS beginning at a starting node

A is as follows:
 First we examine the starting node A
 Then we examine each node N along a path P which begins
at A: that is, we process a neighbor of node A, then a
neighbor of neighbor of A and so on.
 After coming to “dead end” that is, to the end of the path,
we backtrack on path P until we can continue along another
Path P’. And so on.
 Note: DFS if similar to the inorder traversal of a binary
tree.
 DFS use Stack.


 This algorithm will process only those nodes which are

reachable from the starting node A.
 If we want to examine all nodes in graph G, then the
algorithm must be modified so that it begins again with
another node B– that is still in the ready state.
 This node B can be obtained by traversing the list of
nodes.

DFS: Example
Traverse the graph using DFS.

Step-1:
 Initialize all nodes to Ready State (each node have status
= 1) = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
 Remove Starting node from ready state and push into

ready stack (change its status = 2).
 Now, remaining nodes in Ready State (each node have

status = 1) = {0, 1, 3, 4, 5, 6, 7, 8, 9}


Step-2:
 Remove 2 from stack and push its all neighbors into
stack (i.e. 4, 1, 8) and remove them from ready state list:
 Put 2 into processed list.

 Processed List(Status = 3) = {2}
 Now Remaining nodes in Ready list= {0, 3, 5, 6, 7, 9}

Step-3:
 Remove stack top i.e. 8 from stack and push its all
neighbor nodes into stack (only those nodes which are in
ready list) i.e. 0 and 9:

 Processed List(Status = 3) = {2, 8}
 Now Remaining nodes in Ready list= {3, 5, 6, 7}
Step-4:
ready list) i.e. no node to push:

 Processed List(Status = 3) = {2, 8, 0}
Step-5:

 Processed List(Status = 3) = {2, 8, 0, 9}
Step-6:
ready list) i.e. 3 and 7:

 Processed List(Status = 3) = {2, 8, 0, 9, 1}
 Now Remaining nodes in Ready list= { 5, 6}
Step-7:
ready list) i.e. 6:

 Processed List(Status = 3) = {2, 8, 0, 9, 1, 7}
 Now Remaining nodes in Ready list= { 5}
Step-8:
ready list) i.e. 5:

 Processed List(Status = 3) = {2, 8, 0, 9, 1, 7, 6}
 Now Ready list is empty = { }
Step-9:

 Processed List(Status = 3) = {2, 8, 0, 9, 1, 7, 6, 5}
Step-10:

 Processed List(Status = 3) = {2, 8, 0, 9, 1, 7, 6, 5, 3}
Step-11:

 Processed List(Status = 3) = {2, 8, 0, 9, 1, 7, 6, 5, 3, 4}
Traversal Output
 Processed List(Node Status = 3) = {2, 8, 0, 9, 1, 7, 6, 5, 3, 4}

Application of DFS

Application of DFS

Solution

Application of DFS

Thank You

UIT-RGPV
Topic: Graphs

Graphs
 A Graph is a non-linear data structure.
 A Graph G = (V, E) consists of two things:
1. A set V of elements called nodes(or points or vertices)
2. A set E of edges such that each edge e in E is identified
with a unique (unordered) pairs[u, v] of nodes in V,
denoted by e = [u, v]
For Example:

Types of Graphs
 There are many flavors of graphs we use in computer
science. We discuss some of them here:
1. Directed and Undirected Graph
2. Weighted and Unweighted Graph
3. Simple and Non-Simple (Multi-Graph) Graph
4. Cyclic and Acyclic Graph
5. Complete Graph
6. Connected Graph

1. Directed and Undirected Graph
 Directed graph:
 Undirected graph:

2. Weighted and Unweighted Graph
 Weighted Graph:
 Unweighted Graph:

3. Simple and Non-Simple Graph
 Simple Graph:
 Non-Simple Graph:

4. Acyclic and Cyclic Graph
 Acyclic Graph:
 Cyclic Graph:

5. Complete Graph
 Complete Graph: Every two vertices are adjacent
(all edges that could exist are present).

6. Connected Graph
 Connected Graph: It has path between every pair
of vertices (There are no unreachable vertices).

Most Commonly Terms
used in Graphs

Most Commonly Terms used in Graphs
 An edge is (together with vertices) one of the two basic units out
of which graphs are constructed. Each edge has two vertices to
which it is attached, called its endpoints.
 Two vertices are called adjacent if they are endpoints of the same
edge.
 Outgoing edges of a vertex are directed edges that the vertex is
the origin.
 Incoming edges of a vertex are directed edges that the vertex is
the destination.
 The degree of a vertex in a graph is the number of edges incident
to it.
 In a directed graph, outdegree of a vertex is the number of
outgoing edges from it and indegree is the number of incoming
edges.
Most Commonly Terms used in Graphs cont…
 A vertex with indegree zero is called a source vertex, while a
vertex with outdegree zero is called sink vertex.
 An isolated vertex is a vertex with degree zero; that is, a
vertex that is not an endpoint of any edge.
 Path is a sequence of alternating vertex and edges such that
each successive vertex is connected by the edge.
 Cycle is a path that starts and end at the same vertex.
 Simple path is a path with distinct vertices.
 A graph is Strongly Connected if it contains a directed
path from u to v and a directed path from v to u for every
pair of vertices u, v.

Most Commonly Terms used in Graphs cont…
 A bridge is an edge whose removal would disconnect

the graph.
 Forest is a graph without cycles.
 Tree is a connected graph with no cycles. If we remove
all the cycles from DAG(Directed acyclic graph) it
becomes tree and if we remove any edge in a tree it
becomes forest.
 Spanning tree of an undirected graph is a subgraph that
is a tree which includes all of the vertices of the graph.

Thank You

UIT-RGPV
Topic: Kruskal’s and Prim's Algorithms

(Minimum Cost Spanning Tree
Algorithms)

1. Kruskal's Algorithm

Kruskal's Algorithm
 Kruskal's algorithm to find the minimum cost spanning
tree uses the greedy approach.
 This algorithm treats the graph as a forest and every node
it has as an individual tree.
 A tree connects to another only and only if, it has the
least cost among all available options and does not violate
MST properties.

Kruskal's Algorithm
Step-1: Check given graph, if it include loop and parallel edges
then remove all loops and parallel edges (In case of
parallel edges, keep the one which has the least cost
associated and remove all others).
Step-2: Make forest of all nodes (initially forest does not
contain any edge).
Step-3: Arrange all edges in their increasing order of weight.
Step-4: Add the edge which has the least weight, iff it does not
create cycle/loop otherwise ignore it.
Step-5: Repeat Step-4 till all nodes/vertices gets connected.

Kruskal's Algorithm: Example
 To understand Kruskal's algorithm let us consider the
following example:

 Step-1: Remove all loops and Parallel Edges

 Step-2: Make forest of all nodes (initially forest does not
contain any edge).
 Consider only nodes.

 Step-3: Arrange all edges in their increasing order of
weight
 The next step is to create a set of edges and weight, and
arrange them in an ascending order of weight (cost).

 Step-4: Add the edge which has the least weight, iff it does
not create cycle/loop otherwise ignore it.




By adding edge (S, A) we have included all the nodes of the
graph and we now have minimum cost spanning tree.

2. Prim's Algorithm

Prim's Algorithm
 Prim's algorithm to find minimum cost spanning tree (as
Kruskal's algorithm) uses the greedy approach.
 Prim's algorithm, in contrast with Kruskal's algorithm,
treats the nodes as a single tree and keeps on adding new
nodes to the spanning tree from the given graph.

Prim's Algorithm
Step-1: Check given graph, if it include loop and parallel
edges then remove all loops and parallel edges (In
case of parallel edges, keep the one which has the
least cost associated and remove all others).
Step-2: Select any arbitrary node as root node.
Step-3: Check outgoing edges from all the nodes of tree
till constructed and select a new node connected
with least cost edge (select that least cost edge
which does not create any cycle).
Step-4: Repeat Step-3 till all nodes/vertices gets
connected.

Prim's Algorithm: Example
 To understand Prim's Algorithm let us consider the same
example which we use in Kruskal's Algorithm :


 Step-2: Choose any arbitrary node as root node
 In this case, we choose S node as the root node of Prim's
spanning tree. This node is arbitrarily chosen, so any node
can be the root node.

with least cost edge.
 Current tree contain only one node S(root node), we
see that (S, A) and (S, C) are two edges with weight 7
and 8, respectively.
 We choose the edge (S,A) as it is lesser than the other.



 We may find that the output spanning tree of the same graph using
two different algorithms is same.
 Prim’s and Kruskal’s Algorithms may generate different Minimum
Spanning tree if there exist more than one Minimum Spanning Tree
for given graph (But the cost of MST is Same).

Prim's Vs Kruskal's Algorithm

Prim's Algorithm Kruskal's Algorithm
The tree that we are making or The tree that we are making or
growing always remains connected. growing usually remains disconnected.
Prim’s Algorithm grows a solution Kruskal’s Algorithm grows a solution

from a random vertex by adding the from the cheapest edge by adding the
next cheapest vertex to the existing next cheapest edge to the existing
tree. tree / forest.
Prim’s Algorithm is faster for dense Kruskal’s Algorithm is faster for sparse
graphs. graphs.

Thank You

UIT-RGPV
Topic: Kruskal's Algorithm

Kruskal's Algorithm
 Kruskal's algorithm to find the minimum cost spanning
tree uses the greedy approach.
 This algorithm treats the graph as a forest and every node
it has as an individual tree.
 A tree connects to another only and only if, it has the
least cost among all available options and does not violate
MST properties.

Kruskal's Algorithm
Step-1: Check given graph, if it include loop and parallel edges
then remove all loops and parallel edges (In case of
parallel edges, keep the one which has the least cost
associated and remove all others).
Step-2: Make forest of all nodes (initially forest does not
contain any edge).
Step-3: Arrange all edges in their increasing order of weight.
Step-4: Add the edge which has the least weight, iff it does not
create cycle/loop otherwise ignore it.
Step-5: Repeat Step-4 till all nodes/vertices gets connected.

 To understand Kruskal's algorithm let us consider the
following example:


 Step-2: Make forest of all nodes (initially forest does not
contain any edge).
 Consider only nodes.

 Step-3: Arrange all edges in their increasing order of
weight
 The next step is to create a set of edges and weight, and
arrange them in an ascending order of weight (cost).

 Step-4: Add the edge which has the least weight, iff it does
not create cycle/loop otherwise ignore it.




By adding edge (S, A) we have included all the nodes of the
graph and we now have minimum cost spanning tree.

2. Prim's Algorithm

Prim's Algorithm

Prim's Algorithm
connected.










graphs. graphs.

Thank You

UIT-RGPV
Topic: Prim's Algorithm

Prim's Algorithm

Prim's Algorithm
connected.










graphs. graphs.

Thank You

UIT-RGPV
Topic: Spanning Tree

Spanning Tree
 A spanning tree is a subset (sub-graph) of connected
graph G, which includes all the vertices of the graph with
a minimum possible number of edges.
 Hence, a spanning tree does not have cycles and it cannot
be disconnected..
 The edges may or may not have weights assigned to
them.
 A graph can have more than one spanning tree.

General Properties of Spanning Tree
Following are a few properties of the spanning tree to
connected graph G:
 A connected graph G can have more than one spanning
tree.
 All possible spanning trees of graph G, have the same
number of edges and vertices.
 The spanning tree does not have any cycle (loops).
 Removing one edge from the spanning tree will make the
graph disconnected, i.e. the spanning tree is minimally
connected.
 Adding one edge to the spanning tree will create a circuit
or loop, i.e. the spanning tree is maximally acyclic.

Spanning Tree: Example
 Let's understand the spanning tree with example :
 Consider the following connected graph:
 Some of the possible spanning trees that can be created from

the above connected graph are:

 Some of the possible spanning trees are:

 The total number of spanning trees with n vertices that can
be created from a complete graph is equal to n(n-2).
 If we have n = 4, the maximum number of possible spanning
trees is equal to 44-2 = 16. Thus, 16 spanning trees can be
formed from a complete graph with 4 vertices.
 Find all 16 Spanning Trees for the above complete graph.

Minimum Cost Spanning Tree
 Minimum Cost Spanning Tree is also called Minimum
Spanning Tree (MST).
 A minimum cost spanning tree is a spanning tree in which
the sum of the weight/cost of the edges is as minimum as
possible.

Minimum Cost Spanning Tree: Example
 Example: Consider the given weighted graph:
 Construct all possible spanning trees and also find

Minimum Cost Spanning Tree.
 Solution: See Next Slide.

Solution: The possible spanning trees from the given weighted
graph are:

 Out of four spanning trees, Minimum Cost Spanning
Tree is:
 The Minimum Cost = 7

Minimum Cost Spanning Tree
Algorithms

Minimum Cost Spanning Tree Algorithms
 The minimum cost spanning tree from a graph is found
using the following algorithms:
1. Kruskal's Algorithm
2. Prim's Algorithm

Thank You

Data Structure

Uploaded by

Copyright:

Available Formats

Data Structure

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Data Structure

Uploaded by

Copyright:

Available Formats

Department of Computer Science & Engineering

Topic: Introduction to Data Structures

Course: Data Structures (CS303)

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 2

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 3

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 4

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 5

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 6

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 7

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 8

III. Abstraction: Data structure is specified by the ADT

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 10

Data Structures By Asst. Prof. Praveen

Topic: Introduction to Data Structures

Course: Data Structures (CS303)

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 2

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 6

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 7

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 8

Data Structures By Asst. Prof. Praveen

Course: Data Structures (CS303)

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 2

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 3

• The following diagram represents an integer

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 5

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 6

The various types of arrays are as follows.

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 7

• A one-dimensional array is also called a single

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 8

• When the number of dimensions specified is more

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 10

• In the two-dimensional array Arr2D[3] [4], the first index specifies

1. Traverse: print all the array elements one by

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 12

1.While using array, we must need to make the decision

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 15

Topic: Address Calculation in an Array

Course: Data Structures (CS303)

Address Calculation in One Dimensional Array

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 2

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 3

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 4

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 5

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 6

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 7

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 8

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 10

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 11

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 12

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 14

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 15

Q.2. Given an array arr[1………10][1………15] with base

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 16

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 17

• Address of A[8][6] = 100 + 1 * [15*(8 – 1) + (6 – 1)]

Ans: Address of A[8][6] = 210

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 18

Data Structures By Asst. Prof. Praveen Yadav, DoCSE, UIT-RGPV 19

c1g(n) <= f(n) <= c2g(n), for all n >= n0