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: Hardik
Joshi
Enrollment No. :
0827AL231051 Class/Year/Sem
: ALS-1/2nd / 3rd

[LAB ASSIGNMENT DATA STRUCTURES (AL-303)]

T h e O b j e c t i v e o f t h i s l a b or a t or y w or k i s t o s t r e n g t h e n t h e a bi l i t y o f t h e s t u d e n t s t o i d e n t
i f y a n d a p p l y t h e s u i t a bl e d a t a s t r u c t u r e f or t h e g i v e n r e a l - w or l d p r obl e m . I t e n a bl e s
t h e m t o g a i n k n o wl e d g e i n pr a c t i c a l a p p l i c a t i on s o f d a t a s t r u c t u r e s .
1
 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. Hardik Joshi [Link] II year III semester in the Data Structures

Laboratory of this institute during the academic year 2024- 2025.

Signature of the Faculty

2
 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 algorithms 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.

3
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 in the 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 shut down the system
properly.

 DONT’S

 Students bring the bags inside the laboratory.

 Students use the computers in an improper way.

 Students scribbling on the desk and mishandling the chairs.

 Students use mobile phones inside the laboratory.

 Students are making noise inside the laboratory.

4
 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 Dequeue 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 trees; 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 systems, 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++

5
 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 an 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

6
 Index
Date of Page Date of Grade &
[Link] Exp. Name of the Experiment No. Submission Sign of the
Faculty
1 10/9/24 Program for insertion and deletion in array at 09 24/9/24
different positions. (CO 1)

2 24/9/24 Program to perform Insertion and deletion operation 16 1/10/24

in linked list. (CO 1)

3 1/10/24 Program to perform Push, Pop & top operations in 25 8/10/24

stack. (CO 2)

4 8/10/24 Program to perform Insertion and deletion operation 32 15/10/24

in queue. (CO 2)

5 15/10/24 Program to create a tree. (CO 3) 39 22/10/24

6 22/10/24 Program to implement Selection Sort. (CO 5) 46 12/11/24

7 12/11/24 Program to implement Insertion Sort. (CO 5) 51 19/11/24

8 19/11/24 Program to implement Quick Sort. (CO 5) 56 26/11/24

9 3/12/24 Program to implement Merge Sort. (CO 5) 61 10/12/24

10 10/12/24 Program to implement Binary Search. (CO 5) 66 24/12/24

7
 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 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 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.

8
 Acropolis Institute of Technology and Research, Indore
Department of CSE (Artificial Intelligence & Machine
Learning)
Group / Title: Program for insertion and deletion in array at
Lab: Data Structure (AL303) different positions.

EVALUATION RECORD Type/ Lab Session:

Name Hardik Joshi Enrollment No. 0827AL231051
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 - Program for insertion and deletion in array at different positions.

2 Neatly Drawn and labeled experimental setup
Page 10
3 Theoretical solution of the instant problem
3.1 Algorithm
1. Print Array (printdata)
 Loop through the array elements from index 0 to n-1.
 Print each element.
2. Insertion (Insertion)
 Input the index x where insertion is to be performed.
 Validate the index:
o If x > n or x < 0, print an error message and exit the function.
 Shift elements from the end (n-1) to the index x one position to the right.
 Input the value to be inserted at index x.
 Increment the size of the array (n++).
3. Deletion (Deletion)
 Check if the array is empty (n == 0):
o If true, print an error message and exit the function.
 Input the index x of the element to be deleted.
 Validate the index:
o If x >= n or x < 0, print an error message and exit the function.
 Shift elements from index x+1 to the end (n-1) one position to the left.
 Decrement the size of the array (n--).
4. Main Function (main)
1. Input the initial size of the array n and the elements of the array.
2. Display a menu:
o 1: Perform insertion.
o 2: Perform deletion.
o 3: Print the array.
o 4: Exit.
3. Based on user choice:
o Call the corresponding function (Insertion, Deletion, or printdata).
4. Repeat the menu until the user chooses to exit (choice = 4).

Page 11
3.2 Program

#include <iostream>
using namespace std;

void printdata(int &n, int arr[])

{
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
}
void Insertion(int &n, int arr[])
{
int x;
cout << "At which Index you want to perform insertion: ";
cin >> x;
if (x > n || x < 0)
{
cout << "Invalid Index entered" << endl;
return;
}
for (int i = n; i > x; i--)
{
arr[i] = arr[i - 1];
}
cout << "Enter the value of this inserted element: ";
cin >> arr[x];
n++;
}
void Deletion(int &n, int arr[])
{
if (n == 0)
{
cout << "Array is Empty cannot perform deletion!" << endl;
return;
}
int x;
cout << "Which element you want to delete from array: ";
cin >> x;
if (x > n || x < 0)
{
cout << "Invalid Index entered" << endl;
return;

Page 12
 }
if (x != n)
{
for (int i = x; i < n - 1; i++)
{
arr[i] = arr[i + 1];
}
}
n--;
}

