1. WAP in C to find time complexity of Bubble sort by using RAM model.

Code:

#include <stdio.h>
void bubbleSort(int arr[], int n, int *comparisons, int order) {
(*comparisons) += 2;
for (int i = 0; i < n - 1; i++) {
(*comparisons) += 4;
for (int j = 0; j < n - i - 1; j++) {
(*comparisons) += 2;
if ((order == 1 && arr[j] > arr[j + 1]) ||
(order == 2 && arr[j] < arr[j + 1])) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}}
}}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int n;
printf("Nabin Joshi\n");
printf("Enter number of elements: ");
scanf("%d", &n);
int original[n];
printf("Enter %d elements:", n);
for (int i = 0; i < n; i++)
scanf("%d", &original[i]);
int comparisonsAsc = 0;
int ascending[n];
for (int i = 0; i < n; i++) ascending[i] = original[i];
bubbleSort(ascending, n, &comparisonsAsc, 1);
printf("\nSorted Array in Ascending Order: ");
printArray(ascending, n);
printf("Total time complexity (RAM model): %d comparisons\n", comparisonsAsc);
printf("Theoretical time complexity: O(n^2) = %d\n", n * n);
int comparisonsDesc = 0;
int descending[n];

for (int i = 0; i < n; i++) descending[i] = original[i];

bubbleSort(descending, n, &comparisonsDesc, 2);
printf("\nSorted Array in Descending Order: ");
-Nabin Joshi
printArray(descending, n);
printf("Total time complexity (RAM model): %d comparisons\n", comparisonsDesc);
printf("Theoretical time complexity: O(n^2) = %d\n", n * n);
return 0;
}

OUTPUT:

-Nabin Joshi
2. WAP in C to find time complexity of Selection sort by using RAM
model.

Code:

#include <stdio.h>
void selectionSort(int a[], int n, int *count, int order) {
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
(*count) += 1;
if ((order == 1 && a[j] < a[min]) || (order == 2 && a[j] > a[min])) {
min = j;
(*count) += 1;
}
}
int temp = a[min];
a[min] = a[i];
a[i] = temp;
(*count) += 2;
}
}
void printArray(int a[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\n");
}
int main() {
int n;
printf("Nabin Joshi\t (selection sort)\n");
printf("Enter number of elements: ");
scanf("%d", &n);
int original[n];
printf("Enter %d elements:", n);
for (int i = 0; i < n; i++)
scanf("%d", &original[i]);
int comparisons = 0;
int ascending[n];
for (int i = 0; i < n; i++) ascending[i] = original[i];
selectionSort(ascending, n, &comparisons, 1);
printf("\nSorted Array in Ascending Order: ");

-Nabin Joshi
printArray(ascending, n);
printf("Total execution steps for ascending order = %d\n", comparisons);
printf("Theoretical time complexity: O(n^2) = %d\n", n * n);
comparisons = 0;
int descending[n];

for (int i = 0; i < n; i++) descending[i] = original[i];

selectionSort(descending, n, &comparisons, 2);
printf("\nSorted Array in Descending Order: ");
printArray(descending, n);
printf("Total execution steps for descending order = %d\n", comparisons);
printf("Theoretical time complexity: O(n^2) = %d\n", n * n);
return 0;
}

OUTPUT:

-Nabin Joshi
3. WAP in C to find time complexity of Insertion sort by using RAM
model.

Code:

#include <stdio.h>
void insertionSort(int a[], int n, int *count, int order) {
for (int i = 1; i < n; i++) {
int key = a[i];
int j = i - 1;
(*count) += 1;
while (j >= 0 && ((order == 1 && a[j] > key) || (order == 2 && a[j] < key))) {
a[j + 1] = a[j];
j = j - 1;
(*count) += 1;
}
a[j + 1] = key;
(*count) += 1;
}
}
void printArray(int a[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\n");
}
int main() {
int n;
printf("Nabin Joshi\t (insertion sort)\n");
printf("Enter number of elements: ");
scanf("%d", &n);
int original[n];
printf("Enter %d elements:", n);
for (int i = 0; i < n; i++)
scanf("%d", &original[i]);
int comparisons = 0;
int ascending[n];
for (int i = 0; i < n; i++) ascending[i] = original[i];
insertionSort(ascending, n, &comparisons, 1);
printf("\nSorted Array in Ascending Order: ");
printArray(ascending, n);
printf("Total execution steps for ascending order = %d\n", comparisons);

-Nabin Joshi
printf("Theoretical time complexity: O(n^2) = %d\n", n * n);
comparisons = 0;
int descending[n];
for (int i = 0; i < n; i++) descending[i] = original[i];

insertionSort(descending, n, &comparisons, 2);

printf("\nSorted Array in Descending Order: ");
printArray(descending, n);
printf("Total execution steps for descending order = %d\n", comparisons);
printf("Theoretical time complexity: O(n^2) = %d\n", n * n);
return 0;
}

OUTPUT:

-Nabin Joshi
4. WAP in C to find time complexity of Sequential search by using RAM
model.

Code:

#include <stdio.h>
int sequentialSearch(int arr[], int n, int key, int *count) {
(*count) = 0;
for (int i = 0; i < n; i++) {
(*count) += 1;
if (arr[i] == key) {
return i;
}
}
return -1;
}
int main() {
int n, key;
printf("Nabin Joshi \t (sequential search)\n");
printf("Enter number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d elements:", n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("Enter the elements to search: ");
scanf("%d", &key);
int comparisons = 0;
int result = sequentialSearch(arr, n, key, &comparisons);
if (result != -1) {
printf("\nElement %d found at index %d\n", key, result);
} else {
printf("Element %d not found\n", key);
}
printf("Total execution steps (comparisons): %d\n", comparisons);
printf("Theoretical time complexity: O(n) = %d\n", n);
return 0;
}

-Nabin Joshi
OUTPUT:

When element is found:

When element is not found:

-Nabin Joshi
5. WAP in C to simulate Quick sort and find their total execution time in
different types of input.

Code:

#include <stdio.h>
#include <time.h>
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; 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);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
void processArray(int arrayNumber) {
int n;
printf("------------------------------------------ ");
printf("\n--- Array %d ---\n", arrayNumber);
printf("Enter number of elements: ");
scanf("%d", &n);

-Nabin Joshi
int arr[n];
printf("Enter %d elements:", n);
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
printf("Original Array %d: ", arrayNumber);
printArray(arr, n);
clock_t start = clock();
quickSort(arr, 0, n - 1);
clock_t end = clock();
printf("Sorted Array %d: ", arrayNumber);
printArray(arr, n);
double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Execution time for Array %d: %f seconds\n", arrayNumber, time_taken);
}
int main() {
processArray(1);
processArray(2);
printf("------------------------------------------ ");
printf("\nNabin Joshi");
return 0;
}

OUTPUT:

-Nabin Joshi
[Link] in C to simulate Merge sort and find their total execution time in
different types of input.

Code:

#include <stdio.h>
#include <time.h>
int count = 0;
void merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];

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

L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
i = 0;
j = 0;
k = left;

while (i < n1 && j < n2) {

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

while (i < n1) {

arr[k] = L[i];
i++;
k++;
count++;

-Nabin Joshi
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
count++;
}
}

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

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

int main() {
clock_t st = clock();
int n;
printf("------------------------------------------ ");
printf("\nEnter the number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter the elements of the array: ");
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
mergeSort(arr, 0, n - 1);
printf("Sorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
clock_t et = clock();
printf("\nThe execution time is: %f seconds\n", (double)(et - st) / CLOCKS_PER_SEC);
printf("Total comparison steps: %d\n", count);
printf("------------------------------------------ ");
printf("\nNabin Joshi");
return 0;
}

-Nabin Joshi
OUTPUT:

-Nabin Joshi
7. WAP in C to simulate Heap sort and find their total execution time in
different types of input.

Code:

#include <stdio.h>
#include <time.h>
int count = 0;
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
count++;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
count++;
}
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
count++;
}
}
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
swap(&arr[0], &arr[i]);
heapify(arr, i, 0);
}
}
int main() {
clock_t st = clock();

-Nabin Joshi
int n;
printf("------------------------------------------ ");
printf("\nEnter the number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter the elements of the array: ");
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
heapSort(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
clock_t et = clock();
printf("\nThe execution time is: %f seconds\n", (double)(et - st) / CLOCKS_PER_SEC);
printf("Total comparison steps: %d\n", count);
printf("------------------------------------------ ");
printf("\nNabin Joshi");
return 0;
}

OUTPUT:

-Nabin Joshi
8. WAP in C to simulate Selection algorithm and find their total execution
time in different types of input.

Code:
#include <stdio.h>
#include <time.h>

int count = 0;
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}

