❖Vision of the Department

• To be on the cutting edge of computer science and

engineering, producing globally competent graduates with
commendable knowledge and excellent skills who are
committed to building a flourishing nation.

❖Mission of the Department

• To provide top-notch experiential learning opportunities to

acquire proficiency with contemporary software tools and
meet industry demands in real time with a sense of societal
and ethical responsibilities.

Department of Computer Science and Engineering

Introduction to Data Structure


Department of Computer Science and Engineering

 
Contents

▪ Introduction:

▪ Introduction to Data Structures:

▪ Abstract Data Types (ADT),

Department of Computer Science and Engineering

▪ Linear and Non-linear,

▪ Static and Dynamic,

▪ Persistent and Ephemeral data structures

 
Learning Outcome

▪ At the end of this session, every learner will be able to

understand
▪ Data structures
Department of Computer Science and Engineering

▪ Its types

▪ Its Examples

▪ Where it can be used? (Applications)

▪ Which operations can be performed on it?

 
Contents

▪ Data Structures
▪ A data structure is a way of organizing and storing
data so that it can be accessed and modified
Department of Computer Science and Engineering

efficiently.

▪ Purpose:
▪ Efficient data manipulation
▪ Logical data representation
▪ Better algorithm performance
 
Contents

▪ Its types

▪ Primitive and Non-primitive DS

▪ Linear and Non-linear DS

Department of Computer Science and Engineering

▪ Sequential and Linked DS

▪ Persistent and Ephemeral DS

• Examples of DS

• Operations on DS
 
Data, Data Objects and Data Structures

▪ Data : Meaningful information.

▪ e.g. : Name of Person, Adhar Number of Person etc.

▪ Data Objects : Group of Meaningful

Department of Computer Science and Engineering

information.
▪ e.g. : Group of employees, Group of Students etc.

• Data Structures : Organization of Group of

Meaningful information.
▪ e.g. : Employee Management, Students Class Management.
 
Data, Data Objects and Data Structures

Is this
sufficient
Department of Computer Science and Engineering

information?
 
Data Structures

• A data structure is a specialized format for

organizing and storing data.

• General data structure types include the

array, the file, the record, the table, the
Department of Computer Science and Engineering

tree, and so on.

• Any data structure is designed to organize

data to suit a specific purpose so that it can
be accessed and worked with in appropriate
ways.
  Types of Data structures

Types of DS

Non-Primitive
Primitive DS
DS

Non-Linear
Int Linear DS
DS
Department of Computer Science and Engineering

Float Array Tree

Char Linked List Graph

Boolean Stack

Queue
 Primitive Data Structures V/s


Non-Primitive Data Structures

Primitive Data Non-Primitive Data
Structures Structures
• Non - Primitive Data
• Primitive Data Types or
structures are not
structures are predefined
data types. predefined in
Department of Computer Science and Engineering

programming languages.
• All they are supported by
all programming • They can be implemented
languages. with the help of primitive
data types.

• They are linear or non

linear in nature.

• Examples are : • Examples are :

▪ int, float, char ▪ Linear DS : Array,
Linked Lists

▪ Non Linear DS : Tree,

Graph
 Linear v/s Non-Linear Data


Structure
• Linear data structure ▪ Non-Linear data structure
grows linearly. does not grow linearly.
• Different operation which
can be performed are in ▪ They grows level wise.
a linear way.
▪ Examples of Non - Linear
• Examples of Linear DS:
Department of Computer Science and Engineering

DS:
– Array
▪ Tree
0 1 2 3 4 5
6
1 2 3 4 5 6
7 ▪ Graph
– Linked List
Node 0 Node 1 Node 2 Node 3
1 2 3 4
 Linear Data Structure


▪ Linear data structure grows linearly.

▪ Different operation which can be performed are in a linear

way.

▪ Examples of Linear DS:

Department of Computer Science and Engineering

▪ Array 0 1 2 3 4 5
6
1 2 3 4 5 6
7

▪ Linked List Node 0 Node 1 Node 2 Node 3

