1.

Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a given
connected undirected graph using Kruskal's algorithm.

ALGORITHM:-

CODE:-
#include <stdio.h>
#define INF 999
#define MAX 100

int P[MAX], C[MAX][MAX];

int find(int v) {
while (P[v])
v = P[v];
return v;
}

int main() {
int i, j, n, k, u, v, min, edge1, edge2, sum = 0;

printf("Enter No. of Nodes: ");

scanf("%d", &n);

for (i = 1; i <= n; i++)

P[i] = 0;

printf("Enter the Adjacency Matrix:-\n");

for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
scanf("%d", &C[i][j]);
if (i == j && C[i][j] == 0)
C[i][j] = INF;
}
}

printf("\nMinimum Cost Spanning Tree:-\n");

for (k = 1; k < n; k++) {
min = INF;
for (i = 1; i < n; i++) {
for (j = 1; j <= n; j++) {
if (i == j) continue;
if (C[i][j] < min) {
u = find(i);
v = find(j);
if (u != v) {
edge1 = i;
edge2 = j;
min = C[i][j];
}
}
}
 }
P[find(edge2)] = find(edge1);
printf("Edge: (%d -> %d), Cost: %d\n",edge1, edge2, min);
sum += min;
}
printf("\nCost of spanning tree is: %d\n", sum);

return 0;
}

OUTPUT:-

PROBLEM:-
2. Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a given
connected undirected graph using Prim's algorithm.

ALGORITHM:-

CODE:-

#include <stdio.h>
#define INF 999

int prims_algorithm(int adj[][10], int N)

{
int i,j,min;
int min_cost = 0, u = 0, v = 0;

//Pick Arbitrary Node

int visit[10] = {0};
visit[0] = 1;

while(1)
{
min = INF;
for(i=0;i<N;++i)
{
//If in MST, don't include
if(!visit[i])
continue;
 //Select min() of all the reachable remaining nodes
for(j=0;j<N;++j)
{
if(!visit[j] && adj[i][j] < min)
{
min = adj[i][j];
u = i;
v = j;
}
}
}

//If new Connection Could Not be Found

if(min == INF)
break;

//If New Connection Found, Add to Visited and Print Connection

visit[v] = 1;
min_cost += min;
printf("Edge: (%d -> %d), Cost: %d\n",u+1,v+1,min);
}

return min_cost;
}

int main()
{
int adj[10][10],N,i,j;
printf("Enter No. of Nodes: ");
scanf("%d",&N);

printf("Enter The Adjacency Matrix:-\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] = INF;
}
 printf("\nMinimum Cost Spanning Tree:-\n");
printf("\nCost of spanning tree is: %d\n",prims_algorithm(adj,N));
return 0;
}

OUTPUT:-

PROBLEM:-
3 a. Design and implement C/C++ Program to solve All-Pairs Shortest Paths problem
using Floyd's algorithm.
b. Design and implement C/C++ Program to find the transitive closure using Warshall's
algorithm.

a.
ALGORITHM:-

CODE:-

#include <stdio.h>
#include <stdlib.h>
#define INF 999

int main()
{
int n,u,v,k;
printf("N: ");
scanf("%d",&n);

int P[n][n];
printf("Input Adjacency Matrix:-\n");
for(u=0;u<n;++u){
for(v=0;v<n;++v){
scanf("%d",&P[u][v]);
 if(!P[u][v] && u!=v)
P[u][v] = INF;
}
}

for(k=0;k<n;++k)
for(u=0;u<n;++u)
for(v=0;v<n;++v)
if(P[u][v] > P[u][k]+P[k][v])
P[u][v] = P[u][k]+P[k][v];

printf("\nShortest Path Pairs:-\n");

for(u=0;u<n;++u){
for(v=0;v<n;++v)
printf("%d ",P[u][v]);
printf("\n");
}

return 0;
}

OUTPUT:-
PROBLEM:-
b.
ALGORITHM:-

CODE:-

#include <stdio.h>
#include <stdlib.h>

int main()
{
int n,u,v,k;
printf("N: ");
scanf("%d",&n);

short P[n][n];
printf("Input Adjacency Matrix:-\n");
for(u=0;u<n*n;++u)
scanf("%hd",&P[u/n][u%n]);

for(k=0;k<n;++k)
for(u=0;u<n;++u)
for(v=0;v<n;++v)
P[u][v] = (P[u][v] || P[u][k] && P[k][v]);
printf("\nTransitive Closure:-\n");
for(u=0;u<n;++u){
for(v=0;v<n;++v)
printf("%d ",P[u][v]);
printf("\n");
 }

return 0;
}

