DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

Government Polytechnic Banka

Lecture notes for Data Structures and Algorithms

Data Information
Data is unorganised and unrefined Information comprises processed,
facts organised data presented in a
meaningful context
Data is an individual unit that contains Information is a group of data that
raw materials which do not carry any collectively carries a logical meaning.
specific meaning.
Data doesn’t depend on information. Information depends on data.
Raw data alone is insufficient for Information is sufficient for decision
decision making making
An example of data is a student’s test The average score of a class is the
score information derived from the given
data.

DATA STRUCTURES
Data may be organized in many different ways logical or mathematical
model of a program particularly organization of data. This organized
data is called “Data Structure”.
Or

The organized collection of data is called a ‘Data Structure’.

Data Structure=Organized data +Allowed operations

Page 1 of 14
Mr. Raushan Kumar
Guest Lecturer CSE Department
 DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Government Polytechnic Banka
Lecture notes for Data Structures and Algorithms

Primitive Data structures are directly supported by the language ie; any
operation is directly performed in these data items.
Ex: integer, Character, Real numbers etc.
Non-primitive data types are not defined by the programming
language, but are instead created by the programmer.

Array:- It is collection of elements of the same type

Linked List:- linked list or single linked list is a sequence of elements in

which every element has link to its next element in the sequence.
Every element is called as a "node". Every "node" contains two fields,
data and link. The data is a value or string and link is an address of
next node.
The first node is called HEAD which is an empty node contains an
address of the first node so it link to the first node.
 The first node link to the second node and so on.
 The last node does not link to address but link to NULL. Let ptr be a
pointer to the linked list. The example is given below

Page 2 of 14
Mr. Raushan Kumar
Guest Lecturer CSE Department
 DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Government Polytechnic Banka
Lecture notes for Data Structures and Algorithms

Stack:- A stack is a data structure in which additions and deletions are

made at the top of the stack. So we can perform two operations on
stack.
1. Adding elements into the stack known as push;
2.Deleting elements from the stack known as pop

Queue:- A queue is a data structure in which additions are made at

one end and deletions are made at the other end. We can represent a
queue in an array.
 Here we can perform two operations on queue.
1. Adding elements into the queue known as insertion at rear
2.Deleting elements from the queue known as deletion from front

(b)Non-linear data structures:

 Here data elements are not connected in a sequence manner.
 Examples are: Trees and Graphs.
Tree:

Page 3 of 14
Mr. Raushan Kumar
Guest Lecturer CSE Department
 DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Government Polytechnic Banka
Lecture notes for Data Structures and Algorithms

 The tree is
defined as a
finite set of
one or more
nodes such
that
1.One node is
called a root node and
2.Remaining nodes partitioned into sub trees of the root.

Graph:-
 A graph is a pictorial representation of a set of points or nodes
termed as vertices, and the links that connect the vertices are called
edges.
 A Graph(G) consists of two sets V and E where V is called vertices and
E is called edges. We also write G = (V,E) to represent a graph.
 A Graph may be directed graph and undirected graph.

Differences between Linear and Non Linear Data Structures:

Page 4 of 14
Mr. Raushan Kumar
Guest Lecturer CSE Department
 DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Government Polytechnic Banka
Lecture notes for Data Structures and Algorithms

Linear Data Structure Non-Linear Data Structure

Every data element is connected to its Every data element is connected with
previous & many other
next one data elements
Data is arranged in a sequence Data is not arranged in a sequence
manner manner
Data can be traversed in a single run Data cannot be traversed in a single
run
Ex: Array, Stack, Queue, Linked List Ex: Tree, Graph
Implementation is easy Implementation is difficult

Operations on Data Structures:

 The different operations used on data structure are:
1.Create: Here we reserve memory for program elements: This can be done by
using malloc or calloc function. Wecan create a data structure with giving
different elements.
2.Insert: Here we reserve memory for program element. This can be done by
using malloc or calloc function. We can insert an element into a data structure.
3.Delete:
 It delete memory space allocated for specified data structure using free().
4.Display:
 It deals with accessing a particular data within a data structure.
5.Searching:
 It finds the data item in the list of data items.
 It also find the location of all elements.
6.Sorting:
 It is the process of arranging all data items in a data structure in a particular
order say either in ascending
order or in descending order.
7.Merging:
 It is the process of combining the data items of two different sorted list into a
single sorted list.
8.Splitting:- It is the process of partitioning single list to multiple list.
9.Traversal:- It is the process of visiting each and every node of a list in
systematic manner.

Page 5 of 14
Mr. Raushan Kumar
Guest Lecturer CSE Department
 DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Government Polytechnic Banka
Lecture notes for Data Structures and Algorithms

Abstract Data Types

An Abstract Data Type (ADT) is a conceptual model that defines a set of
operations and behaviors for a data structure, without specifying how these
operations are implemented or how data is organized in memory. 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 provides an implementation-independent view.
The process of providing only the essentials and hiding the other details is known
as abstraction.

