Introduction to

DS
DR. DEEPTI REDDY
A S S O C I AT E P R O F E S S O R
D E P T. O F C O M P U T E R E N G I N E E R I N G ,
MPSTME, NMIMS, MUMBAI
 Unit 1- Introduction
oIntroduction to data structure and its importance,
oClassification of data structures,
oBasic operations.,
oAbstract data type,
oPerformance analysis- time and space complexity,
oAsymptotic Notations.
Data Structures
Data structures represents the organization of data in computer
memory on which operations like insert, delete, update can be
performed.
Data structure is basically a group of data elements included under one
name, e.g. the students data, employees data, etc.
The data structures defines a particular way of storing and organizing
data so it can be used efficiently (Thareja, 2014).
A data structure is a way to store and organize data in order to facilitate
access and modifications. No single data structure works well for all
purposes, and so it is important to know the strengths and limitations of
several of them (Corman, 2022)
Fox and crane story
Types Of Data Structures
Applications of DS
◦ Operating Systems
◦ Compiler Construction
◦ DBMS
◦ Some real world problems: lookup a contact on your phone, web search,
login to social network..
Efficiency of Programs
The programs are written to solve problems, like searching a data item,
sorting data items, updating data, etc.
The programs efficiency is based on the execution time and memory
space utilization.
The efficiency of the program depends on the data structure used to
represent data on which operations like search, sort, insert, etc are
performed.
 Types of Data Structures and
its operations
Data structures
and operations

Linear Data Non-linear Data Operations

Structures Structures

Array Linked Stack Graph Tree

Queue
list

Insert Delete Traverse Search Sort

Linear DS- Array
An array is a collection of data elements of same data types.
The data elements are stored in consecutive memory locations, i.e. one
after another.
The elements can be accessed by an index. example:
 Linear DS- Array
Example-
int marks[10]={10,20,30,45,60,70,88,99,33,11};
marks[0]=10, marks[1]=20…
Index 0 1 2 3 4 5 6 … 9
Marks[index] 10 20 30 45 60 70 88 11
Linear DS-Linked List
Linked list is dynamic data structure in which elements can be inserted
and deleted anywhere without shifting. In contract to fixed size in
arrays, linked list can allocate memory to data elements during run time
also.
A linked list consists of nodes that are dynamically created by allotting
memory during run time.
Linked list
The node has two parts: data and pointer to next node. The nodes are
linked to each other as shown in the figure.

12 56 89 29
Linear DS- Stack
A stack is an ordered collection of data elements into which elements
can be inserted or deleted only from one end, called the top of the
stack as shown in figure.

58 Top of stack
98
16
Linear DS-Queue
In contrast to stack, queue is opened at both end. One end is always
used to insert data (enqueue) and the other is used to remove data
(dequeue).
Queue follows First-In-First-Out methodology, i.e., the data item stored
first will be accessed first as shown in figure.
 Nonlinear DS- Trees
A binary tree is another commonly
used data structure. It is organized
like an upside down tree.
A node, holds an item of data along
with a left pointer and a right pointer.
Useful for efficient search, e.g
telephone directory
 Nonlinear DS- Use of Trees
A binary search tree is a good data structure to use for
searching sorted data.
The middle item from the list is stored in the root node,
with lesser items to the left and greater items to the
right.
A search begins at the root. The computer either find
the data, or moves left or right, depending on the value
for which you are searching.
Each move down the tree cuts the remaining data in half.
Items can be located very quickly in a tree.
Telephone directory assistance information is stored in a
tree, so that a name and phone number can be found
quickly.
Nonlinear DS- Graphs
Graph is a collection of vertices(nodes) and edges that connect these
vertices.
Unlike trees, in graph the nodes may not be connected in hierarchy.
Used to represent a complex relationships between components.
City map can be represented using graph, where nodes represent cities
and edges represent road connectivity.
Linear and Nonlinear DS
Linear DS
◦ Data elements are stored sequentially
◦ Traverse forward and backward from the node
◦ E.g. Arrays, stack, queues and linked list.

Nonlinear DS
◦ No linear relation between data elements
◦ Cannot be traversed in a single run.
Reflection
Match the following
A. Stack i. Dynamic memory allocation
B. Queue ii. Last in first out
C. Linked list iii. Static memory allocation
D. Array iv. First in first out

1. A- ii, B- iv, C- iii, D-i

