Introduction

Faculty member, Dept. of CSE, IST

 What is Data Structure?
• A data structure is a particular way of storing and organizing data in a
computer’s memory so that it can be used efficiently.

• Data structures are ways to organize and store data in a computer so that it
can be accessed and modified efficiently.
Categories of Data Structure
 Categories of Data Structure
Primitive data Structures: Primitive data structures are the fundamental data types
which are supported by a programming language known as Primitive data Structures.
• Predefined
• Fixed size
• Hold single value
• Ex. Char, int, float, double.

Non- Primitive data Structures: Non-primitive data structures are those data structures
which are created using primitive data structures.
• User defined/ built from primitive
• Variable size
• Can store multiple values
• Ex linked list, stack, queue, tree, and graph.
 Categories of DS
Linear Data Structure:
⚫ A data structure is said to be linear if its elements form any sequence.
In linear data structures, data elements are arranged sequentially, meaning each element
is connected to its previous and next adjacent element in a single, continuous line.

Key Characteristics:
• Sequential Arrangement: Elements are stored in a linear order, one after another.
• Simple Implementation: Generally easier to implement and understand due to their
straightforward nature.
• Easier Traversal: Traversal is typically done by moving from one element to the next in
a predictable order.
• Contiguous or Linked Memory: Can be stored in contiguous memory locations (like
arrays) or scattered but linked via pointers (like linked lists).
 Categories of DS
Non-Linear Data Structures
In non-linear data structures, data elements are not arranged sequentially. Instead, they
are organized in a hierarchical or interconnected manner, where an element can be
connected to multiple other elements. This allows for more complex relationships to be
represented.

Key Characteristics:
• Non-Sequential Arrangement: Elements are not arranged in a linear fashion.
• Complex Implementation: Generally more challenging to implement and understand
due to the intricate connections.
• Complex Traversal: Traversal often requires specialized algorithms (e.g., Depth-First
Search, Breadth-First Search).
• Dynamic Memory Allocation: Elements are typically stored in non-contiguous
memory locations and connected using pointers
 Array

An array is a linear data structure that

collects elements of the same data type
and stores them in contiguous and
adjacent memory locations. Arrays work on
an index system starting from 0 to (n-1),
where n is the size of the array.
 Linked list

A linked list is a linear data structure

which can store a collection of "nodes"
connected together via links i.e.
pointers. Linked lists nodes are not
stored at a contiguous location, rather
they are linked using pointers to the
different memory locations.
A node consists of the data value and a
pointer to the address of the next node
within the linked list
 Stack

A Stack is a linear data structure that follows a

particular order in which the operations are
performed. The order may be LIFO(Last In First
Out) or FILO(First In Last Out). LIFO implies that
the element that is inserted last, comes out first
and FILO implies that the element that is inserted
first, comes out last.

Think of it this way:

• Pushing an element onto the stack is like adding
a new plate on top.
• Popping an element removes the top plate from
the stack
 Queue

Queue is a linear data structure that

follows FIFO (First In First Out)
Principle, so the first element
inserted is the first to be popped out.

FIFO Principle states that the first

element added to the Queue will be
the first one to be removed or
processed. So, Queue is like a line of
people waiting to purchase
tickets, where the first person in line
is the first person served. (i.e. First
Come First Serve).
 Tree

Tree Data Structure is a non-

linear data structure in which a
collection of elements known as
nodes are connected to each
other via edges such that there
exists exactly one path between
any two nodes.
 Graph
Graph is a non-linear data structure consisting of vertices and
edges. The vertices are sometimes also referred to as nodes and the
edges are lines or arcs that connect any two nodes in the graph.
More formally a Graph is composed of a set of vertices( V ) and a set
of edges( E ). The graph is denoted by G(V, E).
 Data Structure Operations
The following four operations play a major role in this text:
• Traversing: accessing each record/node exactly once so that certain items in the record
may be processed. (This accessing and processing is sometimes called “visiting” the record.)
• Searching: Finding the location of the desired node with a given key value, or finding the
locations of all such nodes which satisfy one or more conditions.
• Inserting: Adding a new node/record to the structure.
• Deleting: Removing a node/record from the structure.

The following two operations, which are used in special situations:

• Sorting: Arranging the records in some logical order (e.g., alphabetically according to some
NAME key, or in numerical order according to some NUMBER key, such as social security
number or account number)
• Merging: Combining the records in two different sorted files into a single sorted file.
Mathematical Notations &
Functions
 Modular Arith
metic

Logarithm Floor and Cell

ing Function

INT and Abs

Permutations
Value

Summation Factorial
Control Structures
 Introduction
Control structures are fundamental building blocks in programming
that define the flow of execution of instructions. They help determine
how, when, and under what conditions parts of code are executed.

