// 1. Kruskal's Algorithm
#include <stdio.h>
int n,a,b,u,v,i,j,min;
int ne=1,cost[20][20], parent[20], mincost=0;
int main(){
printf("Enter the number of vertices: ");
scanf("%d", &n);
printf("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++){
parent[i] = 0;
}
printf("Edge of Spanning Tree: \n");
while(ne<n){
for(i=1,min=999; 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]){
u = parent[u];
}
while(parent[v]){
v = parent[v];
}
if(u != v){
printf("Edge %d: (%d %d) Cost: %d\n",ne++,a,b,min);
mincost += min;
parent[v] = u;
}
cost[a][b] = cost[b][a] = 999;
}
printf("Minimum Cost: %d\n",mincost);
return 0;
}

// 2. Prim's Algorithm
#include<stdio.h>
int a,b,u,v,n,i,j,ne=1;
int visited[10]={0},min,mincost=0,cost[10][10];
void main()
{
printf("\n Enter the number of nodes:");
scanf("%d",&n);
printf("\n Enter the adjacency 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;
}
visited[1]=1;
printf("\n");
while(ne<n)
{
for(i=1,min=999;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]<min)
if(visited[i]!=0)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
if(visited[u]==0 || visited[v]==0)
{
printf("\n Edge %d:(%d %d) cost:%d",ne++,a,b,min);
mincost+=min;
visited[b]=1;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n Minimun cost=%d",mincost);
}

// 3a. Floyd's and Warshall's Algorithm
#include <stdio.h>
#include <limits.h>
#define V 4
void floydWarshall(int graph[V][V]){
int dist[V][V];
for(int i=0; i<V; i++){
for(int j=0; j<V; j++){
dist[i][j] = graph[i][j];
}
}
for(int k=0; k<V; k++){
for(int i=0; i<V; i++){
for(int j=0; j<V; j++){
if(dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][k] + dist[k][j] < dist[i][j]){
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
printf("Shortest distance between every pair of vertices: \n");
for(int i=0; i<V; i++){
for(int j=0; j<V; j++){
if(dist[i][j] == INT_MAX){
printf("INF\t");
}
else{
printf("%d\t", dist[i][j]);
}
}
printf("\n");
}
}
int main(){
int graph[V][V] = {
{0,INT_MAX,3,INT_MAX}, {2,0,INT_MAX,INT_MAX}, {INT_MAX,7,0,1}, {6,INT_MAX,INT_MAX,0}
};
floydWarshall(graph);
return 0;
}

// 3b. Transitive Closure

include <stdio.h>

int n,a[10][10],p[10][10];
void path()
{
int i,j,k;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
p[i][j]=a[i][j];
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(p[i][k]==1&&p[k][j]==1) p[i][j]=1;
}
void main()
{
int i,j;
printf("Enter the number of nodes:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
path();
printf("\nThe path matrix is showm below\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf("%d ",p[i][j]);
printf("\n");
}
}

// 4. Dijkstra's Algo
#include<stdio.h>
void dij(int, int [20][20], int [20], int [20], int);
void main() {
int i, j, n, visited[20], source, cost[20][20], d[20];
printf("Enter no. of vertices: ");
scanf("%d", &n);
printf("Enter the cost adjacency matrix\n");
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
scanf("%d", &cost[i][j]);
}
}
printf("\nEnter the source node: ");
scanf("%d", &source);
dij(source, cost, visited, d, n);
for (i = 1; i <= n; i++) {
if (i != source)
printf("\nShortest path from %d to %d is %d", source, i, d[i]);
}
}
void dij(int source, int cost[20][20], int visited[20], int d[20], int n) {
int i, j, min, u, w;
for (i = 1; i <= n; i++) {
visited[i] = 0;
d[i] = cost[source][i];
}
visited[source] = 1;
d[source] = 0;
for (j = 2; j <= n; j++) {
min = 999;
for (i = 1; i <= n; i++) {
if (!visited[i]) {
if (d[i] < min) {
min = d[i];
u = i;
}
}
}
visited[u] = 1;
for (w = 1; w <= n; w++) {
if (cost[u][w] != 999 && visited[w] == 0) {
if (d[w] > cost[u][w] + d[u])
d[w] = cost[u][w] + d[u];
}
}
}
}

// 5. Topological Sorting
#include <stdio.h>

void findIndegree(int[10][10], int[10], int);
void topologicalSort(int, int[10][10]);

int main()
{
int a[10][10], i, j, n;
printf("Enter the no of nodes: ");
scanf("%d", &n);
printf("Enter the adjacency matrix: \n");
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
scanf("%d", &a[i][j]);
}
}
printf("The adjacency matrix is: \n");
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
printf("%d\t", a[i][j]);
}
printf("\n");
}
topologicalSort(n, a);
return 0;
}

