Data Structures and

Algorithms
LABORATORY MANUAL
Second Year ( SEM - I)
(2023-2024)

DEPARTMENT OF ARTIFICIAL
INTELLIGENCE AND MACHINE LEARNING

GENBA SOPANRAO MOZE COLLEGE OF

ENGINEERING, Balewadi, Pune.
Course Objectives:

1. To study data structures and their implementations and applications.

2. To learn different searching and sorting techniques.
3. To study some advanced data structures such as trees, graphs and tables.
4. To learn different file organizations.
5. To learn algorithm development and analysis of algorithms.
Course Outcomes:
On completion of the course, students will be able to–
CO1: Analyze algorithms and to determine algorithm correctness and time efficiency
class.
CO2: Implement abstract data type (ADT) and data structures for given application.
CO3: Design algorithms based on techniques like brute -force, divide and conquer,
greedy, etc.).
CO4: Solve problems using algorithmic design techniques and data structures.
CO5: Analyze of algorithms with respect to time and space complexity.
 GENERAL LABORATORY INSTRUCTIONS

1. Students are advised to come to the laboratory at least 5 minutes before (to the
starting time), those who come after 5 minutes will not be allowed into the lab. 2.
Plan your task properly much before to the commencement, come prepared to the
lab with the synopsis / program / experiment details.

3. Student should enter into the laboratory with: a. Laboratory observation notes
with all the details (Problem statement, Aim, Algorithm, Procedure, Program,
Expected Output, etc.,) filled in for the lab session. b. Laboratory Record updated
up to the last session experiments and other utensils (if any) needed in the lab. c.
Proper Dress code and Identity card.

4. Sign in the laboratory login register, write the TIME-IN, and occupy the
computer system allotted to you by the faculty.

5. Execute your task in the laboratory, and record the results / output in the lab
observation note book, and get certified by the concerned faculty.

6. All the students should be polite and cooperative with the laboratory staff, must
maintain the discipline and decency in the laboratory.

7. Computer labs are established with sophisticated and high end branded systems,
which should be utilized properly.

8. Students / Faculty must keep their mobile phones in SWITCHED OFF mode
during the lab sessions. Misuse of the equipment, misbehaviors with the staff and
systems etc., will attract severe punishment.

9. Students must take the permission of the faculty in case of any urgency to go
out; if anybody found loitering outside the lab / class without permission during
working hours will be treated seriously and punished appropriately.

10. Students should LOG OFF/ SHUT DOWN the computer system before he/she
leaves the lab after completing the task (experiment) in all aspects. He/she must
ensure the system / seat is kept properly.
 DEPARTMENT OF ARTIFICIAL INTELLIGENCE AND MACHINE
LEARNING
List of Assignments
Subject: Data Structures And Algorithms Class: SE (AIML)
Practical: 4 Hours/Week Practical: 25 Marks
Term Work: 25 Marks
INDEX

Sr.No List of Assignments

1 Searching and Sorting: a) Design a roll call list, arrange list of students
according to roll numbers in ascending order (Use bubble sort)
b) Arrange list of students alphabetically. (Use Insertion sort)
c) Arrange list of students to find out first ten toppers from a class.
(Use Quick sort)
d) Search students according to SGPA. If more than one student
having same SGPA, then print list of all students having same SGPA.
e) Search a particular student according to name using binary search
without recursion.( all the student records having the presence of
search key should be displayed)

2 Stack: Implement stack as an abstract data type using singly linked list
and use this ADT for conversion of infix
Expression to postfix, prefix and evaluation of postfix and prefix
expression.
3 Circular Queue: Implement Circular Queue using Array. Perform
following operations on it.
a) Insertion (Enqueue)
b) Deletion (Dequeue)
c) Display
4 Expression Tree: Construct an Expression Tree from postfix and prefix
expression. Perform recursive and non- recursive
In-order, pre-order and post-order traversals.
5 Binary Search Tree: Implement binary search tree and perform
following operations:
a) Insert (Handle insertion of duplicate entry)
 b) Delete
c) Search
d) Display tree (Traversal)