int main()
{
int n;
cout << "Enter the no. of elements you want in array: ";
cin >> n;
int arr[n];

cout << "Enter the value of elements in the array: ";

for (int i = 0; i < n; i++)
{
cin >> arr[i];
}

int choice;
cout << "Enter choice: \[Link] \[Link] \[Link] array
\[Link]..." << endl;
cin >> choice;
while (choice != 4)
{
if (choice == 1)
{
Insertion(n, arr);
}
else if (choice == 2)
{
Deletion(n, arr);
}
else if (choice == 3)
{
printdata(n, arr);
}
cout << "Enter choice: \[Link] \[Link] \[Link]
array \[Link]..." << endl;
cin >> choice;
}
return 0;

Page 13
 }

4 Tabulation Sheet

INPUT OUTPUT
Enter the no. of elements you want in array:
8
Enter the value of elements in the array:
12345678
Enter choice:
[Link]
[Link]
[Link] array
[Link]...
1
At which Index you want to perform insertion:
2
Enter the value of this inserted element:
99
Enter choice:
[Link]
[Link]
[Link] array
[Link]...
3
1 2 99 3 4 5 6 7 8
Enter choice:
[Link]
[Link]
[Link] array
[Link]...
2
Which element you want to delete from array:
9
Enter choice:
[Link]
[Link]
[Link] array
[Link]...
3
1 2 99 3 4 5 6 7
Enter choice:
[Link]
[Link]
[Link] array
[Link]...
4

Page 14
5 Results
The program successfully implements insertion, deletion, and display operations on an array.
It handles valid and invalid inputs properly, updates the array as expected, and meets the
objectives of the practical.

Page 15
 Acropolis Institute of Technology and Research, Indore
Department of CSE (Artificial Intelligence & Machine
Learning)
Group / Title: Program to perform Insertion and deletion
operation in linked list.
Lab: Data Structure (AL303)

EVALUATION RECORD Type/ Lab Session:

Name Hardik Joshi Enrollment No. 0827AL231051
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- Program to perform Insertion and deletion operation in linked list.

2 Neatly Drawn and labeled experimental setup

Page 16
Page 17
3 Theoretical solution of the instant problem
3.1 Algorithm
1. Creation of Linked List
1.1 Input the number of nodes (n) to be created.
1.2 Loop n times:
 Create a new node dynamically.
 Input data for the new node.
 If the list is empty:
o Set both head and tail to the new node.
 Otherwise:
o Link the new node to the tail.
o Update tail to the new node.
2. Insertion in Linked List
2.1 Input the choice for insertion:
 Beginning:
o Create a new node dynamically.
o Input data for the new node.
o Point the new node to head.
o Update head to the new node.
o Increment n.
 End:
o Create a new node dynamically.
o Input data for the new node.
o Link the new node to tail.
o Update tail to the new node.
o Increment n.
 At Specific Position:
o Input the position (x).
o If the position is invalid, exit.

Page 18
 o Create a new node dynamically.
o Traverse to the node just before the position (x-1).
o Insert the new node between the nodes.
o Increment n.
3. Deletion in Linked List
3.1 Input the node position (x) to delete:
 If the position is invalid or the list is empty, exit.
 Traverse to the node just before the position (x-1).
 Save the node to be deleted (delnode).
 Adjust the next pointer of the previous node to skip delnode.
 Delete delnode dynamically.
 Decrement n.
4. Print the Linked List
4.1 Start from head and traverse the list.
4.2 Print the data of each node.
5. Exit
5.1 Exit the program when the choice is 5.

3.2 Program
#include <iostream>
using namespace std;

class node
{
public:
int data;
node *next;
};

class linkedlist
{
node *head = NULL;
node *tail = NULL;
node *temp = NULL;

int n;

public:

Page 19
 void creation()
{
cout << "Enter the [Link] nodes in ll" << endl;
cin >> n;
cout<<"Enter the data for the nodes "<<endl;

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

{
node *newNode = new node;
cin >> newNode->data;
if (head == NULL && tail == NULL)
{
head = newNode;
tail = newNode;
}
else
{
tail->next = newNode;
tail = newNode;
}
}
}
void insertion()
{
int choiceIns;
cout << "How you want to perform insertion in linked list\n1.
From Beginning\n2. From Ending\n3. At particular address " << endl;
cin >> choiceIns;

if (choiceIns == 1)
{
node *newnode = new node;
cout << "Enter the data of this node: ";
cin >> newnode->data;
newnode->next = head;
head = newnode;
n++;
}
else if (choiceIns == 2)
{
node *newnode = new node;
cout << "Enter the data of this node: ";
cin >> newnode->data;
tail->next = newnode;
tail = newnode;
n++;

Page 20
 }
else if (choiceIns == 3)
{
int x;
cout << "At which node you want to insert new node: ";
cin >> x;
if (x > n)
{
cout << "Wrong node \n";
return;
}
node *newnode = new node;
cout << "Enter the data of this node: ";
cin >> newnode->data;
temp = head;
for (int i = 0; i < x - 1; i++)
{
temp = temp->next;
}
if (temp->next == NULL)
{
newnode->next = NULL;
}
else
{
newnode->next = temp->next;
}
temp->next = newnode;
n++;
}
}
void deletion()
{
if (head == NULL)
{
cout << "Linked List is Empty !!" << endl;
return;
}
int x;
cout << "Which node do you want to delete: ";
cin >> x;
if (x > n || x < 0)
{
cout << "Wrong node entered " << endl;
return;
}
temp = head;

Page 21
 for (int i = 0; i < x - 1; i++)
{
temp = temp->next;
}
node *delnode = temp->next;
temp->next = temp->next->next;
delete delnode;
n--;
}

void printdata()
{
temp = head;
for (int i = 0; i < n; i++)
{
if (head == NULL)
{
cout << "Empty ll" << endl;
}
else
{
cout << temp->data << " ";
temp = temp->next;
}
}
}
};
int main()
{
linkedlist ll;
int choice = 1;
while (choice != 5)
{
if (choice == 1)
{
[Link]();
}
else if (choice == 2)
{
[Link]();
}
else if (choice == 3)
{
[Link]();
}
else if (choice == 4)
{

Page 22
 [Link]();
}
else
{
cout << "wrong choice try again\n";
}
cout << "Enter your choice :\[Link] \[Link]
\[Link] \[Link] list\n5. Exit...\n";
cin >> choice;
}
return 0;
}

