Unit 1: Introduction to data

Structure
Definition, Abstract Data Type, Importance of Data
Structure-(2 hrs)
 Define Define Data Structure and Algorithms.

Classify and Classify and explain the various Data

explain Structures.
Explain
Focus on Explain Data Structure operations.

following Explain Explain an Abstract Data Type.

Questions List out List out the Importance of data structures.

Discuss on Discuss on time and space complexity of

algorithm.
Introduce Introduce asymptotic notations.

@Suresh Raj Sharma 2

 Data structure is representation of the
logical relationship existing between
individual elements of data.

Definition In other word “a data structure is a way

of organizing all data items that considers
of data not only the elements stored but also
Structure? their relationship to each other".
Data structure mainly specify following
four things, they are

@Suresh Raj Sharma 3

 1. Organization of data.

2. Accessing methods
Data
Structure
3. Degree of associativity
focus on
4. Processing alternatives for
information.
@Suresh Raj Sharma 4
 Data structure are the building block of the program and hence
selection of specific data structure stresses on the following two
things.

1. The data structure must be rich enough in structure to reflect

the relationship existing between the data.
Data
Structure definition
Cont.. 2. And the structure should be simple so that we can process the
data effectively wherever required.

The data structure affects the design of both structure and

functional aspect of a program. Algorithm + Data Structure =
Program Algorithm and the best design of data structure yields a
good program

@Suresh Raj Sharma 5

 Processor speed: To handle very large number of
data, high speed processing is required, but as the
data is growing day by day to the billions of files
per entity, processor may fail to deal with that
much amount of data.
Need for Data Search: Consider an inventory size of 106
items in a store, If our application needs to search
data for a particular item, it needs to traverse 106 items
every time, results in slowing down the search
structure process.
Multiple requests: If thousands of users are
searching the data simultaneously on a web server,
then there are the chances that a very large server
can be failed during that process

@Suresh Raj Sharma 6

 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,

Advantages binary search tree or hash tables.

of Data 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

Structures
data structures can be compiled into libraries which can be used by different
clients.

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.

@Suresh Raj Sharma 7

Data Structure Classification.

@Suresh Raj Sharma 8

Primitive The primitive data structures are primitive data types.
The int, char, float, double, and pointer are the primitive
Data data structures that can hold a single value.

structure
and Non- These are basic structure and are directly operated upon
by the machine instructions.

Primitive
Data non-primitive data structure: these are more
sophisticated data structures, there are derived from the
primitive data structure. Non- primitive data structure
structure emphasize on structuring of a group of homogeneous or
heterogeneous data items.

@Suresh Raj Sharma 9

 Linear Data Structures: A data structure is called
linear if all of its elements are arranged in the
linear order. In linear data structures, the
Non- elements are stored in non-hierarchical way
where each element has the successors and
primitive predecessors except the first and last element.

data Non Linear Data Structures: This data structure

does not form a sequence i.e. each item or
structure element is connected with two or more other
items in a non-linear arrangement. The data
elements are not arranged in sequential
structure.

@Suresh Raj Sharma 10

 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

Data 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.
Structure
Operations. 2) Insertion: Insertion can be defined as the process of adding the
elements to the data structure at any location.

If the size of data structure is n then we can only insert n-1 data
elements into it.

@Suresh Raj Sharma 11

Data Structure operation

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.
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

@Suresh Raj Sharma 12

What is ADT (Abstract Data Types).
The definition of ADT only mentions what operations are to be performed but
not how these operations will be implemented. It does not specify how data
will be organized in memory and what algorithms will be used for
implementing the operations. It is called “abstract” because it gives an
implementation-independent view. The process of providing only the
essentials and hiding the details is known as abstraction.

An ADT tells what is to be done and data structure tells how it is to be done. In
other words, we can say that ADT gives us the blueprint while data structure
provides the implementation part. Now the question arises: how can one get
to know which data structure to be used for a particular ADT?.

@Suresh Raj Sharma 13

ADT cont..
As the different data structures can be implemented in a particular ADT, but
the different implementations are compared for time and space. For
example, the Stack ADT can be implemented by both Arrays and linked list.
Suppose the array is providing time efficiency while the linked list is
providing space efficiency, so the one which is the best suited for the
current user's requirements will be selected.
The Advantage Offer by ADT are as following.
1. Modularity
2. Precise Specifications
3. Information Hiding
4. Simplicity
5. Integrity
@Suresh Raj Sharma 14
 Algorithm Analysis

The data structure is a way of organizing the data

efficiently and that efficiency is measured either in terms
of time or space. So, the ideal data structure is a
structure that occupies the least possible time to perform
all its operation and the memory space. Our focus would
be on finding the time complexity rather than space
complexity, and by finding the time complexity, we can
decide which data structure is the best for an algorithm.
@Suresh Raj Sharma 15
How to find
the Time The running time to perform any operation depends on
Complexity the size of the input. Let's understand this statement
through a simple example.
or running
time for
Suppose we have an array of five elements, and we want
performing to add a new element at the beginning of the array. To
achieve this, we need to shift each element towards
the right, and suppose each element takes one unit of time.
There are five elements, so five units of time would be