OUTPUT:-

PROBLEM:-

4. Design and implement C/C++ Program to find shortest paths from a given vertex in a
weighted connected graph to other vertices using Dijkstra's algorithm.

ALGORITHM:-
CODE:-
#include <stdio.h>
#include <stdlib.h>
#define INF 999

int main()
{
int N;
printf("No. of Nodes: ");
scanf("%d",&N);

int cost[N][N];
printf("Enter Cost Adjacency Matrix:-\n");
for(int r=0;r<N;++r)
for(int c=0;c<N;++c){
scanf("%d",&cost[r][c]);
cost[r][c] = (cost[r][c] == 0 && r!=c)?INF:cost[r][c];
}

int src;
printf("Enter Source Vertex: ");
scanf("%d",&src);

//Djikstra's Algorithm
int S[N],D[N],P[N];
for(int i=0;i<N;++i)
{
S[i] = 0;
D[i] = cost[src][i];
P[i] = src;
}

S[src] = 1;

int minCost, u;
for(int i=0;i<N-1;++i)
{
minCost = INF;
for(int j=0;j<N;++j)
if(D[j]<minCost && !S[j]){
minCost = D[j];
 u = j;
}

S[u] = 1;

for(int v=0;v<N;++v)
{
if(S[v])
continue;

if(D[v] > D[u]+cost[u][v])

D[v] = D[u]+cost[u][v];
P[v] = u;
}
}

printf("Single Source Shortest Path:-\n");

for(int i=0;i<N;++i)
printf("%d->%d : (%d)\n",src,i,D[i]);

return 0;
}

OUTPUT:-
PROBLEM:-
5. Design and implement C/C++ Program to obtain the Topological ordering of vertices in
a given digraph.

ALGORITHM:-

CODE:-
#include <stdio.h>

int TOrder[10], k = 0;

void topologicalSort(int A[][10], int inDegree[], int n) {

int i, j;
for (i = 1; i <= n; i++)
{
if (inDegree[i] == 0)
{
inDegree[i] = -1;
TOrder[++k] = i;
for (j = 1; j <= n; j++)
if (A[i][j] == 1 && inDegree[j] != -1)
inDegree[j]--;
i = 0;
}
}
}

int main()
{
int A[10][10], inDegree[10], n, i, j;
 printf("No. of Nodes: ");
scanf("%d", &n);

for (i = 1; i <= n; i++)

inDegree[i] = 0;

printf("Enter the Adjacency Matrix:-\n");

for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
scanf("%d", &A[i][j]);
if (A[i][j] == 1)
inDegree[j]++;
}
}

topologicalSort(A, inDegree, n);

if (k != n)
printf("\nTopological ordering not possible");
else {
printf("\nTopological ordering is: ");
for (i = 1; i <= k; i++)
printf("%d ", TOrder[i]);
}

return 0;
}

OUTPUT:-
PROBLEM:-
6. Design and implement C/C++ Program to solve 0/1 Knapsack problem using Dynamic
Programming method.

ALGORITHM:-
CODE:-
#include <stdio.h>