4 Tabulation Sheet

INPUT OUTPUT
Enter the [Link] nodes in ll
5
Enter the data for the nodes
12345
Enter your choice :
1. Creation
2. Insertion
3. Deletion
4. print list
5. Exit...
2
How you want to perform insertion in linked list
1. From Beginning
2. From Ending
3. At particular address

3 At which node you want to insert new node:

Enter the data of this node:

5
Enter your choice :
99 1. Creation
2. Insertion
3. Deletion
4. print list
5. Exit...

1 2 3 4 5 99 Enter your choice :

4 [Link]
2. Insertion
3. Deletion

Page 23
 [Link] list
5. Exit...

Which node do you want to delete:

3
Enter your choice :
3 [Link]
2. Insertion
3. Deletion
4. print list
5. Exit...

1 2 3 5 99 Enter your choice :

4 [Link]
2. Insertion
3. Deletion
4. print list
5. Exit...
5

5 Results
The program successfully performs all the linked list operations (creation, insertion, deletion,
and display) based on user inputs. It efficiently maintains the list structure and provides the
desired results.

Page 24
 Acropolis Institute of Technology and Research, Indore
Department of CSE (Artificial Intelligence & Machine
Learning)
Group / Title: Program to perform Push, Pop & top operations
Lab: Data Structure (AL303) in stack.

EVALUATION RECORD Type/ Lab Session:

Name Hardik Joshi Enrollment No. 0827AL231051
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- Program to perform Push, Pop & top operations in stack.

2 Neatly Drawn and labeled experimental setup

Page 25
Page 26
3 Theoretical solution of the instant problem
3.1 Algorithm
□ Start.
□ Define a struct node with two members:
 int data (to store the value of the node).
 node* next (to point to the next node, initialized to NULL).
□ Create a class stack with the following:
 node* top (pointer to the top of the stack, initialized to NULL).
 Member functions:
o Push Operation:
 Create a new node.
 Input the data for the new node.
 Set newnode->next = top.
 Update top = newnode.
o Pop Operation:
 Check if top == NULL. If true, print "Stack is empty" and return.
 Store top in a temporary pointer pop.
 Update top = top->next.
 Delete the pop node.
o Top Operation:
 Check if top == NULL. If true, print "Stack is empty" and return.
 Print the data of the top node.
o Print Stack:
 Check if top == NULL. If true, print "Stack is empty" and return.
 Traverse through the stack using a temporary pointer, printing the data
of each node.
□ Main Function:
 Create an object of the stack class.
 Use a menu-driven approach to call the appropriate functions based on the
user's input.

Page 27
 □ End.

3.2 Program
#include <iostream>
using namespace std;

struct node
{
public:
int data;
node *next = NULL;
};
class stack
{
public:
node *top = NULL;
void push_operation()
{
node *newnode = new node;
cout << "Enter the data of this node: ";
cin >> newnode->data;
newnode->next = top;
top = newnode;
}

void pop_operation()
{
if (top == NULL)
{
cout << "Stack is empty ";
return;
}
node *pop = top;
top = top->next;
delete pop;
}

void top_operation()
{
if (top == NULL)
{
cout << "Stack is empty ";
return;
}
cout << "The value of top node is: " << top->data << endl;

Page 28
 }

void print_stack()
{
if(top==NULL)
{
cout<<"Stack is empty ";
return;
}
node *temp = top;
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->next;
}
}
};
int main()
{
stack s;
int choice;
cout << "Which operation do you want to perform operation: \n1.
Push \n2. Pop \n3. Top \n4. Print Stack\n5. Exit...\n";
cin >> choice;
while (choice != 5)
{
if (choice == 1)
{
s.push_operation();
}
else if (choice == 2)
{
s.pop_operation();
}
else if (choice == 3)
{
s.top_operation();
}
else if (choice == 4)
{
s.print_stack();
}
cout << "Which operation do you want to perform operation: \n1.
Push \n2. Pop \n3. Top \n4. Print Stack\n5. Exit...\n";
cin >> choice;
}
return 0;

Page 29
 }