int partition(int arr[], int left, int right)

{
// Initialize pivot to be the first element
int pivot = arr[left];
int i = left;
int j = right;
while (i < j)
{
count++;
while (arr[i] <= pivot && i <= right - 1)
{
i++;
count++;
}
// Condition 2: find the first element smaller than the pivot (from last)
while (arr[j] > pivot && j >= left + 1)
{
j--;
count++;
}
if (i < j)
{
swap(&arr[i], &arr[j]);
count++;
}

-Nabin Joshi
 }
swap(&arr[left], &arr[j]);
return j;
}

int quickSelect(int arr[], int left, int right, int k)

{
if (left <= right)
{
count++;
int partitionIndex = partition(arr, left, right);

if (partitionIndex == k)
{
return arr[partitionIndex];
count++;
}
else if (partitionIndex > k)
{
return quickSelect(arr, left, partitionIndex - 1, k);
count++;
}
else
{
return quickSelect(arr, partitionIndex + 1, right, k);
count++;
}
}
return -1;

int main()
{
clock_t st = clock();
int n, k;
printf("\nEnter the number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter the elements of the array: ");
for (int i = 0; i < n; i++)
{

-Nabin Joshi
 scanf("%d", &arr[i]);
}
printf("Enter the value of k: ");
scanf("%d", &k);
if (k < 1 || k > n)
{
printf("Invalid value of k\n");
return 1;
}
int kthSmallest = quickSelect(arr, 0, n - 1, k - 1);
printf("The %d smallest element is: %d\n", k, kthSmallest);
clock_t et = clock();
printf("Total comparison steps: %d\n", count);
printf("The execution time is: %f seconds\n", (double)(et - st) /
CLOCKS_PER_SEC);
printf(" -----------------------------Nabin Joshi----------------------\n");
return 0;
}
OUTPUT:

-Nabin Joshi
9. WAP in C to simulate Binary search and find their total execution time
in different types of input.

Code:

#include <stdio.h>
#include <time.h>
int binarySearch(int arr[], int left, int right, int x)
{
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] < x)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
int main() {
clock_t st = clock();
int n, x;
printf("------------------------------------------ ");
printf("\nEnter the number of elements in the array: ");
scanf("%d", &n);
int arr[n];
printf("Enter the elements in sorted order: ");
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
printf("Enter the element to search: ");
scanf("%d", &x);
int result = binarySearch(arr, 0, n - 1, x);
if (result == -1) {
printf("Element not found\n");
}
else {
printf("Element found at index %d\n", result);
}

-Nabin Joshi
clock_t et = clock();
printf("The execution time is: %f seconds\n", (double)(et - st) / CLOCKS_PER_SEC);
printf("------------------------------------------ ");
printf("\nNabin Joshi");
return 0;
}
Output:

When element is found:

When element is not found:

-Nabin Joshi
[Link] in C to simulate 0/1 knapsack algorithm and find their total
execution time in different types of input.

Code:

#include <stdio.h>
#include <time.h>
int max(int a, int b)
{
return (a > b) ? a : b;
}
int knapsack(int W, int wt[], int val[], int n)
{
if (n == 0 || W == 0)
return 0;
if (wt[n - 1] > W)
return knapsack(W, wt, val, n - 1);
else
return max(val[n - 1] + knapsack(W - wt[n - 1], wt, val, n - 1), knapsack(W, wt, val, n -
1));
}
int main()
{
printf("------------------------------------------ ");
clock_t st = clock();
int n, W;
printf("\nEnter the number of items: ");
scanf("%d", &n);
int values[n], weight[n];
printf("Enter the values of the items: ");
for (int i = 0; i < n; i++)
{
scanf("%d", &values[i]);
}
printf("Enter the weights of the items: ");
for (int i = 0; i < n; i++)
{
scanf("%d", &weight[i]);
}
printf("Enter the capacity of the knapsack: ");
scanf("%d", &W);

-Nabin Joshi
printf("Maximum value in knapsack = %d\n", knapsack(W, weight, values, n));
clock_t et = clock();
printf("The execution time is: %f seconds\n", (double)(et - st) / CLOCKS_PER_SEC);
printf("------------------------------------------ ");
printf("\nNabin Joshi");
return 0;
}

OUTPUT:

-Nabin Joshi
[Link] in C to simulate LCS algorithm and find their total execution
time in different types of input.

Code:

#include <stdio.h>
#include <time.h>
#include <string.h> // Include this header for strlen()

int max(int a, int b)

{
return (a > b) ? a : b;
}

int lcs(char *X, char *Y, int m, int n)

{
int L[m + 1][n + 1];
for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i - 1] == Y[j - 1])
L[i][j] = L[i - 1][j - 1] + 1;
else
L[i][j] = max(L[i - 1][j], L[i][j - 1]);
}
}
return L[m][n];
}

int main()
{
printf("------------------------------------------ ");
clock_t st = clock();

char X[100], Y[100];

printf("\nEnter the first string: ");
scanf("%s", X);

-Nabin Joshi
 printf("Enter the second string: ");
scanf("%s", Y);

int m = strlen(X);
int n = strlen(Y);

printf("Length of LCS = %d\n", lcs(X, Y, m, n));

clock_t et = clock();
printf("The execution time is: %f seconds\n", (double)(et - st) / CLOCKS_PER_SEC);

printf("------------------------------------------ ");
printf("\nNabin Joshi ");

return 0;
}

OUTPUT:

-Nabin Joshi
[Link] in C to simulate Huffman algorithm and find their total
execution time in different types of input.

