2024-25

Acropolis Institute of
Technology and
Research, Indore Department of CSE
Submitted To: Dr. Mayur Rathi
(Artificial Intelligence & Machine
Learning)

Data Structures (AL303)

Submitted By:
Sejal Raykhere
Enrollment No. : 0827AL231116
Class/Year/Sem : ALS-2/2nd / 3rd

[LAB ASSIGNMENT DATA STRUCTURES (AL-

303)]
The Objective of this laboratory work is to strengthen the ability of the students to identify and apply the suitable data structure for
the given real world problem. It enables them to gain knowledge in practical applications of data structures.

ACROPOLIS INSTITUTE OF TECHNOLOGY & RESEARCH,

INDORE
 Department of CSE (Artificial Intelligence & Machine Learning)

CERTIFICATE

This is to certify that the experimental work entered in this journal as per

the B. TECH. II year syllabus prescribed by the RGPV was done by Mr./

Ms. …………………………………B.TECH II year III semester in the

Data Structures Laboratory of this institute during the academic year

2024- 202.

Signature of the Faculty

 About the Laboratory

In this lab, students will be able to learn and practice basic data structures programming. Students
can expand their skill set by practical learning on various data structures and to understand the
processing of different algorithm for problem-solving. This lab complements the data structures and
computer algorithms courses. Data Structures provides the requisite environment for design and
analysis of algorithms for solving complex problems in the field of computer science. Students gain
practical knowledge by writing and executing programs in C/C++/JAVA/Python using various data
structures and implementing algorithm principles. The latest platforms compilers are provided to the
students to run their programs.
GENERAL INSTRUCTIONS FOR LABORATORY CLASSES

⮚ DO’S

✔ Without Prior permission do not enter into the Laboratory.

✔ While entering into the LAB students should wear their ID cards.

✔ The Students should come with proper uniform.

✔ Students should sign in the LOGIN REGISTER before entering into the
laboratory.

✔ Students should come with observation and record note book to the laboratory.

✔ Students should maintain silence inside the laboratory.

✔ After completing the laboratory exercise, make sure to shutdown the system
properly.

⮚ DONT’S

✔ Students bringing the bags inside the laboratory.

✔ Students using the computers in an improper way.

✔ Students scribbling on the desk and mishandling the chairs.

✔ Students using mobile phones inside the laboratory.

✔ Students making noise inside the laboratory.

 SYLLABUS
Course: AL303 (Data Structures)
Branch/Year/Sem: Artificial Intelligence & Machine Learning / II / III

Module1: Introduction to Data Structure: Concepts of Data and Information,

Classification of Data structures, Abstract Data Types, Implementation aspects: Memory
representation. Data structures operations and its cost estimation. Introduction to linear
data structures- Arrays, Linked List: Representation of linked list in memory, different
implementation of linked list. Circular linked list, doubly linked list, etc. Application of
linked list: polynomial manipulation using linked list, etc..

Module2: Stacks and Queue: Stacks as ADT, Different implementation of stack,

multiple stacks. Application of Stack: Conversion of infix to postfix notation using
stack, evaluation of postfix expression, Recursion. Queues: Queues as ADT, Different
implementation of queue, Circular queue, Concept of Dqueue and Priority Queue, Queue
simulation, Application of queues.

Module3: Tree: Definitions - Height, depth, order, degree etc. Binary Search Tree -
Operations, Traversal, Search. AVL Tree, Heap, Applications and comparison of various
types of tree; Introduction to forest, multi-way Tree, B tree, B+ tree, B* tree and red-
black tree.

Module4: Graphs: Introduction, Classification of graph: Directed and Undirected

graphs, etc, Representation, Graph Traversal: Depth First Search (DFS), Breadth First
Search (BFS), Graph algorithm: Minimum Spanning Tree (MST)-Kruskal, Prim’s
algorithms. Dijkstra’s shortest path algorithm; Comparison between different graph
algorithms. Application of graphs.

Module5: Sorting: Introduction, Sort methods like: Bubble Sort, Quick sort. Selection
sort, Heap sort, Insertion sort, Shell sort, Merge sort and Radix sort; comparison of
various sorting techniques. Searching: Basic Search Techniques: Sequential search,
Binary search, Comparison of search methods. Hashing & Indexing. Case Study:
Application of various data structures in operating system, DBMS etc.
HARDWARE AND SOFTWARE REQUIREMENTS:

