UNIT I ABSTRACT DATA TYPES
Abstract Data Types (ADTs) – ADTs and classes – introduction to OOP – classes in Python –
inheritance – namespaces – shallow and deep copying- Introduction to analysis of algorithms –
asymptotic notations – divide & conquer – recursion –analyzing recursive algorithms.
Prerequisite:
Data:
A collection of facts, concepts, figures, observations, occurrences or instructions in a formalized
manner.
Information:
The meaning that is currently assigned to data by means of the conventions applied to those
data(i.e. processed data)
Record:
Collection of related fields.
Data type:
Set of elements that share common set of properties used to solve a program.
Data Structures:
Data Structure is the way of organizing, storing, and retrieving data and their relationship with
each other.
Characteristics of data structures:
1. It depicts the logical representation of data in computer memory.
2. It represents the logical relationship between the various data elements.
3. It helps in efficient manipulation of stored data elements.
4. It allows the programs to process the data in an efficient manner.
Operations on Data Structures:
1.Traversal
2.Search
3.Insertion
4.Deletion
,CLASSIFICATION OFDATASTRUCTURES
Primary Data Structures/Primitive Data Structures:
Primitive data structure includes all the fundamental data structures that can be directly
manipulated by machine-level instructions. Some of the common primitive data structures
include integer, character, real, Boolean etc.
Secondary Data Structures/Non Primitive Data Structures:
Non primitive data structures, refer to all those data structures that are derived from one
or more primitive data structures. The objective of creating non-primitive data structures is to
form sets of homogeneous or heterogeneous data elements.
Linear Data Structures:
Linear data structures are data structures in which, all the data elements are arranged in
linear or sequential fashion. Examples of data structures include arrays, stacks, queues, linked
lists, etc.
Non Linear Structures:
In non-linear data structures, there is definite order or sequence in which data elements
are arranged. For instance, a non-linear data structures could arrange data elements in a
hierarchical fashion. Examples of non-linear data structures are trees and graphs.
Application of data structures:
Data structures are widely applied in the following areas:
Compiler design
Operating system
Statistical analysis package
DBMS
Numerical analysis
Simulation
, Artificial intelligenceand Graphics
ABSTRACT DATA TYPES (ADTS):
An abstract data type (ADT) is a set of operations.
Abstract data types are mathematical abstractions;
In an ADT’s definition, there is no mention of how the set of operations is implemented.
Objects such as lists, sets and graphs, along with their operations, can be viewed as
abstract data types, just as integers, reals and Booleans are data types. Integers, reals and
Booleans have operations associated with them, and so do abstract data types.
For the set ADT, we might have such operations as union, intersection, size and
complement.
The basic idea is that the implementation of these operations is written once in the
program, and any other part of the program that needs to perform an operation on the
ADT can do so by calling the appropriate function.
If for some reason the implementation details need to be changed, it should be easy to do
so by merely changing the routines that perform the ADT operations.
This change would be completely transparent to the rest of the program.
Advantages/Benefits of ADT:
1.Modularity
2.Reuse
3.code is easier to understand
4.Implementation of ADTs can be changed without requiring changes to the program that uses
the ADTs.
CLASSES
A class is a user-defined blueprint or prototype from which objects are created. The class came
into existence when it instantiated. On the other hand, the object is the instance of a class.
The process of creating an object can be called instantiation. Class instances can also have
methods (defined by their class) for modifying their state.
Creating classes in Python
In Python, a class can be created by using the keyword class, followed by the class name. The
syntax to create a class is given below.
Syntax: Class Definition
class ClassName:
# Statement
Some points on Python class:
Classes are created by keyword class.
Attributes are the variables that belong to a class.
Abstract Data Types (ADTs) – ADTs and classes – introduction to OOP – classes in Python –
inheritance – namespaces – shallow and deep copying- Introduction to analysis of algorithms –
asymptotic notations – divide & conquer – recursion –analyzing recursive algorithms.
Prerequisite:
Data:
A collection of facts, concepts, figures, observations, occurrences or instructions in a formalized
manner.
Information:
The meaning that is currently assigned to data by means of the conventions applied to those
data(i.e. processed data)
Record:
Collection of related fields.
Data type:
Set of elements that share common set of properties used to solve a program.
Data Structures:
Data Structure is the way of organizing, storing, and retrieving data and their relationship with
each other.
Characteristics of data structures:
1. It depicts the logical representation of data in computer memory.
2. It represents the logical relationship between the various data elements.
3. It helps in efficient manipulation of stored data elements.
4. It allows the programs to process the data in an efficient manner.
Operations on Data Structures:
1.Traversal
2.Search
3.Insertion
4.Deletion
,CLASSIFICATION OFDATASTRUCTURES
Primary Data Structures/Primitive Data Structures:
Primitive data structure includes all the fundamental data structures that can be directly
manipulated by machine-level instructions. Some of the common primitive data structures
include integer, character, real, Boolean etc.
Secondary Data Structures/Non Primitive Data Structures:
Non primitive data structures, refer to all those data structures that are derived from one
or more primitive data structures. The objective of creating non-primitive data structures is to
form sets of homogeneous or heterogeneous data elements.
Linear Data Structures:
Linear data structures are data structures in which, all the data elements are arranged in
linear or sequential fashion. Examples of data structures include arrays, stacks, queues, linked
lists, etc.
Non Linear Structures:
In non-linear data structures, there is definite order or sequence in which data elements
are arranged. For instance, a non-linear data structures could arrange data elements in a
hierarchical fashion. Examples of non-linear data structures are trees and graphs.
Application of data structures:
Data structures are widely applied in the following areas:
Compiler design
Operating system
Statistical analysis package
DBMS
Numerical analysis
Simulation
, Artificial intelligenceand Graphics
ABSTRACT DATA TYPES (ADTS):
An abstract data type (ADT) is a set of operations.
Abstract data types are mathematical abstractions;
In an ADT’s definition, there is no mention of how the set of operations is implemented.
Objects such as lists, sets and graphs, along with their operations, can be viewed as
abstract data types, just as integers, reals and Booleans are data types. Integers, reals and
Booleans have operations associated with them, and so do abstract data types.
For the set ADT, we might have such operations as union, intersection, size and
complement.
The basic idea is that the implementation of these operations is written once in the
program, and any other part of the program that needs to perform an operation on the
ADT can do so by calling the appropriate function.
If for some reason the implementation details need to be changed, it should be easy to do
so by merely changing the routines that perform the ADT operations.
This change would be completely transparent to the rest of the program.
Advantages/Benefits of ADT:
1.Modularity
2.Reuse
3.code is easier to understand
4.Implementation of ADTs can be changed without requiring changes to the program that uses
the ADTs.
CLASSES
A class is a user-defined blueprint or prototype from which objects are created. The class came
into existence when it instantiated. On the other hand, the object is the instance of a class.
The process of creating an object can be called instantiation. Class instances can also have
methods (defined by their class) for modifying their state.
Creating classes in Python
In Python, a class can be created by using the keyword class, followed by the class name. The
syntax to create a class is given below.
Syntax: Class Definition
class ClassName:
# Statement
Some points on Python class:
Classes are created by keyword class.
Attributes are the variables that belong to a class.