6 Threaded Binary Tree: Implement In-order Threaded Binary Tree and

traverse it in In-order and Pre-order.
7 Graph: Minimum Spanning Tree: Represent a graph of your college
campus using adjacency list /adjacency matrix. Nodes should
represent the various departments/institutes and links should represent
the distance between them.
Find minimum spanning tree
a) Using Kruskal’s algorithm.
b) Using Prim’s algorithm.
8 Graph: Shortest Path Algorithm: Represent a graph of city using
adjacency matrix /adjacency list. Nodes should represent the various
landmarks and links should represent the distance between them. Find
the shortest path using
Dijkstra's algorithm from single source to all destination.
9 Heap Sort: Implement Heap sort to sort given set of values using max
or min heap
10 FILE Handling: Department maintains student’s database. The file
contains roll number, name, division and address. Write a program to
create a sequential file to store and maintain student data. It should
allow the user to add, delete information of student. Display
information of particular student. If record of student does not exist an
appropriate message is displayed. If student record is found it should
display the student details.
 Assignment 1

Title: Searching and Sorting

Consider a student database of SEIT class (at least 15 records). Database contains
different fields of every student like Roll No, Name and SGPA.(array of structure)
A) Design a roll call list, arrange list of students according to roll numbers in
ascending order (Use Bubble Sort)
B) Arrange list of students alphabetically. (Use Insertion sort)
C) Arrange list of students to find out first ten toppers from a class. (Use Quick
sort)
D) Search students according to SGPA. If more than one student having same
SGPA, then print list of all students having same SGPA.
E) Search a particular student according to name using binary search without
recursion.( all the student records having the presence of search key should be
displayed)

Theory:
Searching and Sorting:
Sorting and Searching is one of the most vital topic in DSA. So many techniques
and algorithms have been developed to efficiently maintain and process
information in databases. The processes of looking up a particular data record in
the database is called searching. The process of ordering the records in a database
is called Sorting.

What is searching?

Searching is the process of finding a particular item in a collection of items. A

search typically answers whether the item is present in the collection or not.
Searching requires a key field such as name, ID, code which is related to the target
item. When the key field of a target item is found, a pointer to the target item is
returned. The pointer may be an address, an index into a vector or array, or some
other indication of where to find the target. If a matching key field isn’t found, the
user is informed.

 The most common searching algorithms are:

 Linear search
  Binary search
 Interpolation search
 Hash table

What is sorting?

Sorting is the process of placing elements from a collection in some kind of order.
For example, a list of words could be sorted alphabetically or by length.

The most common sorting algorithms are:

 Bubble Sort
 Insertion Sort
 Selection Sort
 Quick Sort
 Merge Sort
 Shell Sort

Bubble Sort:

Bubble sort is the simplest sorting algorithm. It is based on comparison where each
adjacent pair of element is compared and swapped if they are not in order.

Algorithm:

 Create a data structure to represent a student with attributes such as roll

number, name, and other relevant information.
 Create an array to store the student records.
 Read and input student records, including roll number, name, and other
information, into the array.
 Implement the Bubble Sort algorithm to sort the student records in
ascending order based on their roll numbers.

Algorithm: Search Students by SGPA

1. Create a data structure to represent a student with attributes such as roll

number, name, SGPA, and other relevant information.
 2. Create an array or list to store the student records.
3. Read and input student records, including roll number, name, SGPA, and
other information, into the array or list.
4. Prompt the user to enter the SGPA they want to search for.
5. Traverse the array or list of student records and compare each student's
SGPA with the user's input.
6. If a student's SGPA matches the user's input, add that student to a list of
matching students.
7. Repeat the process for all students in the array or list.
8. After the traversal, check if the list of matching students is empty:
9. If it's empty, display a message indicating that no students with the given
SGPA were found.
10.If it's not empty, print the list of students with the same SGPA.

Conclusion: In this way, we have studied Searching and sorting different fields
from database by using various algorithms.
 Assignment 2

Title: Implement stack as an abstract data type using singly linked list and use this
ADT for conversion of infix expression to postfix, prefix and evaluation of postfix
and prefix expression.