Using control structures makes programs more readable, modular, and

easier to debug and maintain. These structures allow the program to
analyze conditions and decide which direction to take during execution.

Types:
• Sequence logic, or sequential flow
• Selection logic, or conditional flow
• Iteration logic, or repetitive flow
 Sequence Logic(Sequential Flow)
Sequential logic follows a straight, step-by-step flow of instructions, executed in the
exact order they appear in the program. Unless directed otherwise, the computer
processes each instruction one after another. This is the most basic and commonly
used flow, even for solving complex problems.
 Selection Logic(Conditional Flow)
Selection logic enables a program to make decisions and execute specific blocks of
code based on certain conditions or parameters. It introduces branching, allowing the
flow to take different paths.

Single Alternative (if statement): Executes a block of code only if the condition is true
 Continue…
Double Alternative (if-else statement): Chooses one of two possible blocks based on the
condition.

Multiple Alternative (if-else-if ladder or switch-case): Chooses one out of several possible
blocks.
 Iteration Logic(Repetitive Flow)
Iteration logic allows a set of instructions to be executed repeatedly as long as a certain
condition is true. This is commonly done using loops, which reduce code repetition and
simplify complex tasks.
Each loop has:
• A repetition condition
• A loop body (the module to be repeated)

Repeat-For Structure (for loop): Used when the number of repetitions is known in
advance.
 Continue…
Repeat-While Structure (while or do-while loop): Used when the number of
repetitions is not known in advance, and depends on a condition.
 Algorithm
An algorithm is a self-contained, step-by-step set of instructions used to solve
a problem or perform a task. It takes input, processes it through logical steps, and
produces output.

Think of it like a recipe:

📥 Ingredients → 🛠 Instructions → 📤 Dish
 Essential Properties / Criteria of a Good Algorithm

Property Explanation
Accepts zero or more inputs provided from an external
Input
source.
Produces at least one result, depending on the input and
Output
task.
Each step must be clearly defined, with no ambiguity or
Definiteness
confusion.
All instructions should be basic, easily understandable, and
Effectiveness
executable.
The algorithm must complete after a finite number of
Finiteness
steps, no endless loops.
 Algorithm Complexity
The complexity of an algorithm measures the amount of resources it
requires to complete its task. It helps us understand the efficiency of the
algorithm in terms of time and space.

Time complexity indicates how long an algorithm takes to run as a

function of the size of the input. It measures the total number of basic
operations or steps executed during the algorithm’s process.

Notation:
Often expressed using Big O notation (e.g., O(n), O(log n), O(n²)) which describes
the upper bound of the running time relative to input size n.
 Best, Average, Worst Case.

Best Case: It is defined as the condition that allows an algorithm to complete statement
execution in the shortest amount of time. In this case, the execution time serves as a
lower bound on the algorithm's time complexity.

Average Case: You add the running times for each possible input combination and take
the average in the average case. Here, the execution time serves as both a lower and
upper bound on the algorithm's time complexity.

Worst Case: It is defined as the condition that allows an algorithm to complete statement
execution in the shortest amount of time possible. In this case, the execution time serves
as an upper bound on the algorithm's time complexity.
 Space Complexity
Space complexity measures how much memory or storage an algorithm
needs to complete, relative to the input size.

Components:
Includes the space needed for input data, temporary variables, stack space for
recursion, and any additional data structures used.

Example:
An algorithm that uses a fixed number of variables regardless of input size has
O(1) space complexity (constant space).
 How to measure Complexities

Constant: If the algorithm runs for the same amount of time every time
irrespective of the input size. It is said to exhibit constant time complexity.

Linear: If the algorithm runtime is linearly proportional to the input size then the
algorithm is said to exhibit linear time complexity.

Exponential: If the algorithm runtime depends on the input value raised to an

exponent then it is said to exhibit exponential time complexity.

Logarithmic: When the algorithm runtime increases very slowly compared to an

increase in input size i.e. logarithm of input size then the algorithm is said to
exhibit logarithmic time complexity.
 Continue…
Notation Name Example

O(1) Constant Time Accessing an element in an array: arr[5]

O(log N) Logarithmic Binary Search in a sorted array

O(N) Linear Time Looping through an array once

O(N log N) Log Linear Merge Sort, Quick Sort (average case)

O(N²) Quadratic Bubble Sort, Insertion Sort, Nested loops

Triple nested loops, Matrix multiplication (naive

O(N³) Cubic
way)

O(2^N) Exponential Solving the Tower of Hanoi, recursive Fibonacci

O(N!) Factorial Solving Traveling Salesman using brute-force

Continue…
Calculating Time Complexity
Continue…
Continue…
Continue…
End