1. Construct an avl tree for a given set of elements which are stored in a file.

And implement insert and

delete operation on the constructed tree. Write contents of tree into a new file using in-order.

Source code:

#include <stdio.h>

#include <stdlib.h>

typedef struct TreeNode {

int data;

struct TreeNode *left;

struct TreeNode *right;

int height;

} TreeNode;

int max(int a, int b) {

return (a > b) ? a : b;

int getHeight(TreeNode *N) {

if (N == NULL)

return 0;

return N->height;

TreeNode* newNode(int data) {

TreeNode* node = (TreeNode*) malloc(sizeof(TreeNode));

node->data = data;

node->left = NULL;

node->right = NULL;

node->height = 1; // new node is initially added at leaf

return(node);

TreeNode *rightRotate(TreeNode *y) {

TreeNode *x = y->left;

TreeNode *T2 = x->right;

 x->right = y;

y->left = T2;

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

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

return x;

TreeNode *leftRotate(TreeNode *x) {

TreeNode *y = x->right;

TreeNode *T2 = y->left;

y->left = x;

x->right = T2;

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

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

return y;

int getBalance(TreeNode *N) {

if (N == NULL)

return 0;

return getHeight(N->left) - getHeight(N->right);

TreeNode* insert(TreeNode* node, int data) {

if (node == NULL)

return(newNode(data));

if (data < node->data)

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

else if (data > node->data)

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

else // Equal data not allowed in BST

return node;

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

 int balance = getBalance(node);

// Left Left Case

if (balance > 1 && data < node->left->data)

return rightRotate(node);

// Right Right Case

if (balance < -1 && data > node->right->data)

return leftRotate(node);

// Left Right Case

if (balance > 1 && data > node->left->data) {

node->left = leftRotate(node->left);

return rightRotate(node);

// Right Left Case

if (balance < -1 && data < node->right->data) {

node->right = rightRotate(node->right);

return leftRotate(node);

return node;

TreeNode * minValueNode(TreeNode* node) {

TreeNode* current = node;

while (current->left != NULL)

current = current->left;

return current;

void inOrderTraversal(TreeNode *root) {

if (root != NULL) {

inOrderTraversal(root->left);

printf("%c ", root->data);

inOrderTraversal(root->right);
 }

TreeNode* deleteNode(TreeNode* root, int data) {

if (root == NULL)

return root;

// Standard BST delete

if (data < root->data)

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

else if (data > root->data)

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

else {

if ((root->left == NULL) || (root->right == NULL)) {

TreeNode *temp = root->left ? root->left : root->right;

if (temp == NULL) {

temp = root;

root = NULL;

} else

*root = *temp;

free(temp);

} else {

TreeNode* temp = minValueNode(root->right);

root->data = temp->data;

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

if (root == NULL)

return root;

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

int balance = getBalance(root);

// Left Left Case

 if (balance > 1 && getBalance(root->left) >= 0)

return rightRotate(root);

// Left Right Case

if (balance > 1 && getBalance(root->left) < 0) {

root->left = leftRotate(root->left);

return rightRotate(root);

// Right Right Case

if (balance < -1 && getBalance(root->right) <= 0)

return leftRotate(root);

// Right Left Case

if (balance < -1 && getBalance(root->right) > 0) {

root->right = rightRotate(root->right);

return leftRotate(root);

return root;

int main() {

TreeNode *root = NULL;

char letters[] = {'C', 'B', 'E', 'A', 'D', 'H', 'G', 'F'};

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

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

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

inOrderTraversal(root);

printf("\nDeleting 'A'\n");

root = deleteNode(root, 'A');

inOrderTraversal(root);

return 0;

}
Output:

ABCDEFGH

Deleting 'A'

BCDEFGH

2. Construct B-tree an order of 5 with a set of 100 random elements stored in array. Implement searching,
insertion and deletion operations.

Source code: program for searching

#include <stdio.h>
#include <stdlib.h>
// Structure for a BST node
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Function to create a new node
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Function to insert a node into the BST
struct Node* insert(struct Node* root, int value) {
if (root == NULL) {
return createNode(value);
}
if (value < root->data) {
root->left = insert(root->left, value);
} else {
root->right = insert(root->right, value);
}
return root;
}
// Function to search for a value in the BST
struct Node* search(struct Node* root, int value) {
if (root == NULL || root->data == value) {
return root;
}

if (value < root->data) {

return search(root->left, value);
 } else {
return search(root->right, value);
}
}
int main() {
// Input BST: [8,3,10,1,6,null,14,null,null,4,7,13,null]
struct Node* root = NULL;
root = insert(root, 8);
root = insert(root, 3);
root = insert(root, 10);
root = insert(root, 1);
root = insert(root, 6);
root = insert(root, 4);
root = insert(root, 7);
root = insert(root, 14);
root = insert(root, 13);
int key = 6;
struct Node* result = search(root, key);
if (result != NULL) {
printf("Key %d found in the BST.\n", key);
} else {
printf("Key %d not found in the BST.\n", key);
}
return 0;
}
Output:
Key 6 found in the BST.

Program for insertion and deletion

#include<stdio.h>
#include<stdlib.h>
struct node {
int data;
struct node* left;
struct node* right;
};
struct node* addnode(int data) {
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
void nodedel(struct node* node) {
if (node == NULL) return;
nodedel(node->left);
nodedel(node->right);
 printf(" Node deleted %d\n", node->data);
free(node);
}
int main() {
struct node *root = addnode(9);
root->left = addnode(4);
root->right = addnode(15);
root->left->left = addnode(2);
root->left->right = addnode(6);
root->right->left = addnode(12);
root->right->right = addnode(17);
nodedel(root);
root = NULL;
printf(" Tree deleted ");
return 0;
}
Output:
Node deleted 2
Node deleted 6
Node deleted 4
Node deleted 12
Node deleted 17
Node deleted 15
Node deleted 9
Tree deleted
3. Construct min and max heap using arrays, delete any element and display the content of the heap

Source code:
Program for max heap deletion
#include <stdio.h>
int size = 0;
void swap(int *a, int *b)
{
int temp = *b;
*b = *a;
*a = temp;
}
void heapify(int array[], int size, int i)
{
if (size == 1)
{
printf("Single element in the heap");
}
else
{
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
 if (l < size && array[l] > array[largest])
largest = l;
if (r < size && array[r] > array[largest])
largest = r;
if (largest != i)
{
swap(&array[i], &array[largest]);
heapify(array, size, largest);
}
}
}
void insert(int array[], int newNum)
{
if (size == 0)
{
array[0] = newNum;
size += 1;
}
else
{
array[size] = newNum;
size += 1;
for (int i = size / 2 - 1; i >= 0; i--)
{
heapify(array, size, i);
}
}
}
void deleteRoot(int array[], int num)
{
int i;
for (i = 0; i < size; i++)
{
if (num == array[i])
break;
}
swap(&array[i], &array[size - 1]);
size -= 1;
for (int i = size / 2 - 1; i >= 0; i--)
{
heapify(array, size, i);
}
}
void printArray(int array[], int size)
{
for (int i = 0; i < size; ++i)
printf("%d ", array[i]);
printf("\n");
}
int main()
{
int array[10];
insert(array, 3);
insert(array, 4);
insert(array, 9);
insert(array, 5);
insert(array, 2);
printf("Max-Heap array: ");
printArray(array, size);
deleteRoot(array, 4);
printf("After deleting an element: ");
printArray(array, size);
}
Output:
Max-Heap array: 9 5 4 3 2
After deleting an element: 9 5 2 3

Program for Min Heap deletion:

#include <stdio.h>
#include <stdlib.h>
// Declare a heap structure
struct Heap {
int* arr;
int size;
int capacity;
};
// define the struct Heap name
typedef struct Heap heap;
// forward declarations
heap* createHeap(int capacity, int* nums);
void insertHelper(heap* h, int index);
void heapify(heap* h, int index);
int extractMin(heap* h);
void insert(heap* h, int data);
// Define a createHeap function
heap* createHeap(int capacity, int* nums)
{
// Allocating memory to heap h
heap* h = (heap*)malloc(sizeof(heap));
// Checking if memory is allocated to h or not
if (h == NULL) {
printf("Memory error");
return NULL;
}
// set the values to size and capacity
h->size = 0;
 h->capacity = capacity;
// Allocating memory to array
h->arr = (int*)malloc(capacity * sizeof(int));
// Checking if memory is allocated to h or not
if (h->arr == NULL) {
printf("Memory error");
return NULL;
}
int i;
for (i = 0; i < capacity; i++) {
h->arr[i] = nums[i];
}
h->size = i;
i = (h->size - 2) / 2;
while (i >= 0) {
heapify(h, i);
i--;
}
return h;
}
// Defining insertHelper function
void insertHelper(heap* h, int index)
{
// Store parent of element at index
// in parent variable
int parent = (index - 1) / 2;
if (h->arr[parent] > h->arr[index]) {
// Swapping when child is smaller
// than parent element
int temp = h->arr[parent];
h->arr[parent] = h->arr[index];
h->arr[index] = temp;
// Recursively calling insertHelper
insertHelper(h, parent);
}
}
void heapify(heap* h, int index)
{
int left = index * 2 + 1;
int right = index * 2 + 2;
int min = index;
// Checking whether our left or child element
// is at right index or not to avoid index error
if (left >= h->size || left < 0)
left = -1;
if (right >= h->size || right < 0)
right = -1;
// store left or right element in min if
 // any of these is smaller that its parent
if (left != -1 && h->arr[left] < h->arr[index])
min = left;
if (right != -1 && h->arr[right] < h->arr[min])
min = right;
// Swapping the nodes
if (min != index) {
int temp = h->arr[min];
h->arr[min] = h->arr[index];
h->arr[index] = temp;
// recursively calling for their child elements
// to maintain min heap
heapify(h, min);
}
}
int extractMin(heap* h)
{
int deleteItem;
// Checking if the heap is empty or not
if (h->size == 0) {
printf("\nHeap id empty.");
return -999;
}
// Store the node in deleteItem that
// is to be deleted.
deleteItem = h->arr[0];
// Replace the deleted node with the last node
h->arr[0] = h->arr[h->size - 1];
// Decrement the size of heap
h->size--;
// Call minheapify_top_down for 0th index
// to maintain the heap property
heapify(h, 0);
return deleteItem;
}
// Define a insert function
void insert(heap* h, int data)
{
// Checking if heap is full or not
if (h->size < h->capacity) {
// Inserting data into an array
h->arr[h->size] = data;
// Calling insertHelper function
insertHelper(h, h->size);
// Incrementing size of array
h->size++;
}
}
 void printHeap(heap* h)
{
for (int i = 0; i < h->size; i++) {
printf("%d ", h->arr[i]);
}
printf("\n");
}
int main()
{
int arr[9] = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
heap* hp = createHeap(9, arr);
printHeap(hp);
extractMin(hp);
printHeap(hp);
return 0;
}
Output:
123654789
25369478

4. Implement BFT and DFT for given graph , when graph is represented by
a.)Adjacency matrix b.)Adjacency lists

Source code:
a.)Adjacency matrix:
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
int visited[MAX];
void BFT(int graph[MAX][MAX], int n, int start) {
int queue[MAX], front = 0, rear = -1, i;
visited[start] = 1;
queue[++rear] = start;
while (front <= rear) {
int v = queue[front++];
printf("%d ", v);
for (i = 0; i < n; i++)
if (graph[v][i] && !visited[i]) {
queue[++rear] = i;
visited[i] = 1;
}
}
}
void DFT(int graph[MAX][MAX], int n, int start) {
int stack[MAX], top = -1, i;
visited[start] = 1;
stack[++top] = start;
while (top != -1) {
 int v = stack[top--];
printf("%d ", v);
for (i = 0; i < n; i++)
if (graph[v][i] && !visited[i]) {
stack[++top] = i;
visited[i] = 1;
}
}
}
int main() {
int graph[MAX][MAX] = {{0, 1, 1, 0, 0},
{1, 0, 0, 1, 0},
{1, 0, 0, 1, 1},
{0, 1, 1, 0, 1},
{0, 0, 1, 1, 0}}, n = 5;
int i;
BFT(graph, n, 0);
for (i = 0; i < n; i++) visited[i] = 0; // Reset visited
printf("\n");
DFT(graph, n, 0);
return 0;
}

Output:

BFT:
01234
DFT:
02431

b.)Adjacency lists:

#include <stdio.h>
#include <stdlib.h>
#define MAX 10
typedef struct Node {
int vertex;
struct Node* next;
} Node;
typedef struct {
Node* head;
} List;
void addEdge(List* graph, int u, int v) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->vertex = v;
newNode->next = graph[u].head;
graph[u].head = newNode;
}
void BFT(List* graph, int n, int start) {
int visited[MAX] = {0}, queue[MAX], front = 0, rear = -1;
visited[start] = 1;
queue[++rear] = start;
while (front <= rear) {
int v = queue[front++];
printf("%d ", v);
Node* temp = graph[v].head;
while (temp) {
if (!visited[temp->vertex]) {
queue[++rear] = temp->vertex;
visited[temp->vertex] = 1;
}
temp = temp->next;
}
}
}
void DFT(List* graph, int n, int start) {
int visited[MAX] = {0}, stack[MAX], top = -1;
visited[start] = 1;
stack[++top] = start;
while (top != -1) {
int v = stack[top--];
printf("%d ", v);
Node* temp = graph[v].head;
while (temp) {
if (!visited[temp->vertex]) {
stack[++top] = temp->vertex;
visited[temp->vertex] = 1;
}
temp = temp->next;
}
}
}
int main() {
List graph[MAX] = {0};
int n = 5;
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 0);
addEdge(graph, 1, 3);
addEdge(graph, 2, 0);
addEdge(graph, 2, 3);
addEdge(graph, 2, 4);
addEdge(graph, 3, 1);
addEdge(graph, 3, 2);
addEdge(graph, 3, 4);
addEdge(graph, 4, 2);
 addEdge(graph, 4, 3);
BFT(graph, n, 0);
printf("\n");
DFT(graph, n, 0);
return 0;
}
Output:
BFT:
02143
DFT:
01342

5.Write a program for finding the bi-connected components in a given graph.

Source code:
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
int disc[MAX], low[MAX], parent[MAX], time = 0, st[MAX][2], top = -1;
void BCCUtil(int u, int graph[MAX][MAX], int n) {
int v;
disc[u] = low[u] = ++time;
for (v = 0; v < n; v++) {
if (graph[u][v]) {
if (disc[v] == -1) {
parent[v] = u;
st[++top][0] = u;
st[top][1] = v;
BCCUtil(v, graph, n);
low[u] = (low[u] < low[v]) ? low[u] : low[v];
if (low[v] >= disc[u]) {
while (st[top][0] != u || st[top][1] != v) {
printf("%d-%d ", st[top][0], st[top][1]);
top--;
}
printf("%d-%d\n", st[top][0], st[top][1]);
top--;
}
} else if (v != parent[u] && disc[v] < low[u]) {
low[u] = disc[v];
st[++top][0] = u;
st[top][1] = v;
}
}
}
}
void findBCC(int graph[MAX][MAX], int n) {
int i;
 for (i = 0; i < n; i++) {
disc[i] = low[i] = parent[i] = -1;
}
for (i = 0; i < n; i++) {
if (disc[i] == -1) {
BCCUtil(i, graph, n);
}
}
}
int main() {
int graph[MAX][MAX] = {{0, 1, 1, 0, 0},
{1, 0, 1, 1, 0},
{1, 1, 0, 1, 1},
{0, 1, 1, 0, 1},
{0, 0, 1, 1, 0}}, n = 5;
findBCC(graph, n);
return 0;
}
Output:

4-2 3-4 3-1 2-3 2-0 1-2 0-1

6.Implement Quick sort and Merge sort and observe the execution time for various input
sizes(Average, Worst and Best Cases).
Source code:
Execution time for Quicksort and Merge sort
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void quickSort(int *a, int l, int h) {
if (l < h) {
int p = a[h], i = l - 1, j;
for (j = l; j < h; j++) if (a[j] < p) { i++; int t = a[i]; a[i] = a[j]; a[j] = t; }
int t = a[i + 1]; a[i + 1] = a[h]; a[h] = t;
quickSort(a, l, i); quickSort(a, i + 2, h);
}
}
void merge(int *a, int l, int m, int h) {
int n1 = m - l + 1, n2 = h - m, i, j, k;
int L[n1], R[n2];
for (i = 0; i < n1; i++) L[i] = a[l + i];
for (j = 0; j < n2; j++) R[j] = a[m + 1 + j];
for (i = 0, j = 0, k = l; i < n1 && j < n2; k++) a[k] = (L[i] <= R[j]) ? L[i++] : R[j++];
while (i < n1) a[k++] = L[i++]; while (j < n2) a[k++] = R[j++];
}

void mergeSort(int *a, int l, int h) {

if (l < h) {
 int m = l + (h - l) / 2;
mergeSort(a, l, m); mergeSort(a, m + 1, h); merge(a, l, m, h);
}
}
void measure(int *a, int n, void (*sort)(int*, int, int), const char *label) {
clock_t start = clock();
sort(a, 0, n - 1);
printf("%s Time: %f\n", label, (double)(clock() - start) / CLOCKS_PER_SEC);
}
int main() {
int n = 10000, a[n], i;
for (i = 0; i < n; i++) a[i] = i; // Best Case
measure(a, n, quickSort, "Quick Sort Best Case");
measure(a, n, mergeSort, "Merge Sort Best Case");
for (i = 0; i < n; i++) a[i] = rand() % 10000; // Average Case
measure(a, n, quickSort, "Quick Sort Average Case");
measure(a, n, mergeSort, "Merge Sort Average Case");
for (i = 0; i < n; i++) a[i] = n - i; // Worst Case
measure(a, n, quickSort, "Quick Sort Worst Case");
measure(a, n, mergeSort, "Merge Sort Worst Case");
return 0;
}

Output:

Quick Sort Best Case Time: 0.205982

Merge Sort Best Case Time: 0.000855
Quick Sort Average Case Time: 0.000837
Merge Sort Average Case Time: 0.000784
Quick Sort Worst Case Time: 0.141546
Merge Sort Worst Case Time: 0.000961

7.Compare the performance of single source shortest paths using greedy method when the graph is
represented by adjacency matrix and adjacency lists.
Source code:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>
#define V 5
#define INF INT_MAX
int minDistance(int dist[], int sptSet[]) {
int min = INF, min_index;
int v;
for (v = 0; v < V; v++)
if (!sptSet[v] && dist[v] <= min)
min = dist[v], min_index = v;
 return min_index;
}
void dijkstraMatrix(int graph[V][V], int src) {
int dist[V], sptSet[V];
int i, count, u, v;
for (i = 0; i < V; i++) dist[i] = INF, sptSet[i] = 0;
dist[src] = 0;
for (count = 0; count < V - 1; count++) {
u = minDistance(dist, sptSet);
sptSet[u] = 1;
for (v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v] && dist[u] != INF && dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
for (i = 0; i < V; i++) printf("Matrix: Vertex %d -> Distance %d\n", i, dist[i]);
}
void dijkstraList(int graph[V][V], int src) {
int dist[V], sptSet[V];
int i, count, u, v;
for (i = 0; i < V; i++) dist[i] = INF, sptSet[i] = 0;
dist[src] = 0;
for (count = 0; count < V - 1; count++) {
u = minDistance(dist, sptSet);
sptSet[u] = 1;
for (v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v] && dist[u] != INF && dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
for (i = 0; i < V; i++) printf("List: Vertex %d -> Distance %d\n", i, dist[i]);
}
int main() {
int graph[V][V] = {{0, 10, 0, 5, 0},
{10, 0, 1, 2, 0},
{0, 1, 0, 9, 4},
{5, 2, 9, 0, 2},
{0, 0, 4, 2, 0}};
clock_t start, end;
start = clock();
dijkstraMatrix(graph, 0);
end = clock();
printf("Matrix Time: %f\n", (double)(end - start) / CLOCKS_PER_SEC);
start = clock();
dijkstraList(graph, 0);
end = clock();
printf("List Time: %f\n", (double)(end - start) / CLOCKS_PER_SEC);
return 0;
}
Output:

Matrix: Vertex 0 -> Distance 0

Matrix: Vertex 1 -> Distance 7
Matrix: Vertex 2 -> Distance 8
Matrix: Vertex 3 -> Distance 5
Matrix: Vertex 4 -> Distance 7
Matrix Time: 0.000099

List: Vertex 0 -> Distance 0

List: Vertex 1 -> Distance 7
List: Vertex 2 -> Distance 8
List: Vertex 3 -> Distance 5
List: Vertex 4 -> Distance 7
List Time: 0.000026

8.Implement Job sequencing with deadlines using greedy strategy.

Source code:

#include <stdio.h>
#include <stdlib.h>
typedef struct {
char id;
int deadline, profit;
} Job;
int cmp(const void *a, const void *b) {
return ((Job*)b)->profit - ((Job*)a)->profit;
}
void jobSequencing(Job jobs[], int n) {
qsort(jobs, n, sizeof(Job), cmp);
int result[n];
int slot[n];
int i, j;
for (i = 0; i < n; i++) {
slot[i] = 0;
}
for (i = 0; i < n; i++) {
for (j = (jobs[i].deadline < n ? jobs[i].deadline : n) - 1; j >= 0; j--) {
if (!slot[j]) {
result[j] = i;
slot[j] = 1;
break;
}
}
}
for (i = 0; i < n; i++) {
if (slot[i]) {
printf("%c ", jobs[result[i]].id);
 }
}
}
int main() {
Job jobs[] = {{'a', 2, 100}, {'b', 1, 19}, {'c', 2, 27}, {'d', 1, 25}, {'e', 3, 15}};
int n = sizeof(jobs) / sizeof(jobs[0]);
printf("Scheduled Jobs: ");
jobSequencing(jobs, n);
return 0;
}
Output:
Scheduled Jobs: c a e

9.Write a program to solve 0/1 knapsack problem using dynamic programming.

// C Program for 0-1 KnapSack Problem using Recursion

Source code:

#include <stdio.h>
// Function to find maximum between two numbers
int max(int a, int b)
{
if (a > b)
return a;
return b;
}
// Returns the maximum value that can be put in a knapsack
// of capacity W
int knapsackRecursive(int W, int wt[], int val[], int n)
{
// Base Case
if (n == 0 || W == 0)
return 0;
if (wt[n - 1] > W)
return knapsackRecursive(W, wt, val, n - 1);
else
return max(val[n - 1]
+ knapsackRecursive(W - wt[n - 1],
wt, val, n - 1),
knapsackRecursive(W, wt, val, n - 1));
}
// Driver Code
int main()
{
int values[] = { 3, 4, 5, 6 };
int weight[] = { 2, 3, 4, 5 };
int W = 8;
// Find the number of items
 int n = sizeof(values) / sizeof(values[0]);

// Output the maximum profit for the knapSack

printf("Maximum value that can be put in knapsack: %d\n",knapsackRecursive(W, weight, values,
n));
return 0;
}

Output:
Maximum value that can be put in knapsack: 10

10.Implement N-Queens Problem Using Backtracking.

Source code:

#include <stdio.h>
#include <stdbool.h>
#define N 4
void printSolution(int board[N][N]) {
int i, j;
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++)
printf(" %d ", board[i][j]);
printf("\n");
}
}
bool isSafe(int board[N][N], int row, int col) {
int i, j;
for (i = 0; i < col; i++)
if (board[row][i]) return false;
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j]) return false;
for (i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j]) return false;
return true;
}
bool solveNQUtil(int board[N][N], int col) {
int i;
if (col >= N) return true;
for (i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQUtil(board, col + 1)) return true;
board[i][col] = 0;
}
}
return false;
}
bool solveNQ() {
 int board[N][N] = {0};
if (!solveNQUtil(board, 0)) {
printf("Solution does not exist");
return false;
}
printSolution(board);
return true;
}
int main() {
solveNQ();
return 0;
}
Output:
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0

11. Use Backtracking strategy to solve 0/1 Knapsack problem

Source code:

#include <stdio.h>

// Define a struct to hold information about each item

typedef struct {

int weight;

int value;

} Item;

int max(int a, int b) {

return (a > b) ? a : b;

void knapsack(Item items[], int n, int capacity, int index, int currentWeight, int currentValue, int*
maxValue) {

if (index == n) {

if (currentWeight <= capacity && currentValue > *maxValue) {

*maxValue = currentValue;

return;
 }

// Exclude the current item and move to the next

knapsack(items, n, capacity, index + 1, currentWeight, currentValue, maxValue);

// Include the current item and move to the next

if (currentWeight + items[index].weight <= capacity) {

knapsack(items, n, capacity, index + 1, currentWeight + items[index].weight, currentValue +

items[index].value, maxValue);

int main() {

Item items[] = {{2, 3}, {3, 10}, {10, 5}, {5, 6}};

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

int capacity = 5;

int maxValue = 0;

knapsack(items, n, capacity, 0, 0, 0, &maxValue);

printf("Maximum value that can be obtained: %d\n", maxValue);

return 0;

Output:

Maximum value that can be obtained: 13

12.Implement Travelling Sales Person problem using branch and bound approach

Source code:

#include <stdio.h>

#include <limits.h>

#define N 4 // Number of cities

#define INF INT_MAX

int tsp(int graph[N][N], int path[], int visited[], int pos, int count, int cost, int answer) {

int i; // Declare loop variable outside the for loop

 if (count == N && graph[pos][0]) {

answer = (answer < cost + graph[pos][0]) ? answer : cost + graph[pos][0];

return answer;

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

if (!visited[i] && graph[pos][i]) {

visited[i] = 1;

answer = tsp(graph, path, visited, i, count + 1, cost + graph[pos][i], answer);

visited[i] = 0;

return answer;

int main() {

int graph[N][N] = {

{0, 10, 15, 20},

{10, 0, 35, 25},

{15, 35, 0, 30},

{20, 25, 30, 0}

};

int path[N + 1];

int visited[N] = {0};

visited[0] = 1;

int answer = INF;

answer = tsp(graph, path, visited, 0, 1, 0, answer);

printf("The minimum cost of the tour is: %d\n", answer);

return 0;

Output:

The minimum cost of the tour is: 80

 Additional Programs

1.Implementation AVL Tree insertion

Source code:

#include <stdio.h>

#include <stdlib.h>

// AVL tree node structure

struct Node {

int key;

struct Node *left;

struct Node *right;

int height;

};

// Function to get maximum of two integers

int max(int a, int b) {

return (a > b) ? a : b;

// Function to get height of the tree

int height(struct Node *N) {

if (N == NULL)

return 0;

return N->height;

// Function to create a new AVL tree node

struct Node *newNode(int key) {

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

node->key = key;

node->left = NULL;

node->right = NULL;

node->height = 1; // New node is initially added at leaf

return node;

// Function to right rotate subtree rooted with y

struct Node *rightRotate(struct Node *y) {

struct Node *x = y->left;

struct Node *T2 = x->right;

// Perform rotation

x->right = y;

y->left = T2;

// Update heights

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

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

// Return new root

return x;

// Function to left rotate subtree rooted with x

struct Node *leftRotate(struct Node *x) {

struct Node *y = x->right;

struct Node *T2 = y->left;

 // Perform rotation

y->left = x;

x->right = T2;

// Update heights

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

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

// Return new root

return y;

// Get Balance factor of node N

int getBalance(struct Node *N) {

if (N == NULL)

return 0;

return height(N->left) - height(N->right);

// Recursive function to insert a key in the subtree rooted with node and returns the new root of the
subtree

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

// Perform the normal BST insertion

if (node == NULL)

return newNode(key);

if (key < node->key)

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

else if (key > node->key)

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

else // Equal keys are not allowed in BST

return node;

// Update height of this ancestor node

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

// Get the balance factor of this ancestor node to check whether this node became unbalanced

int balance = getBalance(node);

// If this node becomes unbalanced, then there are 4 cases

// Left Left Case

if (balance > 1 && key < node->left->key)

return rightRotate(node);

// Right Right Case

if (balance < -1 && key > node->right->key)

return leftRotate(node);

// Left Right Case

if (balance > 1 && key > node->left->key) {

node->left = leftRotate(node->left);

return rightRotate(node);

// Right Left Case

if (balance < -1 && key < node->right->key) {

node->right = rightRotate(node->right);

return leftRotate(node);
 }

// Return the (unchanged) node pointer

return node;

// Function to find the minimum value node in a given AVL tree

struct Node * minValueNode(struct Node* node) {

struct Node* current = node;

// Loop down to find the leftmost leaf

while (current->left != NULL)

current = current->left;

return current;

// Recursive function to delete a node with given key from AVL tree

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

// Perform standard BST delete

if (root == NULL)

return root;

// If the key to be deleted is smaller than the root's key, then it lies in left subtree

if (key < root->key)

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

// If the key to be deleted is greater than the root's key, then it lies in right subtree

else if (key > root->key)

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

// If key is same as root's key, then this is the node to be deleted

else {

// Node with only one child or no child

if ((root->left == NULL) || (root->right == NULL)) {

struct Node *temp = root->left ? root->left : root->right;

// No child case

if (temp == NULL) {

temp = root;

root = NULL;

} else // One child case

*root = *temp; // Copy the contents of the non-empty child

free(temp);

} else {

// Node with two children: Get the inorder successor (smallest in the right subtree)

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

// Copy the inorder successor's data to this node

root->key = temp->key;

// Delete the inorder successor

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

// If the tree had only one node then return

if (root == NULL)

return root;
// Update height of the current node

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

// Get the balance factor of this node to check whether this node became unbalanced

int balance = getBalance(root);

// If this node becomes unbalanced, then there are 4 cases

// Left Left Case

if (balance > 1 && getBalance(root->left) >= 0)

return rightRotate(root);

// Left Right Case

if (balance > 1 && getBalance(root->left) < 0) {

root->left = leftRotate(root->left);

return rightRotate(root);

// Right Right Case

if (balance < -1 && getBalance(root->right) <= 0)

return leftRotate(root);

// Right Left Case

if (balance < -1 && getBalance(root->right) > 0) {

root->right = rightRotate(root->right);

return leftRotate(root);

return root;
}

// Function to do in-order traversal of AVL tree and write nodes to file

void inOrder(struct Node *root, FILE *fp) {

if (root != NULL) {

inOrder(root->left, fp);

fprintf(fp, "%d ", root->key);

inOrder(root->right, fp);

// Function to read integers from a file and insert them into an AVL tree

struct Node *constructAVLTreeFromFile(char *filename) {

FILE *fp = fopen(filename, "r");

if (fp == NULL) {

fprintf(stderr, "Error opening file: %s\n", filename);

exit(EXIT_FAILURE);

struct Node *root = NULL;

int value;

// Read values from file and insert into AVL tree

while (fscanf(fp, "%d", &value) == 1) {

root = insert(root, value);

fclose(fp);

return root;

}
// Function to write contents of AVL tree to a file in-order

void writeAVLTreeToFile(struct Node *root, char *filename) {

FILE *fp = fopen(filename, "w");

if (fp == NULL) {

fprintf(stderr, "Error opening file: %s\n", filename);

exit(EXIT_FAILURE);

inOrder(root, fp);

fclose(fp);

// Function to deallocate memory allocated for AVL tree nodes

void freeAVLTree(struct Node *root) {

if (root != NULL) {

freeAVLTree(root->left);

freeAVLTree(root->right);

free(root);

// Main function

int main() {

char input_filename[] = "input.txt";

char output_filename[] = "output.txt";

// Construct AVL tree from file

struct Node *root = constructAVLTreeFromFile(input_filename);

 // Perform operations (insertions, deletions if needed)

// Write AVL tree contents to file in-order

writeAVLTreeToFile(root, output_filename);

// Deallocate memory for AVL tree

freeAVLTree(root);

return 0;

Output:

(Input.txt):

50 30 70 20 40 60 80

(output.txt - after insertion and deletion operations):

Initial Tree (Constructed from input.txt):

20 30 40 50 60 70 80

2. Quick sort program

#include <stdio.h>

// Function to swap two elements

void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
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++;
swap(&arr[i], &arr[j]);
 }
}
swap(&arr[i + 1], &arr[high]);
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);
}
}

// Function to print the array

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

int main() {
int arr[] = { 12, 17, 6, 25, 1, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
Output:
Sorted array:
1 5 6 12 17 25

3.Merge sort program

// C program for the implementation of merge sort

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

// Merges two subarrays of arr[].

// First subarray is arr[left..mid]
// Second subarray is arr[mid+1..right]
void merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;

// Create temporary arrays

int leftArr[n1], rightArr[n2];
 // Copy data to temporary arrays
for (i = 0; i < n1; i++)
leftArr[i] = arr[left + i];
for (j = 0; j < n2; j++)
rightArr[j] = arr[mid + 1 + j];

// Merge the temporary arrays back into arr[left..right]

i = 0;
j = 0;
k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
}
else {
arr[k] = rightArr[j];
j++;
}
k++;
}

// Copy the remaining elements of leftArr[], if any

while (i < n1) {
arr[k] = leftArr[i];
i++;
k++;
}

// Copy the remaining elements of rightArr[], if any

while (j < n2) {
arr[k] = rightArr[j];
j++;
k++;
}
}

// The subarray to be sorted is in the index range [left-right]

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

// Calculate the midpoint

int mid = left + (right - left) / 2;

// Sort first and second halves

mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
 // Merge the sorted halves
merge(arr, left, mid, right);
}
}

int main() {
int arr[] = { 86,54,22,47,72 };
int n = sizeof(arr) / sizeof(arr[0]);

// Sorting arr using mergesort

mergeSort(arr, 0, n - 1);

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

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

Output:

22 47 54 72 86

4.Implementation of strassens matrix multiplication

#include <stdio.h>

#include <stdlib.h>

#define MAX 2 // Can be adjusted for larger matrix sizes

void addMatrix(int A[MAX][MAX], int B[MAX][MAX], int C[MAX][MAX], int size) {

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

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

C[i][j] = A[i][j] + B[i][j];

void subMatrix(int A[MAX][MAX], int B[MAX][MAX], int C[MAX][MAX], int size) {

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

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

C[i][j] = A[i][j] - B[i][j];

}
void strassenMatrixMultiplication(int A[MAX][MAX], int B[MAX][MAX], int C[MAX][MAX], int size) {

if (size == 1) {

C[0][0] = A[0][0] * B[0][0];

return;

int halfSize = size / 2;

int tempA[halfSize][halfSize], tempB[halfSize][halfSize], tempC[halfSize][halfSize];

// Initializing submatrices

int A11[halfSize][halfSize], A12[halfSize][halfSize], A21[halfSize][halfSize], A22[halfSize][halfSize];

int B11[halfSize][halfSize], B12[halfSize][halfSize], B21[halfSize][halfSize], B22[halfSize][halfSize];

int C11[halfSize][halfSize], C12[halfSize][halfSize], C21[halfSize][halfSize], C22[halfSize][halfSize];

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

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

A11[i][j] = A[i][j];

A12[i][j] = A[i][j + halfSize];

A21[i][j] = A[i + halfSize][j];

A22[i][j] = A[i + halfSize][j + halfSize];

B11[i][j] = B[i][j];

B12[i][j] = B[i][j + halfSize];

B21[i][j] = B[i + halfSize][j];

B22[i][j] = B[i + halfSize][j + halfSize];

// P1 = (A11 + A22) * (B11 + B22)

 addMatrix(A11, A22, tempA, halfSize);

addMatrix(B11, B22, tempB, halfSize);

strassenMatrixMultiplication(tempA, tempB, C11, halfSize);

// P2 = (A21 + A22) * B11

addMatrix(A21, A22, tempA, halfSize);

strassenMatrixMultiplication(tempA, B11, C12, halfSize);

// P3 = A11 * (B12 - B22)

subMatrix(B12, B22, tempB, halfSize);

strassenMatrixMultiplication(A11, tempB, C21, halfSize);

// P4 = A22 * (B21 - B11)

subMatrix(B21, B11, tempB, halfSize);

strassenMatrixMultiplication(A22, tempB, C22, halfSize);

// Add results to get C matrix

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

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

C[i][j] = C11[i][j];

C[i][j + halfSize] = C21[i][j];

C[i + halfSize][j] = C12[i][j];

C[i + halfSize][j + halfSize] = C22[i][j];

void displayMatrix(int matrix[MAX][MAX], int 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[MAX][MAX], B[MAX][MAX], C[MAX][MAX];

int size = MAX;

// Input matrices

printf("Enter elements of matrix A (%dx%d):\n", size, size);

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

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

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

printf("Enter elements of matrix B (%dx%d):\n", size, size);

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

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

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

// Strassen's Matrix Multiplication

strassenMatrixMultiplication(A, B, C, size);

// Output the result

printf("Resulting matrix C after multiplication:\n");

 displayMatrix(C, size);

return 0;

Output:

Enter elements of matrix A (2x2):

Enter elements of matrix B (2x2):

Resulting matrix C after multiplication:

70 -4

42 -20

5. find the minimum and maximum element of the array

// C program for the above approach

#include <limits.h>

#include <stdio.h>

// Function to find the minimum and

// maximum element of the array

void findMinimumMaximum(int arr[], int N)

int i;

// variable to store the minimum

// and maximum element

 int minE = INT_MAX, maxE = INT_MIN;

// Traverse the given array

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

// If current element is smaller

// than minE then update it

if (arr[i] < minE) {

minE = arr[i];

// If current element is greater

// than maxE then update it

if (arr[i] > maxE) {

maxE = arr[i];

// Print the minimum and maximum element

printf("The minimum element is %d", minE);

printf("\n");

printf("The maximum element is %d", maxE);

return;

// Driver Code

int main()

{
 // Given array

int arr[] = { 1, 2, 4, -1 };

// length of the array

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

// Function call

findMinimumMaximum(arr, N);

return 0;

Output:

The minimum element is -1

The maximum element is 4

6.Program for implementing job sequencing with deadlines

#include <stdio.h>

#include <stdlib.h>

typedef struct {

int id; // Job ID

int deadline; // Deadline of the job

int profit; // Profit if the job is completed before or on the deadline

} Job;

// Comparator function to sort jobs by profit in descending order

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

Job *jobA = (Job *)a;

Job *jobB = (Job *)b;

return jobB->profit - jobA->profit; // Sort in descending order of profit

}
// Function to find the maximum deadline

int findMaxDeadline(Job jobs[], int n) {

int maxDeadline = jobs[0].deadline;

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

if (jobs[i].deadline > maxDeadline) {

maxDeadline = jobs[i].deadline;

return maxDeadline;

// Function to perform job sequencing with deadlines

void jobSequencing(Job jobs[], int n) {

// Sort jobs by descending order of profit

qsort(jobs, n, sizeof(Job), compare);

// Find the maximum deadline to determine the size of the result array

int maxDeadline = findMaxDeadline(jobs, n);

// Array to store the sequence of jobs and track free time slots

int result[maxDeadline];

int slot[maxDeadline]; // Boolean array to track free time slots

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

slot[i] = 0; // Initialize all slots as free

int totalProfit = 0; // Variable to store total profit

// Iterate over each job

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

// Find a free slot for this job (starting from the last possible slot)

for (int j = jobs[i].deadline - 1; j >= 0; j--) {

if (slot[j] == 0) { // If the slot is free

result[j] = jobs[i].id; // Assign job ID to the slot

slot[j] = 1; // Mark this slot as occupied

totalProfit += jobs[i].profit; // Add the job's profit

break;

// Print the result

printf("Job sequence for maximum profit:\n");

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

if (slot[i] == 1) {

printf("Job %d ", result[i]);

printf("\nTotal profit: %d\n", totalProfit);

// Main function

int main() {

int n;

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

scanf("%d", &n);

Job jobs[n];
 // Input jobs details

printf("Enter job details (ID Deadline Profit):\n");

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

printf("Job %d: ", i + 1);

scanf("%d %d %d", &jobs[i].id, &jobs[i].deadline, &jobs[i].profit);

// Perform job sequencing

jobSequencing(jobs, n);

return 0;

Output:

Enter the number of jobs: 5

Enter job details (ID Deadline Profit):

Job 1: 1 1 100

Job 2: 2 2 60

Job 3: 3 2 40

Job 4: 4 3 20

Job 5: 5 1 20

Job sequence for maximum profit:

Job 1 Job 2 Job 4

Total profit: 180

7. C program for Dijkstra's single source shortest path algorithm. The program is for adjacency matrix
representation of the graph

#include <limits.h>

#include <stdbool.h>

#include <stdio.h>
// Number of vertices in the graph

#define V 9

// A utility function to find the vertex with minimum

// distance value, from the set of vertices not yet included

// in shortest path tree

int minDistance(int dist[], bool sptSet[])

// Initialize min value

int min = INT_MAX, min_index;

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

if (sptSet[v] == false && dist[v] <= min)

min = dist[v], min_index = v;

return min_index;

// A utility function to print the constructed distance

// array

void printSolution(int dist[])

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

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

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

// Function that implements Dijkstra's single source

// shortest path algorithm for a graph represented using

// adjacency matrix representation

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

int dist[V]; // The output array. dist[i] will hold the

// shortest

// distance from src to i

bool sptSet[V]; // sptSet[i] will be true if vertex i is

// included in shortest

// path tree or shortest distance from src to i is

// finalized

// Initialize all distances as INFINITE and stpSet[] as

// false

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

dist[i] = INT_MAX, sptSet[i] = false;

// 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. u is always equal to

// src in the first iteration.

int u = minDistance(dist, sptSet);

// Mark the picked vertex as processed

sptSet[u] = true;
 // Update dist value of the adjacent vertices of the

// picked vertex.

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

// Update dist[v] only if is not in sptSet,

// there is an edge from u to v, and total

// weight of path from src to v through u is

// smaller than current value of dist[v]

if (!sptSet[v] && graph[u][v]

&& dist[u] != INT_MAX

&& dist[u] + graph[u][v] < dist[v])

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

// print the constructed distance array

printSolution(dist);

// driver's code

int main()

/* Let us create the example graph discussed above */

int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },

{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },

{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },

{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },

{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },

{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },

{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },

{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
 { 0, 0, 2, 0, 0, 0, 6, 7, 0 } };

// Function call

dijkstra(graph, 0);

return 0;

OUTPUT:

Vertex Distance from Source

0 0

1 4

2 12

3 19

4 21

5 11

6 9

7 8

8 14

8.KRUSKAL’S PROGRAM

// C code to implement Kruskal's algorithm

#include <stdio.h>

#include <stdlib.h>

// Comparator function to use in sorting

int comparator(const void* p1, const void* p2)

const int(*x)[3] = p1;

const int(*y)[3] = p2;

 return (*x)[2] - (*y)[2];

// Initialization of parent[] and rank[] arrays

void makeSet(int parent[], int rank[], int n)

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

parent[i] = i;

rank[i] = 0;

// Function to find the parent of a node

int findParent(int parent[], int component)

if (parent[component] == component)

return component;

return parent[component]

= findParent(parent, parent[component]);

// Function to unite two sets

void unionSet(int u, int v, int parent[], int rank[], int n)

// Finding the parents

u = findParent(parent, u);

v = findParent(parent, v);

if (rank[u] < rank[v]) {

 parent[u] = v;

else if (rank[u] > rank[v]) {

parent[v] = u;

else {

parent[v] = u;

// Since the rank increases if

// the ranks of two sets are same

rank[u]++;

// Function to find the MST

void kruskalAlgo(int n, int edge[n][3])

// First we sort the edge array in ascending order

// so that we can access minimum distances/cost

qsort(edge, n, sizeof(edge[0]), comparator);

int parent[n];

int rank[n];

// Function to initialize parent[] and rank[]

makeSet(parent, rank, n);

// To store the minimun cost

int minCost = 0;
 printf(

"Following are the edges in the constructed MST\n");

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

int v1 = findParent(parent, edge[i][0]);

int v2 = findParent(parent, edge[i][1]);

int wt = edge[i][2];

// If the parents are different that

// means they are in different sets so

// union them

if (v1 != v2) {

unionSet(v1, v2, parent, rank, n);

minCost += wt;

printf("%d -- %d == %d\n", edge[i][0],

edge[i][1], wt);

printf("Minimum Cost Spanning Tree: %d\n", minCost);

// Driver code

int main()

int edge[5][3] = { { 0, 1, 10 },

{ 0, 2, 6 },

{ 0, 3, 5 },

{ 1, 3, 15 },

{ 2, 3, 4 } };
 kruskalAlgo(5, edge);

return 0;

OUTPUT:

Following are the edges in the constructed MST

2 -- 3 == 4

0 -- 3 == 5

0 -- 1 == 10

Minimum Cost Spanning Tree: 19

9.PRIM’S PROGRAM

#include <stdio.h>

#include <limits.h>

#define V 5 // Number of vertices in the graph

// Function to find the vertex with the minimum key value

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

int min = INT_MAX, min_index;

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

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

min = key[v], min_index = v;

return min_index;

// Function to print the constructed MST

void printMST(int parent[], int graph[V][V]) {

int totalCost = 0;
 printf("Edge \tWeight\n");

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

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

totalCost += graph[i][parent[i]];

printf("Total cost of MST: %d\n", totalCost);

// Function to construct and print MST for a graph represented using adjacency matrix

void primMST(int graph[V][V]) {

int parent[V]; // Array to store constructed MST

int key[V]; // Key values to pick minimum weight edge

int mstSet[V]; // To represent set of vertices not yet included in MST

// Initialize all keys as INFINITE

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

key[i] = INT_MAX, mstSet[i] = 0;

// Always include first 1st vertex in MST.

key[0] = 0; // Make key 0 so that this vertex is picked as the first vertex

parent[0] = -1; // First node is always the root of MST

// The MST will have V vertices

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

// Pick the minimum key vertex from the set of vertices not yet included in MST

int u = minKey(key, mstSet);

// Add the picked vertex to the MST Set

mstSet[u] = 1;
 // Update key value and parent index of the adjacent vertices of the picked vertex.

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

// graph[u][v] is non-zero only for adjacent vertices of u

// mstSet[v] is false for vertices not yet included in MST

// Update the key only if graph[u][v] is smaller than key[v]

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

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

// Print the constructed MST

printMST(parent, graph);

int main() {

// Example graph represented as an adjacency matrix

int graph[V][V] = {

{0, 2, 0, 6, 0},

{2, 0, 3, 8, 5},

{0, 3, 0, 0, 7},

{6, 8, 0, 0, 9},

{0, 5, 7, 9, 0}

};

// Run Prim's algorithm

primMST(graph);

return 0;

Output:

Edge Weight
0-1 2

1-2 3

0-3 6

1-4 5

Total cost of MST: 16

10.GREEDY KNAPSACK PROGRAM

#include<stdio.h>

int main()

float weight[50],profit[50],ratio[50],Totalvalue,temp,capacity,amount;

int n,i,j;

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

scanf("%d",&n);

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

printf("Enter Weight and Profit for item[%d] :\n",i);

scanf("%f %f", &weight[i], &profit[i]);

printf("Enter the capacity of knapsack :\n");

scanf("%f",&capacity);

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

ratio[i]=profit[i]/weight[i];

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

for (j = i + 1; j < n; j++)

if (ratio[i] < ratio[j])

temp = ratio[j];
 ratio[j] = ratio[i];

ratio[i] = temp;

temp = weight[j];

weight[j] = weight[i];

weight[i] = temp;

temp = profit[j];

profit[j] = profit[i];

profit[i] = temp;

printf("Knapsack problems using Greedy Algorithm:\n");

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

if (weight[i] > capacity)

break;

else

Totalvalue = Totalvalue + profit[i];

capacity = capacity - weight[i];

if (i < n)

Totalvalue = Totalvalue + (ratio[i]*capacity);

printf("\nThe maximum value is :%f\n",Totalvalue);

return 0;

OUTPUT:

Enter the number of items :4

Enter Weight and Profit for item[0] :

12

Enter Weight and Profit for item[1] :

10

Enter Weight and Profit for item[2] :

20

Enter Weight and Profit for item[3] :

15

Enter the capacity of knapsack :

Knapsack problems using Greedy Algorithm:

The maximum value is :38.333332

11.PROGRAM FOR ALL PAIR SHOTEST PATH

1. /*

2. * C Program to find the shortest path between two vertices in a graph

3. * using the Floyd-Warshall algorithm

4. */

5.

6. #include <stdio.h>

7. #include <stdlib.h>

8.

9. void floydWarshall(int **graph, int n)

10. {

11. int i, j, k;
12. for (k = 0; k < n; k++)

13. {

14. for (i = 0; i < n; i++)

15. {

16. for (j = 0; j < n; j++)

17. {

18. if (graph[i][j] > graph[i][k] + graph[k][j])

19. graph[i][j] = graph[i][k] + graph[k][j];

20. }

21. }

22. }

23. }

24.

25. int main(void)

26. {

27. int n, i, j;

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

29. scanf("%d", &n);

30. int **graph = (int **)malloc((long unsigned) n * sizeof(int *));

31. for (i = 0; i < n; i++)

32. {

33. graph[i] = (int *)malloc((long unsigned) n * sizeof(int));

34. }

35. for (i = 0; i < n; i++)

36. {

37. for (j = 0; j < n; j++)

38. {

39. if (i == j)

40. graph[i][j] = 0;

41. else
42. graph[i][j] = 100;

43. }

44. }

45. printf("Enter the edges: \n");

46. for (i = 0; i < n; i++)

47. {

48. for (j = 0; j < n; j++)

49. {

50. printf("[%d][%d]: ", i, j);

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

52. }

53. }

54. printf("The original graph is:\n");

55. for (i = 0; i < n; i++)

56. {

57. for (j = 0; j < n; j++)

58. {

59. printf("%d ", graph[i][j]);

60. }

61. printf("\n");

62. }

63. floydWarshall(graph, n);

64. printf("The shortest path matrix is:\n");

65. for (i = 0; i < n; i++)

66. {

67. for (j = 0; j < n; j++)

68. {

69. printf("%d ", graph[i][j]);

70. }

71. printf("\n");
 72. }

73. return 0;

74. }

OUTPUT”

Enter the number of vertices: 4

Enter the edges:

[0][0]: 0

[0][1]: 12

[0][2]: 45

[0][3]: 2

[1][0]: 1

[1][1]: 0

[1][2]: 45

[1][3]: 32

[2][0]: 77

[2][1]: 43

[2][2]: 0

[2][3]: 2

[3][0]: 42

[3][1]: 3

[3][2]: 88

[3][3]: 0

The original graph is:

0 12 45 2

1 0 45 32

77 43 0 2

42 3 88 0

The shortest path matrix is:

0 5 45 2

1 0 45 3
6502

4 3 48 0

12.Bellman ford program

#include <limits.h>

#include <stdio.h>

#include <stdlib.h>

// Define maximum number of vertices

#define MAX_VERTICES 1000

// Define infinity for initialization

#define INF INT_MAX

// Define Edge structure

typedef struct {

int source;

int destination;

int weight;

} Edge;

// Define Bellman-Ford function

void bellmanFord(int graph[MAX_VERTICES][MAX_VERTICES],

int vertices, int edges, int source)

// Declare distance array

int distance[MAX_VERTICES];

// Initialize distances from source to all vertices as

// infinity

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

distance[i] = INF;
// Distance from source to itself is 0

distance[source] = 0;

// Relax edges V-1 times

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

// For each edge

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

// If the edge exists and the new distance is

// shorter

if (graph[j][0] != -1

&& distance[graph[j][0]] != INF

&& distance[graph[j][1]]

> distance[graph[j][0]]

+ graph[j][2])

// Update the distance

distance[graph[j][1]]

= distance[graph[j][0]] + graph[j][2];

// Check for negative cycles

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

// If a shorter path is found, there is a negative

// cycle

if (graph[i][0] != -1

&& distance[graph[i][0]] != INF

&& distance[graph[i][1]]

> distance[graph[i][0]] + graph[i][2]) {

printf("Negative cycle detected\n");

return;
 }

// Print shortest distances from source to all vertices

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

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

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

// Define main function

int main()

// Define number of vertices and edges

int vertices = 6;

int edges = 8;

// Define graph as an array of edges

int graph[MAX_VERTICES][MAX_VERTICES]

= { { 0, 1, 5 }, { 0, 2, 7 }, { 1, 2, 3 },

{ 1, 3, 4 }, { 1, 4, 6 }, { 3, 4, -1 },

{ 3, 5, 2 }, { 4, 5, -3 } };

// Call Bellman-Ford function with source vertex as 0

bellmanFord(graph, vertices, edges, 0);

return 0;

Output:

Vertex Distance from Source

0 0

1 5
2 7

3 9

4 8

5 5

13.travelling sales person problem

#include <stdio.h>

int matrix[25][25], visited_cities[10], limit, cost = 0;

int tsp(int c)

int count, nearest_city = 999;

int minimum = 999, temp;

for(count = 0; count < limit; count++)

if((matrix[c][count] != 0) && (visited_cities[count] == 0))

if(matrix[c][count] < minimum)

minimum = matrix[count][0] + matrix[c][count];

temp = matrix[c][count];

nearest_city = count;

if(minimum != 999)

cost = cost + temp;

return nearest_city;

}
void minimum_cost(int city)

int nearest_city;

visited_cities[city] = 1;

printf("%d ", city + 1);

nearest_city = tsp(city);

if(nearest_city == 999)

nearest_city = 0;

printf("%d", nearest_city + 1);

cost = cost + matrix[city][nearest_city];

return;

minimum_cost(nearest_city);

int main()

int i, j;

printf("Enter Total Number of Cities:\t");

scanf("%d", &limit);

printf("\nEnter Cost Matrix\n");

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

printf("\nEnter %d Elements in Row[%d]\n", limit, i + 1);

for(j = 0; j < limit; j++)

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

}
visited_cities[i] = 0;

printf("\nEntered Cost Matrix\n");

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

printf("\n");

for(j = 0; j < limit; j++)

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

printf("\n\nPath:\t");

minimum_cost(0);

printf("\n\nMinimum Cost: \t");

printf("%d\n", cost);

return 0;

Output:

Enter Total Number of Cities:4

Enter Cost Matrix

Enter 4 Elements in Row[1]

1234

Enter 4 Elements in Row[2]

5678

Enter 4 Elements in Row[3]

3456
Enter 4 Elements in Row[4]

9843

Entered Cost Matrix

1234

5678

3456

9843

Path: 1 4 3 2 1

Minimum Cost: 17