4 Tabulation Sheet

INPUT OUTPUT
Which operation do you want to perform
operation:
1. Push
2. Pop
3. Top
4. Print Stack
5. Exit...
1
Enter the data of this node:
6
Which operation do you want to perform
operation:
1. Push
2. Pop
3. Top
4. Print Stack
5. Exit...
1
Which operation do you want to perform
operation:
1. Push
2. Pop
3. Top
4. Print Stack
5. Exit...
5
Which operation do you want to perform
operation:
1. Push
2. Pop
3. Top
4. Print Stack
5. Exit...
4
5 6
Which operation do you want to perform
operation:
1. Push
2. Pop
3. Top
4. Print Stack
5. Exit...
2

Page 30
 Which operation do you want to perform
operation:
1. Push
2. Pop
3. Top
4. Print Stack
5. Exit...
4
6
Which operation do you want to perform
operation:
1. Push
2. Pop
3. Top
4. Print Stack
5. Exit...
5

6 Results
The program successfully demonstrates stack operations (push, pop, top, and print) using a
linked list. It efficiently handles dynamic memory allocation and maintains the stack
structure without overflow issues.

Page 31
 Acropolis Institute of Technology and Research, Indore
Department of CSE (Artificial Intelligence & Machine
Learning)
Group / Title: Program to perform Insertion and deletion
Lab: Data Structure (AL303) operation in queue.

EVALUATION RECORD Type/ Lab Session:

Name Hardik Joshi Enrollment No. 0827AL231051
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- Program to perform Insertion and deletion operation in queue.

2 Neatly Drawn and labeled experimental setup

Page 32
Page 33
3 Theoretical solution of the instant problem
3.1 Algorithm
□ Start.
□ Define a struct node with two members:
 int data (to store the value of the node).
 node* next (to point to the next node, initialized to NULL).
□ Create a class queue with the following:
 node* front (pointer to the front of the queue, initialized to NULL).
 node* rear (pointer to the rear of the queue, initialized to NULL).
 Member functions:
o Enqueue Operation:
 Create a new node.
 Input the data for the new node.
 If front == NULL (queue is empty), set front = newnode and rear =
newnode.
 Else, set rear->next = newnode and update rear = newnode.
o Dequeue Operation:
 Check if front == NULL (queue is empty). If true, print "Queue is
empty" and return.
 Store front in a temporary pointer deal.
 Update front = front->next.
 Delete the del node.
o Front Operation:
 Check if front == NULL. If true, print "Queue is empty" and return.
 Print the data of the front node.
o Print Queue:
 Check if front == NULL. If true, print "Queue is empty" and return.
 Traverse through the queue using a temporary pointer, printing
the data of each node.
□ Main Function:
 Create an object for the queue class.

Page 34
  Use a menu-driven approach to call the appropriate functions based on the
user's input.
□ End.

3.2 Program
#include <iostream>
using namespace std;

struct node
{
public:
int data;
node *next = NULL;
};
class queue
{
public:
node *front = NULL;
node *rear = NULL;
void enqueue()
{
node *newnode = new node;
cout << "Enter the data of this node: ";
cin >> newnode->data;
if (front == NULL)
{
front = newnode;
rear = newnode;
}
else
{
rear->next = newnode;
rear = newnode;
}
}
void dequeue()
{
if (front == NULL)
{
cout << "Queue is empty " << endl;
return;
}
node *del = front;
front = front->next;

Page 35
 delete del;
}
void frontOperation()
{
if (front == NULL)
{
cout << "Queue is empty " << endl;
return;
}
cout <<"The value of front node is : "<< front->data << endl;
}
void print_queue()
{
if (front == NULL)
{
cout << "Queue is empty " << endl;
return;
}
node *temp = front;
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->next;
}
}
};
int main()
{
queue q;
int choice;
cout << "Which operation do you want to perform :\n1. Enqueue \n2.
Dequeue \n3. Front \n4. Print Queue \n";
cin >> choice;
while (choice != 5)
{
if (choice == 1)
{
[Link]();
}
else if (choice == 2)
{
[Link]();
}
else if (choice == 3)
{
[Link]();
}

Page 36
 else if (choice == 4)
{
q.print_queue();
}
cout << "Which operation do you want to perform :\n1. Enqueue
\n2. Dequeue \n3. Front \n4. Print Queue \n5. Exit...\n";
cin >> choice;
}
return 0;
}
4 Tabulation Sheet
INPUT OUTPUT
Which operation do you want to perform :
1. Enqueue
2. Dequeue
3. Front
4. Print Queue
1
Enter the data of this node:
100
Which operation do you want to perform :
1. Enqueue
2. Dequeue
3. Front
4. Print Queue
5. Exit...
1
Enter the data of this node:
200
Which operation do you want to perform :
1. Enqueue
2. Dequeue
3. Front
4. Print Queue
5. Exit...
4
100 200 Which operation do you want to
perform :
1. Enqueue
2. Dequeue
3. Front
4. Print Queue
5. Exit...
2
Which operation do you want to perform :
1. Enqueue
2. Dequeue

