Assignment 1

Set A.
#include <stdio.h>
#include <stdlib.h>
struct Node{
int data;
struct Node *left,*right;

};

struct Node*createNode(int data){

struct Node*newNode=(struct Node*)malloc(sizeof(struct Node));

newNode->data=data;
newNode->left=newNode->right=NULL;
return newNode;
}
struct Node* insert(struct Node*root,int data){
if(root==NULL)
return createNode(data);
if(data<root->data)
root->left=insert(root->left,data);
else if(data>root->data)
root->right=insert(root->right,data);
return root;
}
struct Node* search(struct Node*root,int data){
if(root==NULL)
return root;
if(data<root->data)
return search(root->left,data);
else
return search(root->right,data);
}
void inorder(struct Node*root){
if(root!=NULL){
inorder(root->left);
printf("%d",root->data);
inorder(root->right);
}
}
void preorder(struct Node*root){
if(root!=NULL){
printf("%d",root->data);
preorder(root->left);
 preorder(root->right);
}
}
void postorder(struct Node*root){
if(root!=NULL){
postorder(root->left);
postorder(root->right);
printf("%d",root->data);
}
}
int main()
{
struct Node*root=NULL;
int choice,value;
while(1){
printf("\n BST Operation:\n");
printf("1.Insert\n");
printf("2.Search\n");
printf("3.Inorder Traversal\n");
printf("4.Preorder Traversal\n");
printf("5.Postorder Traversal\n");
printf("6.Exit\n");
printf("Enter your choice:");
scanf("%d",&choice);

switch(choice){
case 1:
printf("Enter value to insert:");
scanf("%d",&value);
root=insert(root,value);
break;
case 2:
printf("Enter value to search:");
scanf("%d",&value);
if(search(root,value))
printf("Value found in BST.\n");
else
printf("Value not found.\n");
break;
case 3:
printf("Inorder Traversal:");
inorder(root);
printf("\n");
break;
case 4:
 printf("Preorder Traversal:");
inorder(root);
printf("\n");
break;
case 5:
printf("Preorder Traversal:");
inorder(root);
printf("\n");
break;
case 6:
printf("Exiting program.\n");
return 0;
default:

printf("Invalid choice! please try again.\n");

}
}
return 0;
}
Set B.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left,*right;
};
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
struct Node* insert(struct Node* root, int data) {
if (root == NULL)
return createNode(data);
if (data < root->data)
root->left = insert(root->left, data);
else if (data > root->data)
root->right = insert(root->right, data);
return root;
}
struct Node* copy(struct Node* root) {
if (root == NULL) return NULL;
Node* newRoot = createNode(root->data);
newRoot->left = copy(root->left);
newRoot->right = copy(root->right);
return newRoot;
}
int compare(Node* root1, Node* root2) {
if (root1 == NULL && root2 == NULL) return 1;
if (root1 == NULL || root2 == NULL) return 0;
return (root1->data == root2->data) && compare(root1->left, root2->left) && compare(root1-
>right,root2->right);
}
void inorder(struct Node* root) {
if (root == NULL) return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
void freeTree(Node* root) {
if (root == NULL) return;
freeTree(root->left);
freeTree(root->right);
free(root);
}
int main() {
Node* root = NULL;
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 70);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 60);
root = insert(root, 80);

printf("Original BST (Inorder): ");

inorder(root);

printf("\n");

Node* copyRoot = copy(root);

printf("Copied BST (Inorder): ");
inorder(copyRoot);
printf("\n");

if (compare(root, copyRoot))
printf("BSTs are identical.\n");
else
printf("BSTs are not identical.\n");

freeTree(root);
freeTree(copyRoot);

return 0;
}
Set C.
#include <stdio.h>

#include <stdlib.h>

struct Node {

int key;

struct Node *left, *right;

};

struct Node* newNode(int item) {

struct Node* temp = (struct Node*)malloc(sizeof(struct Node));

temp->key = item;

temp->left = temp->right = NULL;

return temp;

}
struct Node* insert(struct Node* node, int key) {

if (node == NULL) return newNode(key);

if (key < node->key)

node->left = insert(node->left, key);

else

node->right = insert(node->right, key);

return node;
}

struct Node* findMin(struct Node* node) {

while (node->left != NULL)

node = node->left;

return node;
}