Theory:

Stack

A stack is a linear data structure in which the insertion of a new element and
removal of an existing element takes place at the same end represented as the top
of the stack.

Basic Operations on Stack

In order to make manipulations in a stack, there are certain operations provided to

us.

 push() to insert an element into the stack

 pop() to remove an element from the stack
 top() Returns the top element of the stack.
 isEmpty() returns true if stack is empty else false.
 size() returns the size of stack.

Stack
What is a Linked List?

Linked List is a linear data structure which looks like a chain of nodes, where each
node is a different element. Unlike Arrays, Linked List elements are not stored at a
contiguous location. The elements in a linked list are linked using pointers as
shown in the below image:

Linked-List-Data-Structure

Types of linked lists:

There are mainly three types of linked lists:

1. Single-linked list
2. Double linked list
3. Circular linked list

Single-linked list: Traversal of items can be done in the forward direction only
due to the linking of every node to its next node.
 Singly Linked List

Algorithm:

Implement the algorithm to convert an infix expression to a postfix expression

using the stack. Here's the algorithm:

 Initialize an empty stack.

 Initialize an empty string to store the postfix expression.
 Iterate through each character in the infix expression from left to right.
 For each character, do the following:
o If it is an operand (a letter or digit), append it to the postfix
expression.
o If it is an operator (e.g., +, -, *, /, etc.), pop operators from the stack
and append them to the postfix expression until the stack is empty or
the operator at the top of the stack has lower precedence. Then push
the current operator onto the stack.
o If it is an open parenthesis '(', push it onto the stack.
o If it is a closing parenthesis ')', pop operators from the stack and
append them to the postfix expression until an open parenthesis '(' is
encountered. Pop and discard the '('.
 After processing all characters in the infix expression, pop any remaining
operators from the stack and append them to the postfix expression.
 The final postfix expression is the result.

Conclusion: In this way, we have studied implementation of stack as an abstract

data type using singly linked list.
 Assignment 3

Title : Implement Circular Queue using Array. Perform following operations on it.
a) Insertion (Enqueue)
b) Deletion (Dequeue)
c) Display
Theory:

Queue Data Structure:

A queue is a useful data structure in programming. It is similar to the ticket queue

outside a cinema hall, where the first person entering the queue is the first person
who gets the ticket.

Queue follows the First In First Out (FIFO) rule - the item that goes in first is the
item that comes out first.

FIFO Representation of Queue

Basic Operations of Queue

A queue is an object (an abstract data structure - ADT) that allows the following
operations

 Enqueue: Add an element to the end of the queue

 Dequeue: Remove an element from the front of the queue
 IsEmpty: Check if the queue is empty
 IsFull: Check if the queue is full
 Peek: Get the value of the front of the queue without removing it.
Types of Queues

There are four different types of queues:

 Simple Queue
 Circular Queue
 Priority Queue
 Double Ended Queue

Circular Queue Data Structure

A circular queue is the extended version of a regular queue where the last element
is connected to the first element. Thus forming a circle-like structure.

Circular queue representation

The circular queue solves the major limitation of the normal queue. In a normal
queue, after a bit of insertion and deletion, there will be non-usable empty space.

Algorithm:

1. Initialize the circular queue:

o Create an array of a fixed size to store the elements.
o Initialize front and rear to -1 to indicate an empty queue.
2. Enqueue (Insertion) Operation:
o Check if the queue is empty:
 If front is -1 and rear is -1, the queue is empty.
  In this case, set front and rear to 0.
o Check if the queue is full:
 If front is 0 and rear is the last index of the array, or if rear is
just before front, the queue is full (circularly).
o If the queue is not full, insert the element at the rear index of the array
and increment rear by 1 (circularly).
3. Dequeue (Deletion) Operation:
o Check if the queue is empty:
 If front and rear are -1, the queue is empty.
o If the queue is not empty, remove the element at the front index of the
array.
o If front is the same as rear after the removal, it means the queue is
now empty. Set front and rear back to -1.
o If the queue is not empty, increment front by 1 (circularly).
4. Display Operation:
o Traverse the circular queue from front to rear, and print each element.
5. Additional considerations:
o Ensure that the indices front and rear wrap around the array to form a
circular structure.
o You may need to perform modulo operations when incrementing
indices to handle the circular behavior.