1 2 3 4
 Non-Linear Data Structure


▪ Non-Linear data structure does not grow linearly.

▪ They grows level wise.

▪ Examples of Non - Linear DS:

Department of Computer Science and Engineering

▪ Tree -- Graph
  Sequential v/s
Non-Sequential Data Structures
• Data structure utilizes
▪ Data structure utilizes memory which is not
memory which is allotted allotted sequentially.
sequentially.
• Memory allotted is
scattered in the memory
Department of Computer Science and Engineering

space.

▪ Example : • Example :
▪ Arrays (1D, 2D, nD) – Linked Lists
– Tree
▪ Char Array (Strings)
– Graph
▪ Array of Structures
 Persistent v/s Ephemeral Data


Structures
▪ The data structure which ▪ The data structure which
persists its previous does not persists its
version even after previous version after
performing different performing different
operations. operations.

▪ Example ▪ Example
▪ Stack ▪ Queue Vrsn # 1 a

Vrsn # 2 a b
Change in Operation
30
Vrsn # 3 a b c
20 20 20
Change in Operation
Vrsn # 4 b c
10 10 10 10 10

Vrsn # 1 Vrsn # 2Vrsn # 3Vrsn # 4Vrsn # 5 Vrsn # 5 c

 Persistent Data Structure


▪ Persistent Data Structures

▪ Definition:
Persistent data structures preserve all previous versions of the data structure, even after updates.

▪ Types of Persistence:

▪ Partial Persistence:
Department of Computer Science and Engineering

▪ Can access any version, but only the latest version can be modified.

▪ Full Persistence:
▪ Can access and modify any version.

▪ Confluent Persistence:
▪ Allows merging versions (less common, more advanced).

▪ Characteristics:
▪ Do not overwrite old data.

▪ Enable features like undo, backtracking, and version control.

▪ Common in functional programming and immutable design

 Ephemeral Data Structure


▪ Ephemeral Data Structures

▪ Definition:
Ephemeral data structures are traditional structures where each update (insert, delete,
modify) destroys the previous version.

▪ Characteristics:
Department of Computer Science and Engineering

▪ Only the most recent version is available.

▪ Updates are in-place.

▪ Common in imperative programming.

▪ Examples:

▪ Arrays

▪ Linked Lists

▪ Stacks

▪ Queues (standard versions)

 
Table and Example

Feature Ephemeral Persistent

Multiple versions
Versioning Single version only
maintained

Updates In-place Creates new version

Department of Computer Science and Engineering

Performance-focused History tracking, undo,

Use Case
apps backtrack

Programming Style Imperative Functional

Example Language C, Java (traditional) Haskell, Clojure, Scala

Example:

Imagine a stack:Ephemeral: Each pop() or push()

modifies the same structure.Persistent: Each push() or pop()
creates a new stack version, preserving the old one.
Static v/s Dynamic Data Structures


▪ Static: ▪ Dynamic:

▪ - Size is fixed at compile time ▪ - Size can change at

runtime
▪ - Memory allocation is
predetermined ▪ - Memory is allocated as
needed

▪ - Example: Array
▪ - Examples: Linked List,
Dynamic Arrays
 
Examples of DS

▪ Arrays ▪ Linked
Lists
▪ Matrix
▪ Tree
Department of Computer Science and Engineering

▪ Strings
▪ Graph
▪ Stack

▪ Tables
▪ Queues

▪ Files
 
Applications of DS

▪ DS can be used in: (few applications)

Department of Computer Science and Engineering

▪ Recursive Function Calls (stack)

▪ Printer in Network (Queue)

▪ Store Data (Files)

▪ Connect Cities (Graph)

  Definition of ADT
▪ Abstract Data type (ADT) An Abstract Data Structure is the
conceptual blueprint of how data can be stored, accessed, and
manipulated, without being concerned about the actual
implementation in programming languages.

▪ It is called “abstract” because it gives an implementation-

Department of Computer Science and Engineering

independent view.

▪ The process of providing only the essentials and hiding the details
is known as abstraction.
 
Example of ADT