S. Name of Item Specification

No.
1 Computer System Hard Disk min 5 GB
RAM: 4 GB / 8 GB
Processor: Intel i3 or above

S. Name of Item Specification

No
.
1 Operating system Window XP or 2000
Editor Python3.7 IDLE or Google Colab or
Spyder(Anaconda) , Turbo C/C++
 RATIONALE:
The purpose of this subject is to cover the concepts of Data Structure in terms of Theory
and Implementation .The syllabus provides all the essential concepts of Data Structures.

PREREQUISITE:-

Experience with a high level language (C/C++, Java, Python) is suggested. Prior
knowledge of a Object-Oriented concepts is helpful but not mandatory.

COURSE OBJECTIVES AND OUTCOMES

 Course Objectives

1. To write and execute programs in any high level language to solve problems using data
structures such as arrays, linked lists.
2. To write and execute programs in any high level language to solve problems using data
structures such as stacks, queues.
3. To write and execute programs in C++ to solve problems using data structures such as
trees, graphs, hash tables and search trees. ¬ To write and execute write programs in C+
+ to implement various sorting and searching methods..

⮚ Course Outcomes

At the end of the course student will be able to:

1. List different types of data structures

2. Illustrate the concepts of stack and queue
3. Describe the concepts of various tree
4. Discuss the concepts of Graph
5. Demonstrate various algorithms of sorting

.
 Index
Date Pa Date of Grade &
S. of Name of the Experiment ge Submissio Sign of the
No Exp N n Faculty
. o.
1 Program for insertion and deletion in array at
different positions. (CO 1)

2 Program to perform Insertion and deletion

operation in linked list. (CO 1)

3 Program to perform Push, Pop & top operations in

stack. (CO 2)

4 Program to perform Insertion and deletion

operation in queue. (CO 2)

5 Program to create a tree. (CO 3)

6 Program to implement Selection Sort. (CO 5)

7 Program to implement Insertion Sort. (CO 5)

8 Program to implement Quick Sort. (CO 5)

9 Program to implement Merge Sort. (CO 5)

10 Program to implement Binary Search. (CO 5)

 Program Outcome (PO)

The engineering graduate of this institute will demonstrate:

a) Apply knowledge of mathematics, science, computing and engineering fundamentals to computer
science engineering problems.
b) Able to identify, formulate, and demonstrate with excellent programming, and problem solving skills.
c) Design solutions for engineering problems including design of experiment and processes to meet
desired needs within reasonable constraints of manufacturability, sustainability, ecological,
intellectual and health and safety considerations.
d) Propose and develop effective investigational solution of complex problems using research
methodology; including design of experiment, analysis and interpretation of data, and combination of
information to provide suitable conclusion. synthesis
e) Ability to create, select and use the modern techniques and various tools to solve engineering
problems and to evaluate solutions with an understanding of the limitations.
f) Ability to acquire knowledge of contemporary issues to assess societal, health and safety, legal and
cultural issues.
g) Ability to evaluate the impact of engineering solutions on individual as well as organization in a
societal and environmental context, and recognize sustainable development, and will be aware of
emerging technologies and current professional issues.
h) Capability to possess leadership and managerial skills, and understand and commit to professional
ethics and responsibilities.
i) Ability to demonstrate the team work and function effectively as an individual, with an ability to
design, develop, test and debug the project, and will be able to work with a multi-disciplinary team.
j) Ability to communicate effectively on engineering problems with the community, such as being able
to write effective reports and design documentation.
k) Flexibility to feel the recognition of the need for, and have the ability to engage in independent and
life- long learning by professional development and quality enhancement programs in context of
technological change.
l) A practice of engineering and management principles and apply these to one’s own work, as a
member and leader in a team, to manage projects and entrepreneurship.
 Acropolis Institute of Technology and Research, Indore
Department of CSE (Artificial Intelligence & Machine
Learning)
Group / Title:
Lab: Data Structure (AL303)

EVALUATION RECORD Type/ Lab Session:

Name Enrollment No. 0827AL
Performing on First submission Second submission
Extra Regular