struct Node* deleteNode(struct Node* root, int key) {

if (root == NULL) return root;
 if (key < root->key)

root->left = deleteNode(root->left, key);

else if (key > root->key)

root->right = deleteNode(root->right, key);

else {

if (root->left == NULL) {

struct Node* temp = root->right;

free(root);

return temp;

else if (root->right == NULL) {

struct Node* temp = root->left;

free(root);

return temp;

struct Node* temp = findMin(root->right);

root->key = temp->key;

root->right = deleteNode(root->right, temp->key);

}
return root;

void inorder(struct Node* root) {

if (root != NULL) {

inorder(root->left);

printf("%d ", root->key);

inorder(root->right);
}
}

int main() {

struct Node* root = NULL;

 root = insert(root, 50);

root = insert(root, 30);

root = insert(root, 20);

root = insert(root, 40);

root = insert(root, 70);

root = insert(root, 60);

root = insert(root, 80);

printf("Inorder traversal before deletion: ");

inorder(root);

printf("\n");

root = deleteNode(root, 50);

printf("Inorder traversal after deletion: ");

inorder(root);

printf("\n");

return 0;

}
Assignment 2
Set A.
#include <stdio.h>

#include <stdlib.h>

typedef struct Node {

int data;

struct Node *left, *right;

};

typedef struct QueueNode {

struct Node*treeNode;

struct QueueNode *next;

};

typedef struct Queue {

struct QueueNode *front, *rear;

};

struct Node* createNode(int data) {

struct Node*newNode=(struct Node*)malloc(sizeof(struct Node));

if (!newNode) {

printf("Memory error\n");

return NULL;
}

newNode->data = data;
newNode->left = newNode->right = NULL;

return newNode;

struct Node* insert(struct Node* root, int data) {

if (root == NULL) {
return createNode(data);

}
if (data < root->data)
 root->left = insert(root->left, data);

else

root->right = insert(root->right, data);

return root;
}

struct Queue* createQueue() {

struct Queue*q = (struct Queue*)malloc(sizeof(struct Queue));

q->front = q->rear = NULL;

return q;

void enqueue(struct Queue *q, struct Node *treeNode) {

struct QueueNode*newNode=(struct QueueNode*)malloc(sizeof(struct QueueNode));

newNode->treeNode = treeNode;

newNode->next = NULL;

if (q->rear) {

q->rear->next = newNode;

q->rear = newNode;

if (!q->front) {
q->front = newNode;

struct Node* dequeue(struct Queue *q) {

if (!q->front) {

return NULL;

}
struct QueueNode *temp = q->front;
struct Node *treeNode = temp->treeNode;

q->front = q->front->next;

if (!q->front) {
 q->rear = NULL;

free(temp);

return treeNode;
}

int isQueueEmpty(struct Queue *q) {

return q->front == NULL;

void printLevels(struct Node *root) {

if (!root) return;

struct Queue *q = createQueue();

enqueue(q, root);

int level = 0;

while (!isQueueEmpty(q)) {

int nodeCount = 0;

struct Queue *tempQ = createQueue();

printf("Level %d: ", level);

while (!isQueueEmpty(q)) {

struct Node *node = dequeue(q);

printf("%d ", node->data);

nodeCount++;

if (node->left) enqueue(tempQ, node->left);

if (node->right) enqueue(tempQ, node->right);
}

printf(" (Count: %d)\n", nodeCount);

 free(q);

q = tempQ;

level++;

}
free(q);

printf("Total Levels: %d\n", level);

int main() {

struct Node *root = NULL;

int values[] = {10, 5, 15, 3, 7, 12, 18};

int n = sizeof(values) / sizeof(values[0]);

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

root = insert(root, values[i]);

printLevels(root);

return 0;

}
Set B.
#include <stdio.h>

#include <stdlib.h>

#include <time.h>

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

int temp = *a;

*a = *b;

*b = temp;

void heapify(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])

largest = left;

if (right < n && arr[right] > arr[largest])

largest = right;

if (largest != i) {

swap(&arr[i], &arr[largest]);

heapify(arr, n, largest);
}

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

for (int i = n / 2 - 1; i >= 0; i--)

heapify(arr, n, i);

for (int i = n - 1; i > 0; i--) {

swap(&arr[0], &arr[i]);
heapify(arr, i, 0);
}

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

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

printf("%d ", arr[i]);

printf("\n");
}

int main() {

int n;

printf("Enter number of elements: ");

scanf("%d", &n);

int arr[n];

srand(time(0));

printf("Unsorted array: ");

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

arr[i] = rand() % 100;

printf("%d ", arr[i]);

printf("\n");

heapSort(arr, n);

printf("Sorted array: ");

printArray(arr, n);

return 0;

}
Set C.

#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int data;
struct ListNode* next;
};
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
struct ListNode* findMiddle(struct ListNode* start, struct ListNode* end) {
struct ListNode *slow = start, *fast = start;
while (fast != end && fast->next != end) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
struct TreeNode* sortedListToBST(struct ListNode* start, struct ListNode* end) {
if (start == end) return NULL;
struct ListNode* mid = findMiddle(start, end);
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->data = mid->data;
root->left = sortedListToBST(start, mid);
root->right = sortedListToBST(mid->next, end);
return root;
}
struct ListNode* newListNode(int data) {
struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->data = data;
node->next = NULL;
return node;
}
void inorderTraversal(struct TreeNode* root) {
if (!root) return;
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
 int main() {
struct ListNode* head = newListNode(-10);
head->next = newListNode(-3);
head->next->next = newListNode(0);
head->next->next->next = newListNode(5);
head->next->next->next->next = newListNode(9);
struct TreeNode* root = sortedListToBST(head, NULL);
printf("Inorder Traversal of BST: ");
inorderTraversal(root);
return 0;
}

Assignment 3.
Set A.

#include <stdio.h>

#define MAX 100

void createAdjMatrix(int adj[MAX][MAX], int vertices, int edges) {

int i, src, dest;

for (i = 0; i < vertices; i++)

for (int j = 0; j < vertices; j++)

adj[i][j] = 0;

printf("Enter the edges (format: source destination):\n");

for (i = 0; i < edges; i++) {

scanf("%d %d", &src, &dest);

adj[src][dest] = 1;

adj[dest][src] = 1;

}
}

void displayAdjMatrix(int adj[MAX][MAX], int vertices) {

printf("\nAdjacency Matrix:\n");

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

for (int j = 0; j < vertices; j++)

printf("%d ", adj[i][j]);

printf("\n");

int main() {

int vertices, edges, adj[MAX][MAX];

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

scanf("%d", &vertices);

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

scanf("%d", &edges);

createAdjMatrix(adj, vertices, edges);

displayAdjMatrix(adj, vertices);

return 0;

}
Set B .
#include <stdio.h>

#include <stdlib.h>

#define MAX 100

int adjMatrix[MAX][MAX];

int visited[MAX];

void initializeGraph(int vertices) {

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

for (int j = 0; j < vertices; j++) {

adjMatrix[i][j] = 0;

visited[i] = 0;

void addEdge(int u, int v) {

adjMatrix[u][v] = 1;

adjMatrix[v][u] = 1;

void displayGraph(int vertices) {

printf("\nAdjacency Matrix:\n");

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

for (int j = 0; j < vertices; j++) {

printf("%d ", adjMatrix[i][j]);

printf("\n");

void DFS(int node, int vertices) {

printf("%d ", node);

visited[node] = 1;
 for (int i = 0; i < vertices; i++) {

if (adjMatrix[node][i] == 1 && visited[i] == 0) {

DFS(i, vertices);

int main() {

int vertices, edges, u, v, start;

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

scanf("%d", &vertices);

initializeGraph(vertices);

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

scanf("%d", &edges);

printf("Enter edges (format: u v):\n");

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

scanf("%d %d", &u, &v);

addEdge(u, v);

displayGraph(vertices);

printf("Enter the starting vertex for DFS:”);

scanf("%d", &start);

printf(“\nDFS Traversal:”);

DFS(start, vertices);

printf("\n");

return 0;

}
Set C.

(d) Which Data Structure is Used to Implement the Adjacency Matrix Method?

An Adjacency Matrix is implemented using a 2D array (matrix).

Why a 2D Array?

• The adjacency matrix is a V × V (vertices × vertices) array, where adj[i][j] stores 1 if there is an edge
between vertex i and vertex j, otherwise it stores 0.

• Efficient for dense graphs (many edges).

• Allows O(1) time complexity for checking if an edge exists.

Example Implementation in C:

int adjMatrix[MAX][MAX];
Assignment 4
Set A.

#include <stdio.h>

#include <stdlib.h>

#define MAX 100

struct Node {
int vertex;

struct Node* next;

};

struct Node* adjList[MAX];

struct Node* createNode(int v) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->vertex = v;
newNode->next = NULL;

return newNode;

void createAdjList(int vertices, int edges) {

int i, src, dest;

for (i = 0; i < vertices; i++)

adjList[i] = NULL;
printf("Enter the edges (format: source destination):\n");

for (i = 0; i < edges; i++) {

scanf("%d %d", &src, &dest);

struct Node* newNode = createNode(dest);

newNode->next = adjList[src];

adjList[src] = newNode;

newNode = createNode(src);
newNode->next = adjList[dest];
adjList[dest] = newNode;

}
}

void displayAdjList(int vertices) {

printf("\nAdjacency List:\n");

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

printf("%d -> ", i);

struct Node* temp = adjList[i];

while (temp) {

printf("%d ", temp->vertex);

temp = temp->next;

printf("\n");

}
}

void calculateDegrees(int vertices) {

int indegree[MAX] = {0}, outdegree[MAX] = {0}, totaldegree[MAX] = {0};

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

struct Node* temp = adjList[i];

while (temp) {

outdegree[i]++;
indegree[temp->vertex]++;

temp = temp->next;

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

totaldegree[i] = indegree[i] + outdegree[i];

printf("\nVertex\tIndegree\tOutdegree\tTotal Degree\n");
for (int i = 0; i < vertices; i++)
printf("%d\t%d\t\t%d\t\t%d\n", i, indegree[i], outdegree[i], totaldegree[i]);

int main() {
 int vertices, edges;

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

scanf("%d", &vertices);

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

scanf("%d", &edges);

createAdjList(vertices, edges);

displayAdjList(vertices);

calculateDegrees(vertices);

return 0;

}
Set B.
#include <stdio.h>

#include <stdlib.h>

#define MAX 100

struct Node {

int vertex;
struct Node* next;

};

struct Node* adjList[MAX];

int visited[MAX];

struct Node* createNode(int v) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->vertex = v;
newNode->next = NULL;

return newNode;

void createAdjList(int vertices, int edges) {

int i, src, dest;

for (i = 0; i < vertices; i++) {

adjList[i] = NULL;
visited[i] = 0;

printf("Enter the edges (format: source destination):\n");

for (i = 0; i < edges; i++) {

scanf("%d %d", &src, &dest);

struct Node* newNode = createNode(dest);

newNode->next = adjList[src];
adjList[src] = newNode;
newNode = createNode(src);

newNode->next = adjList[dest];
 adjList[dest] = newNode;

void DFS(int vertex) {

struct Node* temp = adjList[vertex];

printf("%d ", vertex);

visited[vertex] = 1;

while (temp) {

int adjVertex = temp->vertex;

if (!visited[adjVertex])

DFS(adjVertex);

temp = temp->next;
}

int main() {

int vertices, edges, startVertex;

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

scanf("%d", &vertices);

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

scanf("%d", &edges);

createAdjList(vertices, edges);

printf("Enter the starting vertex for DFS: ");

scanf("%d", &startVertex);

printf("DFS Traversal: ");

DFS(startVertex);

printf("\n");
return 0;
}
Set C.
Where is the new node appended in the Breadth-First Search (BFS) OPEN list?

Answer:

• In Breadth-First Search (BFS), the OPEN list (queue) follows the FIFO (First-In-First-Out) principle.

• New nodes are always appended at the rear (end) of the queue.

• Nodes are processed from the front of the queue.

BFS Algorithm Using Queue

1. Enqueue (Append) the starting node into the queue.

2. Dequeue (Remove) a node from the front.

3. Visit all adjacent (unvisited) nodes and enqueue them at the rear.

4. Repeat until the queue is empty.

Assignment 5
Set A.

#include <stdio.h>

#include <limits.h>

#define MAX 100

#define INF INT_MAX

int graph[MAX][MAX];

int vertices;

int minKey(int key[], int mstSet[]) {

int min = INF, minIndex;

for (int v = 0; v < vertices; v++) {

if (mstSet[v] == 0 && key[v] < min) {

min = key[v], minIndex = v;

}

return minIndex;

void printMST(int parent[]) {

printf("Edge \tWeight\n");

for (int i = 1; i < vertices; i++)

printf("%d - %d \t%d\n", parent[i], i, graph[i][parent[i]]);

void primMST() {

int parent[MAX];

int key[MAX];

int mstSet[MAX];

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

key[i] = INF;
mstSet[i] = 0;

}
 key[0] = 0;

parent[0] = -1;

for (int count = 0; count < vertices - 1; count++) {

int u = minKey(key, mstSet);

mstSet[u] = 1;

for (int v = 0; v < vertices; v++) {

if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v]) {

parent[v] = u, key[v] = graph[u][v];

printMST(parent);
}

int main() {

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

scanf("%d", &vertices);

printf("Enter the adjacency matrix (use 0 for no edge):\n");

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

for (int j = 0; j < vertices; j++) {

scanf("%d", &graph[i][j]);

if (graph[i][j] == 0)

graph[i][j] = INF; // Convert 0 to INF for no edge

primMST();

return 0;
}
Set B .
#include <stdio.h>

#include <stdlib.h>

#define MAX 100

struct Edge {

int src, dest, weight;

};

struct Graph {

int V, E;

struct Edge edges[MAX];

};

struct Subset {

int parent, rank;

};

struct Graph* createGraph(int V, int E) {

struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));

graph->V = V;

graph->E = E;

return graph;

int compareEdges(const void* a, const void* b) {

return ((struct Edge*)a)->weight - ((struct Edge*)b)->weight;

}

int find(struct Subset subsets[], int i) {

if (subsets[i].parent != i)

subsets[i].parent = find(subsets, subsets[i].parent);

return subsets[i].parent;

void unionSets(struct Subset subsets[], int x, int y) {

int rootX = find(subsets, x);

int rootY = find(subsets, y);

if (subsets[rootX].rank < subsets[rootY].rank)

subsets[rootX].parent = rootY;

else if (subsets[rootX].rank > subsets[rootY].rank)

subsets[rootY].parent = rootX;

else {

subsets[rootY].parent = rootX;

subsets[rootX].rank++;

void kruskalMST(struct Graph* graph) {

struct Edge result[MAX];

int e = 0, i = 0;

qsort(graph->edges, graph->E, sizeof(graph->edges[0]), compareEdges);

struct Subset* subsets = (struct Subset*)malloc(graph->V * sizeof(struct Subset));

for (int v = 0; v < graph->V; v++) {

subsets[v].parent = v;

subsets[v].rank = 0;

while (e < graph->V - 1 && i < graph->E) {

struct Edge nextEdge = graph->edges[i++];

int x = find(subsets, nextEdge.src);

int y = find(subsets, nextEdge.dest);

if (x != y) {
 result[e++] = nextEdge;

unionSets(subsets, x, y);

printf("Edges in Minimum Spanning Tree:\n");

for (i = 0; i < e; i++)

printf("%d - %d (Weight: %d)\n", result[i].src, result[i].dest, result[i].weight);

int main() {

int V, E;

printf("Enter number of vertices and edges: ");

scanf("%d %d", &V, &E);

struct Graph* graph = createGraph(V, E);

printf("Enter edges (source destination weight):\n");

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

scanf("%d %d %d", &graph->edges[i].src, &graph->edges[i].dest, &graph->edges[i].weight);

kruskalMST(graph);

return 0;

}
Set C .
#include <stdio.h>

#define MAX 100

void detectSelfLoops(int graph[MAX][MAX], int vertices) {

int hasSelfLoop = 0;

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

if (graph[i][i] != 0) { // If diagonal element is non-zero

printf("Self-loop detected at vertex %d\n", i);

hasSelfLoop = 1;

if (!hasSelfLoop)

printf("No self-loops found in the graph.\n");

int main() {

int vertices;

int graph[MAX][MAX];

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

scanf("%d", &vertices);

printf("Enter the adjacency matrix:\n");

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

for (int j = 0; j < vertices; j++)

scanf("%d", &graph[i][j]);

detectSelfLoops(graph, vertices);

return 0;

}
Assignment 6
Set A .
#include <stdio.h>

#include <limits.h>

#define MAX 100

#define INF INT_MAX

int minDistance(int dist[], int visited[], int V) {

int min = INF, min_index = -1;

for (int v = 0; v < V; v++) {

if (!visited[v] && dist[v] < min) {

min = dist[v];

min_index = v;

return min_index;

void printSolution(int dist[], int V) {

printf("Vertex \t Distance from Source\n");

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

printf("%d \t %d\n", i, dist[i]);

void dijkstra(int graph[MAX][MAX], int V, int src) {

int dist[MAX];

int visited[MAX];

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

dist[i] = INF;

visited[i] = 0;

dist[src] = 0;

for (int count = 0; count < V - 1; count++) {

 int u = minDistance(dist, visited, V);

if (u == -1) break;

visited[u] = 1;

for (int v = 0; v < V; v++) {

if (!visited[v] && graph[u][v] && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {

dist[v] = dist[u] + graph[u][v];

printSolution(dist, V);

int main() {

int V;

int graph[MAX][MAX];

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

scanf("%d", &V);

printf("Enter the adjacency cost matrix (use 0 for no edge, except diagonals):\n");

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

for (int j = 0; j < V; j++) {

scanf("%d", &graph[i][j]);

if (graph[i][j] == 0 && i != j)

graph[i][j] = INF;

int src;

printf("Enter the source vertex: ");

scanf("%d", &src);

dijkstra(graph, V, src);

return 0;

}
Set B .
#include <stdio.h>

#define MAX 100

#define INF 99999

void printSolution(int dist[MAX][MAX], int V) {

printf("The shortest distance matrix:\n");

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

for (int j = 0; j < V; j++) {

if (dist[i][j] == INF)

printf("INF ");
else

printf("%d ", dist[i][j]);

}
printf("\n");

void floydWarshall(int graph[MAX][MAX], int V) {

int dist[MAX][MAX];
for (int i = 0; i < V; i++)

for (int j = 0; j < V; j++)

dist[i][j] = graph[i][j];

for (int k = 0; k < V; k++) {

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

 for (int j = 0; j < V; j++) {

if (dist[i][k] != INF && dist[k][j] != INF &&

dist[i][k] + dist[k][j] < dist[i][j]) {

dist[i][j] = dist[i][k] + dist[k][j];

}

printSolution(dist, V);

int main() {

int V;
int graph[MAX][MAX];

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

scanf("%d", &V);

printf("Enter the adjacency cost matrix (Use 99999 for INF/no edge except diagonals):\n");

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

for (int j = 0; j < V; j++)

scanf("%d", &graph[i][j]);
floydWarshall(graph, V);

return 0;

}
Set C .
#include <stdio.h>

#include <string.h>

#define MAX_PEOPLE 7

#define MAX_NAME_LEN 20

typedef struct {
char name[MAX_NAME_LEN];

char friends[MAX_PEOPLE][MAX_NAME_LEN];

int friendCount;

} Person;

void findFriends(Person people[], int size, char personName[]) {

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

if (strcmp(people[i].name, personName) == 0) {
printf("Friends of %s: ", personName);

if (people[i].friendCount == 0) {

printf("None\n");

} else {

for (int j = 0; j < people[i].friendCount; j++) {

printf("%s ", people[i].friends[j]);

}
printf("\n");

return;

printf("%s not found in the list.\n", personName);

}
int main() {
Person people[MAX_PEOPLE] = {

{"George", {"Jean", "John"}, 2},

 {"Jim", {"Fred", "Frank"}, 2},

{"Jean", {"George"}, 1},

{"Frank", {"Fred", "Jim"}, 2},

{"Fred", {"Frank", "Jim"}, 2},

{"John", {"George"}, 1},

{"Susan", {}, 0} // No friends

};

findFriends(people, MAX_PEOPLE, "John");

findFriends(people, MAX_PEOPLE, "Susan");

findFriends(people, MAX_PEOPLE, "Jim");

return 0;

}
Assignment 7
Set A .
#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#define TABLE_SIZE 10

#define MAX_KEYS 100

int hashTable[TABLE_SIZE];

void initializeTable() {

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

hashTable[i] = -1;

void displayHashTable() {

printf("\nHash Table:\n");

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

if (hashTable[i] == -1)

printf("[%d] -> EMPTY\n", i);

else

printf("[%d] -> %d\n", i, hashTable[i]);

int divisionMethod(int key) {

return key % TABLE_SIZE;

int midSquareMethod(int key) {

long long square = (long long)key * key;

int mid = (square / 100) % 100;

return mid % TABLE_SIZE;

int digitFoldingMethod(int key) {

int sum = 0;
 while (key > 0) {

sum += key % 100;

key /= 100;

return sum % TABLE_SIZE;

void insert(int key, int (*hashFunction)(int), const char *methodName) {

int index = hashFunction(key);

if (hashTable[index] == -1) {

hashTable[index] = key;

} else {

printf("Collision detected using %s at index %d for key %d! Using Linear Probing.\n", methodName, index, key);

int i = (index + 1) % TABLE_SIZE;

while (hashTable[i] != -1 && i != index) {

i = (i + 1) % TABLE_SIZE;

if (hashTable[i] == -1) {

hashTable[i] = key;

} else {

printf("Hash table is full, could not insert %d.\n", key);

int main() {

int n, key;

printf("Enter the number of keys to insert: ");

scanf("%d", &n);

if (n > MAX_KEYS) {

printf("Too many keys! Limit is %d.\n", MAX_KEYS);

return 1;

int keys[MAX_KEYS];
 printf("Enter %d keys: ", n);

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

scanf("%d", &keys[i]);

printf("\n--- Hashing using Division Method ---\n");

initializeTable();

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

insert(keys[i], divisionMethod, "Division Method");

displayHashTable();

printf("\n--- Hashing using Mid-Square Method ---\n");

initializeTable();

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

insert(keys[i], midSquareMethod, "Mid-Square Method");

displayHashTable();

printf("\n--- Hashing using Digit Folding Method ---\n");

initializeTable();

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

insert(keys[i], digitFoldingMethod, "Digit Folding Method");

displayHashTable();

return 0;

}
Set B .
#include <stdio.h>

#include <stdlib.h>

#define TABLE_SIZE 10

#define EMPTY -1

int hashTable[TABLE_SIZE];

void initializeTable() {

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

hashTable[i] = EMPTY;

int hashFunction(int key) {

return key % TABLE_SIZE;

void insert(int key) {

int index = hashFunction(key);

while (hashTable[index] != EMPTY) {

index = (index + 1) % TABLE_SIZE;

hashTable[index] = key;

printf("Inserted key %d at index %d\n", key, index);

void search(int key) {

int index = hashFunction(key);

int start = index;

while (hashTable[index] != EMPTY) {

if (hashTable[index] == key) {

printf("Key %d found at index %d\n", key, index);

return;

}
 index = (index + 1) % TABLE_SIZE;

if (index == start) break;

printf("Key %d not found in hash table.\n", key);

void delete(int key) {

int index = hashFunction(key);

int start = index;

while (hashTable[index] != EMPTY) {

if (hashTable[index] == key) {

hashTable[index] = EMPTY;

printf("Key %d deleted from index %d\n", key, index);

return;

index = (index + 1) % TABLE_SIZE;

if (index == start) break;

printf("Key %d not found, cannot delete.\n", key);

void display() {

printf("\nHash Table:\n");

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

if (hashTable[i] == EMPTY)

printf("[%d] -> EMPTY\n", i);

else

printf("[%d] -> %d\n", i, hashTable[i]);

int main() {

int choice, key;

initializeTable();

while (1) {

printf("\n--- Hash Table Operations ---\n");

printf("1. Insert\n");

printf("2. Search\n");

printf("3. Delete\n");

printf("4. Display\n");

printf("5. Exit\n");

printf("Enter choice: ");

scanf("%d", &choice);

switch (choice) {

case 1:

printf("Enter key to insert: ");

scanf("%d", &key);

insert(key);

break;

case 2:

printf("Enter key to search: ");

scanf("%d", &key);

search(key);

break;

case 3:

printf("Enter key to delete: ");

scanf("%d", &key);

delete(key);

break;

case 4:

display();

break;

case 5:
 printf("Exiting...\n");

exit(0);

default:

printf("Invalid choice! Try again.\n");

return 0;

}
Set C .
a) Calculate the time complexity of hash table with Linear Probing.
• Time Complexity of Hash Table with Linear Probing
Linear probing is a collision resolution technique in open addressing, where collisions are resolved by
searching for the next available slot in a sequential manner.

Effect of Load Factor (α) on Complexity

• Load Factor (α) = n/m determines the probability of collision.

• As α increases, the chances of longer probe sequences increase, leading to higher search/insertion
time.

• When α < 0.5, expected number of probes for search/insert is close to 1.

• When α ≈ 1, performance degrades towards O(n).

Expected Probes (Knuth’s Analysis)

For successful search:

For unsuccessful search:

Conclusion
• Best Case: O(1)O(1)O(1) (No collision)

• Average Case: O(1)O(1)O(1) (If α is low)

• Worst Case: O(n)O(n)O(n) (If α is close to 1 and clustering occurs)

Assignment 8
Set A .
#include <stdio.h>

#include <stdlib.h>

#define TABLE_SIZE 10

typedef struct Node {

int key;
struct Node* next;

} Node;

Node* hashTable[TABLE_SIZE];

int hashFunction(int key) {

return key % TABLE_SIZE;

void insert(int key) {

int index = hashFunction(key);

Node* newNode = (Node*)malloc(sizeof(Node));

newNode->key = key;

newNode->next = NULL;

if (hashTable[index] == NULL) {

hashTable[index] = newNode;
} else {

newNode->next = hashTable[index];
hashTable[index] = newNode;

printf("Key %d inserted successfully.\n", key);

void search(int key) {

int index = hashFunction(key);

Node* temp = hashTable[index];

while (temp) {
 if (temp->key == key) {

printf("Key %d found in the hash table.\n", key);

return;

}
temp = temp->next;

printf("Key %d not found in the hash table.\n", key);

void deleteKey(int key) {

int index = hashFunction(key);

Node* temp = hashTable[index];

Node* prev = NULL;

while (temp) {

if (temp->key == key) {

if (prev == NULL) { // Deleting first node

hashTable[index] = temp->next;

} else {

prev->next = temp->next;

}
free(temp);

printf("Key %d deleted successfully.\n", key);

return;

prev = temp;

temp = temp->next;

}
printf("Key %d not found in the hash table.\n", key);
}

void display() {

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

 printf("Index %d: ", i);

Node* temp = hashTable[i];

while (temp) {

printf("%d -> ", temp->key);

temp = temp->next;

printf("NULL\n");

int main() {

int choice, key;

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

hashTable[i] = NULL;

while (1) {

printf("\nHash Table Operations:\n");

printf("1. Insert\n2. Search\n3. Delete\n4. Display\n5. Exit\n");

printf("Enter your choice: ");

scanf("%d", &choice);
switch (choice) {

case 1:

printf("Enter key to insert: ");

scanf("%d", &key);

insert(key);

break;

case 2:
printf("Enter key to search: ");
scanf("%d", &key);

search(key);

break;
 case 3:

printf("Enter key to delete: ");

scanf("%d", &key);

deleteKey(key);
break;

case 4:

display();

break;

case 5:

printf("Exiting program.\n");

return 0;

default:
printf("Invalid choice! Please try again.\n");

return 0;

}
Set B .
#include <stdio.h>

#include <stdlib.h>

#define TABLE_SIZE 10

typedef struct Node {

int key;
struct Node* prev;

struct Node* next;

}Node;

Node* hashTable[TABLE_SIZE];

int hashFunction(int key) {

return key % TABLE_SIZE;

}
void insert(int key) {

int index = hashFunction(key);

Node* newNode = (Node*)malloc(sizeof(Node));

newNode->key = key;

newNode->prev = NULL;

newNode->next = NULL;

if (hashTable[index] == NULL) {
hashTable[index] = newNode;

} else {

newNode->next = hashTable[index];

hashTable[index]->prev = newNode;

hashTable[index] = newNode;

printf("Key %d inserted successfully.\n", key);

}
void search(int key) {

int index = hashFunction(key);

 Node* temp = hashTable[index];

while (temp) {

if (temp->key == key) {

printf("Key %d found in the hash table.\n", key);

return;

temp = temp->next;

printf("Key %d not found in the hash table.\n", key);

void deleteKey(int key) {

int index = hashFunction(key);

Node* temp = hashTable[index];

while (temp) {

if (temp->key == key) {

if (temp->prev == NULL) {

hashTable[index] = temp->next;

if (temp->next) {

temp->next->prev = NULL;
}

} else {

temp->prev->next = temp->next;

if (temp->next) {

temp->next->prev = temp->prev;

}
free(temp);
printf("Key %d deleted successfully.\n", key);

return;

}
 temp = temp->next;

printf("Key %d not found in the hash table.\n", key);

}
void display() {

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

printf("Index %d: ", i);

Node* temp = hashTable[i];

while (temp) {

printf("%d <-> ", temp->key);

temp = temp->next;

}
printf("NULL\n");

int main() {

int choice, key;

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

hashTable[i] = NULL;
}

while (1) {

printf("\nHash Table Operations:\n");

printf("1. Insert\n2. Search\n3. Delete\n4. Display\n5. Exit\n");

printf("Enter your choice: ");

scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter key to insert: ");

scanf("%d", &key);

insert(key);
 break;

case 2:

printf("Enter key to search: ");

scanf("%d", &key);
search(key);

break;

case 3:

printf("Enter key to delete: ");

scanf("%d", &key);

deleteKey(key);

break;

case 4:
display();

break;

case 5:

printf("Exiting program.\n");

return 0;

default:

printf("Invalid choice! Please try again.\n");

}

return 0;

}
Set C .
#include <stdio.h>
#include <stdlib.h>

#define TABLE_SIZE 1000

void findPairs(int arr[], int n, int S) {

int hashTable[TABLE_SIZE] = {0};

printf("Pairs that sum to %d:\n", S);

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

int complement = S - arr[i];

if (complement >= 0 && hashTable[complement] == 1) {

printf("[%d, %d]\n", arr[i], complement);

}
if (arr[i] >= 0) {

hashTable[arr[i]] = 1;

}
 }

int main() {

int arr[] = {3, 5, 2, -4, 8, 11};

int n = sizeof(arr) / sizeof(arr[0]);

int S = 7;

findPairs(arr, n, S);

return 0;