▪ It focuses on
Stack
▪ What operations can be Size Top
performed (e.g., insert,
Type
delete, search)
Values
▪ Not on how the operations
are implemented internally
Stack
Department of Computer Science and Engineering

▪ Stack ADT Push Pop Display

▪ Set of Values:
▪ Data Type of Stack
Operations
▪ Size of Stack

▪ Top of Stack

▪ Set of Operations:
▪ Push
Stack ADT
▪ Pop

▪ Display
  Why Abstract Data Structures?

▪ Helps to write efficient and reusable code.

▪ Makes problem-solving easier by using well-defined

models of data handling.
Department of Computer Science and Engineering

▪ Provides a foundation for data structure design and

algorithm analysis
 
Operations on DS

▪ General operations can be performed on DS:

▪ Create DS

▪ Insert elements in DS

▪ Delete elements in DS
Department of Computer Science and Engineering

▪ Display elements of DS

▪ Search elements from DS

▪ Delete elements from DS

▪ Modify elements in DS
 
Operations on DS

ADS Type Key Operations Example Usage

Stack push, pop, peek Undo functionality in editors

Queue enqueue, dequeue Print job scheduling

Linked List insert, delete, traverse Dynamic memory allocation

Department of Computer Science and Engineering

Tree insert, delete, search File system hierarchy

Graph add edge, traversal Social networks, maps

Hash Table insert, search, delete Fast lookups like DNS caching
 
Algorithm Content
▪ Algorithms:

▪ Space complexity,

▪ Time complexity, Frequency Count

▪ Importance of FC in analysis of an algorithm

▪ Asymptotic notation- Big-O, Theta and Omega,

Department of Computer Science and Engineering

▪ Finding complexity using step count method,

▪ Analysis of programming constructs-Linear,

▪ Quadratic,

▪ Cubic,

▪ Logarithmic.
 
Algorithm
▪ At the end of this session, every learner
will be able to understand

▪ Frequency Count
Department of Computer Science and Engineering

▪ Time Complexity
▪ Space Complexity
▪ Asymptotic Notations
 
Algorithm – Definition

▪ Algorithm is
▪ A fine

▪ Clearly specified

▪ Sequence of instructions
Department of Computer Science and Engineering

▪ To be followed to solve the problem

▪ Or to complete the task.

  Characteristics of Good
Algorithms
▪ Effectiveness ▪ Output
▪ Simple ▪ One or more output
▪ Unambiguous ▪ Correctness
▪ Definiteness ▪ Gives correct output for
▪ Well ordered / all possible cases
sequenced ▪ Finiteness
Department of Computer Science and Engineering

▪ Clear ▪ Halt / stop in finite

▪ Precisely defined amount of

▪ Input ▪ steps

▪ Zero or more number ▪ time

of inputs
 Factors Affecting Time
Complexity of Algorithms

• Time

• Space

• Network
Department of Computer Science and Engineering

• Power Consumption

• CPU register Consumption

 Analysis of Algorithms


▪ It’s a criteria to judge the working of

algorithms

▪ Analysis could be done by measuring the

Department of Computer Science and Engineering

performance of algorithms through

1. Time requirement

2. Space requirement
  1. Time Complexity

▪ Time complexity refers to how the execution time

of an algorithm grows with the input size.
▪ Purpose

▪ It helps understand how the execution time of an

Department of Computer Science and Engineering

algorithm changes as the input data grows.

▪ Time complexity can be calculated from the
frequency count.
 Time
 Complexities Evaluation

Time Complexity is calculated in following steps:

• Write algorithm.

• Obtain Frequency Count.

Department of Computer Science and Engineering

• Consider on the magnitude, discard constants

and ignore coefficients.

• Pick only the most significant term.

  Frequency Count
▪ A frequency count is a measure of the number of times
that an event occurs.
▪ A frequency count is the number of steps executed and
the total number of times (i.e., frequency) each statement
is executed.
▪ To determine the step count of an algorithm,
1. First, determine the number of steps per
Department of Computer Science and Engineering

execution of each statement

