Data Structures & Algorithms

UNIT 1
 Data structures are the fundamental building blocks of computer programming.

 Data Structure defines how data is organized, stored, and manipulated within a
program

 Data Structure is a way of organizing and storing data so that it can be accessed and
modified efficiently.

 Understanding data structures is very important for developing efficient and effective
algorithms

 Data structure is a storage that is used to store and organize data.

 It is a way of arranging data on a computer so that it can be accessed and updated

efficiently.
WHY DATA STRUCTURES IS IMPORTANT ?

✔ Helps manage large amounts of data

✔ Enables faster processing

✔ Crucial for writing efficient algorithms

Real-life Analogy:

Like organizing books in a library (shelves, sections, labels)

Classification of Data Structure:
COMMON DATA STRUCTURES
 Linear Data Structures are a type of data structure in computer science where data elements are
arranged sequentially or linearly.

 Each element has a previous and next adjacent, except for the first and last elements.

Characteristics of Linear Data Structure:

 Sequential Organization: In linear data structures, data elements are arranged sequentially, one after
the other. Each element has a unique predecessor (except for the first element) and a unique
successor (except for the last element)

 Order Preservation: The order in which elements are added to the data structure is preserved. This
means that the first element added will be the first one to be accessed or removed, and the last
element added will be the last one to be accessed or removed.

 Fixed or Dynamic Size: Linear data structures can have either fixed or dynamic sizes. Arrays typically
have a fixed size when they are created, while other structures like linked lists, stacks, and queues can
dynamically grow or shrink as elements are added or removed.
 Efficient Access: Accessing elements within a linear data structure is typically efficient.
For example, arrays offer constant-time access to elements using their index.

Common linear data structures include:

Arrays: Collection of elements stored in contiguous memory locations.

Linked Lists: Collection of nodes, each containing an element and a reference to the next
node.

Stacks: A collection of elements with Last-In-First-Out (LIFO) order.

Queues: A collection of elements with First-In-First-Out (FIFO) order.

Non-linear Data Structures:

 Non-linear data structures are those in which elements are not organized in a sequential manner
with a unique predecessor and successor.

 These structures do not follow a linear order, and elements can have multiple predecessors and
successors, creating complex relationships between elements.

Examples

 Trees: Elements are organized in a hierarchical structure with a root node and child nodes. Each
node can have multiple children, but there is a single path between any two nodes.

 Graphs: Elements (vertices/nodes) are connected by edges, forming arbitrary relationships

between them. Graphs can be directed (edges have a specific direction) or undirected (edges
have no direction).
 Linear data structures are typically used for simpler, straightforward scenarios

 Non-linear data structures are employed to model complex relationships and networks, allowing
for more advanced applications and problem-solving strategies.

 Both types of data structures play essential roles in various computer science applications, and
understanding their characteristics helps in choosing the most suitable data structure for specific
tasks and algorithms.

 Examples:

 Use arrays for fixed-size collections with direct access to elements.

 Linked lists are suitable for dynamic collections with frequent insertions and deletions.

 Trees and graphs are useful for hierarchical or interconnected data.

 Application of Stack

Function Call Management (Recursion & Stack Frames)

 Stacks are used to manage function calls in programming languages.

 The call stack keeps track of active subroutines or function calls.

 When a function is called, its context is pushed onto the stack; when it returns, it's popped.

Expression Evaluation and Conversion

 Stacks are used to evaluate arithmetic expressions (e.g., infix, postfix, prefix).

 They're especially useful for converting infix expressions to postfix (Reverse Polish Notation)
and evaluating them.
Undo Mechanism in Text Editors

 Applications like text editors (e.g., Microsoft Word) use stacks to implement undo and redo
operations.

 Each user action is pushed onto an "undo" stack.

 When an undo is triggered, the action is popped from the undo stack and pushed onto a "redo"
stack.

Browser History Navigation

 Web browsers use stacks to manage the history of visited pages.

 The "Back" button pops the current page from the stack and shows the previous one.

 A separate stack may be used to implement the "Forward" functionality.

Parentheses/Brackets Matching in Compilers

 Stacks are used by compilers to check for balanced parentheses, brackets, or braces in code.

Reversing Data (Strings, Arrays, etc.)

 Stacks are used to reverse strings, arrays, or linked lists.

 By pushing elements onto a stack and then popping them, the order is reversed.
 Application of Queue