void findIndegree(int a[10][10], int indegree[10], int n)
{
int i, j, sum;
for (j = 1; j <= n; j++)
{
sum = 0;
for (i = 1; i <= n; i++)
{
sum = sum + a[i][j];
}
indegree[j] = sum;
}
}

void topologicalSort(int n, int a[10][10])
{
int k, top, indegree[20], i, stack[20], u, v, t[100];
k = 1;
top = -1;
findIndegree(a, indegree, n);
for (int i = 1; i <= n; i++)
{
if (indegree[i] == 0)
{
stack[++top] = i;
}
}
while (top != -1)
{
u = stack[top--];
t[k++] = u;
for (v = 1; v <= n; v++)
{
if (a[u][v] == 1)
{
indegree[v]--;
if (indegree[v] == 0)
{
stack[++top] = v;
}
}
}
}
printf("Topological Sequence is \n");
for (i = 1; i <= n; i++)
{
printf("%d\t", t[i]);
}
}

// 6. Knapsack DP
#include <stdio.h>
#define MAX 50

int p[MAX], w[MAX], n;
int knapsack(int, int);
int max(int, int);

int main() {
int m, i, optsoln;
printf("Enter no. of objects: ");
scanf("%d", &n);
printf("\nEnter the weights:\n");
for (i = 1; i <= n; i++)
scanf("%d", &w[i]);
printf("\nEnter the profits:\n");
for (i = 1; i <= n; i++)
scanf("%d", &p[i]);
printf("\nEnter the knapsack capacity: ");
scanf("%d", &m);
optsoln = knapsack(1, m);
printf("\nThe optimal solution is: %d", optsoln);
return 0;
}

int knapsack(int i, int m) {
if (i == n)
return (w[n] > m) ? 0 : p[n];
if (w[i] > m)
return knapsack(i + 1, m);
return max(knapsack(i + 1, m), knapsack(i + 1, m - w[i]) + p[i]);
}

int max(int a, int b) {
if (a > b)
return a;
else
return b;
}

// 7. knapsack greedy
#include <stdio.h>
#include <stdlib.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
void knapsack(int n, int c, int p[], int w[]) {
int v[n+1][c+1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= c; j++) {
if (i == 0 || j == 0) {
v[i][j] = 0;
} else if (w[i-1] <= j) {
v[i][j] = max(v[i-1][j], p[i-1] + v[i-1][j-w[i-1]]);
} else {
v[i][j] = v[i-1][j];
}
}
}
printf("Optimal Solution: %d\n", v[n][c]);
printf("The objects picked up into the knapsack are: ");
int i = n, j = c;
while (i > 0) {
if (v[i][j] != v[i-1][j]) {
printf("%d ", i);
j -= w[i-1];
}
i--;
}
printf("\n");
}
int main() {
int n, c;
printf("Enter the number of objects: ");
scanf("%d", &n);
if (n <= 0) {
printf("The number of objects must be a positive integer.\n");
return 1;
}
printf("Enter the capacity of the knapsack: ");
scanf("%d", &c);
if (c <= 0) {
printf("The capacity of the knapsack must be a positive integer.\n");
return 1;
}
int p[n], w[n];
printf("Enter the profit for each of the %d objects: \n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &p[i]);
if (p[i] < 0) {
printf("Profit must be a non-negative integer.\n");
return 1;
}
}
printf("Enter the weight for each of the %d objects: \n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &w[i]);
if (w[i] < 0) {
printf("Weight must be a non-negative integer.\n");
return 1;
}
}
knapsack(n, c, p, w);
return 0;
}

