View difference between Paste ID: txcZzfzQ and uwEgL2c3

 //------------------------SELECTION SORT------------------------//
 
 
 #include <stdio.h>
 #include <stdlib.h>
 #include <time.h>
 
 void selection_sort(int arr[], int n) {
     int i, j, min_idx, temp;
     for(i = 0; i < n - 1; i++) {
         min_idx = i;
         for(j = i + 1; j < n; j++) {
             if(arr[j] < arr[min_idx])
                 min_idx = j;
         }
         if(min_idx != i) {
             temp = arr[min_idx];
             arr[min_idx] = arr[i];
             arr[i] = temp;
         }
     }
 }
 void printArray(int arr[], int size) {
     int i;
     for(i = 0; i < size; i++)
         printf("%d ", arr[i]);
     printf("\n");
 }
 int main(void) {
     int i, n;
     clock_t start, end;
     double cpu_time_used;
     printf("Enter the value of n: ");
     scanf("%d", &n);
     int arr[n];
 
     for(i = 0; i < n; i++) {
         arr[i] = rand() % 1000;
         printf("%d", arr[i]);
     }
 
     start = clock();
     selection_sort(arr, n);
     end = clock();
     cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
     printf("Sorted array:\n");
     printArray(arr, n);
     printf("Execution time: %f seconds\n", cpu_time_used);
     return 0;
 }
 
 
 //------------------------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[low];
     int i =low;
     int j = high;
     while(i < j) {
         while(arr[i] <= pivot && i <= high - 1)
             i++;
         while(arr[j] > pivot && j >= low + 1)
             j--;
         if(i < j)
             swap(&arr[i], &arr[j]);
     }
     swap(&arr[low], &arr[j]);
     return j;
 }
 
 void quickSort(int arr[], int low, int high) {
     if(low < high) {
         int partitionIndex = partition(arr, low, high);
         quickSort(arr, low, partitionIndex - 1);
         quickSort(arr, partitionIndex + 1, high);
     }
 }
 
 int main(void) {
     int i, n;
     clock_t start, end;
     double cpu_time_used;
     printf("Enter the value of n: ");
     scanf("%d", &n);
     int arr[n];
     for(i = 0; i < n; i++) {
         arr[i] = rand() % 1000;
         printf("%d", arr[i]);
     }
     start = clock();
     quickSort(arr, 0, n - 1);
     end = clock();
     cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
     printf("\nSorted array: ");
     for(i = 0; i < n; i++)
         printf("%d", arr[i]);
 
     printf("\nExecution time: %f seconds\n", cpu_time_used);
     return 0;
 }
 
 
 //------------------------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++];
         } else {
             arr[k++] = R[j++];
         }
     }
 
     while(i < n1)
         arr[k++] = L[i++];
     while(j < n2)
         arr[k++] = R[j++];
 }
 
 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 main(void) {
     int i, n;
     clock_t start, end;
     double cpu_time_used;
     printf("Enter the value of n: ");
     scanf("%d", &n);
     int arr[n];
     for(i = 0; i < n; i++) {
         arr[i] = rand() % 1000;
         printf("%d ", arr[i]);
     }
     start = clock();
     mergeSort(arr, 0, n - 1);
     end = clock();
     cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
     printf("\nSorted array: ");
     for(i = 0; i < n; i++) printf("%d ", arr[i]);
     printf("\nExecution time: %f seconds\n", cpu_time_used);
     return 0;
 }
 
 
 //------------------------PRIM'S ALGORITHM------------------------//
 
 
 #include <stdio.h>
 
 void my_prim(int adj[][10], int N) {
     int i, j, nv, min, min_cost = 0, u = 0, v = 0;
     int visit[10] = {0};
     visit[0] = 1;
     nv = 1;
     while (nv < N) {
         min = 999;
         for (i = 0; i < N; i++) {
             if (visit[i] == 1) {
                 for (j = 0; j < N; j++) {
                     if (!visit[j] && adj[i][j] < min) {
                         min = adj[i][j];
                         u = i;
                         v = j;
                         printf("\nConsidering edge (%d, %d) with weight %d", i, j, adj[i][j]);
                     }
                 }
             }
         }
         adj[u][v] = 999;
         adj[v][u] = 999;
 
         if (visit[u] == 1 && visit[v] == 0) {
             visit[v] = 1;
             min_cost += min;
             nv++;
             printf("\nEdge %d --> %d : (%d)\n", u, v, min);
         }
     }
     printf("Minimum cost : %d\n", min_cost);
 }
 
 int main() {
     int adj[10][10], N, i, j;
     printf("Enter number of nodes in the graph: ");
     scanf("%d", &N);
 
     printf("Enter the adjacency matrix\n");
     printf("Enter 0 for no connection and weights for connection\n");
 
     for (i = 0; i < N; i++) {
         for (j = 0; j < N; j++) {
             scanf("%d", &adj[i][j]);
             if (adj[i][j] == 0) {
                 adj[i][j] = 999;
             }
         }
     }
     my_prim(adj, N);
     return 0;
 }
 
 
 //------------------------KRUSKAL'S ALGORITHM------------------------//
 
 
 #include <stdio.h>
 
 int ne = 1, min_cost = 0;
 
 int main(void) {
     int n, i, j, min, a, b, u, v, cost[20][20], parent[20];
     printf("Enter the number of vertices: ");
     scanf("%d", &n);
     printf("\nEnter the cost matrix: ");
     for (i = 1; i <= n; i++)
         for (j = 1; j <= n; j++)
             scanf("%d", &cost[i][j]);
     for (i = 1; i <= n; i++)
         parent[i] = 0;
     printf("\nThe edges of 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 && cost[i][j] != 0) {
                     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\t(%d --> %d) = %d\n", ne++, a, b, min);
             min_cost += min;
             parent[v] = u;
         }
         cost[a][b] = cost[b][a] = 999;
     }
     printf("\nMinimum cost = %d\n", min_cost);
 }
 
 
 //------------------------DIJKSTRA'S ALGORITHM------------------------//
 
 
 #include <stdio.h>
 #define infinity 999
 
 void dij(int n, int v, int cost[10][10], int dist[10]) {
     int i, u, count, w, flag[10], min;
     for (i = 1; i <= n; i++) {
         flag[i] = 0;
         dist[i] = cost[v][i];
     }
     count = 2;
     while (count <= n) {
         min = infinity;
         for (w = 1; w <= n; w++) {
             if (dist[w] < min && !flag[w]) {
                 min = dist[w];
                 u = w;
             }
         }
         flag[u] = 1;
         count++;
         for (w = 1; w <= n; w++) {
             if ((dist[u] + cost[u][w] < dist[w]) && !flag[w])
                 dist[w] = dist[u] + cost[u][w];
         }
     }
 }
 
 int main(void) {
     int n, v, i, j, cost[10][10], dist[10];
     printf("\nEnter the number of nodes: ");
     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] = infinity;
         }
     }
     printf("\nEnter the source vertex: ");
     scanf("%d", &v);
     dij(n, v, cost, dist);
     printf("\nShortest Path:\n");
     for (i = 1; i <= n; i++) {
         if (i != v)
             printf("%d --> %d, cost = %d\n", v, i, dist[i]);
     }
 }
 
 
 //-----------------PROGRAM 3a: Floyd's Algo.-----------------//
 
 #include <stdio.h>
 
 int min(int a, int b) {
     return (a < b) ? a : b;
 }
 void floyd(int p[10][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(void) {
     int a[10][10], n, i, j;
     printf("Enter value of n: ");
     scanf("%d", &n);
     printf("Enter the graph data:\n");
     for (i = 1; i <= n; i++) {
         for (j = 1; j <= n; j++) {
             scanf("%d", &a[i][j]);
             if (i != j && a[i][j] == 0) a[i][j] = 999;
         }
     }
     floyd(a, n);
     printf("Shortest path matrix:\n");
     for (i = 1; i <= n; i++) {
         for (j = 1; j <= n; j++) {
             printf("%d ", a[i][j]);
         }
         printf("\n");
     }
 }
 
 //-----------------PROGRAM 3b: Warshall's Algo.-----------------//
 
 #include <stdio.h>
 
 void warshall(int[10][10], int);
 
 int main(void) {
     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 ", a[i][j]);
         }
         printf("\n");
     }
     warshall(a, n);
 }
 
 void warshall(int p[10][10], int n) {
     int i, j, k;
     for (k = 1; k <= n; k++) {
         for (j = 1; j <= n; j++) {
             for (i = 1; i <= n; i++) {
                 if ((p[i][j] == 0) && (p[i][k] == 1) && (p[k][j] == 1))
                     p[i][j] = 1;
             }
         }
     }
     printf("The path matrix is:\n");
     for (i = 1; i <= n; i++) {
         for (j = 1; j <= n; j++) {
             printf("%d ", p[i][j]);
         }
         printf("\n");
     }
 }
 
 //-----------------PROGRAM 5: Topological Sorting-----------------//
 
 #include <stdio.h>
 int a[10][10], n, indegree[10];
 
 void find_indegree() {
 	int j, i, sum;
 	for (j = 0; j < n; j++) {
 		sum = 0;
 		for (i = 0; i < n; i++)
 			sum += a[i][j];
 		indegree[j] = sum;
 	}
 }
 
 void topology() {
 	int i, u, v, t[10], s[10], top = -1, k = 0;
 	find_indegree();
 	for (i = 0; i < n; i++) {
 		if (indegree[i] == 0) s[++top] = i;
 	}
 
 	while (top != -1) {
 		u = s[top--];
 		t[k++] = u;
 		for (v = 0; v < n; v++) {
 			if (a[u][v] == 1) {
 				indegree[v]--;
 				if (indegree[v] == 0) s[++top] = v;
 			}
 		}
 	}
 	printf("The topological sequence is:\n");
 	for (i = 0; i < n; i++)
 		printf("%d ", t[i]);
 	printf("\n");
 }
 
 int main(void) {
 	int i, j;
 	printf("Enter number of nodes: ");
 	scanf("%d", &n);
 	printf("Enter adjacency matrix:\n");
 	for (i = 0; i < n; i++)
 		for (j = 0; j < n; j++)
 			scanf("%d", &a[i][j]);
 	topology();
 }
 
 //-----------------PROGRAM 6: Knapsack 0/1-----------------//
 
 #include <stdio.h>
 
 int w[10], p[10], v[10][10], n, i, j, cap, x[10] = {0};
 
 int max(int i, int j) {
 	return (i > j ? i : j);
 }
 
 int knap(int i, int j) {
 	int value;
 	if (v[i][j] < 0) {
 		if (j < w[i])
 			value = knap(i - 1, j);
 		else
 			value = max(knap(i - 1, j), p[i] + knap(i - 1, j - w[i]));
 		v[i][j] = value;
 	}
 	return v[i][j];
 }
 
 int main(void) {
 	int profit, count = 0;
 	printf("\nEnter the number of elements: ");
 	scanf("%d", &n);
 	printf("Enter the profits and weights of the elements:\n");
 	for (i = 1; i <= n; i++) {
 		printf("For item no. %d\n", i);
 		scanf("%d%d", &p[i], &w[i]);
 	}
 	printf("\nEnter the capacity: ");
 	scanf("%d", &cap);
 	for (i = 0; i <= n; i++) {
 		for (j = 0; j <= cap; j++) {
 			if ((i == 0) || (j == 0))
 				v[i][j] = 0;
 			else
 				v[i][j] = -1;
 		}
 	}
 
 	profit = knap(n, cap);
 	i = n;
 	j = cap;
 	while (j != 0 && i != 0) {
 		if (v[i][j] != v[i - 1][j]) {
 			x[i] = 1;
 			j = j - w[i];
 			i--;
 		}
 		else
 			i--;
 	}
 	printf("Items included are:\n");
 	printf("S.no.\tWeight\tProfit\n");
 	for (i = 1; i <= n; i++)
 		if (x[i])
 			printf("%d\t%d\t%d\n", ++count, w[i], p[i]);
 	printf("Total profit = %d\n", profit);
 }
 
 //-----------------PROGRAM 7: Knapsack Continuous & Discrete-----------------//
 
 #include <stdio.h>
 void knapsack(int n, float weight[], float profit[], float capacity)
 {
 	float x[20], tp = 0;
 	int i, j, u;
 	u = capacity;
 
 	for(i = 0; i < n; i++) x[i] = 0.0;
 
 	for (i = 0; i < n; i++) {
 		if (weight[i] > u)
 			break;
 		else {
 			x[i] = 1.0;
 			tp = tp + profit[i];
 			u = u - weight[i];
 		}
 	}
 	if (i < n)
 		x[i] = u / weight[i];
 
 	tp = tp + (x[i] * profit[i]);
 	printf("\nThe result vector is: ");
 	for (i = 0; i < n; i++)
 		printf("%f\t", x[i]);
 
 	printf("\nMaximum profit is: %f\n", tp);
 }
 
 void Dknapsack(int n, float weight[], float profit[], float capacity) {
 	float x[20], tp = 0;
 	int i, j, u;
 	u = capacity;
 	for (i = 0; i < n; i++) x[i] = 0.0;
 	for (i = 0; i < n; i++) {
 		if (weight[i] > u)
 			continue;
 		else {
 			x[i] = 1.0;
 			tp = tp + profit[i];
 			u = u - weight[i];
 		}
 	}
 	printf("\nThe result vector is: ");
 	for (i = 0; i < n; i++) printf("%f\t", x[i]);
 	printf("\nMaximum profit is: %f\n", tp);
 }
 
 int main(void) {
 	float weight[20], profit[20], capacity;
 	int num, i, j;
 	float ratio[20], temp;
 
 	printf("\nEnter the no. of objects: ");
 	scanf("%d", &num);
 	printf("\nEnter the weights of each object:\n");
 	for (i = 0; i < num; i++) scanf("%f", &weight[i]);
 
 	printf("Enter the profits of each object:\n");
 	for (i = 0; i < num; i++) scanf("%f", &profit[i]);
 
 	printf("Enter the capacity of knapsack: ");
 	scanf("%f", &capacity);
 
 	for (i = 0; i < num; i++) ratio[i] = profit[i] / weight[i];
 
 	for (i = 0; i < num; i++) {
 		for (j = i + 1; j < num; j++) {
 			if (ratio[i] < ratio[j]) {
 				temp = ratio[j];
 				ratio[j] = ratio[i];
 				ratio[i] = temp;
 
 				temp = weight[j];
 				weight[j] = weight[i];
 				weight[i] = temp;
 
 				temp = profit[j];
 				profit[j] = profit[i];
 				profit[i] = temp;
 			}
 		}
 	}
 	knapsack(num, weight, profit, capacity);
 	Dknapsack(num, weight, profit, capacity);
 	return 0;
 }
 
 //-----------------PROGRAM 8: Subset Sum-----------------//
 
 #include <stdio.h>
 
 int s[10], x[10], d;
 void sumofsub(int, int, int);
 
 int main(void) {
 	int i, n, sum = 0;
 	printf("Enter the size of the set: ");
 	scanf("%d", &n);
 	printf("Enter the set in increasing order:\n");
 	for (i = 1; i <= n; i++)
 		scanf("%d", &s[i]);
 	printf("Enter the value of d: ");
 	scanf("%d", &d);
 
 	for (i = 1; i <= n; i++) sum = sum + s[i];
 	if (sum < d || s[1] > d)
 		printf("\nNo subset possible");
 	else {
 		sumofsub(0, 1, sum);
 	}
 }
 
 void sumofsub(int m, int k, int r) {
 	int i = 1;
 	x[k] = 1;
 	if ((m + s[k]) == d)
 	{
 		printf("Subset: ");
 		for(i = 1; i <= k; i++)
 			if (x[i] == 1)
 				printf("%d ", s[i]);
 		printf("\n");
 	} else {
 		if (m + s[k] + s[k + 1] <= d)
 			sumofsub(m + s[k], k + 1, r - s[k]);
 	}
 	if ((m + r - s[k] >= d) && (m + s[k + 1] <= d)) {
 		x[k] = 0;
 		sumofsub(m, k + 1, r - s[k]);
 	}
 }
 
 //-----------------PROGRAM 12: N Queens-----------------//
 
 #include <stdio.h>
 #include <stdlib.h>
 #define MAX 50
 int can_place(int c[], int r) {
 	int i;
 	for (i = 0; i < r; i++) {
 		if (c[i] == c[r] || (abs(c[i] - c[r]) == abs(i - r)))
 			return 0;
 	}
 	return 1;
 }
 
 void display(int c[], int n) {
 	int i, j;
 	char cb[10][10];
 	for (i = 0; i < n; i++ )
 		for (j = 0; j < n; j++)
 			cb[i][j] = '-';
 	for (i = 0; i < n; i++)
 		cb[i][c[i]] = 'Q';
 
 	for (i = 0; i < n; i++) {
 		for (j = 0; j < n; j++)
 			printf("%c", cb[i][j]);
 		printf("\n");
 	}
 }
 
 void n_queens(int n) {
 	int r;
 	int c[MAX];
 	c[0] = -1;
 	r = 0;
 	while ( r >= 0) {
 		c[r]++;
 		while (c[r] < n && !can_place(c, r))
 			c[r]++;
 		if (c[r] < n) {
 			if (r == n - 1) {
 				display(c, n);
 				printf("\n\n");
 			}
 			else {
 				r++;
 				c[r] = -1;
 			}
 		}
 		else r--;
 	}
 }
 
 int main(void) {
 	int n;
 	printf("\nEnter the number of queens: ");
 	scanf("%d", &n);
 	n_queens(n);
 }