2. A- ii, B- iv, C- iii, D- i
3. A- ii, B- iv, C- i, D-iii
4. A- iv, B- ii, C- i, D-iii
Operations on Data Structures
Various operations performed on various data
structures are-
Traversing- access each data item exactly once. E.g. Print the values of
all the elements in the array.
Searching- find location of one or more data items that satisfies the
given constraint. E.g. find all students who secured 100 marks in Maths.
Inserting- add new data item in the given list of data items.
Deleting- remove the data item from the given set of data items.
Sorting- arrange data items in specific order- ascending or descending.
Merging- combine two data sets.
Array
•An array is defined as the collection of similar type of data items stored
at contiguous memory locations.
•The array is the simplest data structure where each data element can be
randomly accessed by using its index number.
•Arrays are the derived data type in C programming language which can
store the primitive type of data such as int, char, double, float, etc.
•Declaration of C Array
•data_type array_name[array_size];
•int marks[5];
•int marks[5]={20,30,40,50,60};
Array- Traverse
#include<stdio.h>
int main()
{
int i=0;
int marks[5]={20,30,40,50,60};//declaration and initialization of array
//traversal of array
for(i=0;i<5;i++){
printf("%d \n",marks[i]);
}
return 0;
}
Array- Search
#include<stdio.h>
int main(){
int i,n;
int marks[5]={20,30,40,50,60};//declaration and initialization of array
printf(“enter element to be searched”);
scanf(“%d”, &n);
for(i=0;i<5;i++){
_______
}
return 0;
}

Input: number to be searched

Output: Element found or Element not found
Write the missing statement in the code below to
insert a number at a given position in an array-
#include <stdio.h>

int main()
{
int array[100], position, c, n, value;
printf("Enter number of elements in array\n");
scanf("%d", &n);

printf("Enter %d elements\n", n);

for (c = 0; c < n; c++)

scanf("%d", &array[c]);

printf("Enter the location where you wish to insert an element\n");

scanf("%d", &position);

printf("Enter the value to insert\n");

scanf("%d", &value);

for (c = n - 1; c >= position - 1; c--)

_______________________

array[position-1] = value;

printf("Resultant array is\n");

for (c = 0; c <= n; c++)

printf("%d\n", array[c]);

return 0;
}
Abstract Data Type
Solving a problem involves processing data, this requires that we
identify-
1. the collection of data items and
2. basic operations that must be performed on them.
Such a collection of data items together with the operations on the data
is called an abstract data type (ADT).
The word abstract refers to the fact that data and operations are
defined independent of its implementation.
We just specify what can be done with the data, and not how it is done.
Example of ADT
Problem- Because of new government regulation, the university has to keep records
of all students currently receiving financial aid and submit regular reports to
government. Design the program for the same.
Data: Financial_aid_awards: text string source, real value amount
Operations:
Get_amount(): Access and return the amount stored
Display(): display on screen source and amount
Update_amount(): modify the amount
Data: Student_data: numeric id, text string name, list of financial aid awarded <
source, amount>
Operation:
Get_record(),Update_amount()
Example of ADT
ADT of List
List holds an ordered collection of items accessible by an integer index.
Operations
1. Insert(element, position) – inserts element at a given position
2. delete(element)- deletes the existing element
3. search(element)- returns the position of the element
Abstract Data Type
Advantage of ADT
Data abstraction: The idea of separating the definition of data
definition from implementation enables software designers to study
data types without being concerned about the details of its
implementation.
Reuse: Programmers may reuse these data types and its operation
without worrying about its implementation.
To manage complexity: To manage the complexity of problems and the
problem-solving process, computer scientists use abstractions to allow
them to focus on the “big picture” without getting lost in the details.
Reflection
1. Abstract data type represents –
◦ A. Set of data types and operations defined on that data type.
◦ B. The data types and operations implemented using programming language
◦ C. The data types and its values only

2. We can have several implementations of the same ADT

◦ A. True
◦ B. False

3. Write ADT for library management system

Analysis of algorithms
An algorithm is any well-defined computational procedure that takes some
value, or set of values, as input and produces some value, or set of values, as
output. An algorithm is thus a sequence of computational steps that transform
the input into the output.
sorting problem
Input: A sequence of n numbers
Output: sorted sequence INSERTION-SORT(A)
1 for j ← 2 to length[A]
2 do key ← A[ j ]
3 ✄ Insert A[ j ] into the sorted sequence A[1 . . j − 1].
4i←j−1
5 while i > 0 and A[i ] > key
6 do A[i + 1] ← A[i ]
7 i ←i − 1
8 A[i + 1] ← key
Analysis of algorithms
Analyzing an algorithm has come to mean predicting the resources that
the algorithm requires.
The time taken by the INSERTION-SORT procedure depends on the input:
sorting a thousand numbers takes longer than sorting three numbers.
INSERTIONSORT can take different amounts of time to sort two input
sequences of the same size depending on how nearly sorted they already are.
we need to define the terms “running time” and “size of input” more carefully.
The running time of an algorithm on a particular input is the number of
primitive operations or “steps” executed.
Analysis of algorithms