CPU Scheduling / Process Scheduling

 Queues are used to manage processes in operating systems using scheduling algorithms like
FCFS (First Come First Serve) or Round Robin.

Print Queue

 When multiple print jobs are sent to a printer, they are queued and printed in the order they
arrive

Keyboard/Buffer Handling

 Key presses are stored in a queue (keyboard buffer) and processed in the same order they
are

typed.
Call Center / Customer Service

 Incoming customer calls are placed in a queue and answered in the order they arrive.

Searching in Graphs

 BFS algorithm( Breadth first search algorithm ) uses a queue to explore nodes level by level.

Network Packet Management

 Routers and switches use queues to manage data packets before forwarding them to the

destination.
 Application of Tree Data Structure

File System Organization

 Operating systems use a tree structure to represent files and directories

 Root of the tree is the main directory

 Each directory (folder) can contain files (leaves) and subdirectories (branches), forming a
hierarchical tree

Routing Algorithms in Networking

 Tree structures are used to determine routing paths in networks.

AI Game Trees
 Used in games like chess, tic-tac-toe, etc., to explore possible moves
 Each node represents a game state, and branches represent possible moves
Binary Search Tree (BST) for Searching and Sorting
 A BST allows fast lookup, insertion, and deletion of data
Expression Trees in Compilers
 Used to represent and evaluate arithmetic expressions.
 Operators are internal nodes, and operands (numbers/variables) are leaves
 Example : (2 * 5) + 3
Autocomplete and Spell Check

 Tree is used in text editors and search engines to store a dictionary of words, allowing quick
word lookup, autocomplete, and spell checking.
 Application of Graph

Social Networks
 Users are represented as nodes, and friendships/followers are edges
 Used to find connections, friend suggestions, etc.

Google Maps and GPS Navigation

 Locations (cities/intersections) are nodes, and roads are edges.
 Used to find the shortest path between places
Network Routing

 Computers/routers are nodes, and communication links are edges.

 Graph algorithms help in packet routing and network optimization.

Web Page Linking (Internet)

 Web pages are nodes, and hyperlinks are edges.

 Search engines use this graph to rank pages

Recommendation Systems

 Items and users are represented as nodes

 Edges represent interactions (likes, ratings, views)

 Used in platforms like Netflix, Amazon, or YouTube to suggest related items based on user

behavior.
 Choice of Right Data Structure:

Key Considerations:

 Size of data

 Type of operations (Insert/Delete/Search)

 Memory constraints

 Performance needs
Choice of Right Data Structure:

Factors to Consider:

 Efficiency: Choose a data structure that optimizes the required operations for the given
problem.

Space Complexity: Consider the amount of memory the data structure consumes.

Scalability: Ensure that the data structure can handle growing datasets efficiently.

Simplicity: Opt for simpler data structures when the problem doesn't demand complex ones.
Algorithm : An algorithm is a step-by-step method for solving some problem.

Algorithms characteristics:

Input: The algorithm receives input. Zero or more quantities are externally supplied.

Output: The algorithm produces output. At least one quantity is produced.

Precision: The steps are precisely stated. Each instruction is clear and unambiguous.

Feasibility: It must be feasible to execute each instruction.

Flexibility: Possible to make changes in the algorithm without putting so much effort on it.

Generality: The algorithm applies to a set of inputs.

Finiteness: Algorithm must complete after a finite number of instruction have been executed.
How to Design and Develop Algorithms:

 Problem Understanding: Clearly understand the problem requirements, constraints, and

expected outcomes.

 Plan and Pseudocode: Outline the steps to solve the problem in a high-level language-
independent manner (pseudocode).

 Choose the Right Data Structure: Based on the problem requirements, select the
appropriate data structure to represent the data.

 Break Down the Problem: Divide the problem into smaller subproblems and solve them
individually.

 Step-by-Step Implementation: Write the algorithm in a programming language, one step at

a time.
How to Design and Develop Algorithms:

Testing and Optimization: Test the algorithm with various inputs, identify bottlenecks, and
optimize it for better performance.

Analyze Complexity: Analyze the time and space complexity of the algorithm to ensure it meets
the problem requirements.
 Operations on Data Structures

 Insertion

 Deletion

 Traversing

 Searching