For example, we use primitive values like int, float, and char with the
understanding that these data types can operate and be performed on without
any knowledge of their implementation details. ADTs operate similarly by
defining what operations are possible without detailing their implementation.
Difference Between ADTs and UDTs

User-Defined Data
Aspect Abstract Data Types (ADTs) Types (UDTs)

Definition Defines a class of objects and A custom data type

the operations that can be created by combining or
performed on them, along with extending existing
their expected behavior primitive types, specifying
(semantics), but without both structure and
specifying implementation operations.

Page 6 of 14
Mr. Raushan Kumar
Guest Lecturer CSE Department
 DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Government Polytechnic Banka
Lecture notes for Data Structures and Algorithms

User-Defined Data
Aspect Abstract Data Types (ADTs) Types (UDTs)

details.

What operations are allowed and

How data is organized in
how they behave, without
memory and how
dictating how they are
operations are executed.
Focus implemented.

Allows programmers to
Provides an abstract model to create concrete
define data structures in a implementations of data
conceptual way. structures using primitive
Purpose types.

Does not specify how operations Specifies how to create

Implementa are implemented or how data is and organize data types to
tion Details structured. implement the structure.

Used to implement data

Used to design and structures that realize the
conceptualize data structures. abstract concepts defined
Usage by ADTs.

Structures, classes,
List ADT, Stack ADT, Queue ADT.
Example enumerations, records

An abstract data type (ADT) is a collection of values and a set of operations

without specifying its implementation.
 For example in Array ADT set of values are index and item & set of
operations are create(),retrieval() and store().
 The purpose of the ADT is to hide the implementation details of a data
structure, thus improving software maintenance, reuse and portability.
 The developers of ADT will adapt changing requirements and save time.

Page 7 of 14
Mr. Raushan Kumar
Guest Lecturer CSE Department
 DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Government Polytechnic Banka
Lecture notes for Data Structures and Algorithms

 The users of ADT are concerned with the interface, but not the implementation.
 The different ADTs given by
String ADT, List ADT, Stack (last-in, first-out) ADT,
Queue (first-in, first-out) ADT
Binary Search Tree ADT etc
Example:
 A List ADT contains operations known as add element, remove element, etc.
 A List ADT can be represented by an array-based implementation or a linked-
list based implementation. In this the linked-list based implementation is so
commonly used.
 Similarly, a Binary Search Tree ADT can be represented in different ways with
the same operations known
as insert, remove, display, etc.

What is Algorithm?
Definition: - An algorithm is a Step By Step process to solve a problem, where
each step indicates an intermediate task. Algorithm contains finite number of
steps that leads to the solution of the problem.
Properties /Characteristics of an Algorithm:-
Algorithm has the following basic properties
 Input-Output:- Algorithm takes ‘0’ or more input and produces the required
output. This is the basic characteristic of an algorithm.
 Finiteness:- An algorithm must terminate in countable number of steps.
 Definiteness: Each step of an algorithm must be stated clearly and
unambiguously.
 Effectiveness: Each and every step in an algorithm can be converted in to
programming language statement.
 Generality: Algorithm is generalized one. It works on all set of inputs and
provides the required output. In other words it is not restricted to a single input
value.
Categories of Algorithm:
Based on the different types of steps in an Algorithm, it can be divided into three
categories, namely
 Sequence

Page 8 of 14
Mr. Raushan Kumar
Guest Lecturer CSE Department
 DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Government Polytechnic Banka
Lecture notes for Data Structures and Algorithms

 Selection and
 Iteration

Sequence: The steps described in an algorithm are performed successively one

by one without skipping any step. The sequence of steps defined in an algorithm
should be simple and easy to understand. Each instruction of such an algorithm
is executed, because no selection procedure or conditional branching exists in a
sequence algorithm.
Example:
// adding two numbers
Step 1: start
Step 2: read a,b
Step 3: Sum=a+b
Step 4: write Sum
Step 5: stop
Selection: The sequence type of algorithms are not sufficient to solve the
problems, which involves decision and conditions. In order to solve the problem
which involve decision making or option selection, we go for Selection type of
algorithm. The general format of Selection type of statement is as shown below:
if(condition)
Statement-1;
else
Statement-2;
The above syntax specifies that if the condition is true, statement-1 will be
executed otherwise statement-2 will be executed. In case the operation is
unsuccessful. Then sequence of algorithm should be changed/ corrected in such
a way that the system will re-execute until the operation is successful.
Iteration: Iteration type algorithms are used in solving the problems which
involves repetition of statement. In this type of algorithms, a particular number
of statements are repeated ‘n’ no. of times.
Example1:
Step 1 : start
Step 2 : read n
Step 3 : repeat step 4 until n>0
Page 9 of 14
Mr. Raushan Kumar
Guest Lecturer CSE Department
 DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Government Polytechnic Banka
