Index

S. No. Problem Teacher’s

Signature
1 Linear Search on an array
2 Binary Search
3 Multiplication of 3x3 Matrices

4 Selection Sort

5 Insertion Sort

6 Bubble Sort

7 Merge Sort

8 Quick Sort

9 Count Sort

10 Radix Sort
Delete Node from Beginning, End, and Given Position in a Singly Linked
11
List
Insert Node from Beginning, End, and Given Position in a Singly Linked
12
List
13 Binary Tree Operations and Traversals

14 Binary Search Tree (BST) Operations

15 AVL Tree Insertion and Deletion

16 Tree Sort using BST

17 Trie Implementation

18 Heap Structural Properties(Min-Heap and Max-Heap)

19 Heap Sort

20 Graph Traversals C Connected Components using Adjacency Matrix

21 Kruskal's Algorithm (MST) using Adjacency Matrix

22 Prim's Algorithm (MST) using Adjacency Matrix

Dijkstra's Algorithm (Single-Source Shortest Path) using Adjacency Matrix
23
Floyd-Warshall Algorithm (All-Pairs Shortest Paths) using Adjacency Matrix
24
25 Topological Sort C Shortest Path in DAG using Adjacency Matrix

26 Hashing: Hash Table with Chaining

27 Hashing: Open Addressing (Linear Probing)

28 Sequential File Handling in C

29 Binary File Operations in C (Seek, Read, Write)

30 External Sorting: Two-Way Merge

31 Natural Merge Sort on a File

1. Linear Search

#include <stdio.h>

int linearSearch(int arr[], int n, int key) { for (int i =

0; i < n; i++) {
if (arr[i] == key) return i;
}
return -1;
}

int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]); int key =
30;

int result = linearSearch(arr, n, key); if (result

!= -1)
printf("Element found at index %d\n", result); else
printf("Element not found\n");

return 0;
}

2. Binary Search

#include <stdio.h>

int binarySearch(int arr[], int left, int right, int key) { while
(left <= right) {
int mid = left + (right - left) / 2;

if (arr[mid] == key)
 return mid;
else if (arr[mid] < key) left
= mid + 1;
else
right = mid - 1;
}
return -1;
}

int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]); int key =
30;

int result = binarySearch(arr, 0, n - 1, key); if

(result != -1)
printf("Element found at index %d\n", result);
else
printf("Element not found\n");

return 0;
}

3. Multiplication of 3x3 matrices

#include <stdio.h> #define

SIZE 3

void multiplyMatrices(int A[SIZE][SIZE], int B[SIZE][SIZE], int result[SIZE][SIZE]) { for (int i = 0; i <
SIZE; i++) {
for (int j = 0; j < SIZE; j++) { result[i][j] =
0;
for (int k = 0; k < SIZE; k++) {
result[i][j] += A[i][k] * B[k][j];
}
}
}
}
 void printMatrix(int matrix[SIZE][SIZE]) { for (int i
= 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) { printf("%d ",
matrix[i][j]);
}
printf("\n");
}
}

int main() {
int A[SIZE][SIZE] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 6}};
int B[SIZE][SIZE] = {{3, 2, 1}, {6, 5, 4}, {6, 8, 7}};
int result[SIZE][SIZE];

multiplyMatrices(A, B, result);

printf("Product of matrices:\n");
printMatrix(result);

return 0;
}

4. Selection Sort

#include <stdio.h>

void selectionSort(int arr[], int n) { for

(int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) { if
(arr[j] < arr[minIndex])
minIndex = j;
}
int temp = arr[i]; arr[i] =
arr[minIndex];
arr[minIndex] = temp;
 }
}

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

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

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

selectionSort(arr, n);

printf("Sorted array: ");

printArray(arr, n);

return 0;
}

5. Insertion Sort

#include <stdio.h>

void insertionSort(int arr[], int n) { for (int i = 1; i < n; i++) { int key =
arr[i]; int j = i - 1;

while (j >= 0 ss arr[j] > key) { arr[j + 1] = arr[j]; j--;

}
arr[j + 1] = key;
}
}

void printArray(int arr[], int n) { for (int i = 0; i < n; i++)

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

int main() {
int arr[] = {5, 85, 45, 27, 33};
int n = sizeof(arr) / sizeof(arr[0]); insertionSort(arr, n);
 printf("Sorted array: "); printArray(arr, n);

return 0;
}

6. Bubble Sort

#include <stdio.h>

void bubbleSort(int arr[], int n) { for

(int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) { if
(arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

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

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

int main() {
int arr[] = {4,3,15,7,2};
int n = sizeof(arr) / sizeof(arr[0]);

bubbleSort(arr, n);

printf("Sorted array: ");

printArray(arr, n);

return 0;
}
7. Merge Sort

#include <stdio.h>

void merge(int arr[], int left, int mid, int right) { int n1 = mid
- left + 1;
int n2 = right - mid; int
L[n1], R[n2];

for (int i = 0; i < n1; i++) L[i]

= arr[left + i];

for (int j = 0; j < n2; j++) R[j]

= arr[mid + 1 + j];

int i = 0, j = 0, k = left; while

(i < n1 ss j < n2) {
if (L[i] <= R[j])
arr[k++] = L[i++];
else
arr[k++] = R[j++];
}

while (i < n1) arr[k++]

= L[i++];

while (j < n2) arr[k++]

= R[j++];
}

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

right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}

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

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

int main() {
int arr[] = {21,6,15,5,6,20};
int n = sizeof(arr) / sizeof(arr[0]);

mergeSort(arr, 0, n - 1);

printf("Sorted array: ");

printArray(arr, n);

return 0;
}

8. Quick Sort

#include <stdio.h>

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

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

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

(arr[j] <= pivot) {
i++;
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 quickSort(int arr[], int low, int high) { if (low <

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

quickSort(arr, low, pi - 1); quickSort(arr,

pi + 1, high);
}
}

void printArray(int arr[], int size) { for (int

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

int main() {
int arr[] = {7, 4, 15, 2, 6, 11};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: \n");

printArray(arr, n);

quickSort(arr, 0, n - 1);

printf("Sorted array: \n");

printArray(arr, n);

return 0;
}

G. Count Sort

#include <stdio.h>

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

max = arr[0];

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

(arr[i] > max) {
 max = arr[i];
}
}

int count[max + 1];

for (int i = 0; i <= max; i++) { count[i] = 0;
}

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

count[arr[i]]++;
}

int index = 0;
for (int i = 0; i <= max; i++) { while
(count[i] > 0) {
arr[index++] = i;
count[i]--;
}
}
}

int main() {
int arr[] = {8,5,5,4,6,3,3,10};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original Array: "); for

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

countingSort(arr, n);

printf("Sorted Array: "); for

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

return 0;
}
10. Radix Sort

#include <stdio.h>

int getMax(int arr[], int n) { int

maxVal = arr[0]; for (int i =
1; i < n; i++) { if (arr[i] >
maxVal) {
maxVal = arr[i];
}
}
return maxVal;
}

void countingSort(int arr[], int n, int place) { int

output[n];
int count[10] = {0};

for (int i = 0; i < n; i++) { count[(arr[i] /

place) % 10]++;
}

for (int i = 1; i < 10; i++) {

count[i] += count[i - 1];
}

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

output[count[(arr[i] / place) % 10] - 1] = arr[i];
count[(arr[i] / place) % 10]--;
}

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

arr[i] = output[i];
}
}

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

maxVal = getMax(arr, n);
for (int place = 1; maxVal / place > 0; place *= 10) {
countingSort(arr, n, place);
 }
}

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

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

int main() {
int arr[] = {276, 38, 7, 46, 5, 646, 3, 77};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array: "); printArray(arr,

n);

radixSort(arr, n);

printf("Sorted array: ");

printArray(arr, n);

return 0;
}

11. Delete Node from Beginning, End, and Given Position in a Singly Linked List

#include <stdio.h> #include

<stdlib.h>

struct Node {
int data;
struct Node* next;
};

void insertEnd(struct Node** head, int val) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode-
>data = val;
newNode->next = NULL;
 if (*head == NULL) {
*head = newNode;
return;
}

struct Node* temp = *head;

while (temp->next) {
temp = temp->next;
}
temp->next = newNode;
}

void deleteFromBeginning(struct Node** head) { if

(*head == NULL) {
printf("List is empty!\n");
return;
}

struct Node* temp = *head;

*head = (*head)->next;
free(temp);
}