2. Second, determine the total number of times
(i.e., frequency) each statement is executed.
3. Combining these two quantities gives us the total
contribution of each statement to the total step count.
  Frequency Count

▪ Time Complexity ▪ Space Complexity

▪ def swap(x,y): ▪ def swap(x,y):

▪ Temp = x ---------------1 ▪ Temp = x ----------------1

▪ x = y----------------------1 ▪ x = y-----------------------1
Department of Computer Science and Engineering

▪ y = Temp----------------1 ▪ y = Temp-----------------1
▪ -------------------- f(n) = 3 ▪ -------------------- s(n) = 3
 Example
 of Frequency Count

Algorithm Count Algorithm Count

int p = 0; 1 int p = 0; 1

for (i=0; i<5; i++) 6 (5+1) for (i=0; i<n; i++) n+1

{ - { -

cout << i; 5 cout << i; n

Department of Computer Science and Engineering

p = p + i; 5 int p = p + i; n

} - } -

TOTAL FC 17 TOTAL FC 3n+2

 Types of Time Function


Time
Name Example Description
Function

Time doesn't change with

O(1) Constant Time Accessing array element arr[i]
input size.

Logarithmic Time grows slowly even

O(log n) Binary Search
Time with large inputs.

Time grows directly with

O(n) Linear Time Linear Search
input size.

Linearithmic Efficient sorting and

Department of Computer Science and Engineering

O(n log n) Merge Sort, Quick Sort (avg)

Time divide & conquer.

Time grows rapidly; bad

O(n²) Quadratic Time Bubble Sort, Selection Sort
for large inputs.

Very inefficient for large

O(n³) Cubic Time Matrix multiplication (naive)
data.

Exponential Time doubles with each

O(2ⁿ) Recursive Fibonacci
Time input increase.

Solving Traveling Salesman

O(n!) Factorial Time Extremely inefficient.
via brute-force
 Types of Time Function


1 < logn < √n < n < nlogn < n² < n³ < …….. <2ⁿ <3ⁿ <nⁿ
Department of Computer Science and Engineering
Common
 Time Complexities
Department of Computer Science and Engineering
  Why is Time Complexity
Important?

▪ It Predicts how an algorithm performs as

input size grows.
▪ Helps in comparing different algorithms
Department of Computer Science and Engineering

solving the same problem.

▪ Crucial in selecting the most efficient
algorithm for large data sets.
 Common
 Time Complexities

Time
Name Example Scenario
Complexity

O(1) Constant time Accessing an array element by index

O(log n) Logarithmic time Binary Search

O(n) Linear time Linear search, traversing an array

O(n log n) Linearithmic time Merge Sort, Quick Sort (average case)
Department of Computer Science and Engineering

O(n²) Quadratic time Bubble Sort, Insertion Sort

O(2ⁿ) Exponential time Solving recursive problems like Fibonacci

Solving the Traveling Salesman Problem

O(n!) Factorial time
(TSP)
  2. Space Complexity
▪ Space Complexity of program is the amount of memory that it needs to
run the algorithm / program.

▪ The space needed by a program is the sum of the following two

components
▪ Fixed space requirement

▪ Space that do not depend on the number or size of program

▪ It includes
Department of Computer Science and Engineering

▪ Instruction space

▪ Variable / constants space

▪ Variable space requirement

▪ Space depend on the particular instance.

▪ It includes

▪ Control statements like while. Do-while, for loops

▪ Recursive function call.

Example
 of Space Complexity
Department of Computer Science and Engineering
  Asymptotic Notations

▪ Asymptotic notations is a short hand way to represent the time

complexity.
▪ Asymptotic notation describes the growth rate of an algorithm’s time
or space complexity as the input size n becomes very large.
▪ It helps to:

▪ Ignore constant factors and lower-order terms

Department of Computer Science and Engineering

▪ Focus on how the algorithm scales with input size

▪ Using asymptotic notations, we can give time complexity as

▪ Fastest Possibility by big O (Upper Bound)
▪ Lowest Possibility by Ω (Lower Bound)
▪ Average Possibility by Θ (Average Bound)
 Cases to Examine

