1) Kruskals Program

#include <stdio.h>
void main() {
int cost[10][10];
int parent[10];
int i, j, n, ne = 1;
int a = 0, b = 0, u = 0, v = 0;
int min, mincost = 0;
prin ("Enter the Number of Nodes: ");
scanf("%d", &n);
prin ("Enter the Cost Matrix:\n");a
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
scanf("%d", &cost[i][j]);
if (cost[i][j] == 0)
cost[i][j] = 999;
}
}
for (i = 1; i <= n; i++)
parent[i] = 0;
prin ("\n\tKruskal's Algorithm\n");
prin ("\n\tThe Edges of Minimum Spanning Tree are:\n");
while (ne < n) {
min = 999;
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
if (cost[i][j] < min) {
min = cost[i][j];
a = u = i;
b = v = j;
}
}
 }
while (parent[u] != 0)
u = parent[u];
while (parent[v] != 0)
v = parent[v];
if (u != v) {
prin (" %d Edge [%d , %d] = %d\n", ne++, a, b, min);
mincost += min;
parent[v] = u;
}
cost[a][b] = cost[b][a] = 999;
}
prin ("\n\tMinimum Cost = %d\n", mincost);
}

2) Prims Program
#include <stdio.h>
void main()
{
int cost[10][10];
int visited[10];
int i,j,n,ne=1,a=0,b=0,u=0,v=0;
int min,mincost=0;
prin ("Enter the number of Nodes: ");
scanf("%d",&n);
prin ("Enter the cost Matrix: \n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
 cost[i][j]=999;
}
}
for(i=1;i<=n;i++)
visited[i]=0;

prin (" Prim's Algorithm \n");

prin (" The Edge of Spanning Trees are: \n");
visited[1]=1;
while(ne<n)
{
min=999;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(visited[i]==1 && visited[j]==0 && cost[i][j]<min)
{
min=cost[i][j];
a=i;
b=j;
}
}
}
if(visited[a]==0 || visited[b]==0)
{
prin ("\t %d Edge[%d,%d]=%d \n",ne,a,b,min);
ne++;
mincost+=min;
visited[b]=1;
}
cost[a][b]=cost[b][a]=999;
 }
prin ("\n\t Minimum cost= %d\n",mincost);
}

3 A) Floyd’s Program
#include <stdio.h>
#define INF 999
int min(int a, int b) {
return (a < b) ? a : b;
}
void floyd(int p[][10], int n) {
int i, j, k;
for (k = 1; k <= n; k++) {
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
p[i][j] = min(p[i][j], p[i][k] + p[k][j]);
}
}
}
}

int main() {
int a[10][10], n, i, j;
prin ("\nEnter the number of ver ces: ");
scanf("%d", &n);
prin ("\nEnter the graph data (999 for no edge, 0 for self-loop):\n");
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
scanf("%d", &a[i][j]);
}
}
floyd(a, n);
 prin ("\nShortest Path Matrix:\n");
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
if (a[i][j] == INF)
prin ("INF\t");
else
prin ("%d\t", a[i][j]);
}
prin ("\n");
}
return 0;
}

3 B) Warshall Program
#include <stdio.h>
void warsh(int p[][10], int n) {
int i, j, k;
for (k = 1; k <= n; k++) {
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
p[i][j] = p[i][j] || (p[i][k] && p[k][j]);
}
}
}
}

int main() {
int a[10][10], n, i, j;
prin ("\nEnter the number of ver ces: ");
scanf("%d", &n);
prin ("\nEnter the adjacency matrix (0 for no edge, 1 for edge):\n");
for (i = 1; i <= n; i++) {
 for (j = 1; j <= n; j++) {
scanf("%d", &a[i][j]);
}
}
warsh(a, n);
prin ("\nResultant Path Matrix (Transi ve Closure):\n");
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
prin ("%d ", a[i][j]);
}
prin ("\n");
}
return 0;
}