Grade and Remarks by the Tutor

1. Clarity about the objective of experiment
2. Clarity about the Outcome
3. Submitted the work in desired format
4. Shown capability to solve the problem
5. Contribution to the team work

Additional remarks

Grade: Cross the grade.

A B C D F

Tutor
1 Title
2 Neatly Drawn and labeled experimental setup
2.1 Theoretical solution of the instant problemAlgorithm
2.2 Program
3 Tabulation Sheet
4 Results
INPUT OUTPUT

Acropolis Institute of Technology and Research, Indore

Department of CSE (Artificial Intelligence & Machine
Learning)
Group / Title:
Lab: Data Structure (AL303)
 EVALUATION RECORD Type/ Lab Session:
Name Sejal Raykhere Enrollment No. 0827AL231116
Performing on First submission Second submission
Extra Regular

Grade and Remarks by the Tutor

1. Clarity about the objective of experiment
2. Clarity about the Outcome
3. Submitted the work in desired format
4. Shown capability to solve the problem
5. Contribution to the team work

Page 10
Additional remarks

Grade: Cross the grade.

A B C D F

Page 11
Title 1

Page 12
2.1 Theoretical Solution of the Instant Problem (Algorithm)

Algorithm for Insertion:

1. Start
2. Read the array size and initialize the array.
3. Read the position and value to be inserted.
4. If position is valid (0 ≤ position ≤ size):
 Shift elements from position to the right.
 Insert the value at the specified position.
 Increment the size of the array.
5. Else, display an error message.
6. End.
Algorithm for Deletion:
1. Start
2. Read the position to be deleted.
3. If position is valid (0 ≤ position < size):
 Shift elements from position+1 to the left.
 Decrement the size of the array.
 Display the deleted element.
4. Else, display an error message.
5. End.

2.2 program
#include <stdio.h>

Page 13
#define MAX_SIZE 100

void insert(int arr[], int *size, int position, int value) {

if (*size >= MAX_SIZE) {
printf("Array is full. Cannot insert.\n");
return;
}
if (position < 0 || position > *size) {
printf("Invalid position.\n");
return;
}
for (int i = *size; i > position; i--) {
arr[i] = arr[i - 1];
}
arr[position] = value;
(*size)++;
}

void delete(int arr[], int *size, int position) {

if (*size == 0) {
printf("Array is empty. Cannot delete.\n");
return;
}
if (position < 0 || position >= *size) {
printf("Invalid position.\n");
return;
}
int deletedValue = arr[position];
for (int i = position; i < *size - 1; i++) {
arr[i] = arr[i + 1];
}
(*size)--;
printf("Deleted value: %d\n", deletedValue);
}

void display(int arr[], int size) {

if (size == 0) {
printf("Array is empty.\n");
return;
}
printf("Array elements: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[MAX_SIZE];
int size = 0;

Page 14
 int choice, position, value;

do {
printf("\nMenu:\n");
printf("1. Insert Element\n");
printf("2. Delete Element\n");
printf("3. Display Array\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter position to insert (0 to %d): ", size);
scanf("%d", &position);
printf("Enter value to insert: ");
scanf("%d", &value);
insert(arr, &size, position, value);
break;
case 2:
printf("Enter position to delete (0 to %d): ", size - 1);
scanf("%d", &position);
delete(arr, &size, position);
break;
case 3:
display(arr, size);
break;
case 4:
printf("Exiting...\n");
break;
default:
printf("Invalid choice. Please try again.\n");
}
} while (choice != 4);

return 0;
}

5 Tabulation Sheet

INPUT OUTPUT
Insert =1,2,3,4,5 [1 2 5 3 4]
Insert 5 at position 2

Delete= 1 2 5 3 6 4 [1 2 5 6 4]
Delete element at position 3

Page 15
 Acropolis Institute of Technology and Research, Indore
Department of CSE (Artificial Intelligence & Machine
Learning)
Group / Title:
Lab: Data Structure (AL303)

EVALUATION RECORD Type/ Lab Session:

Name Sejal Raykhere Enrollment No. 0827AL231116
Performing on First submission Second submission
Extra Regular

Grade and Remarks by the Tutor