Page 37
 3. Front
4. Print Queue
5. Exit...
4
200 Which operation do you want to
perform :
1. Enqueue
2. Dequeue
3. Front
4. Print Queue
5. Exit...
5

5 Results
The program successfully demonstrates queue operations (enqueue, dequeue, front, and
print) using a linked list. It ensures dynamic memory allocation and maintains the queue
structure without overflow issues.

Page 38
 Acropolis Institute of Technology and Research, Indore
Department of CSE (Artificial Intelligence & Machine
Learning)
Group / Title: Program to create a tree.
Lab: Data Structure (AL303)

EVALUATION RECORD Type/ Lab Session:

Name Hardik Joshi Enrollment No. 0827AL231051
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- Program to create a tree.

2 Neatly Drawn and labeled experimental setup

Page 39
Page 40
3 Theoretical solution of the instant problem
3.1 Algorithm
1. Define the Node structure:
 Each node contains:
o data: Value stored in the node.
o left: Pointer to the left child.
o right: Pointer to the right child.
 A constructor initializes the data and sets left and right pointers to nullptr.

2. insert Function (Recursive Insertion in BST):

 Input: Root of the tree (root) and value to insert (val).
 Output: Updated root with the new value inserted.
 Steps:
1. If the tree is empty (root == nullptr), create a new node with the given
value and return it.
2. If val is less than the root's data:
 Recursively insert val into the left subtree (root->left).
3. Otherwise:
 Recursively insert val into the right subtree (root->right).
4. Return the updated root.

3. Tree Traversal Functions:

a. inorderTraversal (Left, Root, Right):
 Input: Root of the tree (root).
 Steps:
1. If root == nullptr, return.
2. Recursively call inorderTraversal on the left subtree.
3. Print the current node's data (root->data).
4. Recursively call inorderTraversal on the right subtree.
b. preorderTraversal (Root, Left, Right):
 Input: Root of the tree (root).
 Steps:

Page 41
 1. If root == nullptr, return.
2. Print the current node's data (root->data).
3. Recursively call preorderTraversal on the left subtree.
4. Recursively call preorderTraversal on the right subtree.
c. postorderTraversal (Left, Right, Root):
 Input: Root of the tree (root).
 Steps:
1. If root == nullptr, return.
2. Recursively call postorderTraversal on the left subtree.
3. Recursively call postorderTraversal on the right subtree.
4. Print the current node's data (root->data).

4. main Function:
1. Initialize an empty tree (Node* root = nullptr).
2. Ask the user for the number of nodes to insert.
3. For each node:
o Read the value from the user.
o Call insert to add the value to the BST.
4. Perform and display the results of the following tree traversals:
o Inorder Traversal
o Preorder Traversal
o Postorder Traversal

3.2 Program
#include <iostream>
using namespace std;

struct Node
{
int data;
Node *left;
Node *right;

Node(int val)
{
data = val;

Page 42
 left = nullptr;
right = nullptr;
}
};

Node *insert(Node *root, int val)

{
if (root == nullptr)
{
return new Node(val); // Create a new node if the tree is empty
}

if (val < root->data)

{
root->left = insert(root->left, val); // Insert in the left
subtree
}
else
{
root->right = insert(root->right, val); // Insert in the right
subtree
}

return root;
}

void inorderTraversal(Node *root)

{
if (root == nullptr)
return;

inorderTraversal(root->left);
cout << root->data << " ";
inorderTraversal(root->right);
}

void preorderTraversal(Node *root)

{
if (root == nullptr)
return;

cout << root->data << " ";

preorderTraversal(root->left);
preorderTraversal(root->right);
}

void postorderTraversal(Node *root)

Page 43
{
if (root == nullptr)
return;

postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->data << " ";
}

int main()
{
Node *root = nullptr;

cout << "Enter the number of nodes: ";

int n;
cin >> n;

cout << "Enter the values of the nodes:\n";

for (int i = 0; i < n; i++)
{
int val;
cin >> val;
root = insert(root, val); // insert each value into the binary
tree
}

cout << "\nInorder Traversal: ";

inorderTraversal(root);
cout << endl;

cout << "Preorder Traversal: ";

preorderTraversal(root);
cout << endl;

cout << "Postorder Traversal: ";

postorderTraversal(root);
cout << endl;

return 0;
}

Page 44
4 Tabulation Sheet

INPUT OUTPUT
Enter the number of nodes:
9
Enter the values of the nodes:
158876923
Inorder Traversal: 1 2 3 5 6 7 8 8 9
Preorder Traversal: 1 5 2 3 8 7 6 8 9
Postorder Traversal: 3 2 6 7 9 8 8 5 1

5 Results- This program demonstrates how to build and traverse a binary search tree, leveraging
its properties for efficient insertion and retrieval. It highlights the importance of tree traversal
techniques in managing hierarchical data structures.