Code:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_TREE_HT 100
struct MinHeapNode
{
char data;
unsigned freq;
struct MinHeapNode *left, *right;
};
struct MinHeap
{
unsigned size;
unsigned capacity;
struct MinHeapNode **array;
};
struct MinHeapNode *newNode(char data, unsigned freq)
{
struct MinHeapNode *temp = (struct MinHeapNode *)malloc(sizeof(struct
MinHeapNode));
temp->left = temp->right = NULL;
temp->data = data;
temp->freq = freq;
return temp;
}
struct MinHeap *createMinHeap(unsigned capacity)
{
struct MinHeap *minHeap = (struct MinHeap *)malloc(sizeof(struct MinHeap));
minHeap->size = 0;
minHeap->capacity = capacity;
minHeap->array = (struct MinHeapNode **)malloc(minHeap->capacity * sizeof(struct
MinHeapNode *));
return minHeap;
}
void swapMinHeapNode(struct MinHeapNode **a, struct MinHeapNode **b)
{
struct MinHeapNode *t = *a;

-Nabin Joshi
*a = *b;
*b = t;
}
void minHeapify(struct MinHeap *minHeap, int idx)
{
int smallest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]-
>freq)
smallest = left;
if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]-
>freq)
smallest = right;
if (smallest != idx)
{
swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);
minHeapify(minHeap, smallest);
}
}
int isSizeOne(struct MinHeap *minHeap)
{
return (minHeap->size == 1);
}
struct MinHeapNode *extractMin(struct MinHeap *minHeap)
{
struct MinHeapNode *temp = minHeap->array[0];
minHeap->array[0] = minHeap->array[minHeap->size - 1];
--minHeap->size;
minHeapify(minHeap, 0);
return temp;
}
void insertMinHeap(struct MinHeap *minHeap, struct MinHeapNode *minHeapNode)
{
++minHeap->size;
int i = minHeap->size - 1;
while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq)
{
minHeap->array[i] = minHeap->array[(i - 1) / 2];
i = (i - 1) / 2;

-Nabin Joshi
}
minHeap->array[i] = minHeapNode;
}
void buildMinHeap(struct MinHeap *minHeap)
{
int n = minHeap->size - 1;
for (int i = (n - 1) / 2; i >= 0; --i)
minHeapify(minHeap, i);
}
void printArr(int arr[], int n)
{
for (int i = 0; i < n; ++i)
printf("%d", arr[i]);
printf("\n");
}
int isLeaf(struct MinHeapNode *root)
{
return !(root->left) && !(root->right);
}
struct MinHeap *createAndBuildMinHeap(char data[], int freq[], int size)
{
struct MinHeap *minHeap = createMinHeap(size);
for (int i = 0; i < size; ++i)
minHeap->array[i] = newNode(data[i], freq[i]);
minHeap->size = size;
buildMinHeap(minHeap);
return minHeap;
}
struct MinHeapNode *buildHuffmanTree(char data[], int freq[], int size)
{
struct MinHeapNode *left, *right, *top;
struct MinHeap *minHeap = createAndBuildMinHeap(data, freq, size);
while (!isSizeOne(minHeap))
{
left = extractMin(minHeap);
right = extractMin(minHeap);
top = newNode('$', left->freq + right->freq);
top->left = left;
top->right = right;
insertMinHeap(minHeap, top);

-Nabin Joshi
}
return extractMin(minHeap);
}
void printHuffmanCodes(struct MinHeapNode *root, int arr[], int top)
{
if (root->left)
{
arr[top] = 0;
printHuffmanCodes(root->left, arr, top + 1);
}
if (root->right)
{
arr[top] = 1;
printHuffmanCodes(root->right, arr, top + 1);
}
if (isLeaf(root))
{
printf("%c: ", root->data);
printArr(arr, top);
}
}
int main()
{
printf("------------------------------------------\n");
clock_t st = clock();
char arr[] = {'a', 'b', 'c', 'd', 'e', 'f'};
int freq[] = {75, 4, 9, 18, 34, 5};
int size = sizeof(arr) / sizeof(arr[0]);
struct MinHeapNode *root = buildHuffmanTree(arr, freq, size);
int arrCode[MAX_TREE_HT];
printHuffmanCodes(root, arrCode, 0);
clock_t et = clock();
printf("The execution time is: %f seconds\n", (double)(et - st) / CLOCKS_PER_SEC);
printf("------------------------------------------ ");
printf("\nNabin Joshi");
return 0;
}

-Nabin Joshi
OUTPUT:

-Nabin Joshi
13) WAP in C to simulate Kruskal’s algorithm and find their total
execution time in different types of input.