1. Clarity about the objective of experiment
2. Clarity about the Outcome
3. Submitted the work in desired format
4. Shown capability to solve the problem
5. Contribution to the team work

Additional remarks

Grade: Cross the grade.

A B C D F

Tutor
Title2

Page 16
2.1 Theoretical Solution of the Problem
 Insertion: Inserting a node into a linked list involves:
1. Creating a new node.
2. Inserting the node at the desired position (either at the beginning, middle, or end).
3. Adjusting the pointers to maintain the structure of the linked list.
 Deletion: Deleting a node from a linked list involves:
1. Identifying the position of the node to delete.
2. Adjusting the pointer of the previous node to skip over the node to be deleted.
3. Removing the node from the list to avoid memory leaks.
2.2 program
#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;

Page 17
 struct Node* next;
};
void insertNode(struct Node** head, int position, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;

if (position == 0) {
newNode->next = *head;
*head = newNode;
return;
}

struct Node* temp = *head;

for (int i = 0; temp != NULL && i < position - 1; i++) {
temp = temp->next;
}

if (temp == NULL) {
printf("Position is out of bounds.\n");
free(newNode);
return;
}

newNode->next = temp->next;
temp->next = newNode;
}

// Function to delete a node at a given position

void deleteNode(struct Node** head, int position) {
if (*head == NULL) {
printf("List is empty. Cannot delete.\n");
return;
}

struct Node* temp = *head;

if (position == 0) {
*head = temp->next;
free(temp);
return;
}

Page 18
 for (int i = 0; temp != NULL && i < position - 1; i++) {
temp = temp->next;
}

if (temp == NULL || temp->next == NULL) {

printf("Position is out of bounds.\n");
return;
}

struct Node* nextNode = temp->next->next;

free(temp->next);
temp->next = nextNode;
}

