S C H O O L S O F COMPUTING SCIENCE & ENGINEERING

DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Principle Of Data Structure Lab

Subject Code: BSCS1505

Faculty: Mr. Shubham Kumar Singh

Assistant Professor
Department of Computer Science
& Applications
Sharda School of Computing Science &
Engineering, Sharda University
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Detailed Syllabus: L-T-P-C----0-1-4-3

Outline syllabus CO
Mapping
Unit 1 Programs based on arrays
Write programs to implement the matrix operations CO1

Unit 2 Programs based on stacks and queues

Programs to implement the stacks and queues CO2
operations

Unit 3 Programs based on linked list, searching and sorting

Programs to implement the linked list, searching and CO3, CO6
sorting
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Unit 4 Programs based on Trees

A Program to implement the trees like insertion, deletion CO4, CO6
of a node including tree traversal
Unit 5 Programs based on Graphs
A Program to implement the graphs like Dijkstra CO5, CO6
algorithm, Prim's algorithm and Kruskal’s algorithm
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Unit 1 Programs based on arrays

Write programs to implement the matrix operations CO1

● Introduction to Data Structure, Application of DS, Classification, 1D, 2D

arrays, Traversal, insertion, deletion
● Linear search, Binary search, Bubble sort, Selection sort
● Matrix definition, representation, Matrix read and display program
● Program for matrix addition, Program for matrix subtraction
● Matrix multiplication logic
● Transpose program
● Check diagonal matrix
● Sparse matrix representation
● Passing matrices to functions
● Combined matrix operations
● Design matrix-based application
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Introduction to Data structures

● In computer terms, a data structure is a Specific way to store and organize
data in a computer's memory so that these data can be used efficiently
later.
● Data may be arranged in many different ways such as the logical or
mathematical model for a particular organization of data is termed as a
data structure.

Explanation with Example

Consider storing student marks:

Without Data Structure

If we store marks in separate variables:
m1 = 85, m2 = 90, m3 = 78 (This becomes difficult to manage when
the number of students increases.)
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

With Data Structure (Array)

marks = [85, 90, 78]
Now:
● Data is stored in an organized manner
● Accessing, updating, and processing data becomes easy
● Memory usage is efficient
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Why Data Structures Are Needed

1. Efficient Data Storage
Data structures help store data in a structured and systematic way.
2. Faster Access and Processing
Searching, sorting, inserting, and deleting data becomes faster.
3. Better Memory Management
Optimizes memory usage and reduces redundancy.
4. Handling Large Data
Essential for applications dealing with huge data (databases, AI, big data).
5. Improves Program Performance
Good data structure selection improves time and space complexity.
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Applications of Data Structures

Data Structure Application

Array Storing lists (marks, salaries)
Stack Function calls, undo/redo operations
Queue CPU scheduling, printer queue
Linked List Dynamic memory allocation
Tree File systems, hierarchical data
Graph Social networks, maps, routing
Hash Table Fast searching (databases, dictionaries)
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Real-World Examples
● Google Maps uses graphs
● Web browsers use stacks
● Operating systems use queues
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Real-World Examples
● Google Maps uses graphs
● Web browsers use stacks
● Operating systems use queues
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Categories of Data Structure:

The data structure can be subdivided into major types:
● Linear Data Structure
● Non-linear Data Structure
Linear Data Structure:
A data structure is said to be linear if its elements combine to form any
specific order.
● There are basically two techniques of representing such linear structure
within memory.
● First way is to provide the linear relationships among all the elements
represented by means of linear memory location. These linear structures
are termed as arrays.
● The second technique is to provide the linear relationship among all the
elements represented by using the concept of pointers or links. These
linear structures are termed as linked lists.
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

The common examples of linear data structure are:

● Arrays
● Queues
● Stacks
● Linked lists
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Non linear Data Structure:

This structure is mostly used for representing data that contains a hierarchical
relationship among various elements.
Examples of Non Linear Data Structures are listed below:
● Graphs
● family of trees and
● table of contents
Tree: In this case, data often contain a hierarchical relationship among
various elements. The data structure that reflects this relationship is termed as
rooted tree
graph or a tree.
Graph: In this case, data sometimes hold a relationship between the pairs of
elements which is not necessarily following the hierarchical structure. Such
data structure is termed as a Graph.
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Array is a container which can hold a fix number of items and these items
should be of the same type. Most of the data structures make use of arrays to
implement their algorithms. Following are the important terms to understand
the concept of Array.