INSERTION OPERATION IN ARRAY
7. For i = n - 1 to pos , repeat
1.Start
arr[i + 1] = arr[i]
2. Read the size of array ‘n’ and the array
elements 8. arr[pos] = x

3. Read the data ‘x’ to be inserted 9. Set n = n + 1

4. Read the position pos (0 ≤ pos < n) where the 10. Print "DATA inserted successfully"
data is to be inserted
11. Print the updated array
5. If n == MAX, then
12. End
Print "Array is full"

Go to Step 12

6. If pos < 0 or pos > n, then

Print "Invalid position"

Go to Step 12
 Deletion in Array
1. Start 6. For i = pos to n - 1, repeat
2. Read the size of array ‘n’ and the array arr[i] = arr[i + 1]
elements 7. Set n = n - 1
3. Read the position pos (0 ≤ pos < n) from 8. Print "DATA deleted successfully"
where the data is to be deleted
9. End
4. If n == 0, then
Print "Array is empty"
Go to Step 9
5. If pos < 0 or pos >= n, then
Print "Invalid position"
Go to Step 9
 Traversing in Array
1. Start
2. Read the size of array ‘n’ and the array elements
3. If n == 0, then
Print "Array is empty"
Go to Step 6
4. For i = 0 to n - 1, repeat
Print arr[i]
5. Print "Array traversed successfully"
6. End
 Searching in Array

6. For i = 0 to n - 1, repeat
1. Start
If arr[i] == x, then
2. Read the size of array ‘n’ and the
array elements Print "Element found at position i”

3. Read the data ‘x’ to be searched Set found = 1

Go to Step 8
4. If n == 0, then
7. If found == 0, then
Print "Array is empty"
Print "Element not found"
Go to Step 8
8. End
5. Set found = 0
 Complexity of Algorithm

 Analysis of an algorithm refers to the process of deriving estimates for the time and space needed to
execute the algorithm

 Complexity in algorithms refers to the amount of resources (such as time or memory) required to solve a
problem or perform a task.

 Estimate the time (e.g., the number of steps) and space (e.g., the number of variables) required by
algorithms.

 Algorithm complexity measures how many steps are required by the algorithm to solve the given problem.
Analysis (Complexity) of Algorithms

 Evaluates the order of count of operations executed by an algorithm as a function of input data size.

 O(f) notation represents the complexity of an algorithm, which is also termed as an Asymptotic
notation or "Big O" notation

 O(f) determines in which order the resources such as CPU time, memory, etc. are consumed by the
algorithm that is articulated as a function of the size of the input data.

 Knowing the time and space required by algorithm allows us to compare the algorithms that solve the
same problem.
 If one algorithm takes n steps to solve a problem and another algorithm takes n2 steps to solve the same
problem, then first algorithm will be preferred.

 Estimation of time and space needed to execute the algorithm is called the time and space complexity of
the algorithm.
Time complexity

 Time Complexity refers to the amount of time an algorithm takes to produce a result as a function of the
size of the input.

 Time taken by the algorithm to solve the problem

 It is measured by calculating the iteration of loops, number of comparisons etc.

 Time complexity is a function describing the amount of time an algorithm takes in terms of the amount of
input to the algorithm.

 Time complexity of an algorithm is the amount of time it takes for each statement to complete.

 It is highly dependent on the size of the processed data.

 “Time” mean the number of memory accesses performed, the number of comparisons between integers,
the number of times some inner loop is executed.

 Time required to execute an algorithm is a function of the input f(n)

Three cases for time complexity of an algorithm

 Worst-case: f (n) represent by the maximum number of steps taken on any instance of size n.

 Best-case: f (n) represent by the minimum number of steps taken on any instance of size n.

 Average case: f (n) represent by the average number of steps taken on any instance of size n.
Space complexity

 Amount of memory used by a program to execute is represented by its space complexity.

 Program requires memory to store input data and temporal values while running .

 Algorithm designers strive to develop algorithms with the lowest possible time and space complexities,
since this makes them more efficient and scalable.
Complexities of an Algorithm

 Constant Complexity: It undergoes an execution of a constant number of steps . It imposes a

complexity of O(1)

 Logarithmic Complexity: It imposes a complexity of O(log(N)). It undergoes the execution of

