Exp.

Name: AVL Tree - Insertion, Date: 2025-08-

Page No: 1
[Link]: 1
Deletion and Search Operations 17

Aim:

ID: 24BQ1A05U9
Write a C program to implement an AVL Tree (self-balancing Binary Search Tree) with the
following functionalities:
• Insert(): Insert a node into the AVL Tree.
• Delete(): Delete a node from the AVL Tree.
• Search(): Search for a node in the AVL Tree.
• Inorder(): Perform an inorder traversal of the AVL Tree, displaying balance factors.
• Exit(): Terminate the program.

Menu Options:
[Link] [Link] [Link] [Link] Traversal [Link]

Option 1: Insert

2024-2028-CSE-E
• Prompt the user with:
Enter an element to be inserted : <value>
• Insert the value into the AVL Tree.
• If the element is already present, display:
Element <value> already exists.
• On successful insertion, print:
Successfully inserted.

Vasireddy Venkatadri Institute of Technology

Option 2: Delete
• Prompt the user with:
Enter an element to be deleted : <value>
• Delete the node with the specified value.
• If the element is not found, print:
Cannot find <value> in the AVL Tree.
• On successful deletion, print:
Deleted <value> from AVL Tree.

Option 3: Search
• Prompt the user with:
Enter an element to be searched : <value>
• If the value exists in the tree:
Element found in the AVL Tree.
• If not found:
Element not found in the AVL Tree.

Option 4: In-Order Traversal

• Perform in-order traversal of the AVL Tree.
• If the tree is empty:
AVL Tree is empty.
Elements of the AVL tree (In-order traversal): <val1>(<bf1>) <val2>(<bf2>) <val3>
(<bf3>) ...

Page No: 2
where <val> is the node value and <bf> is the node's balance factor.

Option 5: Exit
• Exit the program.

ID: 24BQ1A05U9
Note:
• The required print statements are already provided in the code. You need to
implement the remaining functionality accordingly.
• Ensure rotations (LL, RR, LR, RL) are applied to maintain AVL balance after
insertions and deletions.
• Follow the output format strictly to match visible test cases.
Source Code:

AVLTreeMain1.c

2024-2028-CSE-E
Vasireddy Venkatadri Institute of Technology
#include<stdio.h>

Page No: 3
#include<stdlib.h>
#include<conio.h>
#include "AVLTreeOperations.c"