Conclusion: In this way, we have studied Implementation of Circular Queue

using Array.
 Assignment 4:

Title: Construct an Expression Tree from postfix and prefix expression. Perform
recursive and non- recursive In-order, pre-order and post-order traversals.

Theory:

Expression Tree:

The expression tree is a binary tree in which each internal node corresponds to the
operator and each leaf node corresponds to the operand.

Expression Tree is used to represent expressions.

An expression and expression tree shown below

a + (b * c) + d * (e + f)

Expression Tree

There are different types of expression formats:

 Prefix expression
 Infix expression and
 Postfix expression

Recursion
The process in which a function calls itself directly or indirectly is called recursion
and the corresponding function is called a recursive function.
Non- Recursion

A non-recursive algorithm, also known as an iterative algorithm, is an algorithm

that does not use recursion for solving a problem. Instead, it employs loops,
conditional statements, and other control structures to perform its task.

Traversal Techniques

There are 3 standard traversal techniques to represent the 3 different expression

formats.

In order Traversal

We can produce an infix expression by recursively printing out

 The left expression,

 The root, and
 The right expression.

Post order Traversal

The postfix expression can be evaluated by recursively printing out

 the left expression,

 the right expression and
 then the root

Preorder Traversal

We can also evaluate prefix expression by recursively printing out:

 The root,
 The left expression and
 The right expression.

If we apply all these strategies to the sample tree above, the outputs are:

 Infix expression:
 (a+(b*c))+(d*(e + f))

 Postfix Expression:

abc*+def+*+

 Prefix Expression:

++a*bc*d+ef

 Tree traversal is the action of visiting all the nodes in the tree exactly once.
 There are three ways to traverse a tree.
1. Inorder Traversal
2. Preorder Traversal
3. Post Order Traversal
 Primary purpose of tree traversal is to search and locate an item in the tree

Traversal process

First step is to define a traversal process depending on the type of traversal. Then,
repeatedly call the traversal process for each node.

In Order Traversal

In In-order traversal process or function, the nodes on the left are traversed first,
then the root node and then the nodes on the right.

Based on the process, we traverse the left subtree recursively by calling In Order
function, then process the root node, and then traverse the right subtree recursively
by calling In-Order function.
The output of the above tree is. D-->B-->E-->A-->F-->C

Pre-Order Traversal

In Pre-Order traversal, the root node is visited first, then the left sub tree and right
sub tree are traversed.

Based on the process, we first process the root, then traverse the left subtree
recursively by calling Pre-Order function, and traverse the right subtree recursively
by calling Pre-Order function.

The output of the above tree is A-->B-->D-->E-->C-->F

Post-Order Traversal

In Post-Order traversal, we will first traverse the left nodes, then the right nodes
and then traverse the root node.

Based on the process, we traverse the left subtree recursively by calling Post-Order
function, then traverse the right subtree recursively by calling Post-Order function
and finally process the rootnode.
The output of the above tree is. D-->E-->B-->F-->C-->A
Algorithm:

Expression Tree Construction from Postfix Expression:

1. Create an empty stack of tree nodes (the node should have fields for the
operator and two children nodes).
2. Iterate through each character in the postfix expression from left to right.
3. For each character, do the following:
o If it is an operand (e.g., a variable or constant), create a tree node for it
and push it onto the stack.
o If it is an operator (e.g., +, -, *, /, etc.), pop the top two nodes from the
stack, create a new node for the operator, make the popped nodes its
children, and push the new node onto the stack.
4. After processing the entire postfix expression, the stack should contain the
root node of the Expression Tree.

Expression Tree Construction from Prefix Expression:

1. Create an empty stack of tree nodes.

2. Iterate through each character in the prefix expression from right to left.
3. For each character, do the following:
o If it is an operand, create a tree node for it and push it onto the stack.
o If it is an operator, pop the top two nodes from the stack, create a new
node for the operator, make the popped nodes its children, and push
the new node onto the stack.
4. After processing the entire prefix expression, the stack should contain the
root node of the Expression Tree.