4 ) Dijikstra’s Program
#include <stdio.h>
int main(void) {
int n, cost[15][15], i, j, s[15], v, u = 0, w, dist[15], num, min;
prin ("Enter the number of ver ces: ");
scanf("%d", &n);
prin ("Enter the cost adjacency matrix (999 for no edge or self-loop):\n");
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
scanf("%d", &cost[i][j]);
}
}
prin ("Enter the source vertex: ");
scanf("%d", &v);
for (i = 1; i <= n; i++) {
s[i] = 0;
dist[i] = cost[v][i];
 }
s[v] = 1;
dist[v] = 0;
for (num = 2; num <= n; num++) {
min = 999;
for (w = 1; w <= n; w++) {
if (!s[w] && dist[w] < min) {
min = dist[w];
u = w;
}
}
s[u] = 1;
for (w = 1; w <= n; w++) {
if (!s[w] && dist[w] > dist[u] + cost[u][w]) {
dist[w] = dist[u] + cost[u][w];
}
}
}
prin ("\nVERTEX\tDESTINATION\tCOST\n");
for (i = 1; i <= n; i++) {
prin (" %d\t %d\t\t %d\n", v, i, dist[i]);
}
return 0;
}

5 ) Topological Sort Program

#include <stdio.h>

int temp[10], k = 0;
void sort(int a[][10], int id[], int n) {
int i, j;
for (i = 1; i <= n; i++) {
 if (id[i] == 0) {
id[i] = -1;
temp[++k] = i;
for (j = 1; j <= n; j++) {
if (a[i][j] == 1 && id[j] != -1)
id[j]--;
}
i = 0;
}
}
}

int main() {
int a[10][10], id[10], n, i, j;
prin ("Enter the number of ver ces: ");
scanf("%d", &n);
for (i = 1; i <= n; i++)
id[i] = 0;
prin ("Enter the adjacency matrix (1 if edge exists, else 0):\n");
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
scanf("%d", &a[i][j]);
if (a[i][j] == 1)
id[j]++;
}
}

sort(a, id, n);

if (k != n) {
prin ("Topological ordering not possible (Graph has a cycle).\n");
} else {
prin ("Topological ordering is: ");
 for (i = 1; i <= k; i++)
prin ("%d ", temp[i]);
prin ("\n");
}
return 0;
}

6) Knapsack Dynamic Programing

#include <stdio.h>

int v[20][20];
int max1(int a, int b) {
return (a > b) ? a : b;
}

int main() {
int i, j, p[20], w[20], n, max;
prin ("\nEnter the number of items: ");
scanf("%d", &n);
for (i = 1; i <= n; i++) {
prin ("Enter the weight and profit of item %d: ", i);
scanf("%d %d", &w[i], &p[i]);
}
prin ("\nEnter the capacity of the knapsack: ");
scanf("%d", &max);
for (i = 0; i <= n; i++)
v[i][0] = 0;
for (j = 0; j <= max; j++)
v[0][j] = 0;
for (i = 1; i <= n; i++) {
for (j = 1; j <= max; j++) {
if (w[i] > j)
 v[i][j] = v[i - 1][j];
else
v[i][j] = max1(v[i - 1][j], v[i - 1][j - w[i]] + p[i]);
}
}
prin ("\nThe DP table is:\n");
for (i = 0; i <= n; i++) {
for (j = 0; j <= max; j++)
prin ("%d\t", v[i][j]);
prin ("\n");
}
prin ("\nThe maximum profit is: %d\n", v[n][max]);
prin ("The most valuable subset is: {");
j = max;
for (i = n; i >= 1; i--) {
if (v[i][j] != v[i - 1][j]) {
prin (" item %d", i);
j -= w[i];
}
}
prin (" }\n");
return 0;
}

7) Greedy Knapsack Program