// 8. subset
#include<stdio.h>
void subset(int,int,int);
int x[10],w[10],d,count=0;
void main()
{
int i,n,sum=0;
printf("Enter the no. of elements: ");
scanf("%d",&n);
printf("\nEnter the elements in ascending order:\n");
for(i=0;i<n;i++)
scanf("%d",&w[i]);
printf("\nEnter the sum: ");
scanf("%d",&d);
for(i=0;i<n;i++)
sum=sum+w[i];
if(sum<d)
{
printf("No solution\n");
return;
}
subset(0,0,sum);
if(count==0)
{
printf("No solution\n");
return;
}
}
void subset(int cs,int k,int r)
{
int i;
x[k]=1;
if(cs+w[k]==d)
{
printf("\n\nSubset %d\n",++count);
for(i=0;i<=k;i++)
if(x[i]==1)
printf("%d\t",w[i]);
}
else
if(cs+w[k]+w[k+1]<=d)
subset(cs+w[k],k+1,r-w[k]);
if(cs+r-w[k]>=d && cs+w[k]<=d)
{
x[k]=0;
subset(cs,k+1,r-w[k]);
}
}

// 9. Selection Sort
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void selectionSort(int arr[], int n) {
int i, j, minIndex, temp;
for (i = 0; i < n - 1; i++) {
minIndex = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
int generateRandomNumber() {
return rand() % 1000;
}
int main() {
int n;
int* arr = (int*)malloc(n * sizeof(int));
printf("enter size of array: ");
scanf("%d",&n);
srand(time(NULL));
printf("Random numbers for n = %d:\n", n);
for (int i = 0; i < n; i++) {
arr[i] = generateRandomNumber();
printf("%d ", arr[i]);
}
printf("\n");
clock_t start = clock();
selectionSort(arr, n);
clock_t end = clock();
double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("\nTime taken to sort for n = %d: %lf seconds\n\n", n, time_taken);
printf("Sorted numbers for n = %d:\n", n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n\n");
free(arr);
return 0;
}

// 10. Quick Sort
#include <stdio.h>
#include <stdlib.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 - 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);
}
}
int generateRandomNumber() {
return rand() % 1000;
}
int main() {
int n;
int arr = (int)malloc(n * sizeof(int));
printf("enter size of array: ");
scanf("%d",&n);
srand(time(NULL));
printf("Random numbers for n = %d:\n", n);
for (int i = 0; i < n; i++) {
arr[i] = generateRandomNumber();
printf("%d ", arr[i]);
}
printf("\n");
clock_t start = clock();
quickSort(arr, 0, n - 1);
clock_t end = clock();
double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("\nTime taken to sort for n = %d: %lf seconds\n\n", n, time_taken);
printf("Sorted numbers for n = %d:\n", n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n\n");
free(arr);
return 0;
}

// 11. Merge Sort
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
int generateRandomNumber() {
return rand() % 1000;
}
int main() {
int n = 6000;
int* arr = (int*)malloc(n * sizeof(int));
printf("enter size of array");
scanf("%d",&n);
srand(time(NULL));
printf("Random numbers for n = %d:\n", n);
for (int i = 0; i < n; i++) {
arr[i] = generateRandomNumber();
printf("%d ", arr[i]);
}
printf("\n");
clock_t start = clock();
mergeSort(arr, 0, n - 1);
clock_t end = clock();
double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("\nTime taken to sort for n = %d: %lf seconds\n\n", n, time_taken);
printf("Sorted numbers for n = %d:\n", n);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n\n");
free(arr);
return 0;
}

// 12. N queen
#define N 4
#include <stdbool.h>
#include <stdio.h>
void printSolution(int board[N][N])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(board[i][j])
printf("Q ");
else
printf(". ");
}
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) {
if (col >= N)
return true;
for (int 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, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };
if (solveNQUtil(board, 0) == false) {
printf("Solution does not exist");
return false;
}
printSolution(board);
return true;
}
int main()
{
solveNQ();
return 0;
}