Page 45
 Acropolis Institute of Technology and Research, Indore
Department of CSE (Artificial Intelligence & Machine
Learning)
Group / Title: Program to implement Selection Sort.
Lab: Data Structure (AL303)

EVALUATION RECORD Type/ Lab Session:

Name Hardik Joshi Enrollment No. 0827AL231051
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- Program to implement Selection Sort.

2 Neatly Drawn and labeled experimental setup

Page 46
Page 47
3 Theoretical solution of the instant problem
3.1 Algorithm
1. Input the array from the user:
1. Ask the user to input the number of elements, n.
2. Declare an array of size n.
3. Read n elements from the user into the array.

2. Selection Sort Algorithm:

Input: An array arr[] of size n.
Output: The array sorted in ascending order.
Steps:
1. Outer Loop (Start from index i = 0):
o Continue until i < n - 1.
o The outer loop divides the array into two parts:
 Sorted portion (left side).
 Unsorted portion (right side).
2. Inner Loop:
o For each element i, iterate through the remaining unsorted portion (j = i + 1
to n - 1).
o Compare arr[i] with arr[j].
 If arr[i] > arr[j], swap the values of arr[i] and arr[j].
3. Increment i to process the next element in the array.

3. Output the Sorted Array:

 Traverse the array using a loop and print all the elements.

3.2 Program
#include <iostream>
using namespace std;

void selectionSort(int arr[], int n)

{

Page 48
 int i = 0;
while (i < n - 1)
{
for (int j = i + 1; j < n; j++)
{
if (arr[i] > arr[j])
swap(arr[i], arr[j]);
} i+
+;
}
}

void printArray(int arr[], int n)

{
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
}

int main()
{
int n;
cout << "Enter the number of elements you want in array: ";
cin >> n;
int arr[n];
cout << "Enter the elements of your array: " << endl;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
selectionSort(arr, n);
printArray(arr, n);

return 0;
}

Page 49
4 Tabulation Sheet

INPUT OUTPUT
Enter the number of elements you want in
array:
8
Enter the elements of your array:
7 5 9 3 4 -55 0 1
-55 0 1 3 4 5 7 9

5 Results- This program demonstrates the working of the Selection Sort algorithm and how it
arranges elements into ascending order iteratively.

Page 50
 Acropolis Institute of Technology and Research, Indore
Department of CSE (Artificial Intelligence & Machine
Learning)
Group / Title: Program to implement Insertion Sort.
Lab: Data Structure (AL303)

EVALUATION RECORD Type/ Lab Session:

Name Hardik Joshi Enrollment No. 0827AL231051
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- Program to implement Insertion Sort.

2 Neatly Drawn and labeled experimental setup

Page 51
Page 52
3 Theoretical solution of the instant problem
3.1 Algorithm
1. Input the array from the user:
1. Prompt the user to enter the number of elements in the array, n.
2. Declare an array arr[n] to hold n integers.
3. Ask the user to input the n elements of the array.

2. Insertion Sort Algorithm:

Input: An array nums[] of size n.
Output: The array sorted in ascending order.
1. Outer Loop:
o Start from the second element (i = 1) since the first element is
already "sorted."
o Iterate through the array from i = 1 to i = n - 1.
2. Key Element and Comparison:
o Assign the value of the current element (nums[i]) to temp.
o Compare temp with elements in the sorted portion of the array (from
index i - 1 to 0).
3. Shifting Elements:
o If an element in the sorted portion (nums[j]) is greater than temp, shift
it one position to the right.
o Repeat until temp is greater than or equal to nums[j] or the beginning of the
array is reached.
4. Insert Key Element:
o Place temp in its correct position (nums[j + 1]).

3. Output the Sorted Array:

 Traverse the sorted array and print all elements.

3.2 Program
#include <iostream>
using namespace std;

Page 53
void insertionsort(int nums[], int n)
{
for (int i = 1; i < n ; i++)
{
int temp = nums[i];
int j = i - 1;
while (j >= 0)
{
if (nums[j] > temp)
{
nums[j + 1] = nums[j];
}
else
{
break;
}
j--;
}
nums[j + 1] = temp;
}
}
void printsorted(int nums[], int n)
{
for (int i = 0; i < n; i++)
{
cout << nums[i] << " ";
}
}
int main()
{
int n;
cout << "How many elements you want to sort: ";
cin >> n;
int arr[n];
cout << "Enter the elements for sorting: " << endl;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
insertionsort(arr, n);
printsorted(arr, n);
return 0;
}

Page 54
4 Tabulation Sheet

INPUT OUTPUT
How many elements you want to sort:
7
Enter the elements for sorting:
5 1 7 -55 3 7 2
-55 1 2 3 5 7 7

5 Results- This program sorts an array of integers entered by the user using the Insertion Sort
algorithm. It iteratively places each element into its correct position in the sorted portion of
the array by shifting larger elements to the right.

Page 55
 Acropolis Institute of Technology and Research, Indore