#include <stdio.h>
#define MAX 50
int p[MAX], w[MAX], x[MAX];
double maxprofit;
int n, m, i;
void greedyKnapsack(int n, int w[], int p[], int m)
{
double ra o[MAX];
for (i = 0; i < n; i++)
{
ra o[i] = (double)p[i] / w[i];
}
for (i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
if (ra o[i] < ra o[j])
{
double temp = ra o[i];
ra o[i] = ra o[j];
ra o[j] = temp;
int temp2 = w[i];
w[i] = w[j];
w[j] = temp2;
temp2 = p[i];
p[i] = p[j];
p[j] = temp2;
}
}
}
int currentWeight = 0;
maxprofit = 0.0;
for (i = 0; i < n; i++)
{
if (currentWeight + w[i] <= m)
{
x[i] = 1; // Item i is selected
currentWeight += w[i];
maxprofit += p[i];
 }
else
{
x[i] = (m - currentWeight) / (double)w[i];
maxprofit += x[i] * p[i];
break;
}
}
prin ("Op mal solu on for greedy method: %.1f\n", maxprofit);
prin ("Solu on vector for greedy method: ");
for (i = 0; i < n; i++)
prin ("%d\t", x[i]);
}
int main()
{
prin ("Enter the number of objects: ");
scanf("%d", &n);
prin ("Enter the objects' weights: ");
for (i = 0; i < n; i++)
scanf("%d", &w[i]);
prin ("Enter the objects' profits: ");
for (i = 0; i < n; i++)
scanf("%d", &p[i]);
prin ("Enter the maximum capacity: ");
scanf("%d", &m);
greedyKnapsack(n, w, p, m);
return 0;
}
8) Subset program
#include <stdio.h>

int s[10], d, n, set[10], count = 0;

int flag = 0;
void display(int count) {
int i;
prin ("{ ");
for (i = 0; i < count; i++)
prin ("%d ", set[i]);
prin ("}\n");
}

void subset(int sum, int i) {

if (sum == d) {
flag = 1;
display(count);
return;
}

if (sum > d || i >= n)

return;
set[count++] = s[i];
subset(sum + s[i], i + 1);
count--;
subset(sum, i + 1);
}

int main() {
int i;
prin ("Enter the number of elements in the set: ");
scanf("%d", &n);
 prin ("Enter the set values:\n");
for (i = 0; i < n; ++i)
scanf("%d", &s[i]);
prin ("Enter the target sum: ");
scanf("%d", &d);
prin ("\nThe subsets that sum to %d are:\n", d);
subset(0, 0);
if (flag == 0)
prin ("There is no solu on.\n");
return 0;
}

9) Selec on Sort
#include <stdio.h>
#include < me.h>
#include <stdlib.h>
void selsort(int a[], int n) {
int i, j, small, pos, temp;
for (j = 0; j < n - 1; j++) {
small = a[j];
pos = j;
for (i = j + 1; i < n; i++) {
if (a[i] < small) {
small = a[i];
pos = i;
}
}
temp = a[j];
a[j] = small;
a[pos] = temp;
}
}
int main() {
int a[100], i, n;
clock_t start, finish;
double seconds;
long counter = 0;
prin ("Enter the n value (<=100): ");
scanf("%d", &n);
for (i = 0; i < n; i++) {
a[i] = rand() % 1000; // random number between 0-999
prin ("%d\t", a[i]);
}
prin ("\n");
start = clock();
do {
selsort(a, n);
counter++;
finish = clock();
} while ((finish - start) < CLOCKS_PER_SEC / 10); // 0.1 seconds = 100ms
seconds = (double)(finish - start) / CLOCKS_PER_SEC;
prin ("The sorted elements:\n");
for (i = 0; i < n; i++)
prin ("%d\t", a[i]);
prin ("\n");
prin ("Total execu on me: %.6f seconds\n", seconds);
prin ("Number of sorts performed: %ld\n", counter);
prin ("Average me per sort: %.9f seconds\n", seconds / counter);

return 0;
}
10) Quick Sort Program
#include <stdio.h>
#include <stdlib.h>
#include < me.h>
#include <conio.h>
#define MAX 10000
void exch(int *p, int *q) {
int temp = *p;

*p = *q;
*q = temp;
}