Conclusion: In this way, we have studied Construction of an Expression Tree

from postfix and prefix expression.
 Assignment 5

Title: Implement binary search tree and perform following operations: a) Insert
(Handle insertion of duplicate entry) b) Delete c) Search d) Display tree
(Traversal).

Theory:

Binary Search Tree

A binary tree is a hierarchical data structure in which each node has at most two
children, typically referred to as the "left" child and the "right" child.

Binary Search is defined as a searching algorithm used in a sorted array by

repeatedly dividing the search interval in half.

Binary Search Tree (BST): A binary tree in which the nodes are ordered such
that for each node:

 All nodes in its left subtree have values less than the node's value.
 All nodes in its right subtree have values greater than the node's value.

Binary search

A binary tree has the following characteristics:

 1. Root: The topmost node in the tree, from which all other nodes are
descendants.
2. Node: Each element within the tree that stores data.
3. Parent: A node that has child nodes.
4. Child: A node that is descended from another node (its parent).
5. Leaf: A node that has no children.
6. Sub tree: A set of nodes and edges that are part of the main tree but form a
smaller tree themselves.
7. Depth: The length of the path from the root to a particular node (measured
by the number of edges).
8. Height: The length of the longest path from the node to a leaf.

Algorithm:

1. Insertion (Handle duplicates):

o Start at the root node.
o If the tree is empty, create a new node with the given data and make it
the root.
o If the data to be inserted is equal to the data of the current node, you
need to handle duplicates:
 You can add a count field to the node to track the number of
duplicates, or
 You can insert duplicate values to the right subtree or left
subtree based on a rule (e.g., always to the right).
o If the data is less than the current node's data, move to the left child. If
it's greater, move to the right child.
o Repeat the process until you find an empty spot, and insert the new
node there.
2. Deletion:
o Start at the root and search for the node to delete.
o Handle three cases: a. If the node to delete is a leaf (has no children),
simply remove it. b. If the node has one child, replace the node with
its child. c. If the node has two children, find the in-order predecessor
 or successor, copy its data to the node to delete, and then delete the
predecessor or successor node (which falls into one of the first two
cases).
3. Search:
o Start at the root node.
o If the tree is empty, return that the element is not found.
o If the data matches the current node's data, return that the element is
found.
o If the data is less than the current node's data, search in the left
subtree.
o If the data is greater than the current node's data, search in the right
subtree.
o Continue this process until you find the element or reach a leaf node.
4. Display Tree (Traversal):
o There are three common traversal methods: In-order, Pre-order, and
Post-order.
o Use recursive algorithms for each traversal type:

a. In-order Traversal: - Traverse the left subtree. - Visit the current node. -
Traverse the right subtree.

b. Pre-order Traversal: - Visit the current node. - Traverse the left subtree.
- Traverse the right subtree.

c. Post-order Traversal: - Traverse the left subtree. - Traverse the right

subtree. - Visit the current node.

Conclusion: In this way, we have studied Implementation of binary search tree

and perform different operations.
 Assignment 6

Title: Implement In-order Threaded Binary Tree and traverse it in In-order and
Pre-order.

Theory:

Threaded Binary Tree:

In the linked representation of binary trees, more than one half of the link fields
contain NULL values which results in wastage of storage space. If a binary tree
consists of n nodes then n+1 link fields contain NULL values. So in order to
effectively manage the space, a method was devised by Perlis and Thornton in
which the NULL links are replaced with special links known as threads. Such
binary trees with threads are known as threaded binary trees. Each node in a
threaded binary tree either contains a link to its child node or thread to other nodes
in the tree.

Types of Threaded Binary Tree

There are two types of threaded Binary Tree:

 One-way threaded Binary Tree

 Two-way threaded Binary Tree
Data Structures:

1. Define a structure for a tree node with fields for data, left and right children,
and left and right thread flags (indicators).

Algorithm:

