1.Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal's algorithm.

#include<stdio.h>

int parent[10],t[10][3],a[10][10];

int find(int v)

while(parent[v])

v = parent[v];

return v;

void union1(int i,int j)

parent[j] = i;

void kruskal(int n)

int k,i,j,u,v,min,r,c,sum=0;

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

min = 999;

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

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

if(i == j) continue;

if(a[i][j] < min)

u = find(i);

v = find(j);
 if(u != v)

r = i, c = j, min = a[i][j];

union1(r,find(c));

t[k][1] = r;

t[k][2] = c;

sum += min;

printf("\nCost of Spanning Tree = %d",sum);

printf("\nEdges of Spanning Tree\n");

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

printf("%d -> %d\n",t[i][1],t[i][2]);

int main()

int i,j,n;

printf("\nEnter the number of vertices : ");

scanf("%d",&n);

printf("\nEnter the Adjacency Matrix(999 for NoEdge)\n");

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

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

scanf("%d",&a[i][j]);

kruskal(n);

return 0;

}
2.Find Minimum Cost Spanning Tree of a given undirected graph using Prim’s algorithm.

#include<stdio.h>

void prims(int c[10][10],int v[10],int n)

int i,j,v1,v2,min,edges=0;

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

v[i]=0;

v[0]=1;

while(edges<n-1)

min=999;

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

for(j=0;j<n;j++)

if(v[i]==1 && v[j]==0 && c[i][j]<min)

min=c[i][j];

v1=i;

v2=j;

if(min=999)

printf("\nSpanning Tree does not exist");

else

v[v2]=1;

printf("\nEdges %d %d has been selected and its cost is

}
 edges++;

int main()

int i,j,c[10][10],v[10];

printf("\nEnter the number of vertices : ");

scanf("%d",&n);

printf("\nEnter the cost of matrix : \n");

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

for(j=0;j<n;j++)

scanf("%d",&c[i][j]);

if(c[i][j]==0)

c[i][j]=999;

printf("\nThe Spanning Tree is \n");

prims(c,v,n);

return 0;

OUTPUT:
3a. Design and implement C/C++ Program to solve All-Pairs Shortest Paths problem using Floyd's
algorithm.

void main()

int a[100][100], i, j, k, n;

printf("Enter the number of vertices in the Graph : ");

scanf("%d",&n);

printf("Enter the cost matrix (enter 999 if no edge exists)\n"); for( i = 0 ; i < n ; i++)

for( j = 0 ; j < n ; j++)

scanf("%d",&a[i][j]);

for( k = 0 ; k < n ; k++)

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

for( j = 0 ; j < n ; j++)

if(a[i][j]>a[i][k]+a[k][j])

a[i][j]= a[i][k]+a[k][j];

printf("the shortest path matrix is:\n");

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

for( j = 0 ; j < n ; j++)

printf("%d\t",a[i][j]);

Printf(“\n”);

}
3b. Design and implement C/C++ Program to find the transitive closure using Warshal's algorithm.

void main()

int a[100][100], i, j, k, n;

printf("Enter the number of vertices in the Graph : ");

scanf("%d",&n);

printf("Enter the cost matrix (enter 0 if no edge exists)\n"); for( i = 0 ; i < n ; i++)

for( j = 0 ; j < n ; j++)

scanf("%d",&a[i][j]);

for( k = 0 ; k < n ; k++)

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

for( j = 0 ; j < n ; j++)

if(a[i][j]||a[i][k]&&a[k][j])

a[i][j]= 1

printf("the shortest path matrix is:\n");

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

for( j = 0 ; j < n ; j++)

printf("%d\t",a[i][j]);

Printf(“\n”);

}
4.From a given vertex in a weighted connected graph, find shortest paths to other vertices using
Dijkstra's algorithm.

#include<stdio.h>

int minimum(int,int);

int main()

int cost[20][20],s[20],d[20];

int source,n,mini,u;

int i,j,v;

printf("Enter the number of verticies : ");