void displayList(struct Node* node) {

if (node == NULL) {
printf("List is empty.\n");
return;
}
printf("Linked List: ");
while (node != NULL) {
printf("%d -> ", node->data);
node = node->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = NULL;
int choice, position, value;

do {
printf("\nMenu:\n");
printf("1. Insert Node\n");
printf("2. Delete Node\n");
printf("3. Display List\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {

Page 19
 case 1:
printf("Enter position to insert (0 for beginning): ");
scanf("%d", &position);
printf("Enter value to insert: ");
scanf("%d", &value);
insertNode(&head, position, value);
break;
case 2

6 Tabulation Sheet
7 Results
INPUT OUTPUT
Inert at begin NULL inert at the 10NULL
beginning
Inert at end 10NULL insert 20 at the 1020NULL
end
Delete at position 051020NULL 1020NULL
delete node at position 0

Acropolis Institute of Technology and Research, Indore

Department of CSE (Artificial Intelligence & Machine
Learning)
Group / Title:
Lab: Data Structure (AL303)

EVALUATION RECORD Type/ Lab Session:

Name Sejal Raykhere Enrollment No. 0827AL231116
Performing on First submission Second submission
Extra Regular

Grade and Remarks by the Tutor

1. Clarity about the objective of experiment

Page 20
 2. Clarity about the Outcome
3. Submitted the work in desired format
4. Shown capability to solve the problem
5. Contribution to the team work

Additional remarks

Grade: Cross the grade.

A B C D F

Title 3

3. Theoretical Solution of the Instant Problem

A stack is a linear data structure that follows the Last In First Out (LIFO) principle. The main
Page 21
operations of a stack include:
 Push: Add an element to the top of the stack.
 Pop: Remove the element from the top of the stack.
 Top: Retrieve the element at the top of the stack without removing it.
3.1 Algorithm
1. Push Operation:
 Check if the stack is full.
 If not, increment the top index and add the new element at that index.
2. Pop Operation:
 Check if the stack is empty.
 If not, retrieve the element at the top index and decrement the top index.
3. Top Operation:
 Check if the stack is empty.
 If not, return the element at the top index
#include <stdio.h>
#include <stdlib.h>

#define MAX 100 // Maximum size of the stack

typedef struct Stack {

int arr[MAX];
int top;
} Stack
void initStack(Stack* s) {
s->top = -1; // Stack is initially empty
}

int isFull(Stack* s) {
return s->top == MAX - 1;
}
int isEmpty(Stack* s) {
return s->top == -1;
}

void push(Stack* s, int value) {

if (isFull(s)) {
printf("Stack Overflow! Cannot push %d\n", value);
return;
}
s->arr[++s->top] = value;
printf("Pushed %d onto the stack\n", value);
}

Page 22
int pop(Stack* s) {
if (isEmpty(s)) {
printf("Stack Underflow! Cannot pop\n");
return -1; // Return -1 to indicate an error
}
return s->arr[s->top--];
}

int top(Stack* s) {
if (isEmpty(s)) {
printf("Stack is empty! No top element\n");
return -1; // Return -1 to indicate an error
}
return s->arr[s->top];
}
int main() {
Stack s;
initStack(&s);

push(&s, 10);
push(&s, 20);
push(&s, 30);

printf("Top element is: %d\n", top(&s));

printf("Popped element is: %d\n", pop(&s));

printf("Top element after pop is: %d\n", top(&s));

return 0;
}

8 Tabulation Sheet
9 Results
INPUT OUTPUT
Pushed 10 Pushed 10 onto the stack
Top Top element is: 100
Popped Popped element is: 10

Page 23
 Acropolis Institute of Technology and Research, Indore
Department of CSE (Artificial Intelligence & Machine
Learning)
Group / Title:
Lab: Data Structure (AL303)

EVALUATION RECORD Type/ Lab Session:

Name Sejal Raykhere Enrollment No. 0827AL231116
Performing on First submission Second submission
Extra Regular

Grade and Remarks by the Tutor

1. Clarity about the objective of experiment
2. Clarity about the Outcome
3. Submitted the work in desired format
4. Shown capability to solve the problem
5. Contribution to the team work

Page 24
Additional remarks

Grade: Cross the grade.

A B C D F

Tilte 4

Page 25
Page 26
3. Theoretical Solution of the Instant Problem
A stack is a linear data structure that follows the Last In First Out (LIFO) principle. The main
operations of a stack include:
 Push: Add an element to the top of the stack.
 Pop: Remove the element from the top of the stack.
 Top: Retrieve the element at the top of the stack without removing it.
3.1 Algorithm
1. Push Operation:
 Check if the stack is full.
 If not, increment the top index and add the new element at that index.
2. Pop Operation:
 Check if the stack is empty.
 If not, retrieve the element at the top index and decrement the top index.
3. Top Operation:
 Check if the stack is empty.
 If not, return the element at the top index.
3.2 program
#include <stdio.h>
#include <stdlib.h>

#define MAX 100 // Maximum size of the queue

typedef struct Queue {

int arr[MAX];
int front;
int rear;
} Queue;

void initQueue(Queue* q) {
q->front = 0; // Front index
q->rear = -1; // Rear index
}

int isFull(Queue* q) {
return q->rear == MAX - 1;
}

int isEmpty(Queue* q) {
return q->front > q->rear;
}

void enqueue(Queue* q, int value) {

Page 27
 if (isFull(q)) {
printf("Queue Overflow! Cannot enqueue %d\n", value);
return;
}
q->arr[++q->rear] = value;
printf("Enqueued %d into the queue\n", value);
}

int dequeue(Queue* q) {
if (isEmpty(q)) {
printf("Queue Underflow! Cannot dequeue\n");
return -1; // Return -1 to indicate an error
}
return q->arr[q->front++];
}
int main() {
Queue q;
initQueue(&q);

enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);

printf("Dequeued element is: %d\n", dequeue(&q));

printf("Dequeued element is: %d\n", dequeue(&q));

enqueue(&q, 40);
enqueue(&q, 50);

while (!isEmpty(&q)) {
printf("Dequeued element is: %d\n", dequeue(&q));
}

return 0;
}

10 Tabulation Sheet
11 Results
INPUT OUTPUT
Enqueued 10 Enqueued 10 into the queue
Enqueued 20 Enqueued 20 into the queue

Dequeued 10 Dequeued element is: 10

Page 28
 Acropolis Institute of Technology and Research, Indore
Department of CSE (Artificial Intelligence & Machine
Learning)
Group / Title:
Lab: Data Structure (AL303)

EVALUATION RECORD Type/ Lab Session:

Name Sejal Raykhere Enrollment No. 0827AL231116
Performing on First submission Second submission
Extra Regular

Grade and Remarks by the Tutor

1. Clarity about the objective of experiment
2. Clarity about the Outcome
3. Submitted the work in desired format
4. Shown capability to solve the problem
5. Contribution to the team work

Additional remarks

Grade: Cross the grade.

A B C D F

Tilte 5

3. Theoretical Solution of the Instant Problem

A binary tree is a hierarchical data structure in which each node has at most two children,
referred to as the left child and the right child. The top node is called the root, and nodes with no
children are called leaves.
3.1 Algorithm
1. Create a Node:
 Allocate memory for a new node.
 Assign data to the node.
 Initialize left and right children to NULL.
2. Insert a Node:
 If the tree is empty, the new node becomes the root.
 Otherwise, recursively find the appropriate position for the new node based on the
desired order (e.g., binary search tree).
3. Display the Tree:
Page 29
  Use a traversal method (e.g., in-order, pre-order, post-order) to display the tree
nodes.
3.2 Program
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {

char data;
struct Node* left;
struct Node* right;
} Node;

Node* createNode(char data) {

Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

void inOrderTraversal(Node* root) {

if (root != NULL) {
inOrderTraversal(root->left);
printf("%c ", root->data);
inOrderTraversal(root->right);
}
}

int main() {
Node* root = createNode

('A');
root->left = createNode('B');
root->right = createNode('C');
root->left->left = createNode('D');
root->left->right = createNode('E');
root->right->right = createNode('F');

printf("In-order Traversal of the Binary Tree: ");

inOrderTraversal(root);
printf("\n");
return 0;

Page 30
}
Tabulation Sheet

INPUT OUTPUT
Create A Node created with data 'A'
Create B Node created with data 'B'
Create C Node created with data 'C'
Create D Node created with data 'D'
Create E Node created with data 'E'
Create F Node created with data 'F'
In-order Traversal In-order Traversal
Results
The program successfully creates a binary tree with the following structure:

A
/\
B C
/\ \
D E F
In-order Traversal of the Binary Tree: D B E A C F

Acropolis Institute of Technology and Research, Indore

Page 31
 Department of CSE (Artificial Intelligence & Machine
Learning)
Group / Title:
Lab: Data Structure (AL303)

EVALUATION RECORD Type/ Lab Session:

Name Sejal Raykhere Enrollment No. 0827AL231116
Performing on First submission Second submission
Extra Regular

Grade and Remarks by the Tutor

1. Clarity about the objective of experiment
2. Clarity about the Outcome
3. Submitted the work in desired format
4. Shown capability to solve the problem
5. Contribution to the team work

Page 32
Additional remarks

Grade: Cross the grade.

A B C D F

Page 33
Tilte 6

Page 34
Page 35
3. Theoretical Solution of the Instant Problem
Selection Sort is a simple comparison-based sorting algorithm. It works by dividing the input list
into two parts: a sorted part and an unsorted part. The algorithm repeatedly selects the smallest
(or largest, depending on the order) element from the unsorted part and moves it to the end of the
sorted part.
3.1 Algorithm
1. Start with the first element as the minimum.
2. Compare this minimum with the other elements in the array.
3. If a smaller element is found, update the minimum.
4. After completing the comparisons, swap the minimum element with the first element of
the unsorted part.
5. Move the boundary of the sorted part one element to the right.
6. Repeat the process for the remaining unsorted elements until the entire array is sorted.
3.2 Program
#include <stdio.h>

// Function to perform selection sort

void selectionSort(int arr[], int n) {
int i, j, minIndex, temp;

for (i = 0; i < n - 1; i++) {

minIndex = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);

Page 36
 printf("Initial Array: ");
printArray(arr, n);

selectionSort(arr, n);

printf("Sorted Array: ");

printArray(arr, n);

return 0;
}
Tabulation Sheet

INPUT OUTPUT
[64, 25, 12, 22, 11] Find minimum (11), swap with 64
[11, 25, 12, 22, 64] Find minimum (12), swap with 25
[11, 12, 25, 22, 64] Find minimum (22), swap with 25
[11, 12, 22, 25, 64] No swap needed (already sorted)
[11, 12, 22, 25, 64] Final sorted array

Results
The program successfully implements the Selection Sort algorithm. The output shows the initial
and sorted arrays:
Initial Array: 64 25 12 22 11
Sorted Array: 11 12 22 25 64

Page 37
 Acropolis Institute of Technology and Research, Indore
Department of CSE (Artificial Intelligence & Machine
Learning)
Group / Title:
Lab: Data Structure (AL303)

EVALUATION RECORD Type/ Lab Session:

Name Sejal Raykhere Enrollment No. 0827AL231116
Performing on First submission Second submission
Extra Regular

Grade and Remarks by the Tutor

1. Clarity about the objective of experiment
2. Clarity about the Outcome
3. Submitted the work in desired format
4. Shown capability to solve the problem
5. Contribution to the team work

Additional remarks

Grade: Cross the grade.

A B C D F

Tilte 7

Page 38
Page 39
3. Theoretical Solution of the Instant Problem
Insertion Sort is a simple and intuitive sorting algorithm that builds a sorted array (or list) one
element at a time. It works similarly to the way you might sort playing cards in your hands. The
algorithm divides the input list into a sorted and an unsorted part. It repeatedly takes the first
element from the unsorted part and inserts it into the correct position in the sorted part.
3.1 Algorithm
1. Start from the second element (index 1) of the array.
2. Compare the current element with the elements in the sorted part (to its left).
3. Shift all elements in the sorted part that are greater than the current element to the right.
4. Insert the current element into its correct position.
5. Repeat the process for all elements in the array until the entire array is sorted
3.2 program
#include <stdio.h>
void insertionSort(int arr[], int n) {
int i, key, j;

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

key = arr[i];
j = i - 1;

while (j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Initial Array: ");

printArray(arr, n);

Page 40
 insertionSort(arr, n);

printf("Sorted Array: ");

printArray(arr, n);

return 0;
}

12 Tabulation Sheet
13
INPUT OUTPUT
[64, 25, 12, 22, 11] Insert 25 before 64
[25, 64, 12, 22, 11] Insert 12 before 25
[12, 25, 64, 22, 11] Insert 22 before 64
[12, 22, 25, 64, 11] Insert 11 before 12
[11, 12, 22, 25, 64] Final sorted array

Results

The program successfully implements the Insertion Sort algorithm. The output shows the
initial and sorted array
Initial Array: 64 25 12 22 11
Sorted Array: 11

Page 41
Page 42
Page 43
3. Theoretical Solution of the Instant Problem
Quick Sort is a highly efficient sorting algorithm and is based on partitioning an array into
smaller sub-arrays. A pivot element is selected from the array, and the other elements are
rearranged so that those less than the pivot come before it and those greater come after it. The
sub-arrays are then sorted recursively.
3.1 Algorithm
1. Choose a Pivot: Select an element from the array as the pivot (commonly the last
element).
2. Partitioning: Rearrange the array so that elements less than the pivot are on the left, and
elements greater than the pivot are on the right.
3. Recursion: Recursively apply the above steps to the sub-arrays formed by the
partitioning.
4. Base Case: If the array has one or zero elements, it is already sorted.
3.2 program
#include <stdio.h>

void swap(int* a, int* b) {

int temp = *a;
*a = *b;
*b = temp;
}

int partition(int arr[], int low, int high) {

int pivot = arr[high];
int i = (low - 1);

for (int j = low; j < high; j++) {

if (arr[j] <= pivot) {

i++;
swap(&arr[i], &arr[j]);

Page 44
 }
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {

int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

void printArray(int arr[], int n) {

for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Initial Array: ");

printArray(arr, n);

quickSort(arr, 0, n - 1);

printf("Sorted Array: ");

printArray(arr, n);

return 0;
}

INPUT OUTPUT
[64, 25, 12, 22, 11] Choose pivot (22)
[11, 12, 22, 64, 25] Partitioning around pivot (22)
Left Sub-array: [11, 12] Already sorted
Right Sub-array: [64, 25] Choose pivot (25)
[11, 12, 22, 25, 64] Final sorted array

Page 45
Results
The program successfully implements the Quick Sort algorithm. The output shows the
initial and sorted arrays:

Initial Array: 64 25 12 22 11
Sorted Array: 11 12

Acropolis Institute of Technology and Research, Indore

Department of CSE (Artificial Intelligence & Machine
Learning)
Group / Title:
Lab: Data Structure (AL303)

EVALUATION RECORD Type/ Lab Session:

Name Sejal Raykhere Enrollment No. 0827AL231116
Performing on First submission Second submission
Extra Regular

Grade and Remarks by the Tutor

1. Clarity about the objective of experiment
2. Clarity about the Outcome
3. Submitted the work in desired format
4. Shown capability to solve the problem
5. Contribution to the team work

Page 46
Additional remarks

Grade: Cross the grade.

A B C D F

Tilte 9

Page 47
3. Theoretical Solution of the Instant Problem
Merge Sort is a divide-and-conquer algorithm that sorts an array by recursively dividing it into
two halves, sorting each half, and then merging the sorted halves back together. It is particularly
effective for large datasets and has a guaranteed time complexity of O(n log n).
3.1 Algorithm
1. Divide: Split the array into two halves until each sub-array contains one element.
2. Conquer: Recursively sort each half.
3. Combine: Merge the two sorted halves into a single sorted array.
3.2 Program
#include <stdio.h>
void merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1; // Size of left sub-array
int n2 = right - mid;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j]
i = 0;
j = 0;
k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}

Page 48
}
void mergeSort(int arr[], int left, int right) {
if (left < right) {

int mid = left + (right - left) / 2;

mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Initial Array: ");

printArray(arr, n);

mergeSort(arr, 0, n - 1);

printf("Sorted Array: ");

printArray(arr, n);

return 0;
}

Acropolis Institute of Technology and Research, Indore

Department of CSE (Artificial Intelligence & Machine
Learning)
Group / Title:
Lab: Data Structure (AL303)

EVALUATION RECORD Type/ Lab Session:

Page 49
 Name Sejal Raykhere Enrollment No. 0827AL231116
Performing on First submission Second submission
Extra Regular

Grade and Remarks by the Tutor

1. Clarity about the objective of experiment
2. Clarity about the Outcome
3. Submitted the work in desired format
4. Shown capability to solve the problem
5. Contribution to the team work

Additional remarks

Grade: Cross the grade.

A B C D F

Page 50
Tilte 10

Page 51
3. Theoretical Solution of the Instant Problem
Binary Search is an efficient algorithm for finding an item from a sorted list of items. It works by
repeatedly dividing the search interval in half. If the value of the search key is less than the item
in the middle of the interval, the search continues in the lower half, or if it is greater, it continues
in the upper half. This process repeats until the value is found or the interval is empty.
3.1 Algorithm
1. Set two pointers, low and high, to the first and last index of the array, respectively.
2. While low is less than or equal to high:
 Calculate the middle index: mid = (low + high) / 2.
 If the target value is equal to the middle element, return the index.
 If the target value is less than the middle element, adjust high to mid - 1.
 If the target value is greater than the middle element, adjust low to mid + 1.
3. If the target value is not found, return -1.
3.2 program
#include <stdio.h>

int binarySearch(int arr[], int size, int target) {

int low = 0;
int high = size - 1;

while (low <= high) {

int mid = (low + high) / 2;

if (arr[mid] == target) {
return mid; // Target found
}

else if (arr[mid] > target) {

high = mid - 1;
}

else {
low = mid + 1;
}
}
return -1; // Target not found
}
void printArray(int arr[], int size) {

Page 52
 for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {11, 12, 22, 25, 64};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 22;

printf("Initial Sorted Array: ");

printArray(arr, size);

int result = binarySearch(arr, size, target);

if (result != -1) {
printf("Target %d found at index: %d\n", target, result);
} else {
printf("Target %d not found in the array.\n", target);
}

return 0;
}
14 Tabulation Sheet
15
INPUT OUTPUT
[11, 12, 22, 25, 64] Compare arr[2] (22) with target (22)

L=0 , m=2 ,h=4

Results

The program successfully implements the Binary Search algorithm. The output shows the initial
sorted array and the result of the search:
Initial Sorted Array: 11 12 22 25 64
Target 22 found at index: 2

Page 53
Page 54