void quicksort(int a[], int low, int high) {

int i, j, pivot;
if (low >= high)
return;
pivot = low;
i = low + 1;
j = high;

while (i <= j) {
while (i <= high && a[i] <= a[pivot]) i++;
while (a[j] > a[pivot]) j--;
if (i < j)
exch(&a[i], &a[j]);
}
exch(&a[j], &a[pivot]);
quicksort(a, low, j - 1);
quicksort(a, j + 1, high);
}
int main() {
 int n, i;
int a[MAX];
long counter = 0;
double seconds;
clock_t start, finish;
prin ("\nEnter the number of elements to be sorted: ");
scanf("%d", &n);

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

a[i] = rand() % 1000;
prin ("%d\t", a[i]);
}

prin ("\n");
start = clock();
do {
quicksort(a, 0, n - 1);
counter++;
finish = clock();
} while ((finish - start) < CLOCKS_PER_SEC / 10); // run for about 100ms
seconds = (double)(finish - start) / CLOCKS_PER_SEC;
prin ("\nThe sorted elements:\n");
for (i = 0; i < n; i++)
prin ("%d\t", a[i]);
prin ("\n");
prin ("Total execu on me: %.6f seconds\n", seconds);
prin ("Number of sorts performed: %ld\n", counter);
prin ("Average me per sort: %.9f seconds\n", seconds / counter);
return 0;
}
11) Merge Sort
#include <stdio.h>
#include <stdlib.h>
#include < me.h>
#define MAX 10000

void merge(int array[], int low, int mid, int high) {

int i = low, j = mid + 1, k = low;

int c[MAX];
while (i <= mid && j <= high) {
if (array[i] <= array[j])
c[k++] = array[i++];
else
c[k++] = array[j++];
}
while (i <= mid)
c[k++] = array[i++];
while (j <= high)
c[k++] = array[j++];
for (i = low; i < k; i++)
array[i] = c[i];
}

void merge_sort(int array[], int low, int high) {

if (low < high) {
int mid = (low + high) / 2;
merge_sort(array, low, mid);
merge_sort(array, mid + 1, high);
merge(array, low, mid, high);
}
}
int main() {
int n, i;
int array[MAX];
clock_t start, finish;
double seconds;
long counter = 0;
prin ("Enter the size of the array: ");
scanf("%d", &n);
for (i = 0; i < n; i++) {
array[i] = rand() % 1000;
prin ("%d\t", array[i]);

}
prin ("\n");
start = clock();
do {
merge_sort(array, 0, n - 1);
counter++;
finish = clock();
} while ((finish - start) < CLOCKS_PER_SEC / 10); // Run for about 100 ms
seconds = (double)(finish - start) / CLOCKS_PER_SEC;
prin ("\nThe sorted elements:\n");
for (i = 0; i < n; i++)
prin ("%d\t", array[i]);
prin ("\n");
prin ("Total execu on me: %.6f seconds\n", seconds);
prin ("Number of sorts performed: %ld\n", counter);
prin ("Average me per sort: %.9f seconds\n", seconds / counter);
return 0;
}
12) N Queens Program
#include <stdio.h>
#include <conio.h>
#include <math.h>

int a[30], count = 0;

int place(int pos) {
int i;

for (i = 1; i < pos; i++) {

if ((a[i] == a[pos]) || (abs(a[i] - a[pos]) == abs(i - pos)))
return 0;
}
return 1;
}
void print_sol(int n) {
int i, j;
count++;
prin ("\n\nSolu on #%d:\n", count);
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
if (a[i] == j)
prin ("Q\t");
else
prin ("*\t");
}
prin ("\n");
}
}
void queen(int n) {
int k = 1;
a[k] = 0;
 while (k != 0) {
a[k] = a[k] + 1;
while ((a[k] <= n) && !place(k))
a[k]++;
if (a[k] <= n) {
if (k == n)
print_sol(n);
else {
k++;
a[k] = 0;
}
} else {

k--;
}
}
}
void main() {
int n;
clrscr();
prin ("Enter the number of Queens\n");
scanf("%d", &n);
queen(n);
prin ("\nTotal solu ons = %d\n", count);
}