Running time of the algorithm-

Best case analysis
in INSERTION-SORT, the best case occurs if the array is already sorted. For
each j = 2, 3, . . . , n, we then find that A[i ] ≤ key in line 5 when i has its initial
value of j − 1. Thus t j = 1 for j = 2, 3, . . . , n, and the best-case running time is
T (n) = c1n + c2(n − 1) + c4(n − 1) + c5(n − 1) + c8(n − 1)
= (c1 + c2 + c4 + c5 + c8)n − (c2 + c4 + c5 + c8) .
This running time can be expressed as an +b for constants a and b that depend
on the statement costs ci; it is thus a linear function of n.
 Worst case analysis
If the array is in reverse sorted order—that is, in decreasing order—the worst
case results. We must compare each element A[ j ] with each element in the
entire sorted subarray A[1 . . j − 1], and so t j = j for j = 2, 3, . . . , n. Noting that

find that in the worst case, the running time of INSERTION-SORT is

This worst-case running time can be expressed as an2 + bn + c for constants a, b,

and c that again depend on the statement costs ci ; it is thus a quadratic function
of n.
Worst-case and average-case
analysis
we shall usually concentrate on finding only the worst-case running time, that
is, the longest running time for any input of size n. We give three reasons for this
orientation.
1. The worst-case running time of an algorithm is an upper bound on the running
time for any input.
2. For some algorithms, the worst case occurs fairly often. For example, in
searching a database for a particular piece of information, the searching
algorithm’s worst case will often occur when the information is not present in
the database.
3. The “average case” is often roughly as bad as the worst case
Order of growth
Given the worst-case running time of insertion sort as an2+bn+c
We shall now make one more simplifying abstraction. It is the rate of growth, or
order of growth, of the running time that really interests us. We therefore
consider only the leading term of a formula (e.g., an2), since the lower-order
terms are relatively insignificant for large n.
Thus, we write that insertion sort, for example, has a worst-case running time of
θ(n2) (pronounced “theta of n-squared”).
Asymptotic notation
When we look at input sizes large enough to make only the order of growth of
the running time relevant, we are studying the asymptotic efficiency of
algorithms.
The notations we use to describe the asymptotic running time of an algorithm are
defined in terms of functions whose domains are the set of natural numbers N =
{0, 1, 2, . . .}. Such notations are convenient for describing the worst-case
running-time function T (n), which is usually defined only on integer input sizes.
Asymptotic notation
Θ –notation
we found that the worst-case running time of insertion sort is T (n) = (n2). Let us
define what this notation means.
For a given function g(n), we denote by θ(g(n)) the set of functions
θ (g(n)) = { f (n) : there exist positive constants c1, c2, and n0 such that 0 ≤
c1g(n) ≤ f (n) ≤ c2g(n) for all n ≥ n0} .
For example- 1/2n2 − 3n = Θ (n2).
c1n2 ≤ 1/2n2 − 3n ≤ c2n2,
for all n ≥ n0. Dividing by n2 yields c1 ≤ 1/2− 3n≤ c2 . Thus, by choosing c1 =
1/14, c2 = 1/2, and n0 = 7, we can verify that 1/2 n2 − 3n = Θ (n2).
Asymptotic notation
O-notation
The θ -notation asymptotically bounds a function from above and below. When
we have only an asymptotic upper bound, we use O-notation.
For a given function g(n), we denote by O(g(n)) (pronounced “big-oh of g of n”
or sometimes just “oh of g of n”) the set of functions
O(g(n)) = { f (n) : there exist positive constants c and n0 such that 0 ≤ f (n) ≤
cg(n) for all n ≥ n0} .
Asymptotic notation
Ω-notation
Just as O-notation provides an asymptotic upper bound on a function, Ω notation
provides an asymptotic lower bound. For a given function g(n), we denote by
Ω(g(n)) (pronounced “big-omega of g of n” or sometimes just “omega of g of
n”)
the set of functions
Ω(g(n)) = { f (n) : there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f
(n) for all n ≥ n0}
Comparison
Activity
Perform best case and worst case analysis of following algorithm to find
sum of n numbers-
Algorithm sum(n)
1. int s=0
2. for i=1 to n
3. s=s+I;
4. Print s
Bubble sort analysis
Algorithm: Sequential-Bubble-Sort (A)
for i← 1 to length [A] do
for j ← length [A] down-to i +1 do
if A[j] < A[j - 1] then
Exchange A[j] ↔ A[j-1]

Perform best case and worst case analysis

References
1. Thareja, Reema. "Data structures using C." (2014).
2. Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.