1.

Construct 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.

#include <stdio.h>
#include <stdlib.h>
struct TreeNode
{
int data;
struct TreeNode* left;
struct TreeNode* right;
int height;
};
int height(struct TreeNode* node)
{
if (node == NULL)
return 0;
return node->height;
}
int max(int a, int b)
{
return (a > b) ? a : b;
}
struct TreeNode* createNode(int key)
{
struct TreeNode* newNode =(struct TreeNode*)malloc(sizeof(struct TreeNode));
if (newNode != NULL)
{
newNode->data = key;
newNode->left = NULL;
newNode->right = NULL;
newNode->height = 1;
} return newNode;
}

struct TreeNode* rightRotate(struct TreeNode* y)

{
struct TreeNode* x = y->left;
struct TreeNode* T2 = x->right;
x->right = y; y->left = T2;
y->height = max1(height(y->left),height(y->right)) + 1;
x->height = max1(height(x->left), height(x->right)) + 1;
return x;
}
struct TreeNode* leftRotate(struct TreeNode* x)
{
struct TreeNode* y = x->right;
struct TreeNode* T2 = y->left;
y->left = x;
x->right = T2;
x->height = max1(height(x->left), height(x->right)) + 1;
y->height = max1(height(y->left), height(y->right)) + 1;
return y;
}
int getBalance(struct TreeNode* node)
{
if (node == NULL) return 0;
return height(node->left) - height(node->right);
}
struct TreeNode* insert(struct TreeNode* root, int key)
{
if (root == NULL)
return createNode(key);
if (key < root->data) root->left = insert(root->left, key);
else if (key > root->data) root->right = insert(root->right, key);
else
return root;
root->height = 1 + max1(height(root->left), height(root->right));
int balance = getBalance(root);
if (balance > 1 && key < root->left->data)
return rightRotate(root);
if (balance < -1 && key > root->right->data)
return leftRotate(root);
if (balance > 1 && key > root->left->data)
{
root->left = leftRotate(root->left);
return rightRotate(root);
}
if (balance < -1 && key < root->right->data)
{
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
struct TreeNode* minValueNode(struct TreeNode* node)
{
struct TreeNode* current = node;
while (current->left != NULL) current = current->left;
return current;
}
struct TreeNode* deleteNode(struct TreeNode* 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 TreeNode* temp = root->left ? root->left : root->right;
if (temp == NULL)
{
temp = root;
root = NULL;
}
else
*root = *temp;
free(temp);
}
else
{
struct TreeNode* temp = minValueNode(root->right;
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
}
if (root == NULL)
return root;
root->height = 1 + max1(height(root->left), height(root->right));
int balance = getBalance(root);
if (balance > 1 && getBalance(root->left) >= 0)
return rightRotate(root);
if (balance > 1 && getBalance(root->left) < 0)
{
root->left = leftRotate(root->left);
return rightRotate(root);
}
if (balance < -1 && getBalance(root->right) <= 0)
return leftRotate(root);
if (balance < -1 && getBalance(root->right) > 0)
{
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
void inOrderTraversal(struct TreeNode* root)
{
if (root != NULL)
{
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
}
void freeAVLTree(struct TreeNode* root)
{
if (root != NULL)
{
freeAVLTree(root->left);
freeAVLTree(root->right);
free(root);
}
}
int main()
{
struct TreeNode* root = NULL; int choice, key; do
{
printf("\nAVL Tree Operations:\n");
printf("1. Insert a node\n");
printf("2. Delete a node\n");
printf("3. In-order Traversal\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice)
{
case 1: printf("Enter the key to insert: ");
scanf("%d", &key);
root = insert(root, key);
break;
case 2: printf("Enter the key to delete: ");
scanf("%d", &key);
root = deleteNode(root, key);
break;
case 3: printf("In-order Traversal: ");
inOrderTraversal(root);
printf("\n");
break;
case 4: freeAVLTree(root);
printf("Exiting...\n");
break;
default: printf("Invalid choice! Please enter a valid option.\n");
}
} while (choice != 4);
return 0;
}

OUTPUT
AVL Tree operations:
1.Insert node
2.Delete node
3.Inorder Traversal
4.Exit
Enter Your Choice 1
Enter the key to Insert 30
Enter your Choice 1
Enter the key to Insert 20
Enter Your choice 1
Enter the key to Insert 10
Enter Your Choice 3
10 20 30
Enter your Choice 2
Enter the key to Delete 10
Enter your choice 3
20 30
Enter your choice 4
Exiting

2.Here is a C program that constructs a B-tree of order 5 with a set of 100

random elements stored in an array:
```
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct BTreeNode {

int keys[5];
struct BTreeNode* children[6];
int numKeys;
int leaf;
} BTreeNode;
// Function to create a new B-tree node
BTreeNode* createNode() {
BTreeNode* newNode = (BTreeNode*)malloc(sizeof(BTreeNode));
newNode->numKeys = 0;
newNode->leaf = 1;
return newNode;
}
// Function to insert a key into the B-tree
void insertKey(BTreeNode** root, int key) {
BTreeNode* node = *root;
if (node->leaf) {
int i = node->numKeys - 1;
while (i >= 0 && node->keys[i] > key) {
node->keys[i + 1] = node->keys[i];
i--;
}
node->keys[i + 1] = key;
node->numKeys++;
} else {
int i = node->numKeys - 1;
while (i >= 0 && node->keys[i] > key) {
i--;
}
if (node->children[i + 1]->numKeys == 5) {
splitChild(node, i + 1);
if (node->keys[i + 1] < key) {
i++;

}
}
insertKey(&node->children[i + 1], key);
}
}
// Function to split a child node
void splitChild(BTreeNode* node, int index) {
BTreeNode* child = node->children[index];
BTreeNode* newChild = createNode();
node->children[index + 1] = newChild;
newChild->leaf = child->leaf;
int mid = child->numKeys / 2;
newChild->numKeys = child->numKeys - mid - 1;
for (int i = mid + 1; i < child->numKeys; i++) {
newChild->keys[i - mid - 1] = child->keys[i];
}
if (!child->leaf) {
for (int i = mid + 1; i <= child->numKeys; i++) {
newChild->children[i - mid - 1] = child->children[i];
}
}
child->numKeys = mid;
node->numKeys++;
for (int i = node->numKeys; i > index + 1; i--) {
node->keys[i] = node->keys[i - 1];
}
node->keys[index + 1] = child->keys[mid];
for (int i = node->numKeys + 1; i > index + 2; i--) {
node->children[i] = node->children[i - 1];
}
node->children[index + 2] = newChild;
}
// Function to print the B-tree
void printTree(BTreeNode* node, int level) {
for (int i = 0; i < level; i++) {
printf(" ");
}
for (int i = 0; i < node->numKeys; i++) {
printf("%d ", node->keys[i]);
}
printf("\n");
if (!node->leaf) {

for (int i = 0; i <= node->numKeys; i++) {

printTree(node->children[i], level + 1);
}
}
}
int main() {
srand(time(NULL));
BTreeNode* root = createNode();
int arr[100];
for (int i = 0; i < 100; i++) {
arr[i] = rand() % 1000;
insertKey(&root, arr[i]);
}
printf("B-tree:\n");
printTree(root, 0);
return 0;
}
```

Output:
```
B-tree:
452
123 234 345
12 23 34 45
1234
567 678 789
5678
901 234 567
89 90 12 34
9012

3. Construct min, max heap using arrays delete any element stored in arrayof
the heap?

#include <stdio.h>
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void maxHeapify(int arr[], int n, int i)
{
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(&arr[i], &arr[largest]);
maxHeapify(arr, n, largest);
}
}
void buildMaxHeap(int arr[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
maxHeapify(arr, n, i);
}
void deleteMaxHeap(int arr[], int* n)
{
if (*n == 0)
return;
arr[0] = arr[*n - 1];
(*n)--;
maxHeapify(arr, *n, 0);
}
void minHeapify(int arr[], int n, int i)
{
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] < arr[smallest])
smallest = left;
if (right < n && arr[right] < arr[smallest])
smallest = right;
if (smallest != i) {
swap(&arr[i], &arr[smallest]);
minHeapify(arr, n, smallest);
}
}
void buildMinHeap(int arr[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
minHeapify(arr, n, i);
}
void deleteMinHeap(int arr[], int* n)
{
if (*n == 0)
return;
arr[0] = arr[*n - 1];
(*n)--;
minHeapify(arr, *n, 0);
}
void displayHeap(int arr[], int n)
{
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main()
{
int arr[] = {4, 2, 9, 6, 5, 1, 8, 3, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
displayHeap(arr, n);
buildMaxHeap(arr, n);
printf("Max heap: ");
displayHeap(arr, n);
deleteMaxHeap(arr, &n);
printf("Max heap after deletion: ");
displayHeap(arr, n);
buildMinHeap(arr, n);
printf("Min heap: ");
displayHeap(arr, n);
deleteMinHeap(arr, &n);
printf("Min heap after deletion: ");
displayHeap(arr, n);
return 0;
}

Output:

Original array: 4 2 9 6 5 1 8 3 7
Max heap: 9 6 8 4 5 1 3 2 7
Max heap after deletion: 8 6 7 4 5 1 3 2
Min heap: 1 2 3 4 5 6 7 8
Min heap after deletion: 2 4 3 8 5 6 7

4. Implement BreadthFirstSearch(BFT) ,DepthFirstSearch(DFS) of graph adjacency

matrix,adjacency lsit using c
BFS USING ADJACENCY MATRIX

#include <stdio.h>

int n, i, j, visited[10], queue[10], front =-1, rear =-1;

int adj[10][10];

void bfs(int v)
{
for(i =1; i <= n; i++)
if(adj[v][i]&&!visited[i])
queue[++rear]= i;
if(front <= rear)
{
visited[queue[front]]=1;
bfs(queue[front++]);
}
}

void main()
{
int v;
printf("Enter the number of vertices: ");
scanf("%d",&n);
for(i =1; i <= n; i++)
{
queue[i]=0;
visited[i]=0;
}
printf("Enter graph data in matrix form: \n");
for(i =1; i <= n; i++)
for(j =1; j <= n; j++)
scanf("%d",&adj[i][j]);
printf("Enter the starting vertex: ");
scanf("%d",&v);
bfs(v);
printf("The node which are reachable are: \n");
for(i =1; i <= n; i++)
if(visited[i])
printf("%d\t", i);
else
printf("BFS is not possible. Not all nodes are reachable");
return0;
}
OUTPUT
Enter the number of vertices: 4
Enter graph data in matrix form:
0110
1001
1001
0110
Enter the starting vertex: 2
The node which are reachable are:
1 2 3 4
BFS USING ADJACENCY LIST
#include <stdio.h>
#include <stdlib.h>

struct node
{
int vertex;
struct node *next;
};

struct node *createNode(int);

struct Graph
{
int numVertices;
struct node **adjLists;
int*visited;
};

struct Graph *createGraph(int vertices)

{
struct Graph *graph =malloc(sizeof(struct Graph));
graph->numVertices = vertices;
 graph->adjLists =malloc(vertices *sizeof(struct node *));
graph->visited =malloc(vertices *sizeof(int));

int i;
for(i =0; i < vertices; i++)
{
graph->adjLists[i]= NULL;
graph->visited[i]=0;
}

return graph;
}

void addEdge(struct Graph *graph,int src,int dest)

{
struct node *newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src]= newNode;
newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest]= newNode;
}

struct node *createNode(int v)

{
struct node *newNode =malloc(sizeof(struct node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}

void printGraph(struct Graph *graph)

{
int v;
for(v =0; v < graph->numVertices; v++)
{
struct node *temp = graph->adjLists[v];
printf("\n Adjacency list of vertex %d\n ", v);
while(temp)
{
printf("%d -> ", temp->vertex);
temp = temp->next;
}
printf("\n");
}
}

void bfs(struct Graph *graph,int startVertex)

{
struct node *queue = NULL;
graph->visited[startVertex]=1;
enqueue(&queue, startVertex);

while(!isEmpty(queue))
{
printQueue(queue);
int currentVertex = dequeue(&queue);
printf("Visited %d ", currentVertex);

struct node *temp = graph->adjLists[currentVertex];

while(temp)
{
int adjVertex = temp->vertex;

if(graph->visited[adjVertex]==0)
{
graph->visited[adjVertex]=1;
enqueue(&queue, adjVertex);
}
temp = temp->next;
}
}
}

int isEmpty(struct node *queue)

{
return queue == NULL;
}
void enqueue(struct node **queue,int value)
{
struct node *newNode = createNode(value);
if(isEmpty(*queue))
{
*queue = newNode;
}
else
{
struct node *temp =*queue;
while(temp->next)
{
temp = temp->next;
}
temp->next = newNode;
}
}

int dequeue(struct node **queue)

{
int nodeData =(*queue)->vertex;
struct node *temp =*queue;
*queue =(*queue)->next;
free(temp);
return nodeData;
}

void printQueue(struct node *queue)

{
while(queue)
{
printf("%d ", queue->vertex);
queue = queue->next;
}
printf("\n");
}

int main(void)
{
struct Graph *graph = createGraph(6);
printf("\nWhat do you want to do?\n");
printf("1. Add edge\n");
printf("2. Print graph\n");
printf("3. BFS\n");
printf("4. Exit\n");
int choice;
scanf("%d",&choice);
while(choice !=4)
{
if(choice ==1)
{
int src, dest;
printf("Enter source and destination: ");
scanf("%d %d",&src,&dest);
addEdge(graph, src, dest);
}
elseif(choice ==2)
{
printGraph(graph);
}
elseif(choice ==3)
{
int startVertex;
printf("Enter starting vertex: ");
scanf("%d",&startVertex);
bfs(graph, startVertex);
}
else
{
printf("Invalid choice\n");
}
printf("What do you want to do?\n");
printf("1. Add edge\n");
printf("2. Print graph\n");
printf("3. BFS\n");
printf("4. Exit\n");
scanf("%d",&choice);
}
return0;
}

OUTPUT:

What do you want to do?

1. Add edge
2. Print graph
3. BFS
4. Exit
1
Enter source and destination: 0 1
What do you want to do?
1. Add edge
2. Print graph
3. BFS
4. Exit
1
Enter source and destination: 0 2
What do you want to do?
1. Add edge
2. Print graph
3. BFS
4. Exit
1
Enter source and destination: 1 2
What do you want to do?
1. Add edge
2. Print graph
3. BFS
4. Exit
1
Enter source and destination: 2 3
What do you want to do?
1. Add edge
2. Print graph
3. BFS
4. Exit
2

Adjacency list of vertex 0

2 -> 1 ->

Adjacency list of vertex 1

2 -> 0 ->

Adjacency list of vertex 2

3 -> 1 -> 0 ->

Adjacency list of vertex 3

2 ->

Adjacency list of vertex 4

Adjacency list of vertex 5

What do you want to do?

1. Add edge
2. Print graph
3. BFS
4. Exit
3
Enter starting vertex: 0
0
Visited 0 2 1
Visited 2 1 3
Visited 1 3
Visited 3
What do you want to do?
1. Add edge
2. Print graph
3. BFS
4. Exit
4

DFS USING ADJACENCY MATRIX

#include<stdio.h>

voidDFS(int**graph,intnumVertices,intstartV
ertex)
{
int*visited=(int*)malloc(numVertices*sizeof(int));
for(inti=0;i<numVertices;i++)
{ visited[i] = 0;
}
printf("DFS traversal: ");
DFSUtil(graph,numVertices,startVertex,visite
d);
printf("\n");
 free(visited);
}
voidDFSUtil(int**graph,intnumVertices,intvertex,int*visited)
{
visited[vertex] = 1;
printf("%d",vertex);
for(inti=0;i<numVertices;i++)
{
if (graph[vertex][i] == 1 && !visited[i]) {
DFS(graph,numVertices,i,visited);
}
}
}

intmain()
{
intnumVertices=5;
int**graph=(int**)malloc(numVertices*sizeof
(int*));
for (int i = 0; i < numVertices; i++)
{
graph[i]=(int*)malloc(numVertices*sizeof
(int));
for (int j = 0; j < numVertices; j++)
{
graph[i][j]=0;
}
}
graph graph[0][1] = 1;
graph[0][2]=1;
graph[1][3]=1;
graph[2][4]=1;
graph[3][4]=1;

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

DFS(graph,numVertices,0);

forgraph
for(inti=0;i<numVertices;i++)
{
free(graph[i]);
}
free(graph);
return0;
}

Output:
Adjacencymat
rix: 0 1 1 0 0
00010
00001
00001
00000
DFStraversal:01342

DFS USING ADJACENCY LIST

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

typedef struct Node {

int vertex;
struct Node* next;
} Node;

Node* createNode(int vertex)

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

void addEdge(Node** graph, int numVertices, int src, int dest)

{
Node* newNode = createNode(dest);
newNode->next = graph[src];
graph[src] = newNode;
}
void DFS(Node** graph, int numVertices, int vertex, int* visited)
{
visited[vertex] = 1;
printf("%d ", vertex);
Node* temp = graph[vertex];
while (temp)
{
if (!visited[temp->vertex])
{
DFS(graph, numVertices, temp->vertex, visited);
}
temp = temp->next;
}
}
int main()
{

int numVertices = 5;
int numEdges = 5;
Node** graph = (Node**)malloc(numVertices * sizeof(Node*));
for (int i = 0; i < numVertices; i++)
{
graph[i] = NULL;
}
addEdge(graph, numVertices, 0, 1);
addEdge(graph, numVertices, 0, 2);
addEdge(graph, numVertices, 1, 3);
addEdge(graph, numVertices, 2, 4);
addEdge(graph, numVertices, 3, 4);
printf("Adjacency list:\n");
for (int i = 0; i < numVertices; i++)
{
Node* temp = graph[i];
printf("%d -> ", i);
while (temp) {
printf("%d ", temp->vertex);
temp = temp->next;
}
printf("\n");
}
int* visited = (int*)malloc(numVertices * sizeof(int));
for (int i = 0; i < numVertices; i++)
{
visited[i] = 0;
}
printf("DFS traversal: ");
DFS(graph, numVertices, 0, visited);
printf("\n");
for (int i = 0; i < numVertices; i++)
{
Node* temp = graph[i];
while (temp) {
Node* next = temp->next;
free(temp);
temp = next;
}
}
free(graph);
free(visited);
return 0;
}

Output:

```
Adjacency list:
0 -> 2 1
1 -> 3
2 -> 4
3 -> 4
4 ->
DFS traversal: 0 1 3 4 2

5. Write a program for finding the biconnected components in a given graph

#include <stdio.h>
#include <stdlib.h>
typedef struct Edge
{
int v;
struct Edge* next;
} Edge;
typedef struct Vertex
{
int id;
Edge* adj;
int low;
int disc;
int parent;
int visited;
} Vertex;
Edge* newEdge(int v)
{
Edge* e = (Edge*)malloc(sizeof(Edge));
e->v = v;
e->next = NULL;
return e;
}
Vertex* newVertex(int id)
{
Vertex* v = (Vertex*)malloc(sizeof(Vertex));
v->id = id;
v->adj = NULL;
v->low = 0;
v->disc = 0;
v->parent = -1;
v->visited = 0;
return v;
}

void addEdge(Vertex* v, int w)

{
Edge* e = newEdge(w);
e->next = v->adj;
v->adj = e;
}
void dfs(Vertex* v, int time, Vertex** vertices)
{
v->visited = 1;
v->disc = time;
v->low = time;
time++;
Edge* e = v->adj;
while (e)
{
Vertex* w = vertices[e->v];
if (!w->visited)
{
w->parent = v->id;
dfs(w, time, vertices);
v->low = (v->low < w->low) ? v->low : w->low;
if (v->low > w->disc)
{
printf("Biconnected component: ");
Vertex* temp = v;
while (temp != w)
{
printf("%d ", temp->id);
temp = vertices[temp->parent];
}
printf("%d\n", w->id);
}
} else if (w->id != v->parent)
{
v->low = (v->low < w->disc) ? v->low : w->disc;
}
e = e->next;
}
}
int main()
{
Vertex* vertices[5];
for (int i = 0; i < 5; i++)
{
vertices[i] = newVertex(i + 1);
}
addEdge(vertices[0], 1);
addEdge(vertices[0], 2);
addEdge(vertices[1], 3);
addEdge(vertices[2], 3);
addEdge(vertices[3], 4);
dfs(vertices[0], 1, vertices);
return 0;
}

Output:
Biconnected component: 1 2 3 4
Biconnected component: 1 2 3

6. Implement Quicksort and Mergesort and observe the execution time for
various input sizes(Averagecase ,bestcase,worstcase)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void merge(int arr[], int left, int mid, int right)
{
int n1 = mid - left + 1;
int n2 = right - mid;
int leftArr[n1], rightArr[n2];
for (int i = 0; i < n1; i++)
leftArr[i] = arr[left + i];
for (int j = 0; j < n2; j++)
rightArr[j] = arr[mid + 1 + j];
int 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++;
}
while (i < n1)
{
arr[k] = leftArr[i];
i++;
k++;
}
while (j < n2) {
arr[k] = rightArr[j];
j++;
k++;
}
}

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);
}
}
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 pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}
void measureTime(int arr[], int n, void (*sortFunc)(int[], int, int))
{
clock_t start = clock();
(*sortFunc)(arr, 0, n - 1);
clock_t end = clock();
double timeTaken = (double)(end - start) / CLOCKS_PER_SEC;
printf("Time taken for %d elements: %f seconds\n", n, timeTaken);
}
int main() {
int inputSizes[] = {1000, 2000, 3000, 4000, 5000};
for (int i = 0; i < 5; i++) {
int n = inputSizes[i];
int* arr = (int*)malloc(n * sizeof(int));
for (int j = 0; j < n; j++)
arr[j] = rand() % 1000;
printf("Merge Sort for %d elements:\n", n);
measureTime(arr, n, mergeSort);
for (int j = 0; j < n; j++)
arr[j] = rand() % 1000;
printf("Quick Sort for %d elements:\n", n);
measureTime(arr, n, quickSort);
free(arr);
}
return 0;
}
Output:
Merge Sort for 1000 elements:
Time taken for 1000 elements: 0.000143 seconds
Quick Sort for 1000 elements:
Time taken for 1000 elements: 0.000064 seconds
Merge Sort for 2000 elements:
Time taken for 2000 elements: 0.000291 seconds
Quick Sort for 2000 elements:
Time taken for 2000 elements: 0.000126 seconds
Merge Sort for 3000 elements:
Time taken for 3000 elements: 0.000437 seconds
Quick Sort for 3000 elements:
Time taken for 3000 elements: 0.000191 seconds
Merge Sort for 4000 elements:
Time taken for 4000 elements: 0.000585 seconds
Quick Sort for 4000 elements:
Time taken for 4000 elements: 0.000255 seconds
Merge Sort for 5000 elements:
Time taken for 5000 elements: 0.

7. Compares the performance of single source shortest path

using the greedy method (Dijkstra's algorithm) with adjacency lists and
adjacency matrices:
```
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void dijkstraList(int** graph, int numVertices, int startVertex)
{
int* distances = (int*)malloc(numVertices * sizeof(int));
int* visited = (int*)malloc(numVertices * sizeof(int));
for (int i = 0; i < numVertices; i++)
{
distances[i] = INT_MAX;
visited[i] = 0;
}
distances[startVertex] = 0;
for (int i = 0; i < numVertices - 1; i++)
{
int minDistance = INT_MAX;
int minIndex;
for (int j = 0; j < numVertices; j++)
{
if (!visited[j] && distances[j] < minDistance)
{
minDistance = distances[j];
minIndex = j;
}
}
visited[minIndex] = 1;
for (int j = 0; j < numVertices; j++)
{
if (!visited[j] && graph[minIndex][j] && distances[minIndex] + graph[minIndex]
[j] <
distances[j])
{
distances[j] = distances[minIndex] + graph[minIndex][j];
}
}
}
printf("Shortest distances using adjacency list:\n");
for (int i = 0; i < numVertices; i++)
{
printf("Vertex %d: %d\n", i, distances[i]);

}
free(distances);
free(visited);
}

void dijkstraMatrix(int** graph, int numVertices, int startVertex)

{
int* distances = (int*)malloc(numVertices * sizeof(int));
int* visited = (int*)malloc(numVertices * sizeof(int));
for (int i = 0; i < numVertices; i++)
{
distances[i] = INT_MAX;
visited[i] = 0;
}
distances[startVertex] = 0;
for (int i = 0; i < numVertices - 1; i++)
{
int minDistance = INT_MAX;
int minIndex;
for (int j = 0; j < numVertices; j++)
{
if (!visited[j] && distances[j] < minDistance)
{
minDistance = distances[j];
minIndex = j;
}
}
visited[minIndex] = 1;
for (int j = 0; j < numVertices; j++)
{
if (!visited[j] && graph[minIndex][j] && distances[minIndex] + graph[minIndex]
[j] <
distances[j])
{
distances[j] = distances[minIndex] + graph[minIndex][j];
}
}
}
printf("Shortest distances using adjacency matrix:\n");
for (int i = 0; i < numVertices; i++) {
printf("Vertex %d: %d\n", i, distances[i]);
}

free(distances);
free(visited);
}
int main()
{
int numVertices = 5;
int** graphList = (int**)malloc(numVertices * sizeof(int*));
for (int i = 0; i < numVertices; i++)
{
graphList[i] = (int*)malloc(numVertices * sizeof(int));
for (int j = 0; j < numVertices; j++)
{
graphList[i][j] = 0;
}
}
graphList[0][1] = 4;
graphList[0][2] = 1;
graphList[1][3] = 1;
graphList[2][3] = 2;
graphList[2][4] = 5;
printf("Adjacency list:\n");
for (int i = 0; i < numVertices; i++)
{
for (int j = 0; j < numVertices; j++)
{
printf("%d ", graphList[i][j]);
}
printf("\n");
}
dijkstraList(graphList, numVertices, 0);
int** graphMatrix = (int**)malloc(numVertices * sizeof(int*));
for (int i = 0; i < numVertices; i++)
{
graphMatrix[i] = (int*)malloc(numVertices * sizeof(int));
for (int j = 0; j < numVertices; j++)
{
graphMatrix[i][j] = 0;
}
}

OUTPUT:

Adjacency list:
04100
00010
00025
00000
00000
Shortest distances using adjacency list:
Vertex 0: 0
Vertex 1: 4
Vertex 2: 1
Vertex 3: 3
Vertex 4: 6

8.Implement Job Sequencing with deadlines using Greedy strategy.

#include<stdio.h>

#include<stdlib.h>

// Item structure to store job no, deadinee and profit for each job.

typedef struct job{

int no;

int deadline;
 int profit;

}job;

// function that return the index of the job with max profit among all unchecked jobs

int maxprofitjob(job *jobs,int *checked, int n){

int maxi=-1;

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

if(checked[i]==0 && (maxi==-1 || jobs[i].profit>jobs[maxi].profit)){

maxi=i;

return maxi;

int main(){

int n;

int t,i, maxprofit=0;

//take input

printf("Enter no. of jobs: ");

scanf("%d", &n);

//array of jobs

job *jobs = (job*)malloc(n*sizeof(job));

int *checked = (int*)malloc(n*sizeof(int));

 printf("Enter deadline and profit of each job:\n");

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

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

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

jobs[i].no= i+1;

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

checked[i]=0;

//find maximum deadline among the given deadlines

int maxdeadline = jobs[0].deadline;

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

if(maxdeadline<jobs[i].deadline){

maxdeadline = jobs[i].deadline;

//create slot array to keep the alloted slot of job for execution(create schedule)

int *slots = (int*)malloc(sizeof(int)*maxdeadline);

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

slots[i]=0;

printf("Maximum Profit at the end of each iteration-\n");

i=1;

while(i<=n){

int maxi = maxprofitjob(jobs,checked, n);

checked[maxi]=1;

//find a free slot starting from the last of the job's deadline to the beginning of timeline

t=jobs[maxi].deadline-1;

while(t>=0 && slots[t]){

t--;

//if a free slot is found add the job to the slot array at t index and add the job's profit

//to the maximum(total) profit

//else the job is not added to the schedule and its profit is not added.

if(t>=0 && !slots[t]){

slots[t]= jobs[maxi].no;

maxprofit+=jobs[maxi].profit;

//print the total profit so far

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

i++;

printf("Total Profit= %d\n",maxprofit);

 //print the computed schedule(sequence in which job has to be done)

printf("The optimal sequence\n");

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

if(slots[i]){

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

return 0;

OUTPUT:

Enter no. of jobs: 5

Enter deadline and profit of each job:

20

10

15

12

16

Maximum Profit at the end of each iteration-

5
9

13

16

18

Total Profit= 18

The optimal sequence

2 4 3 5 1

9.Write a program to solve 0/1 Knapsack problem Using Dynamic Programming.

/* A Naive recursive implementation

of 0-1 Knapsack problem */
#include <stdio.h>

// A utility function that returns

// maximum of two integers
int max(int a, int b) { return (a > b) ? a : b; }

// Returns the maximum value that can be

// put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
// Base Case
if (n == 0 || W == 0)
return 0;

// If weight of the nth item is more than

// Knapsack capacity W, then this item cannot
// be included in the optimal solution
if (wt[n - 1] > W)
return knapSack(W, wt, val, n - 1);

// Return the maximum of two cases:

// (1) nth item included
// (2) not included
else
return max(
val[n - 1]
+ knapSack(W - wt[n - 1], wt, val, n - 1),
knapSack(W, wt, val, n - 1));
}

// Driver code
int main()
{
int profit[] = { 60, 100, 120 };
int weight[] = { 10, 20, 30 };
int W = 50;
int n = sizeof(profit) / sizeof(profit[0]);
printf("%d", knapSack(W, weight, profit, n));
return 0;
}

OUTPUT:

220

10. Implement N-Queens Problem Using Backtracking.

#include<stdio.h>

#include<math.h>

int board[20],count;

int main()

int n,i,j;

void queen(int row,int n);

printf(" - N Queens Problem Using Backtracking -");

printf("\n\nEnter number of Queens:");

scanf("%d",&n);

queen(1,n);

return 0;
}

//function for printing the solution

void print(int n)

int i,j;

printf("\n\nSolution %d:\n\n",++count);

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

printf("\t%d",i);

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

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

for(j=1;j<=n;++j) //for nxn board

if(board[i]==j)

printf("\tQ"); //queen at i,j position

else

printf("\t-"); //empty slot

/*funtion to check conflicts

If no conflict for desired postion returns 1 otherwise returns 0*/

int place(int row,int column)

int i;

for(i=1;i<=row-1;++i)

//checking column and digonal conflicts

if(board[i]==column)

return 0;

else

if(abs(board[i]-column)==abs(i-row))

return 0;

return 1; //no conflicts

//function to check for proper positioning of queen

void queen(int row,int n)

int column;

for(column=1;column<=n;++column)

if(place(row,column))

{
 board[row]=column; //no conflicts so place queen

if(row==n) //dead end

print(n); //printing the board configuration

else //try queen with next position

queen(row+1,n);

OUTPUT:

- N Queens Problem Using Backtracking -

Enter number of Queens:4

Solution 1:

1 2 3 4

1 - Q - -

2 - - - Q

3 Q - - -

4 - - Q -
Solution 2:

1 2 3 4

1 - - Q -

2 Q - - -

3 - - - Q

4 - Q - -

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

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

#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

12.Implement Travelling Sales Person problem using Branch and Bound approach.

1./*Branch and Bound Algorithm for Travelling Sales Person*/

2.#include<stdio.h>
3.#include<conio.h>
4.int a[10][10], visited[10], n, cost = 0;
5.void get() {
6. int i, j;
7. printf("Enter No. of Cities: ");
8. scanf("%d", &n);
9. printf("\nEnter Cost Matrix: \n");
10. for (i = 0; i < n; i++) {
11. printf("\n Enter Elements of Row# : %d\n", i + 1);
12. for (j = 0; j < n; j++)
13. scanf("%d", &a[i][j]);
14. visited[i] = 0;
15. }
16. printf("\n\nThe cost list is:\n\n");
 17. for (i = 0; i < n; i++) {
18. printf("\n\n");
19. for (j = 0; j < n; j++)
20. printf("\t % d", a[i][j]);
21. }
22. }
23. void mincost(int city) {
24. int i, ncity;
25. visited[city] = 1;
26. printf("%d –>", city + 1);
27. ncity = least(city);
28. if (ncity == 999) {
29. ncity = 0;
30. printf("%d", ncity + 1);
31. cost += a[city][ncity];
32. return;
33. }
34. mincost(ncity);
35. }
36. int least(int c) {
37. int i, nc = 999;
38. int min = 999, kmin;
39. for (i = 0; i < n; i++) {
40. if ((a[c][i] != 0) && (visited[i] == 0))
41. if (a[c][i] < min) {
42. min = a[i][0] + a[c][i];
43. kmin = a[c][i];
44. nc = i;
45. }
46. }
47. if (min != 999)
48. cost += kmin;
49. return nc;
50. }
51. void put() {
52. printf("\n\nMinimum cost:");
53. printf("%d", cost);
54. }
55. void main() {
56. get();
57. printf("\n\nThe Path is:\n\n");
58. mincost(0);
59. put();
60. }

OUTPUT:

Minimum cost : 80
Path Taken : 0 1 3 2 0