int max(int a, int b) {

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

void knapsack(int profit[], int weight[], int n, int M) {

int i, w;
int dp[n+1][M+1];
 // Build table dp[][] in bottom-up manner
for (i = 0; i <= n; i++) {
for (w = 0; w <= M; w++) {
if (i == 0 || w == 0)
dp[i][w] = 0;
else if (weight[i-1] <= w)
dp[i][w] = max(profit[i-1] + dp[i-1][w-weight[i-1]],
dp[i-1][w]);
else
dp[i][w] = dp[i-1][w];
}
}

// Store the result of the Knapsack

int result = dp[n][M];
printf("\nMaximum Profit : %d", result);

w = M;
int X[n];
for (i = 0; i < n; i++) {
X[i] = 0;
}

// Trace back to find the solution vector

for (i = n; i > 0 && result > 0; i--) {
if (result == dp[i-1][w])
continue;
else {
X[i-1] = 1;
result -= profit[i-1];
w -= weight[i-1];
}
}

printf("\nSolution Vector X[]: ");

for (i = 0; i < n; i++) {
printf("%d ", X[i]);
}
}
int main()
{
int n;
printf("Input No. of Objects: ");
scanf("%d",&n);

int profit[n];
printf("Enter Profits: ");
for(int i=0;i<n;++i)
scanf("%d",&profit[i]);

int weight[n];
printf("Enter Weights: ");
for(int i=0;i<n;++i)
scanf("%d",&weight[i]);

int M;
printf("Enter Capacity: ");
scanf("%d",&M);

knapsack(profit, weight, n, M);

return 0;
}

OUTPUT:-

PROBLEM:-
7. Design and implement C/C++ Program to solve discrete Knapsack and continuous
Knapsack problems using greedy approximation method.

ALGORITHM:-
CODE:-
#include <stdio.h>
#define MAX 50

typedef struct {
int profit;
int weight;
double ratio;
int index;
} Item;

Item items[MAX];
double maxprofit;
double X[MAX];
int n, m;
void greedyKnapsack(int n, Item items[], int m) {
// Sort items based on the ratio in non-increasing order
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (items[i].ratio < items[j].ratio) {
Item temp = items[i];
items[i] = items[j];
items[j] = temp;
}
}
}

int currentWeight = 0;
maxprofit = 0.0;

// Fill the knapsack with items

for (int i = 0; i < n; i++) {
if (currentWeight + items[i].weight <= m) {
X[items[i].index] = 1.0; // Item i is selected
currentWeight += items[i].weight;
maxprofit += items[i].profit;
} else {
// Fractional part of item i is selected
X[items[i].index] = (m - currentWeight) /
(double)items[i].weight;
maxprofit += X[items[i].index] * items[i].profit;
break;
}
}

printf("\nOptimal solution: %.1f\n", maxprofit);

printf("Solution vector X[]: ");
for (int i = 0; i < n; i++) {
printf("%.1f, ", X[i]);
}
printf("\n");
}

int main() {
printf("Enter the No. of objects: ");
 scanf("%d", &n);

printf("Enter the Profits: ");

for (int i = 0; i < n; i++) {
scanf("%d", &items[i].profit);
}

printf("Enter the Weights: ");

for (int i = 0; i < n; i++) {
scanf("%d", &items[i].weight);
items[i].ratio = (double)items[i].profit / items[i].weight;
items[i].index = i;
}

printf("Enter the Maximum capacity: ");

scanf("%d", &m);

// Initialize the solution vector

for (int i = 0; i < n; i++) {
X[i] = 0;
}

greedyKnapsack(n, items, m);

return 0;
}

OUTPUT:-

PROBLEM:-
8. Design and implement C/C++ Program to find a subset of a given set S = {sl, s2, ......,
sn} of n positive integers whose sum is equal to a given positive integer d.
ALGORITHM:-

CODE:-
#include <stdio.h>
#define MAX 10

int S[MAX], X[MAX], D;

void sumOfSub(int p, int k, int r)

{
int i;
X[k] = 1;
if ((p + S[k]) == D)
{
for (i = 1; i <= k; i++)
if (X[i] == 1)
printf("%d ", S[i]);
printf("\n");
}
else if (p + S[k] + S[k + 1] <= D)
 sumOfSub(p + S[k], k + 1, r - S[k]);

if ((p + r - S[k] >= D) && (p + S[k + 1] <= D))

{
X[k] = 0;
sumOfSub(p, k + 1, r - S[k]);
}
}

int main()
{
int i, n, sum = 0;
printf("Input N: ");
scanf("%d", &n);
printf("Input set S(in Increasing Order): ");
for (i = 1; i <= n; i++)
scanf("%d", &S[i]);

printf("Input Max Integer d: ");

scanf("%d", &D);

printf("Possible Subsets:-\n");
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);

return 0;
}

OUTPUT:-
9. Design and implement C/C++ Program to sort a given set of n integer elements using
Selection Sort method and compute its time complexity. Run the program for varied
values of n> 5000 and record the time taken to sort. Plot a graph of the time taken versus
n. The elements can be read from a file or can be generated using the random number
generator.

CODE:-

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define SWAP(x,y) x^=y, y^=x, x^=y;

clock_t start,end;
int n;

void selectionSort(int A[])

{
int i,j,min_idx;

for(i=0; i<n-1; ++i)

{
min_idx = i;
for(j=i+1 ; j<n ;++j)
if(A[j] < A[min_idx])
 min_idx = j;

if(min_idx != i)
SWAP(A[i],A[min_idx]);
}
}