scanf("%d",&n);

printf("Enter the weights of the graph\n");

printf("If no connection enter 999 and for self loop enter 0\n");

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

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

scanf("%d",&cost[i][j]);

printf("Enter the source node : ");

scanf("%d",&source);

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

s[i]=0;

d[i]=cost[source][i];

s[source]=1;

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

{
 mini=999;

u=0;

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

if(d[j]<mini && s[j]==0)

mini=d[j];

u=j;

s[u] = 1;

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

if(s[v]==0)

d[v]=minimum(d[v],d[u]+cost[u][v]);

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

printf("Shortest Path From %d to %d is = %d\n",source,i,d[i]);

int minimum(int a,int b)

return((a<b)?a:b);

OUTPUT:

Enter the number of verticies : 4

Enter the weights of the graph

# include <stdio.h>

# include <stdlib.h>

int main(void){

int i, j;

int k, n;

int a[10][10]; // adjacency matrix

int indeg[10] = {0}; // number of incoming edges

int flag[10] = {0}; // checked or not

int count=0; // count value for sorting vertices

printf("Enter the no of vertices: ");

scanf("%d",&n);

printf("Enter the adjacency matrix:\n");

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

printf("Enter row %d\n",i+1);

for(j=0;j<n;j++)

scanf("%d",&a[i][j]); // enter the adjacency matrix

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

for(j=0;j<n;j++)

indeg[i]+=a[j][i]; // number of incoming edges updated

printf("\nThe topological order is:");

while(count<n){

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

if((indeg[k]==0) && (flag[k] ==0)) // zero incoming edges && not sorted yet

printf("%d ", k+1);

flag[k]=1; //checked

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

if(a[k][i]==1){

a[k][i]=0; // delete the sorted vertice's outgoing edges

indeg[i]--; // subtract indeg since the outgoind edge is deleted

count++; // update the iteration count

}
6 .Design and implement C/C++ Program to solve 0/1 Knapsack problem using Dynamic
Programming method.

PROGRAM:

#include<stdio.h>

int w[10],p[10],n;

int max(int a,int b)

return a>b?a:b;

int knap(int i,int m)

if(i==n) return w[i]>m?0:p[i];

if(w[i]>m) return knap(i+1,m);

return max(knap(i+1,m),knap(i+1,m-w[i])+p[i]);

int main()

int m,i,max_profit;

printf("\nEnter the no. of objects:");

scanf("%d",&n);

printf("\nEnter the knapsack capacity:");

scanf("%d",&m);

printf("\nEnter profit followed by weight:\n");

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

scanf("%d %d",&p[i],&w[i]);

max_profit=knap(1,m);

printf("\nMax profit=%d",max_profit);

return 0;
}

Input/Output:

Enter the no. of objects:4

Enter the knapsack capacity:6

Enter profit followed by weight:

78 2

45 3

92 4

71 5

Max profit=170
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. analysis: worst case, average case and
best case.

#include <stdio.h>

#include <sys/time.h>

#include <unistd.h>

void selection(int a[], int n)

int i, j, min;

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

min = i;

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

if (a[j] < a[min])

min = j;

int temp = a[min];

a[min] = a[i];

a[i] = temp;

void printArr(int a[], int n)

int i;

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

printf("%d ", a[i]);

int main()

int a[10000],n, i;

struct timeval t;

double s, e;

printf("Enter the number of elements\n");

scanf("%d",&n);

printf("Before sorting array elements are - \n");

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

a[i]=random()%100;

printArr(a, n);

gettimeofday(&t,NULL);

s=t.tv_sec+(t.tv_usec/1000000.0);

selection(a, n);

gettimeofday(&t,NULL);

e=t.tv_sec+(t.tv_usec/1000000.0);

printf("\nAfter sorting array elements are - \n");

printArr(a, n);

printf("\ntime taken to sort %d elements is %lf\n", n, (e-s));

return 0;

}
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.

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

int p,i,j,temp;

p=a[low];

i=low ;

j=high+1;

do

do {i++;}while(a[i]<p);

do {j--;}while(a[j]>p);

temp=a[i];

a[i]=a[j];

a[j]=temp;

}while(i<j);