Lecture notes for Data Structures and Algorithms

Step 4 : (a) r=n mod 10

(b) s=s+r
(c) n=n/10
Step 5 : write s
Step 6 : stop

Performance Analysis an Algorithm:

The Efficiency of an Algorithm can be measured by the following metrics.
i. Time Complexity and
ii. Space Complexity.
i.Time Complexity:
The amount of time required for an algorithm to complete its execution is its
time complexity. An algorithm is said to be efficient if it takes the minimum
(reasonable) amount of time to complete its execution.
ii. Space Complexity:
The amount of space occupied by an algorithm is known as Space Complexity. An
algorithm is said to be efficient if it occupies less space and required the
minimum amount of time to complete its execution.
1.Write an algorithm for roots of a Quadratic Equation?
// Roots of a quadratic Equation
Step 1 : start
Step 2 : read a,b,c
Step 3 : if (a= 0) then step 4 else step 5
Step 4 : Write “ Given equation is a linear equation “
Step 5 : d=(b * b) _ (4 *a *c)
Step 6 : if ( d>0) then step 7 else step8
Step 7 : Write “ Roots are real and Distinct”
Step 8: if(d=0) then step 9 else step 10
Step 9: Write “Roots are real and equal”
Step 10: Write “ Roots are Imaginary”
Step 11: stop

Page 10 of 14
Mr. Raushan Kumar
Guest Lecturer CSE Department
 DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Government Polytechnic Banka
Lecture notes for Data Structures and Algorithms

2. Write an algorithm to find the largest among three different numbers

entered by user
Step 1: Start
Step 2: Declare variables a,b and c.
Step 3: Read variables a,b and c.
Step 4: If a>b
If a>c
Display a is the largest number.
Else
Display c is the largest number.
Else
If b>c
Display b is the largest number.
Else
Display c is the greatest number.
Step 5: Stop
3.Write an algorithm to find the factorial of a number entered by user.
Step 1: Start
Step 2: Declare variables n,factorial and i.
Step 3: Initialize variables
factorial←1
i←1
Step 4: Read value of n
Step 5: Repeat the steps until i=n
5.1: factorial←factorial*i
5.2: i←i+1
Step 6: Display factorial
Step 7: Stop
4.Write an algorithm to find the Simple Interest for given Time and Rate
of Interest .

Page 11 of 14
Mr. Raushan Kumar
Guest Lecturer CSE Department
 DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Government Polytechnic Banka
Lecture notes for Data Structures and Algorithms

Step 1: Start
Step 2: Read P,R,S,T.
Step 3: Calculate S=(PTR)/100
Step 4: Print S
Step 5: Stop

ASYMPTOTIC NOTATIONS
Asymptotic analysis of an algorithm refers to defining the mathematical
boundation/framing of its run-time performance. Using asymptotic analysis, we
can very well conclude the best case, average case, and worst case scenario of
an algorithm.
Asymptotic analysis is input bound i.e., if there's no input to the algorithm, it is
concluded to work in a constant time. Other than the "input" all other factors are
considered constant.
Asymptotic analysis refers to computing the running time of any operation in
mathematical units of computation. For example, the running time of one
operation is computed as f(n) and may be for another operation it is computed
as g(n2). This means the first operation running time will increase linearly with
the increase in n and the running time of the second operation will increase
exponentially when n increases. Similarly, the running time of both operations
will be nearly the same if n is significantly small.
The time required by an algorithm falls under three types −
 Best Case − Minimum time required for program execution.
 Average Case − Average time required for program execution.
 Worst Case − Maximum time required for program execution.

Asymptotic Notations
Following are the commonly used asymptotic notations to calculate the running
time complexity of an algorithm.
 Ο Notation
 Ω Notation
 θ Notation

Page 12 of 14
Mr. Raushan Kumar
Guest Lecturer CSE Department
 DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Government Polytechnic Banka
Lecture notes for Data Structures and Algorithms

Big Oh Notation, Ο
The notation Ο(n) is the formal way to express the upper bound of an algorithm's
running time. It measures the worst case time complexity or the longest amount
of time an algorithm can possibly take to complete.

For example, for a function f(n)

Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n >
n0. }
Omega Notation, Ω
The notation Ω(n) is the formal way to express the lower bound of an algorithm's
running time. It measures the best case time complexity or the best amount of
time an algorithm can possibly take to complete.

For example, for a function f(n)

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n >
n0. }
Theta Notation, θ
The notation θ(n) is the formal way to express both the lower bound and the
upper bound of an algorithm's running time. It is represented as follows –

Page 13 of 14
Mr. Raushan Kumar
Guest Lecturer CSE Department
 DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
Government Polytechnic Banka
Lecture notes for Data Structures and Algorithms

θ(f(n)) = { g(n) if and only if g(n) = Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0. }

Page 14 of 14
Mr. Raushan Kumar
Guest Lecturer CSE Department