1. Create a sentinel node, which will serve as the leftmost node's in-order
successor. Initialize it with left thread pointing to itself.
2. Create the root of the threaded binary tree.
3. Initialize the in_order_successor to the sentinel node.
4. Insertion:
o To insert a node with data: a. If the tree is empty, create a new node
and set its left and right threads to the sentinel node. Update the root.
b. Otherwise, traverse the tree to find the proper location for insertion:
 If the new data is smaller than the current node's data, move
left.
 If the left thread is set, set the left thread to False, and move
left.
 If the left thread is not set, insert the new node to the left and
set its left and right threads.
 If the new data is larger, move right.
 If the right thread is set, set the right thread to False, and move
right.
 If the right thread is not set, insert the new node to the right and
set its left thread.
5. In-Order Traversal (without recursion or stack):
o Start at the sentinel node (leftmost node's in-order successor).
o While the current node is not the sentinel node: a. Follow the left
thread (if it exists) to reach the in-order predecessor. b. Visit the
current node. c. If the current node has a right child, set it as the next
node to visit. d. If the current node doesn't have a right child, follow
the right thread (if it exists) to reach the in-order successor.
6. Pre-Order Traversal (without recursion or stack):
o Start at the root node.
 o While the current node is not the sentinel node: a. Visit the current
node. b. If the current node has a left child, set it as the next node to
visit. c. If the current node doesn't have a left child, follow the right
thread (if it exists) to reach the next node to visit.

Conclusion: In this way, we have studied Implementation of In-order Threaded

Binary Tree and traverse it in In-order and Pre-order.
 Assignment 7
Title : Represent a graph of your college campus using adjacency list /adjacency
matrix. Nodes should represent the various departments/institutes and links should
represent the distance between them.

Find minimum spanning tree

a) Using Kruskal’s algorithm.
b) Using Prim’s algorithm.
Theory:

Minimum Spanning Tree

The cost of the spanning tree is the sum of the weights of all the edges in the tree.
There can be many spanning trees. Minimum spanning tree is the spanning tree
where the cost is minimum among all the spanning trees. There also can be many
minimum spanning trees.

Fig. A Minimum Spanning Tree

Kruskal’s Algorithm

Kruskal’s Algorithm builds the spanning tree by adding edges one by one into a
growing spanning tree. Kruskal's algorithm follows greedy approach as in each
iteration it finds an edge which has least weight and add it to the growing spanning
tree.

Algorithm Steps:

 Sort the graph edges with respect to their weights.

 Start adding edges to the MST from the edge with the smallest weight until
the edge of the largest weight.
 Only add edges which doesn't form a cycle , edges which connect only
disconnected components.

Fig: Kruskal’s Algorithm

Prim’s algorithm.

Prim’s Algorithm also use Greedy approach to find the minimum spanning tree. In
Prim’s Algorithm we grow the spanning tree from a starting position. Unlike an
edge in Kruskal's, we add vertex to the growing spanning tree in Prim's.

Algorithm Steps:

 Maintain two disjoint sets of vertices. One containing vertices that are in the
growing spanning tree and other that are not in the growing spanning tree.
  Select the cheapest vertex that is connected to the growing spanning tree and
is not in the growing spanning tree and add it into the growing spanning tree.
This can be done using Priority Queues. Insert the vertices that are
connected to growing spanning tree, into the Priority Queue.
 Check for cycles. To do that, mark the nodes which have been already
selected and insert only those nodes in the Priority Queue that are not
marked.

Fig.Prim’s algorithm

Data Structures:

1. Define a structure for graph edges that includes source, destination, and
weight.

Algorithm:

1. Create a graph representation of your college campus using either an

adjacency list or an adjacency matrix. The nodes should represent various
departments/institutes, and the links should represent distances between
them.
2. Initialize a data structure to hold the edges of the minimum spanning tree
(MST), initially empty.

Kruskal's Algorithm
 o Create a list of all the edges in the graph.
o Sort the list of edges in ascending order by weight.
o Initialize an empty set (or forest) to keep track of connected
components.
o Iterate through the sorted edges:
 For each edge, check if adding it to the MST would create a