Department of CSE (Artificial Intelligence & Machine
Learning)
Group / Title: Program to implement Quick Sort.
Lab: Data Structure (AL303)

EVALUATION RECORD Type/ Lab Session:

Name Hardik Joshi Enrollment No. 0827AL231051
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- Program to implement Quick Sort.

2 Neatly Drawn and labeled experimental setup

Page 56
Page 57
3 Theoretical solution of the instant problem
3.1 Algorithm
□ Input: An array arr[] of integers of size n.
□ Base Case: If the start index s is greater than or equal to the end index e, return. This
means the subarray has only one element or is empty, so it doesn't need further
sorting.
□ Pivot Selection:
 The pivot element is selected as the first element of the subarray (arr[s]).
 Count the number of elements that are smaller than the pivot element in the
subarray from index s+1 to e.
 This count determines the position where the pivot element should go after
partitioning.
□ Partitioning:
 The pivot element is swapped with the element at position s + cnt to place it in the
correct position (pindex).
 Now, all elements to the left of pindex are smaller than the pivot, and all elements
to the right are greater.
□ Re-arranging:
 Use two pointers (i and j):
o Pointer i starts from the left of the subarray.
o Pointer j starts from the right of the subarray.
 Move the pointers inward, swapping elements if needed, until the i and j pointers
cross.
o The goal is to ensure that all elements on the left of pindex are smaller than
the pivot, and those on the right are greater.
□ Recursive Call:
 Recursively apply the same partitioning process to the left subarray (from s to
pindex - 1) and the right subarray (from pindex + 1 to e).
□ Repeat Steps 2-6 until the entire array is sorted.

3.2 Program

Page 58
#include <iostream>

using namespace std;

void setArray(int *arr, int n)
{
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
}

void getArray(int *arr, int n)

{
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
}

void quickSort(int *arr, int s, int e)

{
if (s>=e)
return;

int cnt = 0, pivot = arr[s];

for (int i = s + 1; i <= e; i++)

{
if (pivot > arr[i]) cnt+
+;
}
int pindex = s + cnt;
swap(arr[s], arr[s + cnt]);

int i = s, j = e;
while (i < pindex && j > pindex)
{
while (arr[i] < pivot)
{
i++;
}
while (arr[j] > pivot)
{
j--;
}
if (i < pindex && j > pindex)
swap(arr[i++], arr[j--]);
}
// Solve left part
quickSort(arr, s, pindex - 1);

// Solve right part

quickSort(arr, pindex + 1, e);
}

int main()

Page 59
{
int n;
cout<<"How many numbers you want to sort: ";
cin >> n;
cout<<"Enter the numbers to perform sorting:"<<endl;
int *arr = new int[n];
setArray(arr, n);
quickSort(arr, 0, n - 1);
getArray(arr, n);

return 0;
}

4 Tabulation Sheet

INPUT OUTPUT
How many numbers you want to sort:
8
Enter the numbers to perform sorting:
9 -77 8 0 7 2 1 63
-77 0 1 2 7 8 9 63

5 Results- This program demonstrates the working of the Quick Sort algorithm and how it
arranges elements into ascending order iteratively.

Page 60
 Acropolis Institute of Technology and Research, Indore
Department of CSE (Artificial Intelligence & Machine
Learning)
Group / Title: Program to implement Merge Sort.
Lab: Data Structure (AL303)

EVALUATION RECORD Type/ Lab Session:

Name Hardik Joshi Enrollment No. 0827AL231051
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- Program to implement Merge Sort.

2 Neatly Drawn and labeled experimental setup

Page 61
Page 62
3 Theoretical solution of the instant problem
3.1 Algorithm
□ Merge Function:
 Input: Array arr[], start index s, and end index e.
 Action:
o Find the midpoint of the array: mid = s + (e - s) / 2.
o Divide the array into two subarrays: arr1[] and arr2[].
o Copy elements from the original array into the two subarrays (arr1[] and arr2[]).
o Merge the two sorted subarrays into the original array:
 Compare the elements from both subarrays and insert the
smaller element into the original array.
 If one subarray is exhausted, copy the remaining elements from the
other subarray to the original array.
□ MergeSort Function:
 Input: Array arr[], start index s, and end index e.
 Action:
o Check for the base case: if s >= e, return (no sorting needed).
o Calculate the midpoint mid = s + (e - s) / 2.
o Recursively call mergeSort for the left half: mergeSort(arr, s, mid).
o Recursively call mergeSort for the right half: mergeSort(arr, mid + 1, e).
o Merge the sorted halves by calling the merge function.
□ Main Function:
 Input: Number of elements n and the array elements from the user.
 Initialize an array arr[] of size n.
 Populate the array with user input.
 Call mergeSort to sort the array.
 Call getArray to print the sorted array.

3.2 Program

#include <iostream>
using namespace std;