Code:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 100
struct Edge
{
int src, dest, weight;
};
struct Graph
{
int V, E;
struct Edge *edge;
};
struct subset
{
int parent;
int rank;
};
int find(struct subset subsets[], int i)
{
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
void Union(struct subset subsets[], int x, int y)
{
int rootX = find(subsets, x);
int rootY = find(subsets, y);
if (subsets[rootX].rank < subsets[rootY].rank)
subsets[rootX].parent = rootY;
else if (subsets[rootX].rank > subsets[rootY].rank)
subsets[rootY].parent = rootX;
else
{
subsets[rootY].parent = rootX;
subsets[rootX].rank++;
}

-Nabin Joshi
}
int compare(const void *a, const void *b)
{
return ((struct Edge *)a)->weight > ((struct Edge *)b)->weight;
}
void kruskal(struct Graph *graph) {
int e = 0;
int i = 0;
struct subset *subsets = (struct subset *)malloc(graph->V * sizeof(struct subset));
struct Edge result[graph->V];
for (i = 0; i < graph->V; ++i)
{
subsets[i].parent = i;
subsets[i].rank = 0;
}
qsort(graph->edge, graph->E, sizeof(graph->edge[0]), compare);
i = 0;
while (e < graph->V - 1)
{
struct Edge next_edge = graph->edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
if (x != y)
{
result[e++] = next_edge;
Union(subsets, x, y);
}
}
printf("Following are the edges in the constructed MST\n");
for (i = 0; i < e; ++i)
printf("%d -- %d == %d\n", result[i].src, result[i].dest, result[i].weight);
}
int main() {
printf("------------------------------------------ ");
clock_t st = clock();
struct Graph *graph = (struct Graph *)malloc(sizeof(struct Graph));
printf("\nEnter number of vertices: ");
scanf("%d", &graph->V);
printf("Enter number of edges: ");
scanf("%d", &graph->E);

-Nabin Joshi
graph->edge = (struct Edge *)malloc(graph->E * sizeof(struct Edge));
printf("Enter the edges (src, dest, weight):\n");
for (int i = 0; i < graph->E; i++) {
scanf("%d %d %d", &graph->edge[i].src, &graph->edge[i].dest, &graph-
>edge[i].weight);
}
kruskal(graph);
clock_t et = clock();
printf("The execution time is: %f seconds\n", (double)(et - st) / CLOCKS_PER_SEC);
printf("------------------------------------------ ");
printf("\nNabin Joshi");
return 0;
}

OUTPUT:

-Nabin Joshi
14) WAP in C to simulate Dijkstra Algorithm and find their total
execution time.

Code:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>
#define V 9
int minDistance(int dist[], int sptSet[])
{
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
{
if (sptSet[v] == 0 && dist[v] <= min)
{
min = dist[v], min_index = v;
}}
return min_index;
}
void dijkstra(int graph[V][V], int src)
{
int dist[V];
int sptSet[V];
for (int i = 0; i < V; i++)
{
dist[i] = INT_MAX;
sptSet[i] = 0;
}
dist[src] = 0;
for (int count = 0; count < V - 1; count++)
{
int u = minDistance(dist, sptSet);
sptSet[u] = 1;
for (int v = 0; v < V; 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];
}}}

-Nabin Joshi
printf("Vertex \t Distance from Source\n");
for (int i = 0; i < V; i++)
{
printf("%d \t %d\n", i, dist[i]);
}}
int main()
{
printf("------------------------------------------ \n");
clock_t st = clock();
int graph[V][V] = {
{0, 10, 0, 0, 0, 0, 0, 5, 0},
{10, 0, 7, 0, 0, 0, 0, 0, 0},
{0, 7, 0, 12, 0, 6, 0, 0, 0},
{0, 0, 12, 0, 8, 15, 0, 0, 0},
{0, 0, 0, 8, 0, 14, 0, 0, 0},
{0, 0, 6, 15, 14, 0, 3, 0, 0},
{0, 0, 0, 0, 0, 3, 0, 2, 7},
{5, 0, 0, 0, 0, 0, 2, 0, 9},
{0, 0, 0, 0, 0, 0, 7, 9, 0}
};
dijkstra(graph, 0);
clock_t et = clock();
printf("The execution time is: %f seconds\n", (double)(et - st) / CLOCKS_PER_SEC);
printf("------------------------------------------ ");
printf("\nNabin Joshi");
return 0;
}
OUTPUT:

-Nabin Joshi
[Link] in C to simulate Euclidean Algorithm and find their total
execution time.