operations? taken. Suppose there are 1000 elements in an array,

then it takes 1000 units of time to shift. It concludes that
time complexity depends upon the input size.

@Suresh Raj Sharma 16

Therefore, if the input size is n, then f(n) is a function of n that denotes the
time complexity.
How to calculate f(n)?

Calculating the value of f(n) for smaller programs is easy but for
bigger programs, it's not that easy. We can compare the data
structures by comparing their f(n) values. We can compare the
data structures by comparing their f(n) values. We will find the
growth rate of f(n) because there might be a possibility that one
data structure for a smaller input size is better than the other one
but not for the larger sizes.

@Suresh Raj Sharma 17

 Worst case: It defines the input for
which the algorithm takes a huge
The time time.

required by
Average case: It takes average time for
an algorithm the program execution.
comes under
Best case: It defines the input for which
three types: the algorithm takes the lowest time

@Suresh Raj Sharma 18

Asymptotic Notations
The commonly used
asymptotic notations used for
calculating the running time
complexity of an algorithm is
given below:
• Big oh Notation (O)

• Omega Notation (Ω)

• Theta Notation (θ)

@Suresh Raj Sharma 19
Big oh Notation (O)

• Big O notation is an asymptotic notation that measures the

performance of an algorithm by simply providing the order
of growth of the function.
• This notation provides an upper bound on a function which
ensures that the function never grows faster than the
upper bound. So, it gives the least upper bound on a
function so that the function never grows faster than this
upper bound.

@Suresh Raj Sharma 20

• It is the formal way to express the upper boundary of an algorithm running time.
It measures the worst case of time complexity or the algorithm's longest amount
of time to complete its operation. It is represented as shown below:

@Suresh Raj Sharma 21

@Suresh Raj Sharma 22
For example:
If f(n) and g(n) are the two functions defined for positive integers,
then f(n) = O(g(n)) as f(n) is big oh of g(n) or f(n) is on the order of g(n))
if there exists constants c and no such that:
f(n)≤c.g(n) for all n≥no
This implies that f(n) does not grow faster than g(n), or g(n) is an upper
bound on the function f(n).
In this case, we are calculating the growth rate of the function which
eventually calculates the worst time complexity of a function, i.e.,
how worst an algorithm can perform.

@Suresh Raj Sharma 23

Omega Notation (Ω)
• It basically describes the best-case scenario which is opposite to the
big o notation.
• It is the formal way to represent the lower bound of an algorithm's
running time. It measures the best amount of time an algorithm can
possibly take to complete or the best-case time complexity.
• It determines what is the fastest time that an algorithm can run.

@Suresh Raj Sharma 24

If we required that an algorithm takes at least certain
amount of time without using an upper bound, we use
big- Ω notation i.e. the Greek letter "omega". It is used
to bound the growth of running time for large input size.​
If f(n) and g(n) are the two functions defined for positive
integers,​
then f(n) = Ω (g(n)) as f(n) is Omega of g(n) or f(n) is on
the order of g(n)) if there exists constants c and no such
that:​
f(n)>=c.g(n) for all n≥no and c>0
@Suresh Raj Sharma 25
Omega Notation (Ω)

@Suresh Raj Sharma 26

Omega Notation (Ω)

As we can see in the above figure that g(n) function

is the lower bound of the f(n) function when the
value of c is equal to 1. Therefore, this notation
gives the fastest running time. But, we are not
more interested in finding the fastest running time,
we are interested in calculating the worst-case
scenarios because we want to check our algorithm
for larger input that what is the worst time that it
will take so that we can take further decision in the
further process.

@Suresh Raj Sharma 27

Theta Notation (θ)

• The theta notation mainly describes the average case scenarios.

• It represents the realistic time complexity of an algorithm. Every time,
an algorithm does not perform worst or best, in real-world problems,
algorithms mainly fluctuate between the worst-case and best-case,
and this gives us the average case of the algorithm.
• Big theta is mainly used when the value of worst-case and the best-
case is same.
• It is the formal way to express both the upper bound and lower
bound of an algorithm running time.

@Suresh Raj Sharma 28

Theta Notation (θ)

Let's understand the big theta notation mathematically:

Let f(n) and g(n) be the functions of n where n is the steps
required to execute the program then:
f(n)= θg(n)
The above condition is satisfied only if when
c1.g(n)<=f(n)<=c2.g(n)

@Suresh Raj Sharma 29

Theta Notation
(θ)

@Suresh Raj Sharma 30

Thank you

Any Query ?

@Suresh Raj Sharma 31