temp=a[i];

a[i]=a[j];

a[j]=temp;

temp=a[low];

a[low]=a[j];

a[j]=temp;

return j;

void qsort(int a[], int low, int high)

if(low<high)
{

int s=partition(a, low, high);

qsort(a,low,s-1);

qsort(a,s+1,high);

void printArr(int a[], int n)

int i;

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

printf("%d ", a[i]);

int main()

int a[10000],n, i;

struct timeval t;

double s, e;

printf("Enter the number of elements\n");

scanf("%d",&n);

printf("Before sorting array elements are - \n");

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

a[i]=random()%100;

printArr(a, n);

gettimeofday(&t,NULL);

s=t.tv_sec+(t.tv_usec/1000000.0);

qsort(a, 0, n-1);

gettimeofday(&t,NULL);
e=t.tv_sec+(t.tv_usec/1000000.0);

printf("\nAfter sorting array elements are - \n");

printArr(a, n);

printf("\ntime taken to sort %d elements is %lf\n", n, (e-s));

return 0;

}
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<sys/time.h>

void merge (int a[], int low, int mid, int high)

int resarr[10000],i, j, k, m;

i=low ;

j=mid+1;

k=low;

while(i<=mid && j<=high)

if(a[i]<a[j]

resarr[k++]=a[i++];

else

resarr[k++]=a[j++];

while(i<=mid)

resarr[k++]=a[i++];

while(j<=high)

resarr[k++]=a[j++];

for(m=low;m<=high;m++)

a[m]=resarr[m];

void msort(int a[], int low, int high)

if(low<high)
{

mid=(low+high)/2

msort(a,low,mid);

msort(a,mid+1,high);

merge(a,low,mid,high);

void printArr(int a[], int n)

int i;

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

printf("%d ", a[i]);

int main()

int a[10000],n, i;

struct timeval t;

double s, e;

printf("Enter the number of elements\n");

scanf("%d",&n);

printf("Before sorting array elements are - \n");

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

a[i]=random()%100;

printArr(a, n);

gettimeofday(&t,NULL);

s=t.tv_sec+(t.tv_usec/1000000.0);

msort(a, 0, n-1);
gettimeofday(&t,NULL);

e=t.tv_sec+(t.tv_usec/1000000.0);

printf("\nAfter sorting array elements are - \n");

printArr(a, n);

printf("\ntime taken to sort %d elements is %lf\n", n, (e-s));

return 0;

}
12 Design and implement C/C++ Program for N Queen's problem using Backtracking.
Aim: To implement N Queens Problem using Back Tracking

#include<stdio.h>
void queens(int);
void PrintBoard(int);
int x[20],soln=1;
int main()
{
int n;
printf("Enter the no. of queens to place : ");
scanf("%d",&n);
queens(n);
return 0;
}
void queens(int n)
{
int i,k=1;
x[k]=0;
while(k!=0)
{
x[k]=x[k]+1;
while(x[k]<=n && !place(k,x))
x[k]=x[k]+1;
if(x[k]<=n)
if(k==n)
PrintBoard(n);
else
k++,x[k]=0;
else
k--;
}
printf("\nThe number of possible solutions are %d",soln-1);
}
int place(int k,int x[])
{
int i;
for(i=1;i<k;i++)
if((x[i]==x[k]) || (i-x[i]==k-x[k]) || (i+x[i]==k+x[k]))
return 0;
return 1;
}

void PrintBoard(int n)
{
int i,j;
printf("\n Solution set %d: ",soln);
for(i=1;i<=n;i++)
printf(" %d ",x[i]);
printf("\n\n Placements are as shown below: \n\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
(j==x[i]) ? printf(" Q%d ",i) : printf(" -- ");
printf("\n");
}
soln++;
}