▪ Best Case

▪ Fewest number of instructions executed.

▪ Worst Case
Department of Computer Science and Engineering

▪ Highest number of instructions executed.

▪ Average Case
▪ Average number of instructions executed.
 Asymptotic Notations

O Notation Ω Notation Θ Notation

▪ Used to represent • Used to represent • Used to represent

“Lower Bound” of algorithms running
“Upper Bound” of
algorithms running time “between Upper
algorithms running time. and Lower Bound”.
time.
Department of Computer Science and Engineering

▪ Longest time of
Computation • Shortest time of • Average time of
computation computation
 Cases to Examine

Notation Name Describes Example

"T(n) = O(n²)" means time

O(f(n)) Big-O Upper bound (worst case)
won’t grow faster than n²

"T(n) = Ω(n)" means time

Ω(f(n)) Omega Lower bound (best case)
takes at least linear time

"T(n) = Θ(n log n)" means

Department of Computer Science and Engineering

Θ(f(n)) Theta Tight bound (average case)

time grows exactly at n log n

"T(n) = o(n²)" means grows

o(f(n)) Little-o Strict upper bound
slower than n²

"T(n) = ω(n)" means grows

ω(f(n)) Little-omega Strict lower bound
faster than linear
 Big O Notation
▪ Describes the asymptotic behavior of a function, not its
exact value. i.e order of growth of time or space in terms of
input size.

▪ It can be used to compare the efficiency of different

algorithms or data structures.

▪ It provides an upper limit on the time taken by an algorithm

Department of Computer Science and Engineering

in terms of the size of the input.

▪ We mainly consider the worst-case scenario of the

algorithm to find its time complexity in terms of Big O

▪ It’s denoted as O(f(n)), where f(n) is a function that

represents the number of operations (steps) that an
algorithm performs to solve a problem of size n.
 BIg O Definition
Given two functions f(n) and g(n),

we say that f(n) is O(g(n)) if there exist constants c > 0 and n0

>= 0 such that

f(n) <= c*g(n) for all n >= n0.

In simpler terms, f(n) is O(g(n))

Department of Computer Science and Engineering

if f(n) grows no faster than c*g(n) for all n >= 1 where c and
n0 are constants.

Example => f(n) = 2n+3

2n+3<=10n , n>=1 , f(n) = O(n)
2n+3<=2n+3n , n>=1 , f(n) = O(n)
2n+3<=2n^2+3n^2 , n>=1 , f(n) = O(n^2)

1 < logn < √n < n < nlogn < n² < n³ < …….. <2ⁿ <3ⁿ <nⁿ
Big O Notation
Department of Computer Science and Engineering
 Big-Omega Ω Notation
Given two functions g(n) and f(n),
we say that f(n) = Ω(g(n)), if there exists constants c
>0 and n0 >= 0 such that

f(n) >= c*g(n) for all n >= n0.

In simpler terms, f(n) is Ω(g(n)) if f(n) will always grow faster

than c*g(n) for all n >= n0 where c and n0 are constants.
Department of Computer Science and Engineering

Example => f(n) = 2n+3

2n+3>=1*n , n>=1 , f(n) = Ω(n)
2n+3>=logn , n>=1 , f(n) = Ω(logn)

1 < logn < √n < n < nlogn < n² < n³ < …….. <2ⁿ <3ⁿ <nⁿ
Big-Omega Ω Notation
Department of Computer Science and Engineering
 Θ (Theta) Notation
Let g and f be the function from the set of natural numbers
to itself.

The function f is said to be Θ(g), if there are constants c1,

c2 > 0 and a natural number n0 such that

c1* g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0

Department of Computer Science and Engineering

Example => f(n) = 2n+3

1*n<=2n+3<=5*n, f(n) = Θ(n)

1 < logn < √n < n < nlogn < n² < n³ < …….. <2ⁿ <3ⁿ <nⁿ
Θ (Theta) Notation
Department of Computer Science and Engineering

Department of Computer Science and Engineering