int main() {

ID: 24BQ1A05U9
int x, op;
AVLNODE root = NULL;
while(1) {
printf("[Link] [Link] [Link] [Link] Traversal
[Link]\n");
printf("Enter your option : ");
scanf("%d", &op);
switch(op) {
case 1: printf("Enter an element to be inserted
: ");
scanf("%d", &x);

2024-2028-CSE-E
root = insertNodeInAVL(root,x);
break;
case 2: printf("Enter an element to be deleted
: ");
scanf("%d", &x);
root = deleteNodeInAVL(root,x);
break;

Vasireddy Venkatadri Institute of Technology

case 3:
printf("Enter an element to be
searched : ");
scanf("%d", &x);
if( searchNodeInAVL(root,x) ==
NULL)
printf("Element not
found in the AVL tree.\n");
else
printf("Element found
in the AVL tree.\n");
break;
case 4:
if(root == NULL) {
printf("AVL Tree is
empty.\n");
}
else {
printf("Elements of the
AVL tree (In-order traversal): ");
inorderInAVL(root);
printf("\n");
 }
}
}

AVLTreeOperations.c
case 5: exit(0);
}
break;

Vasireddy Venkatadri Institute of Technology 2024-2028-CSE-E ID: 24BQ1A05U9 Page No: 4

struct node {

Page No: 5
int data;
struct node *left,*right;
int ht;
};
typedef struct node * AVLNODE;

ID: 24BQ1A05U9
AVLNODE createNodeInAVL(int item) {
AVLNODE temp = (AVLNODE)malloc(sizeof(struct node));
temp->data = item;
temp->left = temp->right = NULL;
return temp;
}
int height(AVLNODE root) {
int lh,rh;
if(root==NULL)
return(0);
if(root->left==NULL)

2024-2028-CSE-E
lh=0;
else
lh=1+root->left->ht;
if(root->right==NULL)
rh=0;
else
rh=1+root->right->ht;

Vasireddy Venkatadri Institute of Technology

if(lh>rh)
return(lh);
return(rh);
}

AVLNODE rotateRight(AVLNODE x) {
AVLNODE y;
y=x->left;
x->left=y->right;
y->right=x;
x->ht=height(x);
y->ht=height(y);
return(y);
}

AVLNODE rotateLeft(AVLNODE x) {
AVLNODE y;
y=x->right;
x->right=y->left;
y->left=x;
x->ht=height(x);
y->ht=height(y);
 return(y);

Page No: 6
}
AVLNODE LL(AVLNODE root) {
root=rotateLeft(root);
return(root);
}

ID: 24BQ1A05U9
AVLNODE RR(AVLNODE root) {
root=rotateRight(root);
return(root);
}
AVLNODE LR(AVLNODE root) {
root->left=rotateLeft(root->left);
root=rotateRight(root);
return(root);
}
AVLNODE RL(AVLNODE root) {
root->right=rotateRight(root->right);

2024-2028-CSE-E
root=rotateLeft(root);
return(root);
}
int balancefactor(AVLNODE root) {
int lh,rh;
if(root==NULL)
return(0);

Vasireddy Venkatadri Institute of Technology

if(root->left==NULL)
lh=0;
else
lh=1+root->left->ht;
if(root->right==NULL)
rh=0;
else
rh=1+root->right->ht;
return(lh-rh);
}

void inorderInAVL(AVLNODE root) {

if (root != NULL) {
inorderInAVL(root->left);
printf("%d(%d) ", root->data, balancefactor(root));
inorderInAVL(root->right);
}
}

AVLNODE insertNodeInAVL(AVLNODE root,int x) {

if(root==NULL){
root = createNodeInAVL(x);
 printf("Successfully inserted.\n");

Page No: 7
}
else if(x>root->data){
root->right = insertNodeInAVL(root->right,x);
if(balancefactor(root)==-2){
if(x>root->right->data)

ID: 24BQ1A05U9
root=LL(root);
else
root=LR(root);
}
}
else if(x<root->data){
root->left=insertNodeInAVL(root->left,x);
if(balancefactor(root)==2){
if(x<root->left->data)
root=RR(root);
else

2024-2028-CSE-E
root=LR(root);
}
}
else{
printf("Element %d already exists.\n",x);
}
root->ht=height(root);

Vasireddy Venkatadri Institute of Technology

return(root);
}

AVLNODE deleteNodeInAVL(AVLNODE root,int x) {

AVLNODE temp = NULL;
if(root==NULL){
printf("Cannot find %d in the AVL Tree.\n",x);
return NULL;
}
else if(x>root->data){
root->right=deleteNodeInAVL(root->right,x);
if(balancefactor(root)==2){
if(balancefactor(root->left)>=0){
root=LL(root);
}
else{
root = LR(root);
}
}
}
else if(x<root->data){
root->left=deleteNodeInAVL(root->left,x);
 if(balancefactor(root)==-2){

Page No: 8
if(balancefactor(root->right)<=0)
root=RR(root);
else
root=RL(root);
}

ID: 24BQ1A05U9
}
else{
if(root->right!=NULL){
temp = root->right;
while(temp->left!=NULL){
temp=temp->left;
}
root->data=temp->data;
temp->data=x;
root->right=deleteNodeInAVL(root-
>right,temp->data);

2024-2028-CSE-E
if(balancefactor(root)==2){
if(balancefactor(root-
>left)>=0)
root=LL(root);
else
root=LR(root);
}

Vasireddy Venkatadri Institute of Technology

}
else{
printf("Deleted %d from AVL Tree.\n",x);
return root->left;
}
}
root->ht=height(root);
return root;
}
AVLNODE searchNodeInAVL(AVLNODE root, int ele) {
if(root==NULL || root->data==ele)
return root;
if(root->data<ele)
return searchNodeInAVL(root->right,ele);
return searchNodeInAVL(root->left,ele);
}

Execution Results - All test cases have succeeded!

 Test Case - 1

Page No: 9
User Output
[Link] [Link] [Link] [Link] Traversal [Link]
Enter your option :

ID: 24BQ1A05U9
1
Enter an element to be inserted :
42
Successfully inserted.
[Link] [Link] [Link] [Link] Traversal [Link]
Enter your option :
1
Enter an element to be inserted :
23
Successfully inserted.

2024-2028-CSE-E
[Link] [Link] [Link] [Link] Traversal [Link]
Enter your option :
1
Enter an element to be inserted :
45
Successfully inserted.

Vasireddy Venkatadri Institute of Technology

[Link] [Link] [Link] [Link] Traversal [Link]
Enter your option :
4
Elements of the AVL tree (In-order traversal): 23(0) 42(0) 45(0)
[Link] [Link] [Link] [Link] Traversal [Link]
Enter your option :
2
Enter an element to be deleted :
42
Deleted 42 from AVL Tree.
[Link] [Link] [Link] [Link] Traversal [Link]
Enter your option :
4
Elements of the AVL tree (In-order traversal): 23(0) 45(1)
[Link] [Link] [Link] [Link] Traversal [Link]
Enter your option :
3
Enter an element to be searched :
42
[Link] [Link] [Link] [Link] Traversal [Link]
Enter your option :

Page No: 10
3
Enter an element to be searched :
45
Element found in the AVL tree.

ID: 24BQ1A05U9
[Link] [Link] [Link] [Link] Traversal [Link]
Enter your option :
1
Enter an element to be inserted :
42
Successfully inserted.
[Link] [Link] [Link] [Link] Traversal [Link]
Enter your option :
4

2024-2028-CSE-E
Elements of the AVL tree (In-order traversal): 23(0) 42(0) 45(0)
[Link] [Link] [Link] [Link] Traversal [Link]
Enter your option :
5

Test Case - 2

Vasireddy Venkatadri Institute of Technology

User Output
[Link] [Link] [Link] [Link] Traversal [Link]
Enter your option :
2
Enter an element to be deleted :
15
Cannot find 15 in the AVL Tree.
[Link] [Link] [Link] [Link] Traversal [Link]
Enter your option :
3
Enter an element to be searched :
14
Element not found in the AVL tree.
[Link] [Link] [Link] [Link] Traversal [Link]
Enter your option :
4
AVL Tree is empty.
[Link] [Link] [Link] [Link] Traversal [Link]
1
Enter an element to be inserted :

Page No: 11
19
Successfully inserted.
[Link] [Link] [Link] [Link] Traversal [Link]
Enter your option :

ID: 24BQ1A05U9
1
Enter an element to be inserted :
17
Successfully inserted.
[Link] [Link] [Link] [Link] Traversal [Link]
Enter your option :
1
Enter an element to be inserted :
19

2024-2028-CSE-E
Element 19 already exists.
[Link] [Link] [Link] [Link] Traversal [Link]
Enter your option :
1
Enter an element to be inserted :
18

Vasireddy Venkatadri Institute of Technology

Successfully inserted.
[Link] [Link] [Link] [Link] Traversal [Link]
Enter your option :
3
Enter an element to be searched :
3
Element not found in the AVL tree.
[Link] [Link] [Link] [Link] Traversal [Link]
Enter your option :
18
[Link] [Link] [Link] [Link] Traversal [Link]
Enter your option :
3
Enter an element to be searched :
18
Element found in the AVL tree.
[Link] [Link] [Link] [Link] Traversal [Link]
Enter your option :
4
 5
Enter your option :
[Link] [Link] [Link] [Link] Traversal [Link]

Vasireddy Venkatadri Institute of Technology 2024-2028-CSE-E ID: 24BQ1A05U9 Page No: 12

 Date: 2025-09-
[Link]: 2 Exp. Name: Min Heap Operations

Page No: 13
01

Aim:
Write a C program that creates a min heap of integers, display the values and perform

ID: 24BQ1A05U9
deletion operation.

Input Format:
• An integer n – the number of elements to be inserted into the Min Heap.
• n integers separated by space – the elements to be inserted into the Min Heap.

Output Format:
• Print the string "Min Heap:" followed by the elements of the Min Heap after all
insertions in a single line separated by spaces.
• Print the string "Extracting elements from the min heap:" followed by lines for each
extracted element until the heap is empty.

2024-2028-CSE-E
• Each extraction should print: "Extracted: x", where x is the smallest element
extracted from the Min Heap in order, each on a new line.
Source Code:

minHeapOfIntegers.c

Vasireddy Venkatadri Institute of Technology

#include <stdio.h>

Page No: 14
#define MAX_HEAP_SIZE 100

// Function to swap two integers

void swap(int *x, int *y) {

ID: 24BQ1A05U9
int temp = *x;
*x = *y;
*y = temp;
}

// Function to perform min heapify on a subtree rooted at index i

void minHeapify(int arr[], int n, int i) {
int smallest = i;
int left = 2*i+1;
int right = 2*i+2;
if(left < n && arr[left] <arr[smallest])

2024-2028-CSE-E
smallest = left;
if(right< n && arr[right] <arr[smallest])
smallest = right;
if(smallest!=i){
swap(&arr[i],&arr[smallest]);
minHeapify(arr,n,smallest);
}

Vasireddy Venkatadri Institute of Technology

}
// Function to build a min heap
void buildMinHeap(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
minHeapify(arr, n, i);
}

// Function to display the min heap

void displayHeap(int arr[], int n) {
printf("Min Heap: ");
for(int i=0;i<n;i++)
printf("%d ",arr[i]);
printf("\n");
}
// Function to perform deletion (extract the minimum element) from the
min heap
int extractMin(int arr[], int *n) {
if(*n<=0)
return -1;
if(*n==1){
(*n)--;
return arr[0];
 }

Page No: 15
int root = arr[0];
arr[0] = arr[*n-1];
(*n)--;
minHeapify(arr,*n,0);
return root;

ID: 24BQ1A05U9
}

int main() {
int arr[MAX_HEAP_SIZE];
int n;

printf("Enter no of elements: ");

scanf("%d", &n);

printf("Enter elements: ");

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

2024-2028-CSE-E
scanf("%d", &arr[i]);

buildMinHeap(arr, n);
displayHeap(arr, n);

printf("Extracting elements from the min heap:\n");

while (n > 0) {

Vasireddy Venkatadri Institute of Technology

int minElement = extractMin(arr, &n);
if (minElement == -1)
printf("Heap is empty.\n");
else
printf("Extracted: %d\n", minElement);
}

return 0;
}

Execution Results - All test cases have succeeded!

Test Case - 1

User Output
Enter no of elements:
5
Enter elements:
12648
Min Heap: 1 2 6 4 8
Extracting elements from the min heap:

Page No: 16
Extracted: 1
Extracted: 2
Extracted: 4
Extracted: 6

ID: 24BQ1A05U9
Extracted: 8

Test Case - 2

User Output
Enter no of elements:
6
Enter elements:
251684

2024-2028-CSE-E
Min Heap: 1 5 2 6 8 4
Extracting elements from the min heap:
Extracted: 1
Extracted: 2
Extracted: 4
Extracted: 5

Vasireddy Venkatadri Institute of Technology

Extracted: 6
Extracted: 8
 Date: 2025-09-
[Link]: 3 Exp. Name: Max Heap of Integers

Page No: 17
01

Aim:
Write a C program that creates a max heap of integers, display the values and perform

ID: 24BQ1A05U9
deletion operations.

Input Format:
• An integer n — the number of elements to insert into the Max Heap.
• n integers separated by spaces — the elements to insert into the Max Heap.

Output Format:
• Print "Max Heap:" followed by the elements of the Max Heap after all insertions
which are space seperated.
• Print "Extracting elements from max heap:"
• Next n Lines, for each extraction, print a line "Extracted: x" where x is the element

2024-2028-CSE-E
extracted one per line, until the heap is empty. The extracted elements will be in
descending order.
Source Code:

maxHeapOfIntegers.c

Vasireddy Venkatadri Institute of Technology

#include <stdio.h>

Page No: 18
#define MAX_HEAP_SIZE 100

// Function to swap two integers

void swap(int *x, int *y) {

ID: 24BQ1A05U9
int temp = *x;
*x = *y;
*y = temp;
}

// Function to perform max heapify on a subtree rooted at index i

void maxHeapify(int arr[], int n, int i) {
int largest = i;
int left = 2*i+1;
int right = 2*i+2;
if(left<n && arr[left]>arr[largest])

2024-2028-CSE-E
largest = left;
if(right<n && arr[right]>arr[largest])
largest = right;
if(largest!=i){
swap(&arr[i],&arr[largest]);
maxHeapify(arr,n,largest);
}

Vasireddy Venkatadri Institute of Technology

}
// Function to build a max heap
void buildMaxHeap(int arr[], int n) {
for(int i = n/2-1;i>=0;i--)
maxHeapify(arr,n,i);
}

// Function to display the max heap

void displayHeap(int arr[], int n) {
printf("Max Heap: ");
for(int i=0;i<n;i++)
printf("%d ",arr[i]);
printf("\n");
}
// Function to perform deletion (extract the maximum element) from the
max heap
int extractMax(int arr[], int *n) {
if(*n <= 0)
return -1;
if(*n==1){
(*n)--;
return arr[0];
 }

Page No: 19
int root = arr[0];
arr[0]=arr[*n-1];
(*n)--;
maxHeapify(arr,*n,0);
return root;

ID: 24BQ1A05U9
}
int main() {
int arr[MAX_HEAP_SIZE];
int n;

printf("Enter no of elements: ");

scanf("%d", &n);

printf("elements: ");
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);

2024-2028-CSE-E
buildMaxHeap(arr, n);
displayHeap(arr, n);

printf("Extracting elements from max heap:\n");

while (n > 0) {
int maxElement = extractMax(arr, &n);

Vasireddy Venkatadri Institute of Technology

if (maxElement == -1)
printf("Heap is empty.\n");
else
printf("Extracted: %d\n", maxElement);
}

return 0;
}

Execution Results - All test cases have succeeded!

Test Case - 1

User Output
Enter no of elements:
5
elements:
64582
Extracting elements from max heap:
Extracted: 8

Page No: 20
Extracted: 6
Extracted: 5
Extracted: 4
Extracted: 2

ID: 24BQ1A05U9
2024-2028-CSE-E
Vasireddy Venkatadri Institute of Technology
 Exp. Name: Graph Traversal - Breadth Date: 2025-09-
[Link]: 4

Page No: 21
First Search 01

Aim:
You are given a string adjacencyMatrix of N [Link] 0's and 1's separated by a space

ID: 24BQ1A05U9
character which are the elements of the adjacency matrix built from an
directed/undirected unweighted graph. Your job is to print the elements of the graph
using Breadth-First Search(BFS).

An adjacency matrix of an unweighted graph is a way of representing the graph that

contains a series of 0's and 1's. The first row contains N elements, each representing the
connection between two nodes. If the connection exists, it will be represented by 1(one)
and 0(zero) represents no connection between two nodes. In total, there will be N * N
elements(0's and 1's) in the string.

Complete the function BreadthFirstSearch with the parameters:

2024-2028-CSE-E
no_of_vertices: [Link] vertices in the graph
adjacencyMatrix: a string of integer elements of the adjacency matrix of the graph.
Every character '0' or '1' is separated by a space.

Functions will return :

a string that contains the BFS result of the graph separated by a space character.

Vasireddy Venkatadri Institute of Technology

Constraints:
• 0 < no_of_vertices <= 100

Note:
• The elements of the matrix will always be N * N
• Always start the BFS from the first element
• Take the nodes name as 0,1,2,3,....,N always

Example:
 Page No: 22
Graph : adjacency

ID: 24BQ1A05U9
matrix of the graph:

the string containing the elements of the matrix is:

2024-2028-CSE-E
adjacencyMatrix: 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0

Sample Test Case:

Input:
4
0111101111011110

Vasireddy Venkatadri Institute of Technology

Output:
0123

Explanation:
Here, 0,1,2,3 are the nodes names. It means the BFS is started at 0(zero)
• Visited node 1 from the node 0
• Visited node 2 from the node 1
• Visited node 3 from the node 2 lastly.
Instruction: To complete the required function please follow the function rules given
below, And to run your custom test cases on the terminal please strictly follow the input
and output layout mentioned in the visible sample test case.
Source Code:

CTC15020.c
#include <stdio.h>

Page No: 23
#include <stdlib.h>
#include <string.h>

char * BreadthFirstSearch(int no_of_vertices, char *adjacencyMatrix) {

// Write code here

ID: 24BQ1A05U9
int graph[no_of_vertices][no_of_vertices];
char *token;
int index = 0;
token = strtok(adjacencyMatrix," ");
while(token!=NULL){
graph[index/no_of_vertices][index%
no_of_vertices]=atoi(token);
token=strtok(NULL," ");
index++;
}
int visited[no_of_vertices];

2024-2028-CSE-E
memset(visited,0,sizeof(visited));
int queue[no_of_vertices];
int front = 0,rear =0;
char *result = (char*)malloc(no_of_vertices*4);
result[0]='\0';
queue[rear++]=0;
visited[0]=1;

Vasireddy Venkatadri Institute of Technology

while(front<rear){
int current=queue[front++];
char buffer[4];
sprintf(buffer,"%d",current);
strcat(result,buffer);
for(int i=0;i<no_of_vertices;i++){
if(graph[current][i]==1 &&! visited[i]){
queue[rear++]=i;
visited[i] = 1;
}
}
if(front<rear){
strcat(result," ");
}
}
if(strlen(result)>0)
strcat(result," ");
strcat(result,"\n");
return result;
}

int main(int argc, char *argv[]) {

 int no_of_vertices = atoi(argv[1]);

Page No: 24
char *adjacencyMatrix = argv[2];
printf("%s\n", BreadthFirstSearch(no_of_vertices,
adjacencyMatrix));
return 0;
}

ID: 24BQ1A05U9
Execution Results - All test cases have succeeded!
Test Case - 1

User Output
0 1 2 3

2024-2028-CSE-E
Test Case - 2

User Output
0 1 4 2 3

Vasireddy Venkatadri Institute of Technology

 Exp. Name: Graph Traversal - Depth Date: 2025-10-
[Link]: 5

Page No: 25
First Search 06

Aim:
You are given a string adjacencyMatrix of N [Link] 0's and 1's separated by a space

ID: 24BQ1A05U9
character which are the elements of the adjacency matrix built from an unweighted
graph. Your job is to print the elements of the graph using Depth-First Search(DFS).

An adjacency matrix of an unweighted and undirected graph is a way of representing the

graph that contains a series of 0's and 1's. The first row contains N elements, each
representing the connection between two nodes. If the connection exists, it will be
represented by 1(one) and 0(zero) represents no connection between two nodes. In total,
there will be N * N elements(0's and 1's) in the string.

Complete the function depthFirstSearch with the parameters:

no_of_vertices: [Link] vertices in the graph

2024-2028-CSE-E
adjacencyMatrix: a string of integer elements of the adjacency matrix of the graph

Functions will return :

a string that contains the DFS result of the graph separated by a space character.

Constraints:
• 0 < no_of_vertices <= 100

Vasireddy Venkatadri Institute of Technology

Note:
• The elements of the matrix will always be N * N
• Always start the DFS from the first element
• Take the nodes names as 0,1,2,3,....,N always

Example:
 Page No: 26
Graph : adjacency

ID: 24BQ1A05U9
matrix of the graph:

the string containing the elements of the matrix is:

2024-2028-CSE-E
adjacencyMatrix: 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0

Sample Test Case:

Input:
4
0111101111011110

Vasireddy Venkatadri Institute of Technology

Output:
0123

Explanation:
Here, 0,1,2,3 are the nodes names and the DFS is started at 0(zero)
• Visited node 1 from the node 0
• Visited node 2 from the node 1
• Visited node 3 from the node 2 lastly.

Instruction: To complete the required function please follow the function rules given
below, And to run your custom test cases on the terminal please strictly follow the input
and output layout mentioned in the visible sample test case.
Source Code:

CTC15028.c
#include <stdio.h>

Page No: 27
#include <stdlib.h>
#include <string.h>
#define MAX_VERTICES 100
void dfs(int vertex,int adj[MAX_VERTICES][MAX_VERTICES],int
visited[MAX_VERTICES],int no_of_vertices,char *result){

ID: 24BQ1A05U9
visited[vertex]=1;
char buffer[10];
sprintf(buffer, "%d ",vertex);
strcat(result, buffer);
for(int i=0;i<no_of_vertices;i++)
{
if((adj[vertex][i]==1)&& !visited[i])

dfs(i,adj,visited,no_of_vertices,result);
}
}

2024-2028-CSE-E
char * depthFirstSearch(int no_of_vertices, char *adjacencyMatrix) {
int adj[MAX_VERTICES][MAX_VERTICES];
int visited[MAX_VERTICES]={0};
char *result = (char *)malloc(500 * sizeof(char));
result[0] = '\0';
char *token = strtok(adjacencyMatrix, " ");
for(int i=0;i<no_of_vertices;i++)

Vasireddy Venkatadri Institute of Technology

{
for(int j=0;j<no_of_vertices;j++)
{
adj[i][j] = atoi(token);
token = strtok(NULL, " ");
}
}
dfs(0,adj,visited,no_of_vertices,result);
return result;

int main(int argc, char *argv[]) {

int no_of_vertices = atoi(argv[1]);
char *adjacencyMatrix = argv[2];
printf("%s\n", depthFirstSearch(no_of_vertices,
adjacencyMatrix));
return 0;
}
 Execution Results - All test cases have succeeded!

Page No: 28
Test Case - 1

User Output
0 1 2 3

ID: 24BQ1A05U9
Test Case - 2

User Output
0 1 2 3 4

2024-2028-CSE-E
Vasireddy Venkatadri Institute of Technology
 Date: 2025-10-
[Link]: 6 Exp. Name: Breadth First Search (BFS)

Page No: 29
06

Aim:
Write a program to implement Breadth First Search (BFS) graph traversal methods.

ID: 24BQ1A05U9
Input Format:
• The first line contains an integer N , the number of vertices in the graph.
• The second line contains an integer E, the number of edges in the graph.
• The next E pairs of lines contain two integers each:
• The first line of each pair contains an integer s representing the source
vertex.
• The second line of each pair contains an integer d representing the
destination vertex.
• The last line contains an integer v, which is the starting vertex for the BFS traversal.

2024-2028-CSE-E
Output Format:
• The program will output the vertices of the graph, each on a new line, in the order
they are visited by the BFS traversal, starting from the vertex v.

Note:
• Driver code is already provided to you in the editor, your task is to fill in the
required code.

Vasireddy Venkatadri Institute of Technology

• Refer to visible test cases for better understanding.
Source Code:

GraphsBFS.c
#include <stdio.h>

Page No: 30
#include <stdlib.h>
#define MAX 99

struct node {
int vertex;

ID: 24BQ1A05U9
struct node* next;
};
typedef struct node* GNODE;

GNODE graph[20];
int visited[20];
int queue[MAX], front = -1, rear = -1;
int n;

void insertQueue(int vertex) {

if (rear == MAX - 1)

2024-2028-CSE-E
printf("Queue Overflow.\n");
else {
if (front == -1)
front = 0;
rear++;
queue[rear] = vertex;
}

Vasireddy Venkatadri Institute of Technology

}

int isEmptyQueue() {
return (front == -1 || front > rear);
}

int deleteQueue() {
if (isEmptyQueue()) {
printf("Queue Underflow\n");
exit(1);
}
return queue[front++];
}

void BFS(int v) {
int s;
insertQueue(v);
while(!isEmptyQueue())
{
v= deleteQueue();
printf("\n%d",v);
GNODE g = graph[v];
 for(;g!=NULL;g= g->next){

Page No: 31
s=g->vertex;
if(visited[s]==0){
insertQueue(s);
visited[s]=1;
}

ID: 24BQ1A05U9
}
}
}

void main() {
int N, E, s, d, i, v;
GNODE p, q;

printf("Enter the number of vertices: ");

scanf("%d", &N);
n = N;

2024-2028-CSE-E
for (i = 0; i < N; i++) {
graph[i] = NULL;
visited[i] = 0;
}

printf("Enter the number of edges: ");

Vasireddy Venkatadri Institute of Technology

scanf("%d", &E);
for (i = 1; i <= E; i++) {
printf("Enter source: ");
scanf("%d", &s);
printf("Enter destination: ");
scanf("%d", &d);

q = (GNODE)malloc(sizeof(struct node));
q->vertex = d;
q->next = NULL;

if (graph[s] == NULL) {
graph[s] = q;
} else {
p = graph[s];
while (p->next != NULL)
p = p->next;
p->next = q;
}
}

printf("Enter Start Vertex for BFS: ");

 scanf("%d", &v);

Page No: 32
printf("BFS of graph: ");
BFS(v);
printf("\n");
}

ID: 24BQ1A05U9
Execution Results - All test cases have succeeded!
Test Case - 1

User Output
Enter the number of vertices:
5
Enter the number of edges:

2024-2028-CSE-E
5
Enter source:
1
Enter destination:
2
Enter source:

Vasireddy Venkatadri Institute of Technology

1
Enter destination:
4
Enter source:
4
Enter destination:
2
Enter source:
2
Enter destination:
3
Enter source:
4
Enter destination:
5
Enter Start Vertex for BFS:
1
BFS of graph:
2
4

Page No: 33
3
5

Test Case - 2

ID: 24BQ1A05U9
User Output
Enter the number of vertices:
4
Enter the number of edges:
3
Enter source:
1
Enter destination:

2024-2028-CSE-E
2
Enter source:
2
Enter destination:
3
Enter source:

Vasireddy Venkatadri Institute of Technology

3
Enter destination:
4
Enter Start Vertex for BFS:
2
BFS of graph:
2
3
4
 Date: 2025-10-
[Link]: 7 Exp. Name: Depth First Search (DFS)

Page No: 34
06

Aim:
Write a program to implement Depth First Search (DFS) graph traversal methods.

ID: 24BQ1A05U9
Input Format:
• The first line of input contains an integer N , the number of vertices in the graph.
• The second line contains an integer E, the number of edges in the graph.
• The next E pairs of lines contain two integers each:
• The first line of each pair contains an integer s representing the source
vertex.
• The second line of each pair contains an integer d representing the
destination vertex.
• The last line contains an integer v, the starting vertex for the DFS traversal.

2024-2028-CSE-E
Output Format:
• The output should display the order of vertices visited during the DFS traversal
starting from the specified vertex v each in a new line.

Note:
• Driver code is already provided to you in the editor, your task is to fill in the
required code.

Vasireddy Venkatadri Institute of Technology

• Refer to visible test cases for better understanding.
Source Code:

GraphsDFS.c
#include<stdio.h>

Page No: 35
#include<stdlib.h>

// Define structure for adjacency list node

struct node {
int vertex;

ID: 24BQ1A05U9
struct node* next;
};

typedef struct node* GNODE;

GNODE graph[20]; // Adjacency list for the graph

int visited[20]; // Visited array to track visited vertices
int n; // Number of vertices

// DFS function
void DFS(int i) {

2024-2028-CSE-E
GNODE s = graph[i];
visited[i] = i;
printf("\n%d",i);
while(s!=NULL)
{
int vertex = s->vertex;
if(!visited[vertex])

Vasireddy Venkatadri Institute of Technology

{
DFS(vertex);
}
s = s->next;
}
}

// Main function
void main() {
int N, E, i, s, d, v;
GNODE q;

// Input number of vertices

printf("Enter the number of vertices: ");
scanf("%d", &N);
n = N;

// Initialize graph
for (i = 0; i < N; i++) {
graph[i] = NULL;
}
 // Input number of edges

Page No: 36
printf("Enter the number of edges: ");
scanf("%d", &E);

// Input edges
for (i = 1; i <= E; i++) {

ID: 24BQ1A05U9
printf("Enter source: ");
scanf("%d", &s);
printf("Enter destination: ");
scanf("%d", &d);

// Create new node for destination

q = (GNODE)malloc(sizeof(struct node));
q->vertex = d;
q->next = NULL;

// Add to adjacency list

2024-2028-CSE-E
if (graph[s] == NULL)
graph[s] = q;
else {
GNODE p = graph[s];
while (p->next != NULL)
p = p->next;
p->next = q;

Vasireddy Venkatadri Institute of Technology

}
}

// Initialize visited array

for (i = 0; i < n; i++)
visited[i] = 0;

// Input start vertex

printf("Enter Start Vertex for DFS: ");
scanf("%d", &v);

printf("DFS of graph: ");

DFS(v);
printf("\n");
}

Execution Results - All test cases have succeeded!

Test Case - 1
User Output

Page No: 37
Enter the number of vertices:
6
Enter the number of edges:
7

ID: 24BQ1A05U9
Enter source:
1
Enter destination:
2
Enter source:
1
Enter destination:
4
Enter source:
4

2024-2028-CSE-E
Enter destination:
2
Enter source:
2
Enter destination:
3

Vasireddy Venkatadri Institute of Technology

Enter source:
4
Enter destination:
5
Enter source:
4
Enter destination:
3
Enter source:
3
Enter destination:
6
Enter Start Vertex for DFS:
1
DFS of graph:
1
2
3
4
5

Page No: 38
Test Case - 2

User Output

ID: 24BQ1A05U9
Enter the number of vertices:
5
Enter the number of edges:
5
Enter source:
1
Enter destination:
2
Enter source:

2024-2028-CSE-E
1
Enter destination:
4
Enter source:
4
Enter destination:

Vasireddy Venkatadri Institute of Technology

2
Enter source:
2
Enter destination:
3
Enter source:
4
Enter destination:
5
Enter Start Vertex for DFS:
1
DFS of graph:
1
2
3
4
5
 Test Case - 3

Page No: 39
User Output
Enter the number of vertices:
4
Enter the number of edges:

ID: 24BQ1A05U9
4
Enter source:
1
Enter destination:
1
Enter source:
1
Enter destination:
3

2024-2028-CSE-E
Enter source:
2
Enter destination:
2
Enter source:
4

Vasireddy Venkatadri Institute of Technology

Enter destination:
3
Enter Start Vertex for DFS:
1
DFS of graph:
1
3
 Exp. Name: Bi-Connected Components Date: 2025-10-
[Link]: 8

Page No: 40
in Graph 15

Aim:
Write a C program to find the number of biconnected components (BCCs) in a given

ID: 24BQ1A05U9
undirected graph.

Input Format:
• The first line contains a single integer, V , the number of vertices in the graph.
• The second line contains a single integer, E, the number of edges.
• Each of the next E lines contains two space-separated integers u and v,
representing an edge between vertex u and vertex v.

Output Format:
• Print a single integer: the number of biconnected components in the graph.

2024-2028-CSE-E
Constraints:
• 1 ≤ V ≤ 1000
• 0 ≤ E ≤ V ∗ (V − 1)/2

• 0 ≤ u, v < V
Source Code:

biConnected.c

Vasireddy Venkatadri Institute of Technology

#include <stdio.h>

Page No: 41
#include <stdlib.h>
#include <limits.h>
typedef struct {
int V;
int** adj;

ID: 24BQ1A05U9
} Graph;

typedef struct {
int x, y;
} Edge;

typedef struct {
Edge* edges;
int size;
int capacity;
} BCCStack;

2024-2028-CSE-E
// Function to create a new graph
Graph* createGraph(int vertices) {
Graph* g = (Graph*)malloc(sizeof(Graph));
g->V = vertices;
g->adj = (int**)malloc(vertices * sizeof(int*));
for (int i = 0; i < vertices; i++) {

Vasireddy Venkatadri Institute of Technology

g->adj[i] = (int*)malloc(vertices * sizeof(int));
for (int j = 0; j < vertices; j++) {
g->adj[i][j] = 0;
}
}
return g;
}

// Function to add an edge to the graph

void addEdge(Graph* g, int u, int v) {
g->adj[u][v] = 1;
g->adj[v][u] = 1;
}

// Function to create a new BCC stack

BCCStack* createBCCStack(int capacity) {
BCCStack* stack = (BCCStack*)malloc(sizeof(BCCStack));
stack->edges = (Edge*)malloc(capacity * sizeof(Edge));
stack->size = 0;
stack->capacity = capacity;
return stack;
}
 Page No: 42
// Function to push an edge to the BCC stack
void pushBCCStack(BCCStack* stack, int u, int v) {
if (stack->size == stack->capacity) {
stack->capacity *= 2;
stack->edges = (Edge*)realloc(stack->edges, stack->capacity *

ID: 24BQ1A05U9
sizeof(Edge));
}
stack->edges[stack->size].x = u;
stack->edges[stack->size].y = v;
stack->size++;
}

// Function to pop an edge from the BCC stack

Edge popBCCStack(BCCStack* stack) {
return stack->edges[--stack->size];
}

2024-2028-CSE-E
void dfs(Graph *g,int u,int visited[],int disc[],int low[],int
parent[],BCCStack* stack,int* time,int* biConnectedCount){
visited[u]=1;
disc[u]=low[u]=++(*time);
int children=0;
for(int v=0;v<g->V;v++){
if(g->adj[u][v]){

Vasireddy Venkatadri Institute of Technology

if(!visited[v]){
children++;
parent[v]=u;
pushBCCStack(stack,u,v);
dfs(g,v,visited,disc,low,parent,stack,time,biConnectedCount);
low[u]=(low[u]<low[v]?low[u]:low[v]);
if((parent[u]==-1 && children>1)||
(parent[u]!=-1 && low[v]>=disc[u])){
(*biConnectedCount)++;
Edge edge;
do{
edge =
popBCCStack(stack);
}while(!
(edge.x==u&&edge.y==v));
}
}else if(v!=parent[u]&&disc[v]<disc[u]){
low[u]=(low[u]<disc[v])?low[u]:disc[v];
pushBCCStack(stack,u,v);
}
}
}
}

Page No: 43
// Function to find bi-connected components
void findBiConnectedComponents(Graph* g) {
int* disc = (int*)malloc(g->V*sizeof(int));
int* low=(int*)malloc(g->V*sizeof(int));

ID: 24BQ1A05U9
int* parent = (int*)malloc(g->V*sizeof(int));
int* visited=(int*)calloc(g->V,sizeof(int));
BCCStack* stack=createBCCStack(10);
int time=0;
int biConnectedCount=0;
for(int i=0;i<g->V;i++){
parent[i]=-1;
if(!visited[i]){

dfs(g,i,visited,disc,low,parent,stack,&time,&biConnectedCount);
if(stack->size>0){

2024-2028-CSE-E
biConnectedCount++;
while(stack->size>0){
popBCCStack(stack);
}
}
}
}

Vasireddy Venkatadri Institute of Technology

printf("%d\n",biConnectedCount);
free(disc);
free(low);
free(parent);
free(visited);
free(stack->edges);
free(stack);
}
int main() {
int vertices, edges;
//printf("Enter number of vertices: ");
scanf("%d", &vertices);
//printf("Enter number of edges: ");
scanf("%d", &edges);

Graph* g = createGraph(vertices);
//printf("Enter edges (u v):\n");
for (int i = 0; i < edges; i++) {
int u, v;
scanf("%d %d", &u, &v);
addEdge(g, u, v);
}
 Page No: 44
findBiConnectedComponents(g);

// Free the graph memory

for (int i = 0; i < vertices; i++) {
free(g->adj[i]);

ID: 24BQ1A05U9
}
free(g->adj);
free(g);

return 0;
}

Execution Results - All test cases have succeeded!

2024-2028-CSE-E
Test Case - 1

User Output
3
2
01

Vasireddy Venkatadri Institute of Technology

02
2

Test Case - 2

User Output
5
4
01
12
13
24
4
 Date: 2025-10-
[Link]: 9 Exp. Name: Implementing Merge Sort

Page No: 45
06

Aim:
Write a C program that implements the merge sort to sort a given array of integers in

ID: 24BQ1A05U9
ascending order, where the function splitAndMerge() for recursive splitting and merging
and the function merge() to combine two sorted sub-arrays.

Input Format:
• The first line of input contains an integer representing the total number of
elements of the array.
• The second line of input contains space-separated integers representing the
elements of the array.

Output Format:
• The first line contains the input array.

2024-2028-CSE-E
• The second line contains the array after sorting.

Note:
• The size of the array is fixed to 15
• Refer to visible test cases to strictly match with the input/output layout.
Source Code:

Vasireddy Venkatadri Institute of Technology

mergeSort.c
#include <stdio.h>

Page No: 46
void display(int arr[15], int n) {
int i;
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");

ID: 24BQ1A05U9
}

void merge(int arr[15], int low, int mid, int high) {

int leftArraySize = mid-low+1;
int rightArraySize = high-mid;
int leftArray[leftArraySize];
int rightArray[rightArraySize];
for(int i=0;i<leftArraySize;i++)
leftArray[i] = arr[low+i];
for(int j=0;j<rightArraySize;j++)
rightArray[j] = arr[mid+1+j];

2024-2028-CSE-E
int i=0;
int j=0;
int index = low;
while(i<leftArraySize && j<rightArraySize)
{
if(leftArray[i]<=rightArray[j])
{

Vasireddy Venkatadri Institute of Technology

arr[index] = leftArray[i];
index++;
i++;
}
else{
arr[index]=rightArray[j];
index++;
j++;
}
}
while(i<leftArraySize){
arr[index]=leftArray[i];
index++;
i++;
}
while(j<rightArraySize){
arr[index] = rightArray[j];
index++;
j++;
}
}
void splitAndMerge(int arr[115],int low,int high){
 if(low>=high)

Page No: 47
return;
int mid = low+(high-low)/2;
splitAndMerge(arr,low,mid);
splitAndMerge(arr,mid+1,high);
merge(arr,low,mid,high);

ID: 24BQ1A05U9
}

void main() {
int arr[15], i, n;
printf("Enter array size: ");
scanf("%d", &n);
printf("Enter %d elements: ", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("Before sorting: ");

2024-2028-CSE-E
display(arr, n);
splitAndMerge(arr, 0, n - 1);
printf("After sorting: ");
display(arr, n);
}

Vasireddy Venkatadri Institute of Technology

Execution Results - All test cases have succeeded!
Test Case - 1

User Output
Enter array size:
5
Enter 5 elements:
12354
Before sorting: 1 2 3 5 4
After sorting: 1 2 3 4 5

Test Case - 2

User Output
Enter array size:
8
Enter 8 elements:
95 14 10 2 32 5 9 4
Before sorting: 95 14 10 2 32 5 9 4

Page No: 48
After sorting: 2 4 5 9 10 14 32 95

ID: 24BQ1A05U9
2024-2028-CSE-E
Vasireddy Venkatadri Institute of Technology
 Date: 2025-10-
[Link]: 10 Exp. Name: Implementing Quick Sort

Page No: 49
06

Aim:
Write a C program that implements the Quick Sort algorithm to sort a given list of natural

ID: 24BQ1A05U9
numbers in ascending order.

Input Format:
• The first input is an integer n which represents the size of the array.
• The next n inputs are the n natural numbers to be sorted which are space
separated.

Output Format:
• The first line display the elements of the array before sorting, prefixed by: "Before
sorting the elements are :"
• The second line displays the sorted array after sorting, prefixed by: "After sorting

2024-2028-CSE-E
the elements are :"
Source Code:

quickSort.c

Vasireddy Venkatadri Institute of Technology

#include <stdio.h>

Page No: 50
int Partition(int arr[15],int low,int high);
void display(int arr[15],int n){
int i;
for(int i=0;i<n;i++)
printf("%d ",arr[i]);

ID: 24BQ1A05U9
printf("\n");
}
void quickSort(int arr[15],int low,int high){
int pi;
if(low<high){
pi=Partition(arr,low,high);
quickSort(arr,low,pi-1);
quickSort(arr,pi+1,high);
}
}
int Partition(int arr[15],int low,int high)

2024-2028-CSE-E
{
int j;
int pivot = arr[high];
int i = low-1;
for(j=low;j<high;j++){
if(arr[j]<=pivot){
i++;

Vasireddy Venkatadri Institute of Technology

int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
void main() {
int arr[15], i, n;
printf("Enter array size : ");
scanf("%d", &n);
printf("Enter %d elements : ", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("Before sorting the elements are : ");
display(arr, n);
quickSort(arr, 0, n - 1);
printf("After sorting the elements are : ");
 display(arr, n);

Page No: 51
}

Execution Results - All test cases have succeeded!

ID: 24BQ1A05U9
Test Case - 1

User Output
Enter array size :
6
Enter 6 elements :
6 2 8 10 36 14
Before sorting the elements are : 6 2 8 10 36 14
After sorting the elements are : 2 6 8 10 14 36

2024-2028-CSE-E
Test Case - 2

User Output
Enter array size :

Vasireddy Venkatadri Institute of Technology

8
Enter 8 elements :
95 14 10 23 36 2 5 35
Before sorting the elements are : 95 14 10 23 36 2 5 35
After sorting the elements are : 2 5 10 14 23 35 36 95
 Exp. Name: Job Sequencing Problem Date: 2025-10-
[Link]: 11

Page No: 52
with Deadline 15

Aim:
You are given n jobs, where each job has a profit and a deadline. Your task is to schedule

ID: 24BQ1A05U9
the jobs to maximize the total profit such that no two jobs are scheduled at the same
time and each job takes 1 unit of time.

If a job cannot be scheduled before its deadline, it is rejected. The output should display
the job index, profit, deadline, and the slot assigned (or "Rejected" if the job cannot be
scheduled).

Input Format:
First line: An integer n, the number of jobs.
Next 2 × n lines: For each job i (1 ≤ i ≤ n):
• Line 1: Profit of job i (integer)

2024-2028-CSE-E
• Line 2: Deadline of job i (integer)

Output Format:
Print the table with columns:
Index Profit Deadline Slot Alloted
For each job:
• If scheduled, print [start_time - end_time] as the slot allocated in the format that

Vasireddy Venkatadri Institute of Technology

is shown in the visible test cases
• If the job cannot be scheduled, print Rejected in the pattern that is shown in the
visible test cases.

Constraints:
• 1 ≤ n ≤ 100
• 1 ≤ P rof it ≤ 1000
• 1 ≤ Deadline ≤ 100

Refer to visible test cases for better understanding and to strictly match with the
input/output format and indentations.
Source Code:

jobDeadline.c
#include<stdio.h>

Page No: 53
void swap(int *x,int *y)
{
int temp;
temp = *x;
*x = *y;

ID: 24BQ1A05U9
*y = temp;
}
int main(){
int n,i,j;
printf("Enter the no of jobs: ");
scanf("%d",&n);
int slot[n],profit,p[n],d[n],maxprofit;
for(i=0;i<n;i++){
printf("Enter the profit of job %d: ",i+1);
scanf("%d",&p[i]);
printf("Enter the deadline of job %d: ",i+1);

2024-2028-CSE-E
scanf("%d",&d[i]);
}
for(int i=0;i<n;i++)
slot[i]=0;
for(i=0;i<n;i++){
int min=i;
for(int j=i+1;j<n;j++){

Vasireddy Venkatadri Institute of Technology

if(p[j]>p[min])
min=j;
}
if(min!=i){
swap(&p[i],&p[min]);
swap(&d[i],&d[min]);
}
}
int temp[100];
for(int i=0;i<n;i++){
temp[i]=0;
}
for(int i=0;i<n;i++){
for(int j=d[i];j>0;j--){
if(temp[j-1]==0)
{
slot[i]=j;
temp[j-1]=1;
break;
}
}
}
 printf("Index Profit Deadline Slot Alloted ");

Page No: 54
for(i=0;i<n;i++){
if(slot[i]>0)
printf("\n%d\t%d \t%d \t[%d - %d]",
i+1,p[i],d[i],(slot[i]-1),slot[i]);else
printf("\n%d\t%d\t%d

ID: 24BQ1A05U9
\tRejected",i+1,p[i],d[i]);
}
}

Execution Results - All test cases have succeeded!

Test Case - 1

User Output

2024-2028-CSE-E
Enter the no of jobs:
3
Enter the profit of job 1:
190
Enter the deadline of job 1:
3

Vasireddy Venkatadri Institute of Technology

Enter the profit of job 2:
110
Enter the deadline of job 2:
4
Enter the profit of job 3:
50
Enter the deadline of job 3:
2
Index Profit Deadline Slot Alloted
1 190 3 [2 - 3]
2 110 4 [3 - 4]
3 50 2 [1 - 2]

Test Case - 2

User Output
Enter the no of jobs:
2
Enter the profit of job 1:
200

Page No: 55
Enter the deadline of job 1:
1
Enter the profit of job 2:
180

ID: 24BQ1A05U9
Enter the deadline of job 2:
1
Index Profit Deadline Slot Alloted
1 200 1 [0 - 1]
2 180 1 Rejected

2024-2028-CSE-E
Vasireddy Venkatadri Institute of Technology
 Exp. Name: Dijkstra's Shortest Path Date: 2025-10-
[Link]: 12

Page No: 56
Algorithm 15

Aim:
Given a graph G and source vertex S , Dijkstra's shortest path algorithm is used to find

ID: 24BQ1A05U9
the shortest paths from source S to all vertices in the given graph.

The Dijkstra algorithm is also known as the single-source shortest path algorithm. It is
based on the greedy technique. A little variation in the algorithm can find the shortest
path from the source nodes to all the other nodes in the graph.

The function void dijkstra(int G[M AX][M AX], int n, int startnode) computes and
prints the shortest path distances and corresponding paths from the given source node
to all other nodes in a weighted directed graph using Dijkstra's algorithm. It outputs the
distance or "INF" if unreachable, along with the path or "NO PATH" for each node.

2024-2028-CSE-E
Note:
• Vertices are numbered from 1 through V .
• All input values are separated by spaces and/or newlines.

Sample Input and Output:

Enter the number of vertices : 4
Enter the number of edges : 5

Vasireddy Venkatadri Institute of Technology

Enter source : 1
Enter destination : 2
Enter weight : 4
Enter source : 1
Enter destination : 4
Enter weight : 10
Enter source : 1
Enter destination : 3
Enter weight : 6
Enter source : 2
Enter destination : 4
Enter weight : 5
Enter source : 3
Enter destination : 4
Enter weight : 2
Enter the source :1
Node Distance Path
2 4 2<-1
3 6 3<-1
4 8 4<-3<-1
Source Code:

Dijkstras.c
#include <limits.h>

Page No: 57
#include <stdio.h>
#define MAX 20
int V, E;
int graph[MAX][MAX];
#define INFINITY 99999

ID: 24BQ1A05U9
void dijkstra(int G[MAX][MAX], int n, int startnode) {
int dist[MAX];
int visited[MAX]={0};
int parent[MAX];
int i,j;
for(i=1;i<=V;i++)
{
dist[i]=INFINITY;
parent[i]=-1;
}

2024-2028-CSE-E
dist[startnode]=0;
for(int count=-1;count<=V-1;count++)
{
int min=INFINITY,u=-1;
for(i=1;i<=V;i++){
if(!visited[i]&&dist[i]<=min)
{

Vasireddy Venkatadri Institute of Technology

min=dist[i];
u=i;
}
}
if(u==-1)
break;
visited[u]=1;
for(j=1;j<=V;j++){
if(!visited[j]&&G[u]
[j]&&dist[u]!=INFINITY&&dist[u]+G[u][j]<dist[j])
{
dist[j]=dist[u]+G[u][j];
parent[j]=u;
}
}
}
printf("Node\tDistance\tPath\n");
for(i=1;i<=V;i++){
if(i!=startnode){
printf(" %d\t",i);
if(dist[i]==INFINITY){
printf(" INF\tNO PATH");
 }

Page No: 58
else{
printf(" %d\t",dist[i]);
int temp=i;
printf("%d",i);
while(parent[temp]!=-1)

ID: 24BQ1A05U9
{
printf("<-
%d",parent[temp]);
temp=parent[temp];
}
}
printf("\n");
}
}
}
int main() {

2024-2028-CSE-E
int s, d, w, i, j;
printf("Enter the number of vertices : ");
scanf("%d", &V);
printf("Enter the number of edges : ");
scanf("%d", &E);
for(i = 1 ; i <= V; i++) {
for(j = 1; j <= V; j++) {

Vasireddy Venkatadri Institute of Technology

graph[i][i] = 0;
}
}
for(i = 1; i <= E; i++) {
printf("Enter source : ");
scanf("%d", &s);
printf("Enter destination : ");
scanf("%d", &d);
printf("Enter weight : ");
scanf("%d", &w);
if(s > V || d > V || s <= 0 || d <= 0) {
printf("Invalid index. Try again.\n");
i--;
continue;
} else {
graph[s][d] = w;
}
}
printf("Enter the source :");
scanf("%d", &s);
dijkstra(graph, V, s);
 return 0;

Page No: 59
}

Execution Results - All test cases have succeeded!

ID: 24BQ1A05U9
Test Case - 1

User Output
Enter the number of vertices :
4
Enter the number of edges :
5
Enter source :
1

2024-2028-CSE-E
Enter destination :
2
Enter weight :
4
Enter source :
1

Vasireddy Venkatadri Institute of Technology

Enter destination :
4
Enter weight :
10
Enter source :
1
Enter destination :
3
Enter weight :
6
Enter source :
2
Enter destination :
4
Enter weight :
5
Enter source :
3
4
Enter weight :

Page No: 60
2
Enter the source :
1
Node Distance Path

ID: 24BQ1A05U9
2 4 2<-1
3 6 3<-1
4 8 4<-3<-1

Test Case - 2

User Output
Enter the number of vertices :
5

2024-2028-CSE-E
Enter the number of edges :
6
Enter source :
1
Enter destination :
2

Vasireddy Venkatadri Institute of Technology

Enter weight :
2
Enter source :
1
Enter destination :
5
Enter weight :
3
Enter source :
2
Enter destination :
4
Enter weight :
4
Enter source :
2
Enter destination :
3
7
Enter source :

Page No: 61
4
Enter destination :
3
Enter weight :

ID: 24BQ1A05U9
2
Enter source :
5
Enter destination :
4
Enter weight :
1
Enter the source :
2

2024-2028-CSE-E
Node Distance Path
1 INF NO PATH
3 6 3<-4<-2
4 4 4<-2
5 INF NO PATH

Vasireddy Venkatadri Institute of Technology

Test Case - 3

User Output
Enter the number of vertices :
4
Enter the number of edges :
5
Enter source :
1
Enter destination :
2
Enter weight :
4
Enter source :
3
Enter destination :
2
Enter weight :
Enter source :
4

Page No: 62
Enter destination :
1
Enter weight :
1

ID: 24BQ1A05U9
Enter source :
4
Enter destination :
2
Enter weight :
3
Enter source :
4
Enter destination :

2024-2028-CSE-E
3
Enter weight :
8
Enter the source :
1
Node Distance Path

Vasireddy Venkatadri Institute of Technology

2 4 2<-1
3 INF NO PATH
4 INF NO PATH
 Exp. Name: 0/1 knapsack problem using Date: 2025-10-
[Link]: 13

Page No: 63
Dynamic programming 15

Aim:
Write a program to implement Knapsack using Dynamic programming

ID: 24BQ1A05U9
Source Code:

DynamicKnapsack.c

#include<stdio.h>
int max(int a,int b){
return(a>b)?a:b;
}
int knapsack(int W,int wt[],int val[],int n){
int dp[n+1][W+1];
for(int i=0;i<=n;i++){

2024-2028-CSE-E
for(int w=0;w<=W;w++){
if(i==0||w==0)
dp[i][w]=0;
else if(wt[i-1]<=w)
dp[i][w]=max(val[i-1]+dp[i-1][w-wt[i-
1]],dp[i-1][w]);
else

Vasireddy Venkatadri Institute of Technology

dp[i][w]=dp[i-1][w];
}
}
return dp[n][W];
}
int main(){
int n,W;
printf("Enter the no. of items: ");
scanf("%d",&n);
int pri[n],wt[n];
printf("Enter the weight and price of all items\n");
for(int i=0;i<n;i++){
scanf("%d %d",&wt[i],&pri[i]);
}
printf("enter the capacity of knapsack: ");
scanf("%d",&W);
printf("The maximum value of items that can be put into
knapsack is: %d \n",knapsack(W,wt,pri,n));
}
 Execution Results - All test cases have succeeded!

Page No: 64
Test Case - 1

User Output
Enter the no. of items:

ID: 24BQ1A05U9
3
Enter the weight and price of all items
10 60
20 100
30 120
enter the capacity of knapsack:
50
The maximum value of items that can be put into knapsack is: 220

2024-2028-CSE-E
Test Case - 2

User Output
Enter the no. of items:
3
Enter the weight and price of all items

Vasireddy Venkatadri Institute of Technology

41
52
13
enter the capacity of knapsack:
4
The maximum value of items that can be put into knapsack is: 3
 Exp. Name: N Queen problem using Date: 2025-10-
[Link]: 14

Page No: 65
backtracking 15

Aim:
N-Queens using Backtracking:

ID: 24BQ1A05U9
Here is an algorithm for solving the N-Queens problem using backtracking:
1. Start with an empty chessboard of size N x N.
2. Place the first queen in the leftmost column of the first row.
3. Move to the next row and try to place a queen in an empty square in that row that is
not attacked by any of the queens already placed on the board.
4. If a queen can be placed in the current row, move to the next row and repeat step 3.
5. If a queen cannot be placed in the current row, backtrack to the previous row and try
a different square in that row. If all squares in the previous row have been tried and
none of them worked, backtrack again to the previous row.
6. Repeat steps 3-5 until all N queens have been placed on the board or it is determined

2024-2028-CSE-E
that no solution exists.
The key to this algorithm is the "not attacked" rule. To determine whether a queen is
being attacked by any other queen on the board, we need to check whether any other
queen is in the same row, column, or diagonal as the current queen.

Write the code to implement the N Queen problem using backtracking

Vasireddy Venkatadri Institute of Technology

Given an Array, you need to place a queen in the array such that no queen can strike
down any other queen. A queen has the possibility to attack horizontally, vertically, or
diagonally. You need to check whether the queen is placed in the correct position or not.

Input Format:
It contains the number of queens in an Array.

Output Format:
An array in which the queens are placed and print a*symbol when there is no queen in
that particular row or column. You need to print all the possible solutions based on the
input and display the Total no of solutions. If there are no solutions then print the
solution as 0.

Constraints:
1 <= N <= 6
Source Code:

nQueen.c
#include<stdio.h>

Page No: 66
#define N 10
int arr[N][N];
void print(int n){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){

ID: 24BQ1A05U9
if(arr[i][j]==0)
printf("*\t");
else
printf("Q\t");
}
printf("\n");
}
}
int check(int r,int c,int n){
int dr=r;
int dc=c;

2024-2028-CSE-E
while(dr>=0 && dc>=0){
if(arr[dr][dc]==1)
return 0;
dr--;
dc--;
}
dr=r;

Vasireddy Venkatadri Institute of Technology

dc=c;
while(dr>=0){
if(arr[dr][dc]==1)
return 0;
dr--;
}
dc=c;
dr=r;
while(dc<n && dr>=0)
{
if(arr[dr][dc]==1)
return 0;
dc++;
dr--;
}
return 1;
}
void placing(int n,int row,int*count){
if(row==n){
*count=*count+1;
printf("Solution #%d:\n",*count);
print(n);
 return;

Page No: 67
}
for(int i=0;i<n;i++)
{
if(check(row,i,n))
{

ID: 24BQ1A05U9
arr[row][i]=1;
placing(n,row+1,count);
arr[row][i]=0;
}
}
}
void main(){
int n;
scanf("%d",&n);
int count=0;
for(int i=0;i<n;i++){

2024-2028-CSE-E
for(int j=0;j<n;j++){
arr[i][j]=0;
}
}
placing(n,0,&count);
printf("Total solutions:%d\n",count);
}

Vasireddy Venkatadri Institute of Technology

Execution Results - All test cases have succeeded!
Test Case - 1

User Output
4
Solution #1:
* Q * *
* * * Q
Q * * *
* * Q *
Solution #2:
* * Q *
Q * * *
* * * Q
* Q * *
 3
User Output

Total solutions:0
Total solutions:2

Test Case - 2

Vasireddy Venkatadri Institute of Technology 2024-2028-CSE-E ID: 24BQ1A05U9 Page No: 68

 Exp. Name: Knapsack using Date: 2025-10-
[Link]: 15

Page No: 69
backtracking 15

Aim:
Write a C program to solve the 0/1 Knapsack Problem using backtracking approach. The

ID: 24BQ1A05U9
program aims to maximize the total value of items that can be included in a knapsack
without exceeding its capacity

Input Format:

• Prompt the user to enter an integer n, indicating the number of items.

• For each item, prompt the user to enter its value and weight separated by space.
• Prompt the user to enter the capacity of the knapsack.

Output Format:


2024-2028-CSE-E
• Print the maximum profit (total value) that can be obtained by selecting items,
considering the knapsack's capacity constraint.
Source Code:

knapsackBacktracking.c

Vasireddy Venkatadri Institute of Technology

#include <stdio.h>

Page No: 70
#include <stdlib.h>

int knapsack(int *weights, int *values, int capacity, int n) {

int dp[n+1][capacity+1];
for(int i=0;i<=n;i++){

ID: 24BQ1A05U9
for(int w=0;w<=capacity;w++)
{
if(i==0||w==0)
{
dp[i][w]=0;
}
else if(weights[i-1<=w]){
int include=values[i-1]+dp[i-1]
[w-weights[i-1]];
int exclude=dp[i-1][w];
dp[i][w]=(include>exclude)?

2024-2028-CSE-E
include:exclude;
}
else{
dp[i][w]=dp[i-1][w];
}
}
}

Vasireddy Venkatadri Institute of Technology

return dp[n][capacity];
}

int main() {
int n;

// Read number of items

scanf("%d", &n);

// Allocate memory for values and weights

int *values = (int *)malloc(n * sizeof(int));
int *weights = (int *)malloc(n * sizeof(int));

// Read values and weights of items

for (int i = 0; i < n; i++) {
scanf("%d %d", &values[i],&weights[i]);
}

int capacity;
scanf("%d", &capacity);
 // Calculate and print the maximum profit

Page No: 71
printf("%d\n", knapsack(weights, values, capacity, n));

// Free allocated memory

free(values);
free(weights);

ID: 24BQ1A05U9
return 0;
}

Execution Results - All test cases have succeeded!

Test Case - 1

User Output

2024-2028-CSE-E
3
60 10
100 20
120 30
50

Vasireddy Venkatadri Institute of Technology

220

Test Case - 2

User Output
5
10 5
40 4
30 3
50 2
20 1
100
150
 Exp. Name: Problem on Travelling Date: 2025-10-
[Link]: 16

Page No: 72
Salesman 15

Aim:
A traveler needs to visit all the cities from a given list of cities, where the distances

ID: 24BQ1A05U9
between the cities are known. The traveler must start at the origin city (City 1), visit each
city exactly once, and then return to the origin city. The goal is to determine the shortest
possible route and its total travel cost using a Branch and Bound technique.

You are given the number of cities and the cost matrix, where the value in the matrix at
position [i][j] represents the travel cost between city i and city j. A value of 0 in the
matrix means there is no travel cost between a city and itself.

Task:
• Find the shortest route that visits all cities exactly once and returns to the starting
city.

2024-2028-CSE-E
• Print the sequence of cities in the shortest path.
• Print the total minimum cost of this route.

Input Format:
• The first line contains an integer n representing the number of cities.
• The next n lines contain n integers each, representing the cost matrix C , where
C[i][j] denotes the cost of traveling from city i to city j. The integers are

Vasireddy Venkatadri Institute of Technology

separated by spaces.

Output Format:
• An integer representing the total minimum cost of traveling through a shortest
path.

Constraints:
• 2 ≤ n ≤ 25
• The cost matrix will always be symmetric, i.e., C[i][j] == C[j][i] ] and C[i][j] = 0 .
Source Code:

CTC36670.c
#include<stdio.h>

Page No: 73
#include<stdlib.h>
#include<limits.h>
#define MAX 25
#define INF INT_MAX
int n;

ID: 24BQ1A05U9
int cost[MAX][MAX];
int best_cost=INF;
int best_path[MAX];
int current_path[MAX];
void tsp(int current_pos,int count,int cost_so_far){
if(count==n && cost[current_pos][0]>0){
if(cost_so_far + cost[current_pos][0]<best_cost){
best_cost=cost_so_far + cost[current_pos][0];
for(int i=0;i<n;i++)
best_path[i]=current_path[i];
best_path[n]=0;

2024-2028-CSE-E
}
return;
}
for(int next_pos=0;next_pos <n;next_pos++){
if(cost[current_pos][next_pos]>0 &&
(current_path[next_pos]==-1)){
current_path[next_pos]=count;

Vasireddy Venkatadri Institute of Technology

tsp(next_pos,count+1,cost_so_far +
cost[current_pos][next_pos]);
current_path[next_pos]=-1;
}
}
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&cost[i][j]);
for(int i=0;i<n;i++)
current_path[i]=-1;
current_path[0]=0;
tsp(0,1,0);
printf("%d\n",best_cost);
return 0;
}

Execution Results - All test cases have succeeded!

 3

60
15 35 0
10 0 35
0 10 15
User Output
Test Case - 1

Vasireddy Venkatadri Institute of Technology 2024-2028-CSE-E ID: 24BQ1A05U9 Page No: 74