FOREWORD
This is the second iteration of preparing our own courseware material, after successful completion
of a similar task undertaken a few years ago. These contents have been carefully prepared and
should serve as excellent auxiliary material for both instructors and students.
The Special Academic Group, Autonomy (SAGA) was formed for the sole purpose of preparing
courseware contents primarily in the first-year theory subjects; a few second-year subjects were
also included. The subjects for the first year were - Basic Electrical Engineering, Basic Electronics
Engineering, Computer Programming, Data Structures and Algorithms, Engineering Mathematics
I and II, Engineering Physics, Engineering Chemistry, Constitution of India, Environmental
Science and Engineering and Communicative and Technical English. For the second year, the
subjects for which courseware material was prepared were Analog Electronic Circuits, Digital
Systems Design, Circuit Theory and Measurements and Instruments.
Faculty members from all the departments contributed to the task. They were, in no particular
order, Nalini Singh, Bimal Meher, Saumyaranjan Dash, Mukti Routray, Susmita Biswal, Manasa
Dash, Bipin Tripathy, Sibasankar Nayak, Janmejay Senapati, Subrat Sahu, Pradeep Moharana,
Rupambika Pattanaik, Dhananjay Tripathy, Jagadish Patra, Sachin Das, Deepak Ranjan Nayak,
Amulya Roul, Bodhisattva Dash, Sanghamitra Das, Gyana Ranjan Biswal, Nibedita Swain and
Rajan Mishra.
The entire group worked diligently to successfully complete the task which included a peer review
of the material. I take this opportunity to thank all the members of the SAGA group for a job well
done.
I sincerely hope that this courseware material comes in handy and is utilized to the fullest extent.
These are readily available additional resources prepared in accordance with the Silicon autonomy
syllabus, to complement textbooks and classroom lectures. If there are any errors, I would be
grateful if they are brought to my notice so that we can correct them in subsequent versions.
Dr. Jaideep Talukdar, Principal
Silicon Institute of Technology
Bhubaneswar
December 2020
, MODULE – 1
Introduction to Data Structure and Classification of Data Structure
1.1 Definition of Data Structure
Data structure is a way to represent relationship among different available data items and
along with set of operations which can be performed on that group. A data structure is a way of
storing data in a computer so that it can be used efficiently and it will allow the most efficient
algorithm to be used.
Data structure = Related Data + Allowed Operations on them
Program = Algorithm + Data structure
A data structure should be seen as a logical concept that must address two fundamental
concerns.
1. First, how the data will be stored, and
2. Second, what operations will be performed on the data structure?
Data structures are used in almost every program or software for manipulation of data.
Manipulation of data requires the following tasks: Storing of the data, insertion, deletion,
searching, sorting, merge, searching.
Example: Array, Stack, Queue, Linked List, Tree, Graph
1.2 Classification of Data Structure
1.2.1 Linear and Non-Linear Data Structure
• Linear Data Structure: - In a linear data structure, the data items are arranged in a linear
sequence. In the linear Data Structures the relationship of adjacency is maintained
between the data elements. Example is array.
• Non-Linear Data Structure: - In a non-linear data structure, the data items are not
arranged in a sequence. Example is tree. In the linear Data Structures the relationship
of adjacency is maintained between the data elements.
Linear Data Structure Non-Linear Data Structure
, Every item is related to its previous and Every item is linked to many other items
next item.
Data items are arranged in a sequence. Data items are not arranged in a
sequence.
Only one possible traversal. More than one possible way to traverse
the DS.
Example: Array, Stack, Queue, Linked List Example: Tree, Graph
1.2.2 Static and Dynamic Data Structure
Static Data structure: In Static data structure the size of the structure is fixed. The content
of the data structure can be modified but without changing the memory space allocated to it.
The size of the data structure is fixed during the compilation time(cc) Example: Array.
Dynamic Data Structure: In Dynamic data structure the size of the structure in not fixed
and can be modified during the operations performed on it. Dynamic data structures are
designed to facilitate change of data structures in the run time. It uses predefined function used
for dynamic memory allocation like malloc(), calloc(), free() and realloc(). Example: Linked List.
The data items added or deleted from the linked list at run time(./a.out) based on user choice.
1.2.3 Homogeneous and Non-homogeneous Data Structure
Homogeneous Data Structure: The homogeneous data structures are the one in which the
data elements have the same data type. All the data elements in the homogeneous belong to the
single data type. For example: Arrays
Non-homogeneous Data Structure: The non-homogeneous data structures are the one in
which the data elements doesn't belong to the same data type. All the data elements have
different data type. For example: classes, Structure, Union etc.
, 1.2.4 Primitive and Non-primitive Data Structure
Primitive Data Structure: Primitive Data Structures are the basic data structures that directly
operate on the machine instruction. It varies from the system to system.
They have different representations on different computers. Integer, float and character are
example of primitive data structure. These data structure are available in most programming
language built in data type.
Non-primitive data structures: Non-primitive data structures are more sophisticated data
structures and are derived from primitive data structures. They emphasize on grouping same or
different data items with relationship between each data item. Example of Non-primitive data
structure is Array, Stack etc.
2 Algorithm Notation, Complexity, Asymptotic Notation
2.1 Definition and Characteristics of algorithm
Algorithms describe a sequence of precise steps to solve a well -defined computational
problem. Algorithms will terminate after a finite number of steps (they cannot loop indefinitely).
Algorithms are typically expressed in pseudo-code (that is, in a way that is not specific to any
particular programming language). Data structures are implemented using algorithms. An
algorithm is independent of any programming language. The algorithm can be implemented
using any programming language. An algorithm must possess the following properties or
characteristics:
• Finiteness: The algorithm must always terminate after a finite number of steps.
• Definiteness: Each step must be precisely defined; the actions to be carried out
must be rigorously and unambiguously specified for each case.
• Input: An algorithm has zero or more inputs, taken from a specified set of objects.
• Output: An algorithm has one or more outputs, which have a specified relation to
the inputs.
• Effectiveness: All operations to be performed must be sufficiently basic that they
can be done exactly and in finite length.
For each problem or class of problems, there may be many different algorithms. For each
algorithm, there may be many different implementations (programs).
This is the second iteration of preparing our own courseware material, after successful completion
of a similar task undertaken a few years ago. These contents have been carefully prepared and
should serve as excellent auxiliary material for both instructors and students.
The Special Academic Group, Autonomy (SAGA) was formed for the sole purpose of preparing
courseware contents primarily in the first-year theory subjects; a few second-year subjects were
also included. The subjects for the first year were - Basic Electrical Engineering, Basic Electronics
Engineering, Computer Programming, Data Structures and Algorithms, Engineering Mathematics
I and II, Engineering Physics, Engineering Chemistry, Constitution of India, Environmental
Science and Engineering and Communicative and Technical English. For the second year, the
subjects for which courseware material was prepared were Analog Electronic Circuits, Digital
Systems Design, Circuit Theory and Measurements and Instruments.
Faculty members from all the departments contributed to the task. They were, in no particular
order, Nalini Singh, Bimal Meher, Saumyaranjan Dash, Mukti Routray, Susmita Biswal, Manasa
Dash, Bipin Tripathy, Sibasankar Nayak, Janmejay Senapati, Subrat Sahu, Pradeep Moharana,
Rupambika Pattanaik, Dhananjay Tripathy, Jagadish Patra, Sachin Das, Deepak Ranjan Nayak,
Amulya Roul, Bodhisattva Dash, Sanghamitra Das, Gyana Ranjan Biswal, Nibedita Swain and
Rajan Mishra.
The entire group worked diligently to successfully complete the task which included a peer review
of the material. I take this opportunity to thank all the members of the SAGA group for a job well
done.
I sincerely hope that this courseware material comes in handy and is utilized to the fullest extent.
These are readily available additional resources prepared in accordance with the Silicon autonomy
syllabus, to complement textbooks and classroom lectures. If there are any errors, I would be
grateful if they are brought to my notice so that we can correct them in subsequent versions.
Dr. Jaideep Talukdar, Principal
Silicon Institute of Technology
Bhubaneswar
December 2020
, MODULE – 1
Introduction to Data Structure and Classification of Data Structure
1.1 Definition of Data Structure
Data structure is a way to represent relationship among different available data items and
along with set of operations which can be performed on that group. A data structure is a way of
storing data in a computer so that it can be used efficiently and it will allow the most efficient
algorithm to be used.
Data structure = Related Data + Allowed Operations on them
Program = Algorithm + Data structure
A data structure should be seen as a logical concept that must address two fundamental
concerns.
1. First, how the data will be stored, and
2. Second, what operations will be performed on the data structure?
Data structures are used in almost every program or software for manipulation of data.
Manipulation of data requires the following tasks: Storing of the data, insertion, deletion,
searching, sorting, merge, searching.
Example: Array, Stack, Queue, Linked List, Tree, Graph
1.2 Classification of Data Structure
1.2.1 Linear and Non-Linear Data Structure
• Linear Data Structure: - In a linear data structure, the data items are arranged in a linear
sequence. In the linear Data Structures the relationship of adjacency is maintained
between the data elements. Example is array.
• Non-Linear Data Structure: - In a non-linear data structure, the data items are not
arranged in a sequence. Example is tree. In the linear Data Structures the relationship
of adjacency is maintained between the data elements.
Linear Data Structure Non-Linear Data Structure
, Every item is related to its previous and Every item is linked to many other items
next item.
Data items are arranged in a sequence. Data items are not arranged in a
sequence.
Only one possible traversal. More than one possible way to traverse
the DS.
Example: Array, Stack, Queue, Linked List Example: Tree, Graph
1.2.2 Static and Dynamic Data Structure
Static Data structure: In Static data structure the size of the structure is fixed. The content
of the data structure can be modified but without changing the memory space allocated to it.
The size of the data structure is fixed during the compilation time(cc) Example: Array.
Dynamic Data Structure: In Dynamic data structure the size of the structure in not fixed
and can be modified during the operations performed on it. Dynamic data structures are
designed to facilitate change of data structures in the run time. It uses predefined function used
for dynamic memory allocation like malloc(), calloc(), free() and realloc(). Example: Linked List.
The data items added or deleted from the linked list at run time(./a.out) based on user choice.
1.2.3 Homogeneous and Non-homogeneous Data Structure
Homogeneous Data Structure: The homogeneous data structures are the one in which the
data elements have the same data type. All the data elements in the homogeneous belong to the
single data type. For example: Arrays
Non-homogeneous Data Structure: The non-homogeneous data structures are the one in
which the data elements doesn't belong to the same data type. All the data elements have
different data type. For example: classes, Structure, Union etc.
, 1.2.4 Primitive and Non-primitive Data Structure
Primitive Data Structure: Primitive Data Structures are the basic data structures that directly
operate on the machine instruction. It varies from the system to system.
They have different representations on different computers. Integer, float and character are
example of primitive data structure. These data structure are available in most programming
language built in data type.
Non-primitive data structures: Non-primitive data structures are more sophisticated data
structures and are derived from primitive data structures. They emphasize on grouping same or
different data items with relationship between each data item. Example of Non-primitive data
structure is Array, Stack etc.
2 Algorithm Notation, Complexity, Asymptotic Notation
2.1 Definition and Characteristics of algorithm
Algorithms describe a sequence of precise steps to solve a well -defined computational
problem. Algorithms will terminate after a finite number of steps (they cannot loop indefinitely).
Algorithms are typically expressed in pseudo-code (that is, in a way that is not specific to any
particular programming language). Data structures are implemented using algorithms. An
algorithm is independent of any programming language. The algorithm can be implemented
using any programming language. An algorithm must possess the following properties or
characteristics:
• Finiteness: The algorithm must always terminate after a finite number of steps.
• Definiteness: Each step must be precisely defined; the actions to be carried out
must be rigorously and unambiguously specified for each case.
• Input: An algorithm has zero or more inputs, taken from a specified set of objects.
• Output: An algorithm has one or more outputs, which have a specified relation to
the inputs.
• Effectiveness: All operations to be performed must be sufficiently basic that they
can be done exactly and in finite length.
For each problem or class of problems, there may be many different algorithms. For each
algorithm, there may be many different implementations (programs).
