Program 1 int find(int i) {

#include <stdio.h> while (parent[i])

int i, j, k, a, b, u, v, n, ne = 1; i = parent[i];
int min, mincost = 0, cost[9][9], return i; }
parent[9]; int uni(int i, int j) {
int find(int); if (i != j) {
int uni(int, int); parent[j] = i;
void main() { return 1;
printf("\n\tImplementation of }
Kruskal's Algorithm\n"); return 0;
printf("\nEnter the number of }
vertices: "); Program2
scanf("%d", &n); #include <stdio.h>
printf("\nEnter the cost adjacency int visited[10] = {0}, cost[10][10],
matrix:\n"); min, mincost = 0;
for (i = 1; i <= n; i++) { int i, j, ne = 1, a, b, u, v;
for (j = 1; j <= n; j++) { int main() {
scanf("%d", &cost[i][j]); int num;
if (cost[i][j] == 0) printf("\n\t\t\tPrim's Algorithm");
cost[i][j] = 999; printf("\n\nEnter the number of
} } nodes: ");
printf("The edges of Minimum scanf("%d", &num);
Cost Spanning Tree are:\n"); printf("\nEnter the adjacency
while (ne < n) { matrix:\n");
for (i = 1, min = 999; i <= n; i++){ for (i = 1; i <= num; i++) {
for (j = 1; j <= n; j++) { for (j = 1; j <= num; j++) {
if (cost[i][j] < min) { scanf("%d", &cost[i][j]);
min = cost[i][j]; if (cost[i][j] == 0)
a = u = i; cost[i][j] = 999;
b = v = j; } }
} }} visited[1] = 1;
u = find(u); while (ne < num) {
v = find(v); for (i = 1, min = 999; i <= num;
if (uni(u, v)) { i++) {
printf("%d edge (%d,%d) = for (j = 1; j <= num; j++) {
%d\n", ne++, a, b, min); if (cost[i][j] < min) {
mincost += min; } if (visited[i] != 0 &&
cost[a][b] = cost[b][a] = 999: } visited[j] == 0) {
printf("\nMinimum cost = %d\n", min = cost[i][j];
mincost); } a = u = i;
 b = v = j; printf("%d ", a[i][j]);
}}}} printf("\n");
printf("\nEdge %d: (%d - %d) }
cost: %d", ne++, a, b, min);
mincost += min; return 0;
visited[b] = 1; }Program 3b
cost[a][b] = cost[b][a] = 999; #include <stdio.h>
}
printf("\n\nMinimum cost = void warsh(int p[][10], int n) {
%d\n", mincost); int i, j, k;
return 0; for (k = 1; k <= n; k++)
}Program 3a for (i = 1; i <= n; i++)
#include <stdio.h> for (j = 1; j <= n; j++)
#define INF 999 p[i][j] = p[i][j] || (p[i][k] &&
int min(int a, int b) { p[k][j]);
return (a < b) ? a : b; }
} int main() {
void floyd(int p[][10], int n) { int a[10][10], n, i, j;
int i, j, k;
for (k = 1; k <= n; k++) printf("\nEnter the number of
for (i = 1; i <= n; i++) vertices: ");
for (j = 1; j <= n; j++) scanf("%d", &n);
p[i][j] = min(p[i][j], p[i][k] +
p[k][j]); printf("\nEnter the adjacency
} matrix:\n");
int main() { for (i = 1; i <= n; i++)
int a[10][10], n, i, j; for (j = 1; j <= n; j++)
printf("\nEnter the number of scanf("%d", &a[i][j]);
vertices: ");
scanf("%d", &n); warsh(a, n);
printf("\nEnter the adjacency
matrix:\n"); printf("\nResultant path
for (i = 1; i <= n; i++) matrix:\n");
for (j = 1; j <= n; j++) for (i = 1; i <= n; i++) {
scanf("%d", &a[i][j]); for (j = 1; j <= n; j++)
floyd(a, n); printf("%d ", a[i][j]);
printf("\nShortest path printf("\n");
matrix:\n"); }
for (i = 1; i <= n; i++) { return 0;
for (j = 1; j <= n; j++) }
Program4 printf("\nEnter the adjacency
#include <stdio.h> matrix:\n");
#define INF 999 for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
void dijkstra(int c[10][10], int n, int scanf("%d", &c[i][j]);
s, int d[10]) {
int v[10], min, u, i, j; printf("\nEnter the source node:
");
for (i = 1; i <= n; i++) { scanf("%d", &s);
d[i] = c[s][i];
v[i] = 0; dijkstra(c, n, s, d);
}
v[s] = 1; for (i = 1; i <= n; i++)
printf("\nShortest distance from
for (i = 1; i <= n - 1; i++) { %d to %d is %d", s, i, d[i]);
min = INF;
for (j = 1; j <= n; j++) { return 0;
if (v[j] == 0 && d[j] < min) { }Program5
min = d[j]; #include <stdio.h>
u = j;
} void topo_sort(int a[20][20], int n) {
} int t[10], vis[10], stack[10], i, j,
indeg[10], top = 0, ele, k = 1;
v[u] = 1;
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) { t[i] = 0;
if (v[j] == 0 && (d[u] + c[u][j] vis[i] = 0;
< d[j])) indeg[i] = 0;
d[j] = d[u] + c[u][j]; }
}
} for (i = 1; i <= n; i++) {
} for (j = 1; j <= n; j++) {
int main() { if (a[i][j] == 1) {
int c[10][10], d[10], i, j, s, n; indeg[j]++;
}
printf("\nEnter the number of }
vertices: "); }
scanf("%d", &n); printf("Indegree Array: ");
for (i = 1; i <= n; i++) {
printf("%d ", indeg[i]);
 } topo_sort(a, n);
for (i = 1; i <= n; i++) { return 0;
if (indeg[i] == 0) { }Program 6
stack[++top] = i; #include <stdio.h>
vis[i] = 1; } } int w[10], p[10], n;
while (top > 0) { int max(int a, int b) {
ele = stack[top--]; return (a > b) ? a : b;
t[k++] = ele; }
for (j = 1; j <= n; j++) { int knap(int i, int m) {
if (a[ele][j] == 1 && vis[j] == if (i > n) // Changed to i > n to
0) { correctly stop after last object
indeg[j]--; return 0;
if (indeg[j] == 0) { if (w[i] > m)
stack[++top] = j; return knap(i + 1, m);
vis[j] = 1; return max(knap(i + 1, m), knap(i
} + 1, m - w[i]) + p[i]);
} }
} int main() {
} int m, i, max_profit;
printf("\nTopological Ordering is: printf("\nEnter the number of
"); objects: ");
for (i = 1; i <= n; i++) { scanf("%d", &n);
printf("%d ", t[i]); printf("\nEnter the knapsack
} capacity: ");
printf("\n"); scanf("%d", &m);
}
int main() { printf("\nEnter profit followed by
int n, a[20][20], i, j; weight for each object:\n");
printf("Enter the number of for (i = 1; i <= n; i++) {
nodes: "); scanf("%d %d", &p[i], &w[i]);
scanf("%d", &n); }

printf("Enter adjacency max_profit = knap(1, m);

matrix:\n");
for (i = 1; i <= n; i++) { printf("\nMax profit = %d\n",
for (j = 1; j <= n; j++) { max_profit);
scanf("%d", &a[i][j]);
} return 0;
} }
 }
Program7 printf("\nEnter the capacity of
#include <stdio.h> knapsack: ");
void knapsack(int n, float weight[], scanf("%f", &capacity);
float profit[], float capacity) { for (i = 0; i < num; i++) {
float x[20], tp = 0; ratio[i] = profit[i] / weight[i];
int i, u; }
u = capacity; for (i = 0; i < num; i++) {
for (i = 0; i < n; i++) for (j = i + 1; j < num; j++) {
x[i] = 0.0; if (ratio[i] < ratio[j]) {
for (i = 0; i < n; i++) { temp = ratio[j];
if (weight[i] > u) ratio[j] = ratio[i];
break; ratio[i] = temp;
else { temp = weight[j];
x[i] = 1.0; weight[j] = weight[i];
tp += profit[i]; weight[i] = temp
u -= weight[i]; temp = profit[j];
}} profit[j] = profit[i];
if (i < n) profit[i] = temp;
x[i] = u / weight[i]; }}}
tp += x[i] * profit[i]; knapsack(num, weight, profit,
printf("\nThe result vector is: "); capacity);
for (i = 0; i < n; i++) return 0;
printf("%f\t", x[i]); } Program 8
printf("\nMaximum profit is: #include <stdio.h>
%f\n", tp); #define MAX 10
} int s[MAX], x[MAX], d;
int main() { void sumofsub(int p, int k, int r) {
float weight[20], profit[20], int i;
capacity; x[k] = 1;
int num, i, j; if ((p + s[k]) == d) {
float ratio[20], temp; for (i = 1; i <= k; i++) {
printf("\nEnter the number of if (x[i] == 1)
objects: "); printf("%d ", s[i]);
scanf("%d", &num); }
printf("\nEnter the weights and printf("\n");
profits of each object:\n"); }
for (i = 0; i < num; i++) { else if (p + s[k] + s[k + 1] <= d) {
scanf("%f %f", &weight[i], sumofsub(p + s[k], k + 1, r -
&profit[i]); s[k]); }
 if ((p + r - s[k] >= d) && (p + s[k + 1] temp = arr[i];
<= d)) { arr[i] = arr[min_idx];
x[k] = 0; arr[min_idx] = temp;
sumofsub(p, k + 1, r - s[k]); }
}} }
int main() {
int i, n, sum = 0; int main() {
printf("\nEnter the n value: "); int n; // Number of elements
scanf("%d", &n); printf("Enter the value of n: ");
printf("\nEnter the set in scanf("%d", &n);
increasing order:\n");
for (i = 1; i <= n; i++) { int arr[n];
scanf("%d", &s[i]); srand(time(NULL));
} printf("Original Array: ");
printf("\nEnter the max subset for (int i = 0; i < n; i++) {
value: "); arr[i] = rand() % 1000;
scanf("%d", &d); printf("%d ", arr[i]);
for (i = 1; i <= n; i++) { }
sum += s[i]; printf("\n");
} clock_t start_time = clock();
if (sum < d || s[1] > d) { selectionSort(arr, n);
printf("\nNo subset clock_t end_time = clock();
possible\n");
} else { double total_time =
sumofsub(0, 1, sum); (double)(end_time - start_time) /
} CLOCKS_PER_SEC;
return 0;
}} printf("Sorted Array: ");
Program 9 for (int i = 0; i < n; i++) {
#include <stdio.h> printf("%d ", arr[i]);
#include <stdlib.h> }
#include <time.h> printf("\n");
void selectionSort(int arr[], int n) { printf("Time Complexity:
int i, j, min_idx, temp; O(n^2)\n");
for (i = 0; i <= n - 2; i++) { printf("Execution Time: %f
min_idx = i; seconds\n", total_time);
for (j = i + 1; j <= n - 1; j++) {
if (arr[j] < arr[min_idx]) return 0;
min_idx = j;
} }
Program 10 a[i] = rand() % 1000;
#include <stdio.h> printf("%d ", a[i]); }
#include <stdlib.h> printf("\n");
#include <time.h> clock_t start = clock();
int partition(int a[], int low, int high){ quickSort(a, 0, n - 1);
int pivot = a[low]; clock_t end = clock();
int i = low , j = high + 1,temp; printf("Sorted array:\n");
while (1) { for (int i = 0; i < n; i++) {
do { printf("%d ", a[i]); }
i++; printf("\n");
} while (i <= high && a[i] <= double time_taken =
pivot); ((double)(end - start)) /
do { CLOCKS_PER_SEC;
j--; printf("Total time taken to sort %d
} while (a[j] > pivot); elements is %lf seconds\n", n,
if (i >= j) time_taken)
break; return 0; } Program 11
temp = a[i]; #include <stdlib.h>
a[i] = a[j]; #include <stdio.h>
a[j] = temp;} #include <time.h>
temp = a[low]; void merge(int arr[], int l, int m, int
a[low] = a[j]; r) {
a[j] = temp; int i, j, k;
return j; } int n1 = m - l + 1;
void quickSort(int a[], int low, int int n2 = r - m;
high) { int L[n1], R[n2];
if (low < high) { for (i = 0; i < n1; i++)
int k = partition(a, low, high); L[i] = arr[l + i];
quickSort(a, low, k - 1); for (j = 0; j < n2; j++)
quickSort(a, k + 1, high); }} R[j] = arr[m + 1 + j];
int main() { i = 0; j = 0; k = l;
srand(time(0)); while (i < n1 && j < n2) {
int n; if (L[i] <= R[j]) {
printf("Enter the number of arr[k] = L[i];
elements: "); i++;
scanf("%d", &n); } else {
int a[n]; arr[k] = R[j];
printf("Randomly generated j++; }
array:\n"); k++; }
for (int i = 0; i < n; i++) { while (i < n1) {
 arr[k] = L[i]; #define False 0
i++; k++; } int x[10];
while (j < n2) { int n, count;
arr[k] = R[j]; void printsolution() {
j++; k++; } } char c[10][10];
void mergeSort(int arr[], int l, int r) { printf("Solution %d:\n\n",
if (l < r) { ++count);
int m = l + (r - l) / 2; for (int i = 1; i <= n; i++) {
mergeSort(arr, l, m); for (int j = 1; j <= n; j++) {
mergeSort(arr, m + 1, r); c[i][j] = 'X'; } }
merge(arr, l, m, r); } } for (int i = 1; i <= n; i++) {
int main() { c[i][x[i]] = 'Q';
int n, i; } for (int i = 1; i <= n; i++) {
printf("Enter the value of n: "); for (int j = 1; j <= n; j++) {
scanf("%d", &n); printf("%c ", c[i][j]);
int arr[n]; } printf("\n");
srand(time(NULL)); } printf("\n");
printf("Original array:\n"); } int place(int k, int xk) {
for (i = 0; i < n; i++) { for (int i = 1; i <= k - 1; i++) {
arr[i] = rand() % 1000; if ((x[i] == xk) || (abs(i - k) ==
printf("%d ", arr[i]); } abs(x[i] - xk))) {
printf("\n"); return False; } }
clock_t start = clock(); return True; }
mergeSort(arr, 0, n - 1); void nqueen(int k) {
clock_t end = clock(); for (int j = 1; j <= n; j++) {
printf("Sorted array:\n"); if (place(k, j)) {
for (i = 0; i < n; i++) { x[k] = j; // Place queen
printf("%d ", arr[i]); } if (k == n)
printf("\n"); printsolution();
double time_taken = else
((double)(end - start)) / nqueen(k + 1); } } }
CLOCKS_PER_SEC; int main() {
printf("Total time taken to sort %d printf("Enter the number of
elements is %lf seconds\n", n, queens: ");
time_taken); scanf("%d", &n);
return 0; }Program 12 count = 0;
#include <stdio.h> nqueen(1);
#include <stdlib.h> printf("Total solutions: %d\n",
#include <math.h> count);
#define True 1 return 0; }