the order of log(N) steps.

 Linear Complexity: It imposes a complexity of O(N). It encompasses the same number of steps
as that of the total number of elements to implement an operation on N elements.

 Quadratic Complexity: It imposes a complexity of O(n2). For N input data size, it undergoes the
order of N2 count of operations on N number of elements for solving a given problem.
 Complexities of Algorithm

 Cubic Complexity: It imposes a complexity of O(n3). For N input data size, it executes the order
of N3 steps on N elements to solve a given problem.

 Exponential Complexity: It imposes a complexity of O(2n), O(N!), O(nk), …. For N elements, it

will execute the order of count of operations that is exponentially dependable on the input data
size.
 O(1) refers to constant time complexity, which means that the running time of an algorithm
remains constant and does not depend on the size of the input.

 Time complexity of a function (or set of statements) is considered as O(1) if it doesn’t contain a
loop, recursion, and call to any other non-constant time function.

 Time Complexity of a loop is considered as O(n) if the loop variables are

incremented/decremented by a constant amount

for (int i = 1; i <= n; i ++)

statements

}
 Time complexity, denoted as O(n2), refers to an algorithm whose running time
increases proportional to the square of the size of the input
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= n; j ++)
{
statements
}
}
 Time Complexity of a loop is considered as O(Logn) if the loop variables are divided/multiplied by
a constant amount

for (int i = 1; i <= n; i *= c)

statements

}
Algorithm: Sum of First N Numbers

1. Start Time Complexity : O(n)

2. Read a number n.
3. Set sum = 0.
4. For i = 1 to n do:
sum = sum + i
5. Print sum.
6. End
Algorithm : Find the largest element in an array.

Time Complexity : O(n)

Algorithm : Print all pairs of elements in an array.

Time Complexity : O(n2)

 Linear Search Technique
 Binary Search Technique
 Complexity Analysis
 Linear Search Technique
 Linear search is a method for searching for
a data in a collection of data

 Linear Search checks each data of the list

one by one until the required data is found
or the list ends.

 Each data of the collection is visited one by

one in a sequential fashion to find the
desired data

 Linear search is also known as sequential

search

 Linear Search works on both sorted and

unsorted arrays.
Algorithm : Linear Search Technique
1. Start
2. Read the size of array ‘n’ and the array elements.
3. Read the element ‘x’ to be searched.
4. Repeat steps for i = 0 to n-1:
a) If arr[i] == x then
b) Print "Element found at position i”
c) Go to Step 6
5. If element not found, print "Element not present in array".
6. End
Linearsearch(arr, n, x):

for i = 0 to n-1 do

if arr[i] = x then

return i // element found at index i

return -1 // element not found

Example : arr[ ] = {10, 50, 30, 70, 80, 20, 90, 40} and key = 30
Time Complexity:

Best Case: O(1) , Element is found at the first position.

Worst Case: O(n) , Element is at the last position or not present at all.

Average Case: O(n) ,On average, the element is somewhere in the middle.

Space Complexity: O(1), No extra space is used except a few variables.

Applications of Linear Search :

 Unsorted Data Searching: When data is not sorted and we need to find an item

 Small Data Sets: Efficient for small arrays or lists

 Database Lookups : Useful for quick lookups in small tables or files

 Searching in Unstructured Data : searching for a specific keyword in a large text file.

 Inventory Systems : Searching for a product in an unsorted list of items in small-scale shops or
warehouses.

Disadvantage
 Linear search has a time complexity of O(N), which in turn makes it slow for large
datasets.

 Linear search is simple but inefficient for large datasets.

 Binary Search Technique
 Binary Search is an efficient searching algorithm used only on sorted arrays/lists.

 It works on the Divide and Conquer principle:

 Works by repeatedly dividing the search interval in half, reducing the search space until the
target data is found or not found

a) Compare the target data ‘x’ with the middle data of array

b) If x is equal : data found.

c) If x is smaller : search in left half.

d) If x is greater : search in right half.

 This process repeats until the data is found or the sub-array becomes empty.