cycle in the current forest. If not, add it to the MST.
 Update the forest by merging the components of the nodes
connected by the edge.
 Continue this process until the MST contains V-1 edges, where
V is the number of vertices in the graph

Prim's Algorithm:

o Choose a starting node (department/institute) as the root of the MST.

o Initialize a set to keep track of visited nodes and a priority queue
(min-heap) to store the edges.
o Mark the starting node as visited.
o Add all edges connected to the starting node to the priority queue.
o While the MST has fewer than V-1 edges (V is the number of
vertices):
 Pop the edge with the minimum weight from the priority queue.
 If one of its endpoints is already visited and the other is not, add
it to the MST and mark the unvisited endpoint as visited.
 Add all edges connected to the newly visited node to the
priority queue.
 Repeat until the MST contains V-1 edges.
3. The MST generated by either Kruskal's or Prim's algorithm will be the
minimum spanning tree for your college campus graph, representing the
optimal way to connect departments/institutes while minimizing distances.

Conclusion: In this way, we have studied Representation of a graph using a)

Kruskal’s algorithm. b)Prim’s algorithm.
 Assignment 8

Title: Represent a graph of city using adjacency matrix /adjacency list. Nodes
should represent the various landmarks and links should represent the distance
between them. Find the shortest path using Dijkstra's algorithm from single source
to all destination.

Theory:

Dijkstra's Algorithm

It differs from the minimum spanning tree because the shortest distance between
two vertices might not include all the vertices of the graph.

How Dijkstra's Algorithm works

Dijkstra's Algorithm works on the basis that any subpath B -> D of the shortest
path A -> D between vertices A and D is also the shortest path between vertices B
and D.

Each subpath is the shortest path

Djikstra used this property in the opposite direction i.e we overestimate the
distance of each vertex from the starting vertex. Then we visit each node and its
neighbours to find the shortest subpath to those neighbours.

The algorithm uses a greedy approach in the sense that we find the next best
solution hoping that the end result is the best solution for the whole problem.
Example of Dijkstra's algorithm

It is easier to start with an example and then think about the algorithm.

Start with weighted graph

Choose a starting vertex and assign infinity path values to all other devices

Go to each vertex and update its path length

If the path length of the adjacent vertex is lesser than new path length, don't update
it

Avoid updating path lengths of already visited vertices

After each iteration, we pick the unvisited vertex with the least path length. So we
choose 5 before 7
Notice how the rightmost vertex has its path length updated twice

Repeat until all the vertices have been visited.

Conclusion: In this way, we have studied Representation of a graph of using

adjacency matrix and find the shortest path using Dijkstra's algorithm.
 Assignment 9
Title: Implement Heap sort to sort given set of values using max or min heap.

Theory:

What is a heap?

A heap is a complete binary tree, and the binary tree is a tree in which the node can
have the utmost two children. A complete binary tree is a binary tree in which all
the levels except the last level, i.e., leaf node, should be completely filled, and all
the nodes should be left-justified.

What is heap sort?

Heap sort is a popular and efficient sorting algorithm. The concept of heap sort is
to eliminate the elements one by one from the heap part of the list, and then insert
them into the sorted part of the list.

Heap sort is the in-place sorting algorithm.

Working of Heap sort Algorithm

In heap sort, basically, there are two phases involved in the sorting of elements. By
using the heap sort algorithm, they are as follows

 The first step includes the creation of a heap by adjusting the elements of the
array.
 After the creation of heap, now remove the root element of the heap
repeatedly by shifting it to the end of the array, and then store the heap
structure with the remaining elements.

Construct a heap from the given array and convert it into max heap.
After converting the given heap into max heap, the array elements are -

Next, we have to delete the root element (89) from the max heap. To delete this
node, we have to swap it with the last node, i.e. (11). After deleting the root
element, we again have to heapify it to convert it into max heap.

After swapping the array element 89 with 11, and converting the heap into max-
heap, the elements of array are
In the next step, again, we have to delete the root element (81) from the max heap.
To delete this node, we have to swap it with the last node, i.e. (54). After deleting
the root element, we again have to heapify it to convert it into max heap.