Code:
#include <stdio.h>
#include <time.h>
int euclideanGCD(int a, int b)
{
while (b != 0)
{
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int main() {
printf("------------------------------------------ ");

clock_t st = clock();
int a, b;
printf("\nEnter two numbers: ");
scanf("%d %d", &a, &b);
printf("GCD of %d and %d is %d\n", a, b, euclideanGCD(a, b));
clock_t et = clock();
printf("The execution time is: %f seconds\n", (double)(et - st) / CLOCKS_PER_SEC);
printf("------------------------------------------ ");
printf("\nNabin Joshi");
return 0;
}

OUTPUT:

-Nabin Joshi
[Link] in C to simulate Sum of Subset Algorithm and find their total
execution time.

Code:
#include <stdio.h>
#include <time.h>

int sumOfSubset(int arr[], int n, int sum)

{
if (sum == 0)
return 1;
if (n == 0)
return 0;
if (arr[n - 1] > sum)
return sumOfSubset(arr, n - 1, sum);
return sumOfSubset(arr, n - 1, sum) || sumOfSubset(arr, n - 1, sum - arr[n - 1]);
}

int main()
{
printf("------------------------------------------ ");
clock_t st = clock();
int n, sum;
printf("\nEnter the number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter the elements: ");
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
printf("Enter the sum to check: ");
scanf("%d", &sum);
if (sumOfSubset(arr, n, sum))
printf("Subset with the given sum exists\n");
else
printf("Subset with the given sum doesn't exist\n");
clock_t et = clock();
printf("The execution time is: %f seconds\n", (double)(et - st) / CLOCKS_PER_SEC);
printf("------------------------------------------ ");

-Nabin Joshi
 printf("\nNabin Joshi");
return 0;
}

OUTPUT:

-Nabin Joshi
17) WAP in C to simulate 4–Queen Algorithm and find their total
execution time.

Code:
#include <stdio.h>
#include <time.h>
#define N 4

int isSafe(int board[N][N], int row, int col)

{
for (int i = 0; i < col; i++)
if (board[row][i])
return 0;

for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)

if (board[i][j])
return 0;

for (int i = row, j = col; j >= 0 && i < N; i++, j--)

if (board[i][j])
return 0;

return 1;
}

int solveNQUtil(int board[N][N], int col)

{
if (col >= N)
return 1;

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

{
if (isSafe(board, i, col))
{
board[i][col] = 1;
if (solveNQUtil(board, col + 1))
return 1;
board[i][col] = 0;
}

-Nabin Joshi
 }
return 0;
}

void printSolution(int board[N][N])

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

int main()
{
printf("------------------------------------------\n");
clock_t st = clock();
int board[N][N] = {0};

if (solveNQUtil(board, 0))
{
printf("Solution found:\n");
printSolution(board);
}
else
printf("Solution does not exist\n");

clock_t et = clock();
printf("The execution time is: %f seconds\n", (double)(et - st) / CLOCKS_PER_SEC);
printf("------------------------------------------ ");
printf("\nNabin Joshi\n");

return 0;
}

-Nabin Joshi
OUTPUT:

-Nabin Joshi
[Link] in C to simulate Vertex Cover Algorithm and find their total
execution time.

Code:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 20

void vertexCover(int graph[MAX][MAX], int n) {

int visited[MAX] = {0};
for (int u = 0; u < n; u++) {
if (visited[u] == 0) {
for (int v = 0; v < n; v++) {
if (graph[u][v] == 1 && visited[v] == 0) {
visited[u] = 1;
visited[v] = 1;
printf("Vertex %d and %d are in the vertex cover.\n", u, v);
break;
}}}}}

int main() {
clock_t start_time, end_time;
double total_time;
printf("------------------------------------------ ");
int graph[MAX][MAX], n;
printf("\nEnter the number of vertices: ");
scanf("%d", &n);
printf("Enter the adjacency matrix of the graph:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}
start_time = clock();
vertexCover(graph, n);
end_time = clock();
total_time = ((double)(end_time - start_time)) / CLOCKS_PER_SEC;
printf("The execution time is: %f seconds\n", total_time);
printf("------------------------------------------ ");

-Nabin Joshi
 printf("\nNabin Joshi");
return 0;
}

OUTPUT:

-Nabin Joshi