Element − Each item stored in an array is called an element.

Index − Each location of an element in an array has a numerical index, which
is used to identify the element.

Array Representation:(Storage structure)

Arrays can be declared in various ways in different languages. For illustration,
let's take C array declaration.
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Arrays can be declared in various ways in different languages. For illustration,

let's take C array declaration.

As per the above illustration, following are the important points to be

considered.
● Index starts with 0.
● Array length is 10 which means it can store 10 elements.
● Each element can be accessed via its index. For example, we can fetch an
element at index 6 as 9.
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Basic Operations of Array

Following are the basic operations supported by an array.
Traverse − print all the array elements one by one.
Insertion − Adds an element at the given index.
Deletion − Deletes an element at the given index.
Search − Searches an element using the given index or by the value.
Update − Updates an element at the given index.
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

In C, when an array is initialized with size, then it assigns defaults values to its
elements in following order.

Data Type Default Value Data Type Default Value

bool false bool false
char 0 char 0
int 0 int 0
float 0.0 float 0.0
double 0.0f double 0.0f
void
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Types of Arrays in C
An array in C is a collection of elements of the same data type, stored in
contiguous memory locations and accessed using a single variable name
with an index.
Based on dimensions, arrays in C are classified as:
1. One-Dimensional Array
2. Two-Dimensional Array
3. Multi-Dimensional Array
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

1. One-Dimensional Array (1D Array)

A one-dimensional array stores a list of elements in a single row. It is the
simplest form of an array.
Syntax:
datatype array_name[size];
Example:
int a[10];
Representation of 1D Array:
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Two-Dimensional Array (2D Array)

A two-dimensional array stores data in the form of rows and columns,
similar to a matrix.

Syntax:
datatype array_name[rows][columns];
Example:
int matrix[2][3];
Representation of 2D Array
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Logical concept behind array indexing starting with zero

The core logical idea is offset counting.

An array index does not mean position, it means distance (offset) from the starting point.

● The array name represents the starting location

● Index = how many steps to move from the start

So logically:

● Index 0 → move 0 steps → first element

● Index 1 → move 1 step → second element

Simple Analogy

Think of a starting point (A) on a number line:

● Distance from A to A = 0
● Distance from A to next point = 1

You don’t count the starting point as 1; you count how far you moved.
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Mathematical Logic

Array element access:

element_address = base_address + (index × element_size)

If index started from 1, the formula would need extra adjustment.

Key Logical Reason

Zero-based indexing directly maps “position” to “offset”, avoiding unnecessary

subtraction and making array operations simpler, faster, and mathematically clean.
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

int arr[3] = {10, 20, 30};

arr[0] // 10 → first element

arr[1] // 20 → second element

arr[2] // 30 → third element

Memory View

If arr starts at address 1000 and each integer takes 4 bytes:

● arr[0] → 1000 + 0 × 4 = 1000

● arr[1] → 1000 + 1 × 4 = 1004
● arr[2] → 1000 + 2 × 4 = 1008
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

#Traversal of Array element

#include <stdio.h>
int main() {
int marks[5] = {80, 75, 90, 85, 88};
int i;
for(i = 0; i < 5; i++) {
printf("Marks[%d] = %d\n", i, marks[i]);
}
return 0;
}
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Insertion Operation
Insert operation is to insert one or more data elements into an array. Based on the
requirement, a new element can be added at the beginning, end, or any given index of
array.
Here, we see a practical implementation of insertion operation, where we add data at
the end of the array −
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