Page 63
void merge(int *arr, int s, int e)
{
int mid = s + (e - s) / 2;
int len1 = mid - s + 1;
int len2 = e - mid;
int *arr1 = new int[len1];
int *arr2 = new int[len2];

int k = s; //k is deoting the index of the original array

for (int i = 0; i < (len1); i++)
{
arr1[i] = arr[k++];
}
for (int i = 0; i < (len2); i++)
{
arr2[i] = arr[k++];
}

int i = 0, j = 0;
k = s;
while (i < len1 && j < len2)
{
if (arr1[i]<arr2[j]) arr[k+
+] = arr1[i++];
else{
arr[k++] = arr2[j++];
}
}

while (i < len1)

{
arr[k++] = arr1[i++];
}
while (j < len2)
{
arr[k++] = arr2[j++];
}
}

void mergeSort(int *arr, int s, int e)

{
// Basecase
if (s >= e)
return ;
int mid = s + (e - s) / 2;

// Sort the left part

mergeSort(arr, s, mid);

// Sort the right part

mergeSort(arr, mid + 1, e);

// Merge the array

merge(arr, s, e);
}

Page 64
 void getArray(int *arr, int n)
{
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}

int main()
{
int n;
cout<<"How many elements you want to sort: ";
cin >> n;
int *arr = new int[n];
cout<<"Enter elements of for sorting: ";
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
mergeSort(arr, 0, n - 1);
getArray(arr, n);
return 0;
}

4 Tabulation Sheet

INPUT OUTPUT
How many elements you want to sort: 8 -33 0 1 4 7 8 8 9

Enter elements of for sorting: 1

8 0 -33 8 9 7 4

5 Results

In this experiment, we implemented the Merge Sort algorithm, a popular divide-and-

conquer sorting technique. Merge Sort recursively divides the array into two halves, sorts
them, and then merges the sorted halves back together. This process continues until the base
case is reached, where the array contains only one element, which is trivially sorted.

The time complexity of Merge Sort is O(n log n), making it an efficient sorting algorithm
for large datasets. Unlike other sorting algorithms such as Bubble Sort or Insertion Sort
(which have time complexities of O(n²)), Merge Sort consistently performs well even with
large arrays.

Page 65
 Acropolis Institute of Technology and Research, Indore
Department of CSE (Artificial Intelligence & Machine
Learning)
Group / Title: Program to implement Binary Search.
Lab: Data Structure (AL303)

EVALUATION RECORD Type/ Lab Session:

Name Hardik Joshi Enrollment No. 0827AL231051
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- Program to implement Binary Search.

2 Neatly Drawn and labeled experimental setup

Page 66
Page 67
3 Theoretical solution of the instant problem
3.1 Algorithm
□ Set Array (setArray function):
 Input: Integer array arr[] and integer size.
 Action: The function iterates over the array and accepts size number of integers from the
user, storing them in arr[].
□ Binary Search (binarySearch function):
 Input: Integer array arr[], its size, and the integer s (the element to search for).
 Initialize two variables:
o start = 0 (the start index).
o end = size - 1 (the last index).
 Repeat the following steps until start <= end:
o Calculate the middle index: mid = start + (end - start) / 2.
o If arr[mid] == s, return mid (element found).
o If arr[mid] > s, move the end pointer to mid - 1 (search the left half).
o If arr[mid] < s, move the start pointer to mid + 1 (search the right half).
 If the element is not found, return -1.
□ Main Function:
 Input: First, the number of elements n in the array, followed by n integers in
ascending order.
 The program calls setArray to input the elements.
 Input the integer element that you wish to search for.
 Call binarySearch to find the index of element in the array.
 Output the result: the index of element in the array or -1 if not found.

3.2 Program
#include <iostream>
using namespace std;

void setArray(int arr[], int size)

{
for (int i = 0; i < size; i++)

Page 68
 {
cin >> arr[i];
}
}
int binarySearch(int arr[], int size, int s)
{
int start = 0;
int end = size - 1;
while (start <= end)
{
int mid = start + (end - start) / 2;
if (arr[mid] == s)
return mid;

else if (arr[mid] > s)

{ end = mid - 1;
}
else{
start = start + 1;
}
}
return -1;
}

int main()
{
int n;
cout<<"How many elements do you want in array: ";
cin >> n;
int arr[100];
cout<<"Enter elements in array (Enter in ascending arder): "<<endl;
setArray(arr, n);
cout << endl;

int element;
cout<<"Enter the element you want search in array: ";
cin >> element;
cout << endl;

Page 69
 cout << "Index : " << binarySearch(arr, n, element);

return 0;
}

4 Tabulation Sheet

INPUT OUTPUT
How many elements do you want in array: 8 Index : 4

Enter elements in array (Enter in ascending

arder):

12345678

Enter the element you want search in array:

5

5 Results
In this experiment, we implemented a Binary Search algorithm to efficiently search
for an element in a sorted array. The algorithm follows the divide-and-conquer
approach, where the array is divided into smaller sections at each iteration to
narrow down the search range.
The binary search algorithm performs optimally with a time complexity of O(log n),
which makes it significantly faster than linear search for large datasets. This
efficiency, however, is contingent upon the input array being sorted in ascending
order. If the array is unsorted, the binary search will fail to produce correct results,
and sorting the array would be necessary before applying the search.

Page 70
Page 71