int main()
{
printf("Enter Size of N: ");
scanf("%d",&n);

int A[n];
for(int i=0;i<n;++i)
A[i] = rand()%(n*2);

printf("Unsorted Array:-\n");
for(int i=0;i<n;++i)
printf("%d ,",A[i]);

start = clock();
selectionSort(A);
end = clock();

printf("Time Taken:
%lfms\n",(double)(end-start)/(double)(CLOCKS_PER_SEC)*1000);

printf("Sorted Array:-\n");
for(int i=0;i<n;++i)
printf("%d ,",A[i]);

return 0;
}

OUTPUT:-
10. Design and implement C/C++ Program to sort a given set of n integer elements using
Quick Sort method and compute its time complexity. Run the program for varied values
of n> 5000 and record the time taken to sort. Plot a graph of the time taken versus n. The
elements can be read from a file or can be generated using the random number
generator.

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define SWAP(x,y) x^=y, y^=x, x^=y

clock_t start,end;

int partition(int A[],int low, int high)

{
int key = A[low];
int i = low+1;
int j = high;

while(i<=j){
for(;A[i]<=key;++i);
for(;A[j]>key;--j);

if(i < j)
SWAP(A[i],A[j]);
}
if(j != low)
SWAP(A[j],A[low]);
return j;
}

void quickSort(int A[],int low, int high)

{
if(low<high){
int mid = partition(A,low,high);
quickSort(A,low,mid-1);
quickSort(A,mid+1,high);
}
}

int main()
{
int n;
printf("Enter Size of N: ");
scanf("%d",&n);

int A[n];
 printf("Enter Elements of Array:-\n");
for(int i=0;i<n;++i)
A[i] = rand()%(n*2);

printf("Unsorted Array:-\n");
for(int i=0;i<n;++i)
printf("%d ,",A[i]);

start = clock();
quickSort(A,0,n-1);
end = clock();

printf("\nTime Taken:
%lfμs\n",(double)(end-start)/(double)(CLOCKS_PER_SEC)*1000000);

printf("Sorted Array:-\n");
for(int i=0;i<n;++i)
printf("%d ,",A[i]);

return 0;
}

OUTPUT:-
11. Design and implement C/C++ Program to sort a given set of n integer elements using
Merge Sort method and compute its time complexity. Run the program for varied values
of n> 5000, and record the time taken to sort. Plot a graph of the time taken versus n. The
elements can be read from a file or can be generated using the random number
generator.

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

clock_t start,end;

void merge(int A[], 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] = A[l+i];
for(j=0;j<n2;++j)
R[j] = A[m+1+j];

i=j=0;
k=l;

while(i<n1 && j<n2)

A[k++] = (L[i]<R[j])?L[i++]:R[j++];
while(i<n1)
A[k++] = L[i++];
while(j<n2)
A[k++] = R[j++];
}

void mergeSort(int A[], int l, int r)

{
if(l<r){
int m = l+(r-l)/2;
mergeSort(A,l,m);
mergeSort(A,m+1,r);
merge(A,l,m,r);
}
}

int main()
{
int n;
printf("Enter Size of N: ");
scanf("%d",&n);

int A[n];
printf("Enter Elements of Array:-\n");
for(int i=0;i<n;++i)
A[i] = rand()%(n*2);
 printf("Unsorted Array:-\n");
for(int i=0;i<n;++i)
printf("%d ,",A[i]);

start = clock();
mergeSort(A,0,n-1);
end = clock();

printf("Time Taken:
%lfμs\n",(double)(end-start)/(double)(CLOCKS_PER_SEC)*1000000);

printf("Sorted Array:-\n");
for(int i=0;i<n;++i)
printf("%d ,",A[i]);

return 0;
}

OUTPUT:-
12. Design and implement C/C++ Program for N Queen's problem using Backtracking.

ALGORITHM:-
CODE:-
#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 solutionCount=0;
int r,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);
solutionCount++;
printf("\n");
} else {
r++;
 C[r] = -1;
}
}
else
r--;
}

printf("Solutions Found: %d",solutionCount);

}

int main() {
int n;
printf("Enter the No. of Queens: ");
scanf("%d", &n);
n_queens(n);

return 0;
}

OUTPUT:-