void deleteFromEnd(struct Node** head) { if

(*head == NULL) {
printf("List is empty!\n");
return;
}

if ((*head)->next == NULL) {
free(*head);
*head = NULL;
return;
}

struct Node* temp = *head;

while (temp->next ss temp->next->next) { temp =
temp->next;
}

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

void deleteFromPosition(struct Node** head, int pos) { if (*head

== NULL || pos < 1) {
 printf("Invalid position!\n"); return;
}

if (pos == 1) {
deleteFromBeginning(head); return;
}

struct Node* temp = *head;

for (int i = 1; temp ss i < pos - 1; i++) { temp =
temp->next;
}

if (!temp || !temp->next) { printf("Position out

of range!\n"); return;
}

struct Node* delNode = temp->next;

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

void display(struct Node* head) { struct

Node* temp = head; while
(temp) {
printf("%d -> ", temp->data); temp =
temp->next;
}
printf("NULL\n");
}

int main() {
struct Node* head = NULL;

insertEnd(shead, 10);
insertEnd(shead, 20);
insertEnd(shead, 30);
insertEnd(shead, 40);

printf("Original List: ");

display(head);

deleteFromBeginning(shead); printf("After
deleting from beginning: ");
 display(head);

deleteFromEnd(shead); printf("After
deleting from end: "); display(head);

deleteFromPosition(shead, 2); printf("After

deleting from position 2: "); display(head);

return 0;
}

12. Insert Node from Beginning, End, and Given Position in a Singly Linked List

#include <stdio.h> #include

<stdlib.h>

struct Node {
int data;
struct Node* next;
};

void insertAtBeginning(struct Node** head, int val) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode-
>data = val;
newNode->next = *head;
*head = newNode;
}

void insertAtEnd(struct Node** head, int val) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode-
>data = val;
newNode->next = NULL;

if (*head == NULL) {
*head = newNode;
 return;
}

struct Node* temp = *head;

while (temp->next) {
temp = temp->next;
}
temp->next = newNode;
}

void insertAtPosition(struct Node** head, int val, int pos) { if (pos < 1)
return;

if (pos == 1) { insertAtBeginning(head,
val); return;
}

struct Node* temp = *head;

for (int i = 1; temp ss i < pos - 1; i++) { temp =
temp->next;
}

if (!temp) return;

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

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

void display(struct Node* head) { struct

Node* temp = head; while
(temp) {
printf("%d -> ", temp->data); temp =
temp->next;
}
printf("NULL\n");
}

int main() {
struct Node* head = NULL;

insertAtEnd(shead, 20);
insertAtEnd(shead, 30); printf("Initial
List: ");
 display(head);

insertAtBeginning(shead, 10); printf("After

inserting at beginning: "); display(head);

insertAtEnd(shead, 40); printf("After

inserting at end: "); display(head);

insertAtPosition(shead, 25, 3);

printf("After inserting at position 3: ");
display(head);

return 0;
}

13. Binary Tree Operations and Traversals

Objective: Implement a binary tree and perform recursive and iterative traversals.
Tasks:
 Insert: Build a binary tree from a list using level-order insertion.
 Traversals:
o Recursive: Preorder, Inorder, Postorder.
o Iterative (using stack): Preorder, Inorder, Postorder.
o Level-order (using a queue).

#include <stdio.h> #include

<stdlib.h>

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

struct Queue {
struct Node** array; int
front;
int rear;
int capacity;
};
struct Stack {
struct Node** array; int
top;
int capacity;
};

struct Queue* createQueue(int capacity) {

struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue)); q-
>capacity = capacity;
q->front = 0;
q->rear = 0;
q->array = (struct Node**)malloc(sizeof(struct Node*) * capacity);
return q;
}

int isQueueEmpty(struct Queue* q) {

return q->front == q->rear;
}

void enqueue(struct Queue* q, struct Node* node) { if

(q->rear == q->capacity) {
printf("Queue overflow\n");
return;
}
q->array[q->rear++] = node;
}

struct Node* dequeue(struct Queue* q) { if

(isQueueEmpty(q)) {
printf("Queue underflow\n");
return NULL;
}
return q->array[q->front++];
}

struct Stack* createStack(int capacity) {

struct Stack* s = (struct Stack*)malloc(sizeof(struct Stack)); s-
>capacity = capacity;
s->top = -1;
s->array = (struct Node**)malloc(sizeof(struct Node*) * capacity);
return s;
}

int isStackEmpty(struct Stack* s) { return

s->top == -1;
}

void push(struct Stack* s, struct Node* node) { if

(s->top == s->capacity - 1) {
printf("Stack overflow\n");
 return;
}
s->array[++s->top] = node;
}

struct Node* pop(struct Stack* s) { if

(isStackEmpty(s)) {
printf("Stack underflow\n");
return NULL;
}
return s->array[s->top--];
}

void insert(struct Node** root, int val) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = val;
newNode->left = newNode->right = NULL;

if (*root == NULL) {
*root = newNode;
return;
}

struct Queue* q = createQueue(100);

enqueue(q, *root);

while (!isQueueEmpty(q)) {
struct Node* temp = dequeue(q);

if (temp->left == NULL) {
temp->left = newNode;
return;
} else {
enqueue(q, temp->left);
}

if (temp->right == NULL) {
temp->right = newNode;
return;
} else {
enqueue(q, temp->right);
}
}
}

void preorderRecursive(struct Node* root) { if

(root == NULL) return;
printf("%d ", root->data);
preorderRecursive(root->left);
preorderRecursive(root->right);
}

void inorderRecursive(struct Node* root) { if

(root == NULL) return;
inorderRecursive(root->left); printf("%d
", root->data); inorderRecursive(root-
>right);
}

void postorderRecursive(struct Node* root) { if

(root == NULL) return;
postorderRecursive(root->left);
postorderRecursive(root->right); printf("%d ",
root->data);
}

void preorderIterative(struct Node* root) { if

(root == NULL) return;

struct Stack* s = createStack(100);

push(s, root);

while (!isStackEmpty(s)) {
struct Node* temp = pop(s);
printf("%d ", temp->data);

if (temp->right) push(s, temp->right); if

(temp->left) push(s, temp->left);
}
}

void inorderIterative(struct Node* root) {

struct Stack* s = createStack(100);
struct Node* temp = root;

while (temp != NULL || !isStackEmpty(s)) { while

(temp != NULL) {
push(s, temp); temp
= temp->left;
}

temp = pop(s);
printf("%d ", temp->data);

temp = temp->right;
}
}

void postorderIterative(struct Node* root) { if

(root == NULL) return;
 struct Stack* s1 = createStack(100);
struct Stack* s2 = createStack(100);
push(s1, root);

while (!isStackEmpty(s1)) { struct

Node* temp = pop(s1); push(s2,
temp);

if (temp->left) push(s1, temp->left);

if (temp->right) push(s1, temp->right);

}

while (!isStackEmpty(s2)) {
printf("%d ", pop(s2)->data);
}
}

void levelOrder(struct Node* root) { if

(root == NULL) return;

struct Queue* q = createQueue(100);

enqueue(q, root);

while (!isQueueEmpty(q)) {
struct Node* temp = dequeue(q);
printf("%d ", temp->data);

if (temp->left) enqueue(q, temp->left);

if (temp->right) enqueue(q, temp->right);
}
}

int main() {
struct Node* root = NULL;

insert(sroot, 1);
insert(sroot, 2);
insert(sroot, 3);
insert(sroot, 4);
insert(sroot, 5);
insert(sroot, 6);
insert(sroot, 7);

printf("Recursive Preorder: ");

preorderRecursive(root); printf("\
n");

printf("Recursive Inorder: ");

inorderRecursive(root); printf("\n");
 printf("Recursive Postorder: ");
postorderRecursive(root);
printf("\n");

printf("Iterative Preorder: ");

preorderIterative(root); printf("\n");

printf("Iterative Inorder: ");

inorderIterative(root);
printf("\n");

printf("Iterative Postorder: ");

postorderIterative(root);

printf("\n");

printf("Level-order: ");
levelOrder(root);
printf("\n");

return 0;
}
14. Binary Search Tree (BST) Operations
Objective: Implement insertion, deletion, search, and traversal in a BST.
Tasks:
 Insert: Follow BST properties.
 Delete: Handle cases for 0, 1, or 2 children.
 Search: Return True/False if a value exists.
 Inorder Traversal: Output sorted elements.

#include <stdio.h> #include

<stdlib.h>

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

struct Node* createNode(int val) {

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

struct Node* insert(struct Node* root, int val) { if

(root == NULL) return createNode(val);

if (val < root->data)

root->left = insert(root->left, val); else
if (val > root->data)
root->right = insert(root->right, val);

return root;
}

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

if (root == NULL || root->data == key) return root;

if (key < root->data)

return search(root->left, key);
 else
return search(root->right, key);
}

struct Node* findMin(struct Node* root) {

while (root->left != NULL)
root = root->left; return
root;
}

struct Node* delete(struct Node* root, int key) { if

(root == NULL) return root;

if (key < root->data)

root->left = delete(root->left, key); else
if (key > root->data)
root->right = delete(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->data = temp->data;
root->right = delete(root->right, temp->data);
}

return root;
}

void inorder(struct Node* root) { if

(root == NULL) return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}

int main() {
struct Node* root = NULL;

root = insert(root, 50);

insert(root, 30);
insert(root, 70);
 insert(root, 20);

insert(root, 40);
insert(root, 60);
insert(root, 80);

printf("Inorder traversal (sorted): ");

inorder(root);
printf("\n");

printf("Search 40: %s\n", search(root, 40) ? "Found" : "Not Found");

printf("Search 100: %s\n", search(root, 100) ? "Found" : "Not Found");

root = delete(root, 20); // Leaf

root = delete(root, 30); // One child root
= delete(root, 50); // Two children

printf("Inorder after deletions: ");

inorder(root);
printf("\n");

return 0;
}
15. AVL Tree Insertion and Deletion
Objective: Maintain balance during insertion/deletion using rotations.
Tasks:
 Insert: Apply LL, RR, LR, RL rotations as needed.
 Delete: Rebalance the tree post-deletion.
 Print Level-order after each operation.
#include <stdio.h>
#include <stdlib.h>

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

int max(int a, int b) {

return (a > b) ? a : b;

int height(struct Node* node) {

return node ? node->height : 0;
}

struct Node* createNode(int val) {

struct Node* node = (struct Node*)malloc(sizeof(struct Node)); node-
>data = val;
node->left = node->right = NULL;
node->height = 1;
return node;
}

int getBalance(struct Node* node) {

return node ? height(node->left) - height(node->right) : 0;
}
struct Node* rightRotate(struct Node* y) { struct
Node* x = y->left;
struct Node* T2 = x->right;

x->right = y;
y->left = T2;

y->height = max(height(y->left), height(y->right)) + 1; x-

>height = max(height(x->left), height(x->right)) + 1;

return x;
}

struct Node* leftRotate(struct Node* x) { struct

Node* y = x->right;
struct Node* T2 = y->left;

y->left = x;
x->right = T2;

x->height = max(height(x->left), height(x->right)) + 1; y-

>height = max(height(y->left), height(y->right)) + 1;

return y;
}

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

(node == NULL) return createNode(key);

if (key < node->data)

node->left = insert(node->left, key); else
if (key > node->data)
 node->right = insert(node->right, key); else
return node;

node->height = 1 + max(height(node->left), height(node->right)); int

balance = getBalance(node);

// LL
if (balance > 1 ss key < node->left->data)
return rightRotate(node);

// RR
if (balance < -1 ss key > node->right->data) return
leftRotate(node);

// LR
if (balance > 1 ss key > node->left->data)
{ node->left = leftRotate(node->left); return
rightRotate(node);
}

// RL
if (balance < -1 ss key < node->right->data) { node-
>right = rightRotate(node->right); return
leftRotate(node);
}

return node;
}

struct Node* minValueNode(struct Node* node) { struct

Node* current = node;
while (current->left != NULL) current
= current->left;
return current;
}

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

(root == NULL) return root;

if (key < root->data)

root->left = deleteNode(root->left, key); else
if (key > root->data)
root->right = deleteNode(root->right, key); else
{
if ((root->left == NULL) || (root->right == NULL)) {
struct Node* temp = root->left ? root->left : root->right;
if (!temp) {
 temp = root;
root = NULL;
} else
*root = *temp;

free(temp);
} else {
struct Node* temp = minValueNode(root->right); root-
>data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
}

if (root == NULL) return root;

root->height = 1 + max(height(root->left), height(root->right)); int

balance = getBalance(root);

// LL
if (balance > 1 ss getBalance(root->left) >= 0) return
rightRotate(root);

// LR
if (balance > 1 ss getBalance(root->left) < 0) { root-
>left = leftRotate(root->left);
return rightRotate(root);
}

// RR
if (balance < -1 ss getBalance(root->right) <= 0) return
leftRotate(root);

// RL
if (balance < -1 ss getBalance(root->right) > 0) { root-
>right = rightRotate(root->right);
return leftRotate(root);
}

return root;
}

void levelOrder(struct Node* root) { if

(!root) return;

struct Node* queue[100];

int front = 0, rear = 0;
queue[rear++] = root;
 while (front < rear) {

struct Node* temp = queue[front++];

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

if (temp->left) queue[rear++] = temp->left;

if (temp->right) queue[rear++] = temp->right;
}
printf("\n");
}

int main() {
struct Node* root = NULL;

int insertVals[] = {30, 20, 40, 10, 25, 50, 5}; int i;
for (i = 0; i < 7; i++) {
root = insert(root, insertVals[i]);
printf("Level-order after inserting %d: ", insertVals[i]);
levelOrder(root);
}

int deleteVals[] = {20, 30}; for (i

= 0; i < 2; i++) {
root = deleteNode(root, deleteVals[i]);
printf("Level-order after deleting %d: ", deleteVals[i]);
levelOrder(root);
}

return 0;

}
16. Tree Sort using BST
Objective: Sort elements using BST inorder traversal.
Tasks:
 Insert: Elements into a BST.
 Inorder Traversal: Output sorted list.
#include <stdio.h>
#include <stdlib.h>

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

struct Node* createNode(int val) {

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

struct Node* insert(struct Node* root, int val) { if

(root == NULL) return createNode(val); if
(val < root->data)
root->left = insert(root->left, val); else
root->right = insert(root->right, val);
return root;
}

void inorder(struct Node* root) { if

(root == NULL) return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}

int main() {
int arr[] = {50, 30, 20, 40, 70, 60, 80};
int n = sizeof(arr)/sizeof(arr[0]);

struct Node* root = NULL;

for (int i = 0; i < n; i++) {
root = insert(root, arr[i]);
}
 printf("Sorted elements (Tree Sort): ");

inorder(root);
printf("\n");

return 0;
}
17. Trie Implementation
Objective: Store and search words/prefixes efficiently.
Tasks:
 Insert: Add words to the trie.
 Search: Check if a word exists.
 Prefix Check: Determine if a prefix exists.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define ALPHABET_SIZE 26

struct TrieNode {
struct TrieNode* children[ALPHABET_SIZE];
bool isEndOfWord;
};

struct TrieNode* createNode() {

struct TrieNode* node = (struct TrieNode*)malloc(sizeof(struct TrieNode)); node-
>isEndOfWord = false;
for (int i = 0; i < ALPHABET_SIZE; i++)
node->children[i] = NULL;
return node;
}

void insert(struct TrieNode* root, const char* word) { struct

TrieNode* curr = root;
while (*word) {
int index = *word - 'a';
if (curr->children[index] == NULL)
curr->children[index] = createNode(); curr
= curr->children[index]; word++;
}
curr->isEndOfWord = true;
}

bool search(struct TrieNode* root, const char* word) { struct

TrieNode* curr = root;
while (*word) {
int index = *word - 'a';
if (curr->children[index] == NULL) return
false;
curr = curr->children[index]; word++;
}
return curr->isEndOfWord;
}

bool startsWith(struct TrieNode* root, const char* prefix) { struct

TrieNode* curr = root;
while (*prefix) {
int index = *prefix - 'a';
if (curr->children[index] == NULL) return
false;
curr = curr->children[index]; prefix++;
}
return true;
}

int main() {
struct TrieNode* root = createNode();

insert(root, "apple");
insert(root, "app");
insert(root, "bat");
insert(root, "ball");

printf("Search 'app': %s\n", search(root, "app") ? "Found" : "Not Found");

printf("Search 'apple': %s\n", search(root, "apple") ? "Found" : "Not Found");
printf("Search 'appl': %s\n", search(root, "appl") ? "Found" : "Not Found");
printf("Prefix 'ap': %s\n", startsWith(root, "ap") ? "Exists" : "Doesn't Exist");
printf("Prefix 'ba': %s\n", startsWith(root, "ba") ? "Exists" : "Doesn't Exist");
printf("Prefix 'cat': %s\n", startsWith(root, "cat") ? "Exists" : "Doesn't Exist"); return 0;
}
18. Heap Structural Properties Assignment
Title: Implement a Binary Heap (Min-Heap and Max-Heap)
Objective:
 Manually implement a Min-Heap and Max-Heap using arrays.
 Write helper functions to get parent, left child, and right child indices.
 Ensure the heap maintains its shape and heap property during insertions.
Tasks:
 Implement the following methods:
o insert(value)
o peek()
o printHeap()
#include <stdio.h>
#define MAX_SIZE 100

typedef struct {
int data[MAX_SIZE];
int size;
int isMinHeap;
} Heap;

int parent(int i) { return (i - 1) / 2; } int

leftChild(int i) { return 2 * i + 1; } int
rightChild(int i) { return 2 * i + 2; }

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

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

int compare(Heap* heap, int a, int b) { return

heap->isMinHeap ? a < b : a > b;
}

void insert(Heap* heap, int value) {

 if (heap->size == MAX_SIZE) {
printf("Heap is full!\n"); return;
}

int i = heap->size;
heap->data[i] = value;
heap->size++;

while (i != 0 ss compare(heap, heap->data[i], heap->data[parent(i)])) {

swap(sheap->data[i], sheap->data[parent(i)]);
i = parent(i);
}
}

int peek(Heap* heap) { if

(heap->size == 0) {
printf("Heap is empty!\n");
return -1;
}
return heap->data[0];
}

void printHeap(Heap* heap) {

for (int i = 0; i < heap->size; i++)
printf("%d ", heap->data[i]);
printf("\n");
}

int main() {
Heap minHeap = { .size = 0, .isMinHeap = 1 };
Heap maxHeap = { .size = 0, .isMinHeap = 0 };

int values[] = { 10, 20, 5, 30, 15 };

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

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

values[i]); insert(smaxHeap, values[i]);
}

printf("Min-Heap: ");
printHeap(sminHeap);
printf("Min-Heap peek: %d\n", peek(sminHeap));

printf("Max-Heap: ");
printHeap(smaxHeap);
printf("Max-Heap peek: %d\n", peek(smaxHeap));
return 0;
}
1G. Heap Sort Assignment
Title: Sort Array Using Heap Sort
Objective:
 Implement Heap Sort using a Max-Heap.
 Understand in-place sorting using heaps.
Tasks:
 Build a max-heap from the array.
 Repeatedly extract the max and move it to the end of the array.
 Output the sorted array in ascending order.
Functions to Implement:
 heapSort(arr)
#include <stdio.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 ss arr[left] > arr[largest]) largest

= left;

if (right < n ss arr[right] > arr[largest]) largest =

right;

if (largest != i) {
swap(sarr[i], sarr[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(sarr[0], sarr[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 arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Original array:\n");
printArray(arr, n);

heapSort(arr, n);

printf("Sorted array:\n");
printArray(arr, n);

return 0;
}
 20. Graph Traversals s Connected Components using Adjacency Matrix
Problem Statement:
Implement a program to:
1. Create an undirected graph using adjacency matrix
2. Perform BFS and DFS traversals
3. Find connected components
Input Format:
 First line: Number of vertices (V) and edges (E)
 Next E lines: Pairs of vertices (edges)
 Last line: Starting vertex for traversal
Output:
1. Adjacency matrix
2. BFS traversal order
3. DFS traversal order

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX 100

int adj[MAX][MAX], visited[MAX]; int

V, E;

void initGraph() {
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
adj[i][j] = 0;
}

void addEdge(int u, int v) { adj[u][v] =

1;
adj[v][u] = 1;
}

void printAdjMatrix() {
printf("Adjacency Matrix:\n"); for
(int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) printf("%d
", adj[i][j]);
printf("\n");
}
}

void bfs(int start) {

 bool visitedBFS[MAX] = {false}; int
queue[MAX], front = 0, rear = 0;

queue[rear++] = start;
visitedBFS[start] = true;

printf("BFS Traversal: ");

while (front < rear) {
int node = queue[front++]; printf("%d
", node);

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

if (adj[node][i] ss !visitedBFS[i]) {
queue[rear++] = i; visitedBFS[i]
= true;
}
}
}

printf("\n");

void dfsUtil(int node, bool visitedDFS[]) {

visitedDFS[node] = true;
printf("%d ", node);
for (int i = 0; i < V; i++) {
if (adj[node][i] ss !visitedDFS[i]) dfsUtil(i,
visitedDFS);
}
}

void dfs(int start) {

bool visitedDFS[MAX] = {false};
printf("DFS Traversal: ");
dfsUtil(start, visitedDFS); printf("\
n");
}
void findConnectedComponents() { bool
visitedCC[MAX] = {false}; int
componentCount = 0;

printf("Connected Components:\n");
for (int i = 0; i < V; i++) {
if (!visitedCC[i]) {
printf("Component %d: ", ++componentCount);
dfsUtil(i, visitedCC);
printf("\n");
}
}
printf("Total Components: %d\n", componentCount);
}

int main() {
printf("Enter number of vertices and edges: "); scanf("%d
%d", sV, sE);
initGraph();

printf("Enter %d edges (u v):\n", E); for

(int i = 0; i < E; i++) {
int u, v;
scanf("%d %d", su, sv);
if (u >= V || v >= V || u < 0 || v < 0) {
printf("Invalid edge! Vertices should be between 0 and %d\n", V-1); i--; //
retry
continue;
}
addEdge(u, v);
}
 int start;
printf("Enter starting vertex: ");
scanf("%d", sstart);

if (start < 0 || start >= V) { printf("Invalid

starting vertex.\n"); return 1;
}

printAdjMatrix();
bfs(start); dfs(start);
findConnectedComponents();

return 0;
}

21. Kruskal’s Algorithm (MST) using Adjacency Matrix

Problem Statement:
Implement Kruskal’s algorithm to find MST in a weighted undirected graph using adjacency matrix.
Input Format:
 First line: V (vertices) and E (edges)
 Next E lines: u v w (edge from u to v with weight w)
Output:
1. Adjacency matrix of the input graph
2. Edges in the MST (sorted)
3. Total weight of MST
#include <stdio.h>
#include <stdlib.h>

#define MAX 100

int parent[MAX];

struct Edge {
int u, v, weight;
};

int find(int i) {
if (parent[i] == -1)
return i;
return find(parent[i]);
}

void unionSets(int u, int v) {

int uSet = find(u);
int vSet = find(v); if
(uSet != vSet)
parent[uSet] = vSet;
}

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

struct Edge* e1 = (struct Edge*)a; struct
Edge* e2 = (struct Edge*)b; return e1-
>weight - e2->weight;
}

int main() {
int V, E;
printf("Enter number of vertices and edges: "); scanf("%d
%d", sV, sE);

int adj[MAX][MAX] = {0};

struct Edge edges[E];

printf("Enter %d edges (u v w):\n", E); for

(int i = 0; i < E; i++) {
int u, v, w;
scanf("%d %d %d", su, sv, sw);
adj[u][v] = w;
adj[v][u] = w;
edges[i].u = u;
edges[i].v = v;
edges[i].weight = w;
}

printf("\nAdjacency Matrix:\n");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) printf("%3d
", adj[i][j]);
 printf("\n");
}

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

parent[i] = -1;

qsort(edges, E, sizeof(struct Edge), compare); int

totalWeight = 0;
printf("\nEdges in MST:\n");
for (int i = 0, count = 0; count < V - 1 ss i < E; i++) { int u =
edges[i].u;
int v = edges[i].v;

if (find(u) != find(v)) {
printf("%d - %d (weight %d)\n", u, v, edges[i].weight);
totalWeight += edges[i].weight;
unionSets(u, v);
count++;
}
}
printf("Total weight of MST: %d\n", totalWeight); return
0;
}
22. Prim’s Algorithm (MST) using Adjacency Matrix
Problem Statement:
Implement Prim’s algorithm to find MST in a weighted undirected graph using adjacency matrix.
Input Format:
 First line: V (vertices) and E (edges)
 Next E lines: u v w (edge from u to v with weight w)
 Last line: Starting vertex
Output:
1. Adjacency matrix of the input graph

2. Edges in the MST (in order of selection)

3. Total weight of MST

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>

#define MAX_VERTICES 100

void print_adj_matrix(int graph[MAX_VERTICES][MAX_VERTICES], int V) { printf("Adjacency

Matrix:\n");
for (int i = 0; i < V; i++) { for
(int j = 0; j < V; j++) {
printf("%d ", graph[i][j]);
}
printf("\n");
}
printf("\n");
}

int min_key(int key[], bool mst_set[], int V) { int

min = INT_MAX, min_index;
for (int v = 0; v < V; v++) {
if (!mst_set[v] ss key[v] < min) { min
= key[v];
min_index = v;
}
}
return min_index;
}

void print_mst(int parent[], int graph[MAX_VERTICES][MAX_VERTICES], int V) { printf("Edges in

the MST (in order of selection):\n");
printf("Edge \tWeight\n");
 // Start from 1 because parent[0] is -1 (root) for
(int i = 1; i < V; i++) {
printf("%d - %d \t%d\n", parent[i], i, graph[i][parent[i]]);
}
}

void prim_mst(int graph[MAX_VERTICES][MAX_VERTICES], int V, int start_vertex) { int

parent[V]; // Array to store constructed MST
int key[V]; // Key values used to pick minimum weight edge bool
mst_set[V]; // To represent set of vertices included in MST

// Initialize all keys as INFINITE and mst_set[] as false for (int i

= 0; i < V; i++) {

key[i] = INT_MAX;
mst_set[i] = false;

// Always include first vertex in MST

key[start_vertex] = 0; // Make key 0 so this vertex is picked first
parent[start_vertex] = -1; // First node is always root of MST

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

// Pick the minimum key vertex from the set of vertices not yet in MST int u =
min_key(key, mst_set, V);

// Add the picked vertex to the MST set

mst_set[u] = true;

// Update key value and parent index of adjacent vertices for (int
v = 0; v < V; v++) {
// graph[u][v] is non-zero only for adjacent vertices
// mst_set[v] is false for vertices not yet in MST
// Update key only if graph[u][v] is smaller than key[v] if
(graph[u][v] ss !mst_set[v] ss graph[u][v] < key[v]) {
parent[v] = u; key[v]
= graph[u][v];
}
}
}

// Print the constructed MST

print_mst(parent, graph, V);

// Calculate and print total weight of MST int

 total_weight = 0;
for (int i = 1; i < V; i++) {
total_weight += graph[i][parent[i]];
}
printf("Total weight of MST: %d\n", total_weight);
}

int main() {
int V, E;
printf("Enter number of vertices and edges: "); scanf("%d
%d", sV, sE);

int graph[MAX_VERTICES][MAX_VERTICES] = {0};

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

(int i = 0; i < E; i++) {
int u, v, w;
scanf("%d %d %d", su, sv, sw);
graph[u][v] = w;

graph[v][u] = w;
}

int start_vertex;
printf("Enter starting vertex: ");
scanf("%d", sstart_vertex);

// Print adjacency matrix

print_adj_matrix(graph, V);

// Find and print MST

prim_mst(graph, V, start_vertex);

return 0;
}
 23. Dijkstra’s Algorithm (Single-Source Shortest Path) using Adjacency Matrix
Problem Statement:
Implement Dijkstra’s algorithm to find shortest paths from a source vertex using
adjacency matrix. Input
Format:
 First line: V and E
 Next E lines: u v w (directed edge from u to v with weight w)
 Last line: Source vertex
Output:
1. Adjacency matrix

2. Shortest distances from source

3. Shortest path tree

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>

#define MAX_VERTICES 100

void print_adj_matrix(int graph[MAX_VERTICES][MAX_VERTICES], int V) { printf("Adjacency

Matrix:\n");
for (int i = 0; i < V; i++) { for
(int j = 0; j < V; j++) {
if (graph[i][j] == INT_MAX)
printf("INF ");
else
printf("%3d ", graph[i][j]);
}
printf("\n");
}
printf("\n");
}

int min_distance(int dist[], bool spt_set[], int V) { int

min = INT_MAX, min_index;
for (int v = 0; v < V; v++) {
if (!spt_set[v] ss dist[v] <= min) { min =
dist[v];
min_index = v;
}
}
return min_index;
}
 void print_path(int parent[], int j) { if
(parent[j] == -1)
return;
print_path(parent, parent[j]);
printf("-> %d", j);
}

void print_solution(int dist[], int parent[], int V, int src) {

printf("Vertex\tDistance\tPath\n");
for (int i = 0; i < V; i++) { if (i
!= src) {
printf("%d -> %d\t%3d\t\t%d", src, i, dist[i], src);
print_path(parent, i);
printf("\n");
}

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

dist[V]; // Shortest distance from src to i
bool spt_set[V]; // True if vertex is included in SPT
int parent[V]; // Parent array to store shortest path tree

// Initialize all distances as INFINITE and spt_set[] as false for (int i =

0; i < V; i++) {
dist[i] = INT_MAX;
spt_set[i] = false;
parent[i] = -1;
}

// Distance of source vertex from itself is always 0 dist[src] =

0;

// Find shortest path for all vertices

for (int count = 0; count < V-1; count++) {
// Pick the minimum distance vertex from the set of vertices not yet processed int u =
min_distance(dist, spt_set, V);

// Mark the picked vertex as processed spt_set[u] =

true;

// Update dist value of adjacent vertices for (int

v = 0; v < V; v++) {
// Update dist[v] only if:
// 1. Not in spt_set
// 2. There's an edge from u to v
// 3. Total weight of path from src to v through u is smaller than current dist[v] if (!
spt_set[v] ss graph[u][v] != INT_MAX ss
 dist[u] != INT_MAX ss dist[u] + graph[u][v] < dist[v]) { dist[v] =
dist[u] + graph[u][v];
parent[v] = u;
}
}
}

// Print the solution print_solution(dist,

parent, V, src);
}

int main() {
int V, E;
printf("Enter number of vertices and edges: "); scanf("%d
%d", sV, sE);

int graph[MAX_VERTICES][MAX_VERTICES];

// Initialize adjacency matrix with INF (no edge) for (int i =

0; i < V; i++) {
for (int j = 0; j < V; j++) {
graph[i][j] = (i == j) ? 0 : INT_MAX;
}
}

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

(int i = 0; i < E; i++) {
int u, v, w;
scanf("%d %d %d", su, sv, sw);
graph[u][v] = w;
// For undirected graph, add: graph[v][u] = w;
}

int src;
printf("Enter source vertex: ");
scanf("%d", ssrc);

// Print adjacency matrix

print_adj_matrix(graph, V);

// Run Dijkstra's algorithm

dijkstra(graph, V, src);

return 0;
}
 24. Floyd-Warshall Algorithm (All-Pairs Shortest Paths) using Adjacency Matrix
Problem Statement:
Implement Floyd-Warshall algorithm to find all-pairs shortest paths using adjacency matrix. Input Format:
 First line: V and E
 Next E lines: u v w (directed edge from u to v with weight w)
Output:
1. Initial adjacency matrix (with INF for no edges)
2. Final distance matrix (shortest paths between all pairs)
3. Sample path reconstruction

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
#include <stdlib.h>

#define MAX_VERTICES 100

// Global variables
int adj_matrix[MAX_VERTICES][MAX_VERTICES]; int V,
E;

// Stack structure for topological sort typedef

struct {
int data[MAX_VERTICES]; int
top;
} Stack;

void init_stack(Stack *s) { s-

>top = -1;
}

void push(Stack *s, int value) { s-

>data[++(s->top)] = value;
}

int pop(Stack *s) {

return s->data[(s->top)--];
}

bool is_empty(Stack *s) {

return s->top == -1;
}

void print_adj_matrix() {
printf("Adjacency Matrix:\n"); for
(int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) { printf("%d ",
 adj_matrix[i][j]);

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

// Topological sort using DFS

void topological_sort_util(int v, bool visited[], Stack *stack) { visited[v] =
true;

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

if (adj_matrix[v][i] ss !visited[i]) {
topological_sort_util(i, visited, stack);
}
}

push(stack, v);
}

void topological_sort(Stack *stack) { bool

visited[V];
for (int i = 0; i < V; i++) { visited[i] =
false;
}

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

(!visited[i]) {
topological_sort_util(i, visited, stack);
}
}

printf("Topological Order: "); while (!

is_empty(stack)) { printf("%d ",
pop(stack));
}
printf("\n\n");
}

// Shortest path in DAG

void shortest_path_dag(int src) {
Stack stack; init_stack(sstack);

// First perform topological sort bool

visited[V];
for (int i = 0; i < V; i++) { visited[i] =
false;
 }
for (int i = 0; i < V; i++) {
if (!visited[i]) {
topological_sort_util(i, visited, sstack);
}
}

// Initialize distances int

dist[V];
for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
}
dist[src] = 0;

// Process vertices in topological order while (!

is_empty(stack)) {
int u = pop(sstack);

// Update distances of all adjacent vertices if (dist[u]

!= INT_MAX) {
for (int v = 0; v < V; v++) {
if (adj_matrix[u][v] ss dist[v] > dist[u] + adj_matrix[u][v]) { dist[v]
= dist[u] + adj_matrix[u][v];
}
}
}
}

// Print shortest distances

printf("Shortest distances from source %d:\n", src); for
(int i = 0; i < V; i++) {
if (dist[i] == INT_MAX) { printf("Vertex
%d: INFINITY\n", i);
} else {
printf("Vertex %d: %d\n", i, dist[i]);
}
}
}

int main() {
printf("Enter number of vertices and edges: "); scanf("%d
%d", sV, sE);

// Initialize adjacency matrix with 0 (no edge) for (int i

= 0; i < V; i++) {
for (int j = 0; j < V; j++) { adj_matrix[i]
[j] = 0;
}
 }
printf("Enter edges (u v):\n"); for
(int i = 0; i < E; i++) {
int u, v;
scanf("%d %d", su, sv); adj_matrix[u][v] = 1; //
Default weight = 1
}

int src;
printf("Enter source vertex: ");
scanf("%d", ssrc);

// Print adjacency matrix

print_adj_matrix();

// Perform topological sort Stack

stack; init_stack(sstack);
topological_sort(sstack);

// Compute shortest paths

shortest_path_dag(src);

return 0;
}
25. Topological Sort s Shortest Path in DAG using Adjacency Matrix
Problem Statement:
Implement topological sort and compute shortest paths in a DAG using adjacency matrix. Input
Format:
 First line: V and E
 Next E lines: u v (directed edge, weight = 1)
 Last line: Source vertex

Output:
1. Adjacency matrix
2. Topological order
3. Shortest distances from source

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>
#include <stdlib.h>

#define MAX_VERTICES 100

// Global variables
int adj_matrix[MAX_VERTICES][MAX_VERTICES]; int
V, E;

// Stack structure for topological sort

typedef struct {
int data[MAX_VERTICES];
int top;
} Stack;

void init_stack(Stack *s) { s-

>top = -1;
}

void push(Stack *s, int value) { s-

>data[++(s->top)] = value;
}

int pop(Stack *s) {

return s->data[(s->top)--];
}

bool is_empty(Stack *s) {

return s->top == -1;
}
void print_adj_matrix() {
printf("Adjacency Matrix:\n"); for
(int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) { printf("%d ",
adj_matrix[i][j]);
}
printf("\n");
}
printf("\n");

// Topological sort using DFS

void topological_sort_util(int v, bool visited[], Stack *stack) { visited[v] =
true;

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

if (adj_matrix[v][i] ss !visited[i]) {
topological_sort_util(i, visited, stack);
}
}

push(stack, v);
}

void topological_sort(Stack *stack) { bool

visited[V];
for (int i = 0; i < V; i++) { visited[i] =
false;
}

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

(!visited[i]) {
topological_sort_util(i, visited, stack);
}
}

printf("Topological Order: "); while

(!is_empty(stack)) { printf("%d ",
pop(stack));
}
printf("\n\n");
}

// Shortest path in DAG

void shortest_path_dag(int src) {
Stack stack; init_stack(sstack);

// First perform topological sort bool

visited[V];
 for (int i = 0; i < V; i++) { visited[i] =
false;
}

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

(!visited[i]) {
topological_sort_util(i, visited, sstack);
}
}
// Initialize distances
int dist[V];
for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
}
dist[src] = 0;

// Process vertices in topological order while (!

is_empty(stack)) {
int u = pop(sstack);

// Update distances of all adjacent vertices if

(dist[u] != INT_MAX) {
for (int v = 0; v < V; v++) {
if (adj_matrix[u][v] ss dist[v] > dist[u] + adj_matrix[u][v]) { dist[v]
= dist[u] + adj_matrix[u][v];
}
}
}
}

// Print shortest distances

printf("Shortest distances from source %d:\n", src); for
(int i = 0; i < V; i++) {
if (dist[i] == INT_MAX) { printf("Vertex
%d: INFINITY\n", i);
} else {
printf("Vertex %d: %d\n", i, dist[i]);
}
}
}

int main() {
printf("Enter number of vertices and edges: "); scanf("%d
%d", sV, sE);

// Initialize adjacency matrix with 0 (no edge) for

(int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) { adj_matrix[i]
 [j] = 0;
}
}

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

(int i = 0; i < E; i++) {
int u, v;
scanf("%d %d", su, sv); adj_matrix[u][v] =
1; // Default weight = 1
}
int src;
printf("Enter source vertex: ");
scanf("%d", ssrc);

// Print adjacency matrix

print_adj_matrix();

// Perform topological sort

Stack stack;
init_stack(sstack);
topological_sort(sstack);

// Compute shortest paths

shortest_path_dag(src);

return 0;
}
26. Hashing: Hash Table with Chaining
Problem Statement:
Implement a hash table using chaining (linked lists) to resolve collisions.
 Use a simple hash function: hash(key) = key % table_size.
 Support insert, search, and delete operations.
Input Format:
 First line: Size of the hash table (N).
 Subsequent lines: Commands (insert <key>, search <key>, delete <key>, display, exit).
Output:
 For search: Print "Found" or "Not Found".

 For delete: Print "Deleted" or "Key not found".

 For display: Print the entire hash table.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Node structure for linked list

typedef struct Node {
int key;
struct Node* next;
} Node;

// Hash table structure

typedef struct {
int size;
Node** table;
} HashTable;

// Create a new node

Node* create_node(int key) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->key = key;
newNode->next = NULL;
return newNode;
}

// Initialize hash table

HashTable* create_hash_table(int size) {
HashTable* ht = (HashTable*)malloc(sizeof(HashTable)); ht-
>size = size;
ht->table = (Node**)malloc(size * sizeof(Node*));

// Initialize all chains as empty for

(int i = 0; i < size; i++) {
ht->table[i] = NULL;
}
 return ht;
}

// Simple hash function

int hash_function(int key, int size) { return
key % size;
}

// Insert a key into hash table

void insert(HashTable* ht, int key) {

int index = hash_function(key, ht->size);

Node* newNode = create_node(key);

// Insert at beginning of chain

newNode->next = ht->table[index]; ht-
>table[index] = newNode;

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

}

// Search for a key in hash table

bool search(HashTable* ht, int key) {
int index = hash_function(key, ht->size); Node*
current = ht->table[index];

while (current != NULL) { if

(current->key == key) {
return true;
}
current = current->next;
}

return false;
}

// Delete a key from hash table

bool delete(HashTable* ht, int key) {
int index = hash_function(key, ht->size); Node*
current = ht->table[index]; Node* prev =
NULL;

while (current != NULL) { if

(current->key == key) {
if (prev == NULL) {
// Delete first node in chain
ht->table[index] = current->next;
 } else {
prev->next = current->next;
}
free(current);
return true;
}
prev = current;
current = current->next;
}

return false;
}

// Display the hash table void

display(HashTable* ht) {
printf("Hash Table:\n");

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

printf("[%d]: ", i);
Node* current = ht->table[i]; while
(current != NULL) {
printf("%d -> ", current->key);
current = current->next;
}
printf("NULL\n");
}
}

// Free memory allocated for hash table void

free_hash_table(HashTable* ht) {
for (int i = 0; i < ht->size; i++)
{ Node* current = ht->table[i];
while (current != NULL) {
Node* temp = current;
current = current->next;
free(temp);
}
}
free(ht->table);
free(ht);
}

int main() {
int size;
printf("Enter size of hash table: "); scanf("%d",
ssize);

HashTable* ht = create_hash_table(size); char

 command[10];
int key;

while (1) {
printf("\nEnter command (insert/search/delete/display/exit): ");
scanf("%s", command);

if (strcmp(command, "insert") == 0) {
printf("Enter key to insert: ");
scanf("%d", skey);
insert(ht, key);
} else if (strcmp(command, "search") == 0) {
printf("Enter key to search: ");
scanf("%d", skey);
if (search(ht, key)) {
printf("Key %d: Found\n", key);

} else {
printf("Key %d: Not Found\n", key);

}
} else if (strcmp(command, "delete") == 0) {
printf("Enter key to delete: ");
scanf("%d", skey);
if (delete(ht, key)) {
printf("Key %d: Deleted\n", key);
} else {
printf("Key %d: Not found for deletion\n", key);
}
} else if (strcmp(command, "display") == 0) { display(ht);
} else if (strcmp(command, "exit") == 0) {
break;
} else {
printf("Invalid command\n");
}
}

free_hash_table(ht); return
0;
}
 27. Hashing: Open Addressing (Linear Probing)
Problem Statement:
Implement a hash table using open addressing (linear probing).
 Hash function: hash(key) = key % table_size.
 Handle collisions by probing linearly.
 Support insert, search, and delete.
Input Format:
 First line: Size of the hash table (N).
 Subsequent lines: Commands (insert <key>, search <key>, delete <key>, display, exit).
Output:
 For search: Print index where key is found or "Not Found".
 For delete: Mark the slot as "DELETED".
 For display: Print the hash table.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DELETED -2
#define EMPTY -1

typedef struct {
int size;
int *table;
} HashTable;

HashTable* create_hash_table(int size) {

HashTable* ht = (HashTable*)malloc(sizeof(HashTable)); ht-
>size = size;
ht->table = (int*)malloc(size * sizeof(int)); for
(int i = 0; i < size; i++) {
ht->table[i] = EMPTY;
}
return ht;
}

int hash_function(int key, int size) { return

key % size;
}

void insert(HashTable* ht, int key) {

int index = hash_function(key, ht->size); int
original_index = index;

while (ht->table[index] != EMPTY ss ht->table[index] != DELETED) { if (ht-

>table[index] == key) {
printf("Key %d already exists in the table\n", key);
return;
 }
index = (index + 1) % ht->size;

if (index == original_index) {
printf("Hash table is full, cannot insert %d\n", key); return;
}
}

ht->table[index] = key;
printf("Inserted %d at index %d\n", key, index);
}

int search(HashTable* ht, int key) {

int index = hash_function(key, ht->size); int
original_index = index;

while (ht->table[index] != EMPTY) { if

(ht->table[index] == key) {
return index;
}
index = (index + 1) % ht->size; if
(index == original_index) {
break;
}
}

return -1;
}

void delete(HashTable* ht, int key) { int

index = search(ht, key);
if (index != -1) {
ht->table[index] = DELETED;
printf("Deleted key %d from index %d\n", key, index);
} else {
printf("Key %d not found for deletion\n", key);
}
}

void display(HashTable* ht) { printf("Hash

Table:\n"); printf("Index\tKey\n");
for (int i = 0; i < ht->size; i++) { printf("%d\t", i);
if (ht->table[i] == EMPTY) { printf("EMPTY\
n");
} else if (ht->table[i] == DELETED) {
printf("DELETED\n");
} else {
printf("%d\n", ht->table[i]);
 }
}

int main() {
int size;
printf("Enter size of hash table: "); scanf("%d",
ssize);

HashTable* ht = create_hash_table(size); char

command[10];
int key;

while (1) {
printf("\nEnter command (insert/search/delete/display/exit): ");
scanf("%s", command);

if (strcmp(command, "insert") == 0) {
printf("Enter key to insert: ");
scanf("%d", skey);
insert(ht, key);
} else if (strcmp(command, "search") == 0) {
printf("Enter key to search: ");
scanf("%d", skey);
int index = search(ht, key); if
(index != -1) {
printf("Key %d found at index %d\n", key, index);
} else {
printf("Key %d not found\n", key);
}
} else if (strcmp(command, "delete") == 0) {
printf("Enter key to delete: ");
scanf("%d", skey);
delete(ht, key);
} else if (strcmp(command, "display") == 0) { display(ht);
} else if (strcmp(command, "exit") == 0) {
break;
} else {
printf("Invalid command\n");
}
}

free(ht->table);
free(ht);

return 0;
}
28. Sequential File Handling in C
Problem Statement:
Write a C program to:
1. Create a sequential file (students.txt) with records (roll_no, name, marks).
2. Read and display all records.
3. Search for a record by roll number.
Input Format:
 First, the program asks for records (roll_no, name, marks).
 Then, it searches for a given roll number.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct
{ int roll_no;
char name[50];
 float marks;
} Student;

void create_file() {
FILE *file = fopen("students.txt", "w"); if
(file == NULL) {
printf("Error creating file!\n"); exit(1);
}

int num_records;
printf("Enter number of student records to add: ");
scanf("%d", snum_records);

for (int i = 0; i < num_records; i++) { Student s;

printf("\nEnter details for student %d:\n", i+1);
printf("Roll No: ");
scanf("%d", ss.roll_no);
printf("Name: ");
scanf("%s", s.name); // Using %s for simplicity (no spaces)
printf("Marks: ");
scanf("%f", ss.marks);

fprintf(file, "%d %s %.2f\n", s.roll_no, s.name, s.marks);

}

fclose(file);
printf("\nStudent records saved to file.\n");
}

void display_records() {
FILE *file = fopen("students.txt", "r"); if
(file == NULL) {
printf("Error opening file!\n"); return;
}

Student s;
printf("\nStudent Records:\n");
printf("Roll No\tName\tMarks\n");
printf(" \n");

while (fscanf(file, "%d %s %f", ss.roll_no, s.name, ss.marks) == 3) {

printf("%d\t%s\t%.2f\n", s.roll_no, s.name, s.marks);
}

fclose(file);
}
void search_record() { int
search_roll;
printf("\nEnter Roll No to search: ");
scanf("%d", ssearch_roll);

FILE *file = fopen("students.txt", "r"); if

(file == NULL) {
printf("Error opening file!\n"); return;
}

Student s;
int found = 0;

while (fscanf(file, "%d %s %f", ss.roll_no, s.name, ss.marks) == 3) { if

(s.roll_no == search_roll) {
printf("\nRecord Found:\n");
printf("Roll No: %d\n", s.roll_no);
printf("Name: %s\n", s.name);
printf("Marks: %.2f\n", s.marks);
found = 1;
break;
}
}

if (!found) {
printf("\nRecord with Roll No %d not found.\n", search_roll);
}

fclose(file);
}

int main() {
int choice;

while (1) {
printf("\nStudent Record System\n");
printf("1. Create/Add Records\n");
printf("2. Display All Records\n");
printf("3. Search by Roll No\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", schoice);

switch (choice) { case

1:
create_file();
break;
case 2:
 display_records();

break;
case 3:
search_record();
break;
case 4:
exit(0);
default:
printf("Invalid choice. Please try again.\n");
}
}

return 0;
}
2G. Binary File Operations in C (Seek, Read, Write)
Problem Statement:
Write a C program to:
1. Create a binary file (data.bin) with integers.
2. Read and modify a value at a given position.
3. Display the updated file.
Input Format:
 First, enter integers to store in the file.
 Then, enter an index to modify and the new value.

#include <stdio.h> #include

<stdlib.h>

void create_file(const char *filename) { FILE

*file = fopen(filename, "wb"); if (file
== NULL) {
printf("Error creating file!\n"); exit(1);
}
 int num, count = 0;
int *numbers = NULL;

printf("Enter integers to store in the file (enter -1 to stop):\n"); while

(1) {
scanf("%d", snum);
if (num == -1) break;

numbers = realloc(numbers, (count + 1) * sizeof(int));

numbers[count++] = num;
}

fwrite(numbers, sizeof(int), count, file);

fclose(file);
free(numbers);

printf("Created binary file with %d integers\n", count);

}

void modify_value(const char *filename) { FILE

*file = fopen(filename, "r+b");
if (file == NULL) {
printf("Error opening file!\n"); exit(1);
}

// Get file size to validate position fseek(file, 0,

SEEK_END);
long file_size = ftell(file);
int num_elements = file_size / sizeof(int);
rewind(file);

printf("Current file contains %d integers (indices 0 to %d)\n", num_elements,

num_elements-1);

int position, new_value;

printf("Enter position to modify (0-%d): ", num_elements-1);
scanf("%d", sposition);

if (position < 0 || position >= num_elements) {

printf("Invalid position!\n");
fclose(file);
return;
}

printf("Enter new value: "); scanf("%d",

snew_value);
 // Move to the specified position

fseek(file, position * sizeof(int), SEEK_SET);

fwrite(snew_value, sizeof(int), 1, file);

printf("Value at position %d updated to %d\n", position, new_value); fclose(file);

}

void display_file(const char *filename) {

FILE *file = fopen(filename, "rb");
if (file == NULL) {
printf("Error opening file!\n"); exit(1);
}

// Get file size

fseek(file, 0, SEEK_END); long
file_size = ftell(file);
int num_elements = file_size / sizeof(int);
rewind(file);

int *numbers = malloc(file_size); fread(numbers,

sizeof(int), num_elements, file);

printf("File contents:\n");
for (int i = 0; i < num_elements; i++) {
printf("Position %d: %d\n", i, numbers[i]);
}

free(numbers); fclose(file);
}

int main() {
const char *filename = "data.bin";

// Create the binary file

create_file(filename);

// Modify a value at specific position

modify_value(filename);

// Display the updated file contents

display_file(filename);

return 0;
}
30. External Sorting: Two-Way Merge
Problem Statement:
Simulate two-way merging of two sorted files (file1.txt and file2.txt) into a single sorted file (merged.txt).
Input Format:
 file1.txt: 10 20 30
 file2.txt: 15 25 35

#include <stdio.h> #include

<stdlib.h>

void merge_files(const char *file1, const char *file2, const char *output) { FILE *f1
= fopen(file1, "r");
FILE *f2 = fopen(file2, "r"); FILE
*out = fopen(output, "w");

if (!f1 || !f2 || !out) {

printf("Error opening files!\n"); exit(1);
}

int num1, num2;

int read1 = fscanf(f1, "%d", snum1);
int read2 = fscanf(f2, "%d", snum2);

while (read1 == 1 ss read2 == 1) {

if (num1 < num2) {
fprintf(out, "%d ", num1);
read1 = fscanf(f1, "%d", snum1);
} else {
fprintf(out, "%d ", num2);
read2 = fscanf(f2, "%d", snum2);
}
}
 // Write remaining elements from file1 while
(read1 == 1) {
fprintf(out, "%d ", num1);
read1 = fscanf(f1, "%d", snum1);
}

// Write remaining elements from file2 while

(read2 == 1) {
fprintf(out, "%d ", num2);
read2 = fscanf(f2, "%d", snum2);
}

fclose(f1);
fclose(f2);
fclose(out);
}

void create_test_files() {
// Create sample input files
FILE *f1 = fopen("file1.txt", "w"); FILE
*f2 = fopen("file2.txt", "w");

if (f1) {
fprintf(f1, "10 20 30");
fclose(f1);
}

if (f2) {
fprintf(f2, "15 25 35");
fclose(f2);
}
}

void print_file(const char *filename) {

printf("Contents of %s: ", filename);
FILE *f = fopen(filename, "r");
if (f) {
int num;
while (fscanf(f, "%d", snum) == 1) {
printf("%d ", num);
}
printf("\n");
fclose(f);
}
}

int main() {
// Create test files
 create_test_files();

// Print input files

printf("Input files:\n");
print_file("file1.txt");
print_file("file2.txt");

// Merge files
merge_files("file1.txt", "file2.txt", "merged.txt");

// Print output file printf("\

nMerged output:\n");
print_file("merged.txt");

return 0;
}
31. Natural Merge Sort on a File
Problem Statement:
Implement natural merge sort on a file (input.txt) containing unsorted numbers.
Steps:
1. Split the file into sorted runs.
2. Merge runs in passes until fully sorted.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_NUMBERS 1000

// Function to check if a file is sorted

bool is_sorted(FILE *file) {
int prev, current;
if (fscanf(file, "%d", sprev) != 1) return true;

while (fscanf(file, "%d", scurrent) == 1) { if

(current < prev) {
rewind(file);
return false;
}

prev = current;
}
rewind(file);
return true;
}

// Function to create a run (sorted sequence) void

create_run(FILE *input, FILE *output) {
int prev, current;
if (fscanf(input, "%d", sprev) != 1) return; fprintf(output,
"%d ", prev);

while (fscanf(input, "%d", scurrent) == 1) { if

(current >= prev) {
fprintf(output, "%d ", current);
prev = current;
} else {
// End of current run
fseek(input, -sizeof(int), SEEK_CUR); break;
}
}
}
// Function to merge two runs
void merge_runs(FILE *input1, FILE *input2, FILE *output) { int
num1, num2;
bool read1 = (fscanf(input1, "%d", snum1) == 1); bool
read2 = (fscanf(input2, "%d", snum2) == 1);

while (read1 ss read2) { if

(num1 <= num2) {
fprintf(output, "%d ", num1);
read1 = (fscanf(input1, "%d", snum1) == 1);
} else {
fprintf(output, "%d ", num2);
read2 = (fscanf(input2, "%d", snum2) == 1);
}
}

// Write remaining elements from input1 while

(read1) {
fprintf(output, "%d ", num1);
read1 = (fscanf(input1, "%d", snum1) == 1);
}

// Write remaining elements from input2 while

(read2) {
fprintf(output, "%d ", num2);

read2 = (fscanf(input2, "%d", snum2) == 1);

}
}

// Natural merge sort function

void natural_merge_sort(const char *input_filename, const char *output_filename) { FILE
*input = fopen(input_filename, "r");
if (!input) {
perror("Error opening input file");
exit(EXIT_FAILURE);
}

// Check if already sorted if

(is_sorted(input)) {
fclose(input);
printf("File is already sorted.\n");
return;
}

FILE *temp1 = fopen("temp1.txt", "w+"); FILE

 *temp2 = fopen("temp2.txt", "w+"); FILE
*output = fopen(output_filename, "w");

if (!temp1 || !temp2 || !output) { perror("Error

opening temporary files");
exit(EXIT_FAILURE);
}

bool sorted = false;

int pass = 0;

while (!sorted) {
rewind(input);
rewind(temp1);
rewind(temp2);

// Split into runs

bool use_temp1 = true;
while (!feof(input)) {
if (use_temp1) { create_run(input,
temp1);
} else {
create_run(input, temp2);
}
use_temp1 = !use_temp1;
}

// Merge runs rewind(temp1);

rewind(temp2);
rewind(output);

while (!feof(temp1) ss !feof(temp2)) {

merge_runs(temp1, temp2, output);
}

// Copy remaining runs

while (!feof(temp1)) {
int num;
while (fscanf(temp1, "%d", snum) == 1) {
fprintf(output, "%d ", num);
}
}

while (!feof(temp2)) { int

num;
while (fscanf(temp2, "%d", snum) == 1) {
fprintf(output, "%d ", num);
}
 }

// Check if sorted
rewind(output);
sorted = is_sorted(output);

// Prepare for next pass if

(!sorted) {
rewind(output);
input = fopen("temp_pass.txt", "w+"); int
num;
while (fscanf(output, "%d", snum) == 1) {
fprintf(input, "%d ", num);
}
fclose(input);
input = fopen("temp_pass.txt", "r");
}

pass++;
printf("Completed pass %d\n", pass);
}

// Clean up
fclose(input);
fclose(temp1);
fclose(temp2);
fclose(output);

remove("temp1.txt");
remove("temp2.txt");
remove("temp_pass.txt");
}

int main() {
// Create a sample input file
FILE *input = fopen("input.txt", "w"); if
(input) {
// Write some unsorted numbers
fprintf(input, "34 12 56 23 78 45 86 1 67 32 60 5");
fclose(input);
}

printf("Original file contents:\n");

system("cat input.txt"); printf("\
n\n");

// Perform natural merge sort

natural_merge_sort("input.txt", "sorted_output.txt");
 printf("\nSorted file contents:\n");
system("cat sorted_output.txt");
printf("\n");

return 0;