Algorithm : Binary Search Technique
1. Start
2. Read the size of array ‘n’ and sorted array elements.
3. Read the data ‘x’ to be searched.
4. Initialize low = 0, high = n-1
5. Repeat while low <= high:
a) Find mid = (low + high) / 2.
b) If arr[mid] == x, then print " Data found at position mid" and Goto Step 7.
c) If x < arr[mid] , set high = mid - 1.
d) If x> arr[mid] , set low = mid + 1
6. Print " Data not present in array".
7. End
Binarysearch(arr, n, x):
low = 0
high =n - 1
while low <= high do
mid =(low + high) / 2
if arr[mid] == x then
return mid // element found
else if x < arr[mid] then
high =mid - 1
else
low =mid + 1
return -1 // element not found
Time Complexity

Best Case: O(1), Data found at the middle position in the first step.

Worst Case: O(log n), Array keeps dividing until 1 element remains

Average Case: O(log n)

Space Complexity

Iterative Binary Search: O(1) , only a few variables used

Recursive Binary Search: O(log n) , because of recursive stack

Binary Search is much faster than Linear Search for large sorted datasets.

Binary Search cannot be used on unsorted data.

 Multi Dimensional Array

 An array is a collection of elements of the

same
data type stored in contiguous memory
locations.
 Multi-dimensional array is an array of
arrays.
 It is used to store data in table, matrix, or
grid form.
 It is stored in row-major order
 Multi-dimensional array generalizes this into
2D, 3D, or higher dimensions
 int arr[3][4]
// 2D array with 3 rows and 4 columns
 Memory Representation of 2D Array

 2D Arrays are stored in row-major order.

 Data of each row are stored in consecutive memory locations.
int arr[2][3] = { {12, 24, 36}, {42, 52, 62} };
Memory layout: 12, 24, 36, 42, 52, 62
Accessing Elements of 2D Array
 Indexing starts from 0
 Elements are accessed using multiple indices
 Element at row i and column j is accessed as: arr[i][j]
arr[1][2] will return 62
int main()
{
int arr[2][3] = { {12, 22, 32}, {42, 52, 62} };
printf("2D Array Elements:\n");
for (int i = 0; i < 2; i++)
{ Output :
for (int j = 0; j < 3; j++) 2D Array Elements:
{ 12 22 32
printf("%d ", arr[i][j]); 42 52 62
}
printf("\n");
}
return 0;
}
3D Array

 3D array is an array of 2D arrays

 Like a cube of data: layers x rows × columns

Declaration : int array[s1][s2][s3];

s1 → number of layers

s2 → number of rows

s3 → number of columns

 int array[2][3][4] in this 2 layers , 3 rows per layer , 4 columns per layer
int arr[2][2][3] = {
{ {12, 22, 32}, {44, 54, 64} }, // First layer
{ {73, 83, 93}, {18, 15, 14} } // Second layer
};

Memory Representation
 C stores data in row-major order:
 For arr[2][2][3], memory layout will be:
12, 22, 32, 44, 54, 64, 73, 83, 93, 18, 15, 14
 Accessing element at layer i, row j, column k: arr[i][j][k]
arr[1][0][2] will return 93
Applications of Multi-Dimensional Arrays
 Matrices : Used in mathematical computations
 Image Processing :Images stored as 2D arrays of pixels
 Game Development :Storing chess boards, tic-tac-toe, maps
 Database Tables :Rows and columns representation
 Scientific Computations:Storing 3D models
 Medical Imaging : MRI/CT scan images stored as 3D layers.
 Simulation Models: Physics and engineering simulations.
 PYQ from UNIT 1

 Describe Algorithm . What is its need .

 Write the characteristics of Algorithm.
 Describe choice of right data structure.
 Explain different applications of stack.
 Explain Binary Search Algorithm . Compare it with Linear Search Algorithm. Which technique is best? Justify your answer.
 What do you mean by Data Structure ? Explain its various types with suitable examples.
 What is an array ? What are advantages of array ? Write algorithm to search a given number in array .
 What is complexity ? How can you analyze the algorithm ? Explain with the help of example.
 What do you mean by complexity of algorithm .What are its types ? Give example to support your answer.
 Explain various operations that can be performed on different data structures by giving suitable examples.
 Discuss Linear and non linear data structures.
 PYQ from UNIT 1

 Explain multi dimensional array .

 Explain Time complexity and space complexity .
 Explain Linear search Algorithm and mention its complexities.
 What do you mean by Analysis of Algorithm ? Discuss the complexity of Algorithm in detail.
 Write down the steps for designing and developing an algorithm.