#Insertion of element
#include <stdio.h>
int main() {
int arr[100], n, i, element;
printf("Enter the number of elements in the array: ");
scanf("%d", &n);
printf("Enter %d elements:\n", n);
for(i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("Enter the element to insert at the end: ");
scanf("%d", &element);
/* Inserting element at the end */
arr[n] = element;
n = n + 1;
printf("Array after insertion:\n");
for(i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

#Delection of element for(i = pos - 1; i < n - 1; i++)

#include <stdio.h> Arrays in C start from index 0.
int main() {
So:
int arr[50], n, i, pos;
printf("Enter number of elements: "); Position 1 → index 0
scanf("%d", &n); Position 2 → index 1
printf("Enter array elements:\n");
That’s why we use pos - 1 to convert
for(i = 0; i < n; i++) {
scanf("%d", &arr[i]); position into array index.
} arr[i] = arr[i + 1];
printf("Enter position to delete: "); This line copies the next element into the
scanf("%d", &pos);
current position.
for(i = pos - 1; i < n - 1; i++) {
arr[i] = arr[i + 1]; It overwrites the element that needs to be
} deleted.
n--;
arr = {10, 20, 30, 40, 50}
printf("Array after deletion:\n");
for(i = 0; i < n; i++) { n=5
printf("%d ", arr[i]); pos = 3 // delete 30
}
return 0; Loop execution
}
● i = pos - 1 = 2
● Shifting starts from index 2
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Searching in DS:
Searching is a fundamental operation in Data Structures used to find the location or
presence of a specific element(called the key) within a collection of data. The data
may be stored in different forms such as arrays, linked lists, stacks, queues, trees,
graphs, or files. Efficient searching is crucial for improving program performance,
reducing execution time, and enabling fast data retrieval.

The process of searching involves:

1. Input data set – a collection of elements

2. Search key – the element to be found
3. Search method – the algorithm used to locate the element
4. Output – position of the element or a message indicating absence
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Searching Algorithms in Data Structures

● Various searching techniques can be applied on the data structures to retrieve
certain data.
● A search operation is said to be successful only if it returns the desired element or
data; otherwise, the searching method is unsuccessful.

There are two categories these searching techniques fall into. They are −

Sequential Searching
Interval Searching

Sequential Searching
● As the name suggests, the sequential searching operation traverses through each
element of the data sequentially to look for the desired data.
● The data need not be in a sorted manner for this type of search.
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Example − Linear Search

 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Example − Linear Search

#include <stdio.h>
int main() {
int arr[100], n, i, key, found = 0;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d elements:\n", n);
for(i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("Enter element to search: ");
scanf("%d", &key);
// Linear Search logic
for(i = 0; i < n; i++) {
if(arr[i] == key) {
printf("Element %d found at position %d\n", key, i + 1);
found = 1;
break;
}
}
if(found == 0) {
printf("Element %d not found in the array\n", key);
}
return 0;
}
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Interval Searching
Unlike sequential searching, the interval searching operation requires the data to be in
a sorted manner. This method usually searches the data in intervals; it could be done by
either dividing the data into multiple sub-parts or jumping through the indices to
search for an element.

Example − Binary Search, Jump Search etc.

 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Example − Binary
while(low <= high) {
Search
#include mid = (low + high) / 2; <stdio.h>
int main() { if(arr[mid] == key) {
printf("Element %d found at position %d\n",
int arr[100], n, i, key;
key, mid + 1);
int low, high, mid;
return 0;
printf("Enter number of elements: "); }
scanf("%d", &n); else if(arr[mid] < key) {
printf("Enter %d elements in sorted order:\n", n); low = mid + 1;
for(i = 0; i < n; i++) { }
scanf("%d", &arr[i]); else {
} high = mid - 1;
printf("Enter element to search: "); }
scanf("%d", &key); }
low = 0; printf("Element %d not found in the array\n",
high = n - 1; key);
return 0;
}
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Binary Search Algorithm

Below is the step-by-step algorithm for Binary Search:
● Divide the search space into two halves by finding the middle index "mid".
● Compare the middle element of the search space with the key.
● If the key is found at middle element, the process is terminated.
● If the key is not found at middle element, choose which half will be used as the next
search space.
-> If the key is smaller than the middle element, then the left side is used for next
search.
-> If the key is larger than the middle element, then the right side is used for next
search.
● This process is continued until the key is found or the total search space is
exhausted.
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

The Binary Search Algorithm can be implemented in the following two ways
● Iterative Binary Search Algorithm
● Recursive Binary Search Algorithm

Iterative Binary Search Algorithm

Here we use a while loop to continue the process of comparing the key and splitting
the search space in two halves.

Recursive Binary Search Algorithm

Create a recursive function and compare the mid of the search space with the key.
And based on the result either return the index where the key is found or call the
recursive function for the next search space.
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Applications

● Searching in sorted arrays

● Finding first/last occurrence or closest match in a sorted array
● Database indexing — Used in B-trees and similar structures for fast data lookup.
● Debugging in version control — Tools like git bisect use binary search to isolate faulty commits.
● Network routing & IP lookup — Efficiently find routing entries in tables sorted by address ranges.
● File systems & libraries — Fast search through sorted directories or symbol tables.
● Gaming/graphics — Collision detection or ray tracing using sorted spatial data.
● Machine learning tuning — Efficient hyperparameter search (e.g., learning rate, thresholds).
● Optimization problems & competitive programming — Solve boundary-value challenges by
narrowing search space.
● Advanced data structures — Binary search trees, self-balancing BSTs, and fractional cascading
rely on search logic.
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Array Sorting

Sorting is the process of arranging elements of an array in a specific order, usually

ascending or descending.
Sorting improves the efficiency of operations like searching, merging, and data
analysis.

Types of Sorting

Sorting techniques are broadly classified into two main types based on where the data
is stored and processed:

1. Internal Sorting
2. External Sorting
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

1. Internal Sorting

Internal sorting is used when all the data to be sorted can fit into the main memory
(RAM).
Most commonly used sorting algorithms fall under this category.

Characteristics

● Data resides completely in primary memory

● Faster execution
● Suitable for small to medium-sized datasets

Examples of Internal Sorting Algorithms

● Bubble Sort
● Selection Sort
● Insertion Sort
● Quick Sort
● Merge Sort
● Heap Sort
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

2. External Sorting

External sorting is used when the data is too large to fit into main memory and is
stored on secondary storage such as a hard disk.

Characteristics

● Data stored on disk (files)

● Slower than internal sorting due to disk access
● Used for very large datasets

Examples of External Sorting Techniques

● External Merge Sort

● Polyphase Merge Sort
● Balanced Merge Sort
● K-way Merge Sort

Example

Suppose a file contains 100 GB of student records, but RAM size is only 8 GB.
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Steps:

1. Read a portion of data that fits into RAM

2. Sort it using an internal sort
3. Write sorted chunks back to disk
4. Merge all sorted chunks into a single sorted file

This process is known as External Merge Sort.

 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Types of Sorting Techniques

There are various sorting algorithms are used in data structures. The following two types of sorting
algorithms can be broadly classified:
1. Comparison-based: We compare the elements in a comparison-based sorting algorithm)
2. Non-comparison-based: We do not compare the elements in a non-comparison-based
sorting algorithm)
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Bubble Sort - It is a simple sorting algorithm that repeatedly swaps adjacent

elements if they are in the wrong order. It performs multiple passes through the
array, and in each pass, the largest unsorted element moves to its correct position at
the end.
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

#include <stdio.h>
int main() {
int a[10], n, i, j, temp;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter elements:\n");
for(i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
// Bubble Sort
for(i = 0; i < n - 1; i++) {
for(j = 0; j < n - 1 - i; j++) {
if(a[j] > a[j + 1]) {
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
printf("Sorted array:\n");
for(i = 0; i < n; i++) {
printf("%d ", a[i]);
}
return 0;
}
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Selection Sort :
It is a comparison-based sorting algorithm that repeatedly selects the smallest
(or largest) element from the unsorted part of the array and swaps it with the
first unsorted element. This process continues until the array is fully sorted.
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Selection Sort :
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Selection Sort :
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Selection Sort :
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

#include <stdio.h>
int main() {
int a[10], n, i, j, min, temp;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter elements:\n");
for(i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
// Selection Sort
for(i = 0; i < n - 1; i++) {
min = i;
for(j = i + 1; j < n; j++) {
if(a[j] < a[min]) {
min = j;
}
}
// Swap smallest element with first element
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
printf("Sorted array:\n");
for(i = 0; i < n; i++) {
printf("%d ", a[i]);
}
return 0;
}
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

● Insertion sort is a simple sorting algorithm that works by iteratively inserting

each element of an unsorted list into its correct position in a sorted portion of the
list.
● It is like sorting playing cards in your hands. You split the cards into two groups:
the sorted cards and the unsorted cards.
● Then, you pick a card from the unsorted group and put it in the right place in the
sorted group.

● Start with the second element as the first element is assumed to be sorted.
● Compare the second element with the first if the second is smaller then
swap them.
● Move to the third element, compare it with the first two, and put it in its
correct position
● Repeat until the entire array is sorted.
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

#include <stdio.h>
int main() {
// Print sorted array
int n, i, j, key;
printf("Sorted array:\n");
printf("Enter number of elements: ");
for(i = 0; i < n; i++) {
scanf("%d", &n);
printf("%d ", arr[i]);
int arr[n];
}
printf("Enter %d elements:\n", n);
printf("\n");
for(i = 0; i < n; i++) {
scanf("%d", &arr[i]);
return 0;
}
}
// Insertion Sort Algorithm
for(i = 1; i < n; i++) {
key = arr[i]; // Element to be inserted
j = i - 1;
// Move elements greater than key one position ahead
while(j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key; // Insert key at correct position
}
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Merge Sort is a comparison-based sorting algorithm that works by dividing the input
array into two halves, then calling itself for these two halves, and finally it merges the
two sorted halves. In this article, we will learn how to implement merge sort in C
language.
What is Merge Sort Algorithm?
Merge sort is based on the three principles: divide, conquer and combine which is
better implemented using recursion using two functions:
1. mergeSort() - For Divide
2. merge() - For Conquer and Combine

The mergeSort() function keeps dividing array into subarrays till it cannot be further
divided (i.e. single element). Then merge() function is called to merge two subarrays
at a time in the required order until we get back the whole array in the sorted order.
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Matrix Data Structure is a two-dimensional array arranged in rows and columns. It

is commonly used to represent mathematical matrices and is fundamental in various
fields like mathematics, computer graphics, and data processing. Matrices allow for
efficient storage and manipulation of data in a structured format.
Basics
● Representation and Basic Operations
● Row-wise vs column-wise traversal
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Representation and Basic Operations

Matrix is a two-dimensional array mostly used in mathematical and scientific

calculations. It is also considered as an array of arrays, where array at each index has
the same size.
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Representation of Matrix Data Structure:

As you can see from the below image, the elements are organized in rows and
columns. As shown in the image, the cell a[0][0] is the first element of the first row
and first column.
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Operations on Matrix Data Structure:

We can perform a variety of operations on the Matrix Data Structure. Some of the
most common operations are:
● Access elements of Matrix
● Traversal of a Matrix
● Searching in a Matrix
● Sorting a Matrix
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Matrix read and display program

// Display matrix
#include <stdio.h>
printf("\nMatrix is:\n");
int main() {
for(i = 0; i < rows; i++) {
int rows, cols;
for(j = 0; j < cols; j++) {
int matrix[10][10];
printf("%d\t", matrix[i][j]);
int i, j;
}
// Input number of rows and columns
printf("\n");
printf("Enter number of rows: ");
}
scanf("%d", &rows);
printf("Enter number of columns: ");
return 0;
scanf("%d", &cols);
}
// Input matrix elements
printf("Enter matrix elements:\n");
for(i = 0; i < rows; i++) {
for(j = 0; j < cols; j++) {
scanf("%d", &matrix[i][j]);
}}
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Program for addition of two matrices

● Given two matrices of order N × M, write a C program to compute their sum.
● The resultant matrix will also be of order N × M, where each element is
obtained by adding the corresponding elements of the two given matrices.

Approach: Below is the idea to solve the problem.

Iterate over every cell of matrix (i, j), add the corresponding values of the two
matrices and store in a single matrix i.e. the resultant matrix.
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Program for addition of two matrices

#include <stdio.h>
int main() {
int r, c;
int A[10][10], B[10][10], Sum[10][10];
int i, j;
// Input rows and columns
printf("Enter number of rows: ");
scanf("%d", &r);
printf("Enter number of columns: ");
scanf("%d", &c);
// Input first matrix
printf("Enter elements of first matrix:\n");
for(i = 0; i < r; i++) {
for(j = 0; j < c; j++) {
scanf("%d", &A[i][j]);
}
}
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

// Input second matrix

printf("Enter elements of second matrix:\n");
for(i = 0; i < r; i++) {
for(j = 0; j < c; j++) {
scanf("%d", &B[i][j]);
}}
// Add matrices
for(i = 0; i < r; i++) {
for(j = 0; j < c; j++) {
Sum[i][j] = A[i][j] + B[i][j];
}}
// Display result
printf("\n Sum of two matrices:\n");
for(i = 0; i < r; i++) {
for(j = 0; j < c; j++) {
printf("%d\t", Sum[i][j]);
}
printf("\n");
}
return 0;
}
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Given two m x n matrices m1 and m2, the task is to subtract m2 from m1 and return res.
Input: m1 = {{1, 2},
{3, 4}},
m2 = {{4, 3},
{2, 1}}
Output: {{-3, -1},
{1, 3}}

Input: m1 = {{3, 3, 3},

{3, 3, 3}},
m1 = {{2, 2, 2},
{1, 1, 1}},
Output: {{1, 1, 1},
{2, 2, 2}},
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

#Subtraction
#include <stdio.h>
int main() {
int r, c;
int A[10][10], B[10][10], Sub[10][10];
int i, j;
// Input rows and columns
printf("Enter number of rows: ");
scanf("%d", &r);
printf("Enter number of columns: ");
scanf("%d", &c);
// Input first matrix
printf("Enter elements of first matrix:\n");
for(i = 0; i < r; i++) {
for(j = 0; j < c; j++) {
scanf("%d", &A[i][j]);
}
}
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

// Input second matrix

printf("Enter elements of second matrix:\n");
for(i = 0; i < r; i++) {
for(j = 0; j < c; j++) {
scanf("%d", &B[i][j]);
}}
// Subtract matrices
for(i = 0; i < r; i++) {
for(j = 0; j < c; j++) {
Sub[i][j] = A[i][j] - B[i][j];
}}
// Display result
printf("\n Resultant matrix after subtraction:\n");
for(i = 0; i < r; i++) {
for(j = 0; j < c; j++) {
printf("%d\t", Sub[i][j]);
}
printf("\n");
}

return 0;
}
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

● Matrix multiplication is a binary operation that produces a new matrix

from two given matrices.
● For the multiplication to be defined, the number of columns in the first
matrix must equal the number of rows in the second matrix.
● The resulting matrix, called the matrix product, has the same number of
rows as the first matrix and the same number of columns as the second
matrix.
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

For example, if matrices A and B satisfy this condition, their product results in a new
matrix whose order is determined by the rows of A and the columns of B. If A is (m ×
p) and the order of B is (p × n), then the order of the multiplied matrix is (m × n).
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

How to Multiply Matrices

Let's take two matrices A and B of order 2×2
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

How to Multiply Matrices

Let's take two matrices A and B of order 2×2
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

How to Multiply Matrices

Let's take two matrices A and B of order 2×2
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

How to Multiply Matrices

Let's take two matrices A and B of order 2×2
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

How to Multiply Matrices

Let's take two matrices A and B of order 2×2
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Compatibility Conditions for Matrix Multiplication:

We can multiply two matrices if the number of columns in the 1st matrix is
equal to the number of rows in the 2nd matrix, otherwise, the given matrices
cannot be multiplied.
For example:
● A 2×3 matrix can be multiplied by a 3×2 matrix, resulting in a 2×2
matrix.
● A 3×3 matrix cannot be multiplied by a 4×2 matrix because their
dimensions are incompatible.
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

#include <stdio.h>
int main() {
int r1, c1, r2, c2;
int A[10][10], B[10][10], Mul[10][10];
int i, j, k;
// Input dimensions of first matrix
printf("Enter rows and columns of first matrix: ");
scanf("%d %d", &r1, &c1);
// Input dimensions of second matrix
printf("Enter rows and columns of second matrix: ");
scanf("%d %d", &r2, &c2);
// Check if multiplication is possible
if (c1 != r2) {
printf("Matrix multiplication not possible.\n");
return 0;
}
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

// Input first matrix

printf("Enter elements of first matrix:\n");
for(i = 0; i < r1; i++) {
for(j = 0; j < c1; j++) {
scanf("%d", &A[i][j]);
}
}
// Input second matrix
printf("Enter elements of second matrix:\n");
for(i = 0; i < r2; i++) {
for(j = 0; j < c2; j++) {
scanf("%d", &B[i][j]);
}
}
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

// Initialize result matrix to 0

Role of k:
for(i = 0; i < r1; i++) {
for(j = 0; j < c2; j++) { 1. k is the “running index” for the dot product
Mul[i][j] = 0; ○ To compute Mul[i][j], you multiply
}} each element of the i-th row of A with
// Multiply matrices the corresponding element of the j-th
column of B.
for(i = 0; i < r1; i++) {
○ k goes from 0 to c1-1 (or r2-1) and
for(j = 0; j < c2; j++) {
selects the matching elements.
for(k = 0; k < c1; k++) {
2. It picks elements from A and B:
Mul[i][j] += A[i][k] * B[k][j];
○ A[i][k] → the k-th element in the i-th
}}} row of A
// Display result ○ B[k][j] → the k-th element in the j-th
printf("\n Resultant matrix after multiplication:\n"); column of B
for(i = 0; i < r1; i++) { ○ Multiply them and add to the sum.
for(j = 0; j < c2; j++) { 3. Without k, you can’t sum the contributions
printf("%d\t", Mul[i][j]); ○ Each element of the result is the sum
} of products along the row and
printf("\n"); column.
} ○ k ensures you go through all elements
return 0; of the row and column.
}
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Transpose of a Matrix
Transpose of a matrix is a new matrix that is obtained by swapping the rows and
columns of the given matrix or vice versa, i.e., for the given matrix, the elements in rows
are interchanged with the elements in columns.
● For any given matrix A, its transpose is denoted as At, or AT.
● To find AT, take each row of A and rewrite it as a column.
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Transpose of a Matrix (Cont’d…)

 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Transpose of a Matrix (Cont’d…) Rows to Column

#include <stdio.h>
int main() { // Transpose logic
int a[10][10], t[10][10]; for(i = 0; i < r; i++) {
int r, c, i, j; for(j = 0; j < c; j++) {
printf("Enter number of rows: "); t[j][i] = a[i][j];
scanf("%d", &r); }
printf("Enter number of columns: "); }
scanf("%d", &c); printf("\n Transpose of the
printf("Enter elements of the matrix:\n"); matrix:\n");
for(i = 0; i < r; i++) { for(i = 0; i < c; i++) {
for(j = 0; j < c; j++) { for(j = 0; j < r; j++) {
scanf("%d", &a[i][j]); printf("%d ", t[i][j]);
}} }
printf("Enter elements of the matrix:\n"); printf("\n");
for(i = 0; i < r; i++) { }
for(j = 0; j < c; j++) {
return 0;
printf("%d", a[i][j]); }
}
printf("\n");
}
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Transpose of a Matrix (Cont’d…) Columns to Rows

#include <stdio.h>
int main() { // Transpose logic
int a[10][10], t[10][10]; for(i = 0; i < r; i++) {
int r, c, i, j; for(j = 0; j < c; j++) {
printf("Enter number of rows: "); t[i][j] = a[j][i];
scanf("%d", &r); }
printf("Enter number of columns: "); }
scanf("%d", &c); printf("\n Transpose of the
printf("Enter elements of the matrix:\n"); matrix:\n");
for(i = 0; i < r; i++) { for(i = 0; i < c; i++) {
for(j = 0; j < c; j++) { for(j = 0; j < r; j++) {
scanf("%d", &a[i][j]); printf("%d ", t[i][j]);
}} }
printf("Enter elements of the matrix:\n"); printf("\n");
for(i = 0; i < r; i++) { }
for(j = 0; j < c; j++) { return 0;
printf("%d", a[i][j]);} }
printf("\n");}
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS

Diagonal Matrix

● A diagonal matrix is a square matrix in which all of the elements except the
principal diagonal elements are zero.
● It is both upper and lower triangular, as all the elements except the main diagonal
elements are zeros.
● This structure simplifies many operations like multiplication and raising matrices to
powers.
A square matrix "A = [aij]" is said to be a diagonal matrix if aij = 0 when i ≠ j.

What are principal (main) diagonal elements?

In a square matrix, the principal (or main) diagonal consists of elements where the
row index equals the column index, i.e.,
 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS
What are principal (main) diagonal elements?
In a square matrix, the principal (or main) diagonal consists of elements where the
row index equals the column index, i.e.,

Here, the principal diagonal elements are:

 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS
Why is a diagonal matrix both upper triangular and lower triangular?

Upper Triangular Matrix

A matrix is upper triangular if:

(i.e., all elements below the diagonal are zero)

Lower Triangular Matrix

A matrix is lower triangular if:

(i.e., all elements above the diagonal are zero)

 S C H O O L S O F COMPUTING SCIENCE & ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE AND APPLICATIONS
Examples of a Diagonal Matrix
Some common examples of diagonal matrices of different orders are given below:

Diagonal Matrix of order (3 × 3)

 SCHOOL OF ENGINEERING &TECHNOLOGY
D E PAR T M E N T O F C O M P U T E R S C I E N C E AN D E N G I N E E R I N G

THANK
YOU