After swapping the array element 81 with 54 and converting the heap into max-
heap, the elements of array are -

In the next step, we have to delete the root element (76) from the max heap again.
To delete this node, we have to swap it with the last node, i.e. (9). After deleting
the root element, we again have to heapify it to convert it into max heap.
After swapping the array element 76 with 9 and converting the heap into max-
heap, the elements of array are -

In the next step, again we have to delete the root element (54) from the max heap.
To delete this node, we have to swap it with the last node, i.e. (14). After deleting
the root element, we again have to heapify it to convert it into max heap.

After swapping the array element 54 with 14 and converting the heap into max-
heap, the elements of array are -

In the next step, again we have to delete the root element (22) from the max heap.
To delete this node, we have to swap it with the last node, i.e. (11). After deleting
the root element, we again have to heapify it to convert it into max heap.

After swapping the array element 22 with 11 and converting the heap into max-
heap, the elements of array are
In the next step, again we have to delete the root element (14) from the max heap.
To delete this node, we have to swap it with the last node, i.e. (9). After deleting
the root element, we again have to heapify it to convert it into max heap.

After swapping the array element 14 with 9 and converting the heap into max-
heap, the elements of array are -

In the next step, again we have to delete the root element (11) from the max heap.
To delete this node, we have to swap it with the last node, i.e. (9). After deleting
the root element, we again have to heapify it to convert it into max heap.

After swapping the array element 11 with 9, the elements of array are -

Now, heap has only one element left. After deleting it, heap will be empty.
After completion of sorting, the array elements are -

Algorithm:

It can be implemented to sort values in ascending order using a max heap or in

descending order using a min heap.

Algorithm for Heap Sort:

1. Build a Heap:
o Convert the given array into a binary heap (max heap for ascending
order or min heap for descending order). This is done by heapifying
the array, starting from the last non-leaf node down to the root of the
heap. The heapifying process ensures that the max (or min) element is
at the root of the heap.
2. Sort the Array:

1. Swap the root element (which is the maximum in a max heap for
ascending order or the minimum in a min heap for descending
order) with the last element in the array.
2. Reduce the size of the heap by one (effectively excluding the last
element, which is now in its correct position).
3. Heapify the root of the heap to restore the heap property.
4. Repeat steps 2 and 3 until the heap is empty (size is 1).

Conclusion: In this way, we have studied implementation of Heap sort to sort

given set of values using max or min heap.
 Assignment 10

Title: Department maintains student’s database. The file contains roll number,
name, division and address. Write a program to create a sequential file to store and
maintain student data. It should allow the user to add, delete information of
student. Display information of particular student. If record of student does not
exist an appropriate message is displayed. If student record is found it should
display the student details.

Theory:

FILE Handling:

File handling in C++ is a mechanism to store the output of a program in a file and
help perform various operations on it. A ‘File Handling’ method to deal with the
storage of data.

File handling is further divided into sub-topics:

 Create a file
 Open a file
 Read from a file
 Write to a file
 Close a file

Algorithm for File Handling in C++:

1. Open a file in binary mode to work with student records. Create the file if it
doesn't exist.
2. Display a menu-driven interface for the user to perform various operations:
Add student information, Delete student information, and Display student
information.
3. For adding student information:
o Prompt the user to input the roll number, name, division, and address
for the new student.
o Create a Student structure to hold this information.
o Append the Student structure to the end of the file.
4. For displaying student information:
 o Prompt the user to enter the roll number of the student they want to
view.
o Search the file for a Student structure with the given roll number.
o If found, display the student's details.
o If not found, display an appropriate message indicating that the record
does not exist.
5. For deleting student information:
o Prompt the user to enter the roll number of the student they want to
delete.
o Create a temporary file to copy all records except the one to be
deleted.
o Read each Student structure from the original file:
 If the roll number matches the one to be deleted, skip it.
 Otherwise, write the Student structure to the temporary file.
o Close both files.
o Remove the original file and rename the temporary file to the original
file.
6. Provide options for the user to continue performing operations or exit the
program.

Conclusion: In this way, we have studied file handling to store and maintain the
database.