- Sort a given set of elements using the Quicksort method and determine the time required to sort the elements. Repeat the experiment for different values of n, the number of elements in the list to be sorted and 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>
void quicksort(int,int);
int partition(int,int);
void interchange(int,int);
int a[10000000];
void main()
{
int i,n;
clock_t start,end;
printf(“\n\n********QUICK SORT PROGRAM*****\n\n”);
printf(“Enter the number of elements to be sorted \n”);
scanf(“%d”,&n);
for(i=0;i<n;i++) a[i]=rand()%100;
printf(“\n Array elements to be sorted are\n”);
for(i=0;i<n;i++)
printf(“%d\t”,a[i]);
a[n]=999;
start=clock();
quicksort(0,n-1);
end=clock();
printf(“\n\n The sorted elements are\n”);for(i=0;i<n;i++)
printf(“%d\t”,a[i]);
printf(“\n\n The time taken is %f \n”,(double)(end-start)/CLOCKS_PER_SEC);
printf(“\n*********\n\n”);
}
void quicksort(int p,int q)
{
int j;
if(p<q)
{
j=partition(p,q);
quicksort(p,j-1);
quicksort(j+1,q);
}
}
int partition(int p,int q)
{
int v,i,j;
v=a[p];
i=p;
j=q;
while(i<=j)
{
while(a[i]<=v)i++;
while(a[j]>v)j–;
if(i<j)
interchange(i,j);
}
a[p]=a[j];
a[j]=v;
return j;
}
void interchange(int i,int j)
{
int p;
p=a[i];
a[i]=a[j];
a[j]=p;
}
- Using OpenMP, implement a parallelized Merge Sort algorithm to sort a given set of elements and determine the time required to sort the elements. Repeat the experiment for different values of n, the number of elements in the list to be sorted and 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<omp.h>
#include<time.h>
void mergesort(int,int);
void merge(int,int,int);
int a[100000];
void main()
{
int n,i;
clock_t start,end;
printf(“\n\n….MERGESORT PARALLEL PROGRAM….\n\n”);
printf(“\n\nEnter the element to be sorted\n\n”);
scanf(“%d”,&n);
for(i=0;i<n;i++)
a[i]=rand()%100;
printf(“\n Array element to be sorted \n”);
for(i=0;i<n;i++)
printf(“%d\t”,a[i]);
start=clock();
mergesort(0,n-1);
end=clock();
printf(“\n\n The sorted elements are\n”);
for(i=0;i<n;i++)
printf(“%d\t”,a[i]);
printf(“\n\n The time taken is %f\n”,(double)(end-start)/CLOCKS_PER_SEC);
printf(“\n\n****………..*******\n\n”);
}
void mergesort(int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
#pragma omp parallel section
{
#pragma omp section
mergesort(low,mid);
#pragma omp section
mergesort(mid+1,high);
}
merge(low,mid,high);
}
}
void merge(int low,int mid,int high)
{
int i,j,h,k,b[100000];
h=low;
i=low;
j=mid+1;
while((h<=mid)&&(j<=high))
{
if(a[h]<a[j])
{
b[i]=a[h];
h=h+1;
}
else
{
b[i]=a[j];
j=j+1;
}
i=i+1;
}
if(h>mid)
{
for(k=j;k<=high;k++)
{
b[i]=a[j];
i=i+1;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i=i+1;
}
}
for(k=low;k<=high;k++)
a[k]=b[k];
}
- Obtain the Topological ordering of vertices in a given digraph.
#include<stdio.h>
void topo();
int ad[10][10],i,j,n,k;
void main()
{
printf(“\n\n********TOPOLOGICAL SORTING *********\n\n”);
printf(“\n Enter the number of vertices\n”);
scanf(“%d”,&n);
printf(“\n Enter the adjecency matrix\n”);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf(“%d”,&ad[i][j]);
}
}
printf(“\n The entered adjecency matrix is \n”);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(“%d\t”,ad[i][j]);
}
printf(“\n”);
}
topo();
}
void topo()
{
int v[10],in=1,count=0,f=1,flag=0;
while(f)
{
count++;
for(i=1;i<=n;i++)
{
flag=0;
for(j=1;j<=n;j++)
{
if(ad[j][i]!=0||v[j]==i)
{
flag=1;break;
}
}
if(flag!=1)
{
v[in++]=i;for(k=1;k<=n;k++)
ad[i][k]=0;
}
}
if(count==n)f=0;
}
if(in<n)
printf(“\n\n Topological ordering is not possible\n”);
else
{
printf(“\n\n Topological ordering is possible\n”);
printf(“\n Ordering is:\n”);
for(i=1;i<=n;i++)
printf(“%d\t”,v[i]);
}
printf(“\n********\n”);
}
- Compute the transitive closure of a given directed graph using Warshall’s algorithm.
#include<stdio.h>
void warshall(int a[10][10],int n);
void main()
{
int a[10][10],i,j,n;
printf(“\n*********WARSHALL PROGRAM*******\n\n”);
printf(“\n Enter the number of nodes in a graph\n”);
scanf(“%d”,&n);
printf(“\n\n Enter the adjacency matrix of directed graph\n”);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf(“%d”,&a[i][j]);
printf(“\n Entered adjacency matrix of ordered graph\n”);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(“%d\t”,a[i][j]);
}
printf(“\n”);
}
warshall(a,n);
printf(“\n\nTransitive closure matrix is \n”);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(“%d\t”,a[i][j]);
}
printf(“\n”);
}
printf(“\n\n*********************************\n\n”);
}
void warshall(int a[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++)
{
a[i][j]=a[i][j]||(a[i][k]&&a[k][j]);
}
}
}
}
- Implement 0/1 Knapsack problem using Dynamic Programming.
#include<stdio.h>
#include<stdlib.h>
void displayinfo();
void knapsack();
void optimal();
int i,j,x[10],n,m,v[10][10],w[10],p[10],item=0;
void main()
{
printf(“\n\n********KNAPSACK PROBLEM *************\n\n”);
printf(“\n\n Enter the total number of items:\n”);
scanf(“%d”,&n);
printf(“\n\n Enter the weight of each item:\n\n”);
for(i=1;i<=n;i++)
scanf(“%d”,&w[i]);
printf(“\n\n Enter the profit of each ittem:\n\n”);
for(i=1;i<=n;i++)
scanf(“%d”,&p[i]);
printf(“\n\nEnter the knapsack capacity:\n\n”);
scanf(“%d”,&m);
displayinfo();
knapsack();
printf(“\n\n The content of the knapsack table are \n”);
for(i=0;i<=n;i++)
{
for(j=0;j<=m;j++)
{
printf(“%d\t”,v[i][j]);
}
printf(“\n”);
}
optimal();
}
void displayinfo()
{
printf(“\n\nEnterd information about knapsack problem are\n”);
printf(“\nITEM\tWEIGHT\tPROFIT\n”);
for(i=1;i<=n;i++)
printf(“%d\t%d\t%d\n”,i,w[i],p[i]);
printf(“capacity=%d\n\n”,m);
}
void knapsack()
{
for(i=0;i<=n;i++)
{
for(j=0;j<=m;j++)
{
if(i==0||j==0)
v[i][j]=0;
else if(j<w[i])
v[i][j]=v[i-1][j];
else
v[i][j]=max(v[i-1][j],(v[i-1][j-w[i]]+p[i]));
}
}
}
void optimal()
{
int i=n,j=m;
while(i!=0&&j!=0)
{
if(v[i][j]!=v[i-1][j])
{
x[i]=1;
j=j-w[i];
}
i=i-1;
}
printf(“\n\n Optimal solution is %d\n\n”,v[n][m]);
printf(“selected items are:”);
for(i=1;i<=n;i++)
if(x[i]==1)
{
printf(“%d,”,i);
item=1;
}
printf(“\b\b”);
if(item==0)
printf(“NIL\n\t sorry!No item can be placed in knapsack\n”);
printf(“\n***************************************\n”);
}
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
OUTPUT:
Enter the total number of items: 4
Enter the weight of each item: 2 3 1 2
Enter the profit of each item:12 10 15 20
Enter the knapsack capacity:5
Enter the total number of items: 2
Enter the weight of each item: 10 20
Enter the profit of each item:30 25
Enter the knapsack capacity:5
- From a given vertex in a weighted connected graph, find shortest paths to other vertices using Dijkstra’s algorithm.
#include<stdio.h>
void dij();
void printpath();
int sv,i,j,n,w,v=0,t,min,count,dist[10],visited[10],cost[10][10],path[10];
void main()
{
printf(“\n\n********DIJKSTRA’S ALGORITHM***********\n\n”);
printf(“Enter the number of nodes:”);
scanf(“%d”,&n);
printf(“\n\nEnter the cost matrix\n”);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf(“%d”,&cost[i][j]);
printf(“\n\n The entered cost matrix is \n”);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(“%d\t”,cost[i][j]);
}
printf(“\n”);
}
printf(“\n\nEnter the source vertex:”);
scanf(“%d”,&sv);
dij();
printpath();
printf(“\n\n**************************”);
}
void dij()
{
count=2;
for(i=1;i<=n;i++)
{
visited[i]=0;
dist[i]=cost[sv][i];
if(cost[sv][i]==999)
path[i]=0;
else
path[i]=sv;
}
visited[sv]=1;
while(count<=n)
{
min=999;
for(w=1;w<=n;w++)
if(dist[w]<min&&!visited[w])
{
min=dist[w];
v=w;
}
visited[v]=1;
count++;
for(w=1;w<=n;w++)
{
if(dist[w]>dist[v]+cost[v][w])
{
dist[w]=dist[v]+cost[v][w];
path[w]=v;
}
}
}
}
void printpath()
{
for(w=1;w<=n;w++)
{
if(visited[w]==1 && w!=sv)
{
printf(“\n\nThe shortest distance between %d->%d=%d”,sv,w,dist[w]);
t=path[w];
printf(“\nThe path is:\n”);
printf(“%d”,w);
while(t!=sv)
{
printf(“<–>%d”,t);
t=path[t];
}
printf(“<–>%d”,sv);
}
}
}
- Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal’s algorithm.
#include<stdio.h>
void kruskals();
int parent[10],cost[10][10],ne,i,j,n,min,a,b,u,v,mincost=0;
void main()
{
printf(“\n\n*********KRUSKALS ALGORITH*********\n\n”);
printf(“Enter the number of nodes:”);
scanf(“%d”,&n);
printf(“\n\nEnter the cost matrix\n”);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf(“%d”,&cost[i][j]);
}
}
printf(“\n\nThe entered cost matrix is\n”);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(“%d\t”,cost[i][j]);
}
printf(“\n”);
}
kruskals();
printf(“\n\nThe minimum spanning tree cost is %d”,mincost);
printf(“\n\n************ ************** *************”);
}
void kruskals()
{
ne=1;
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(“%d> minimum edge from %d to %d is %d\n\n”,ne++,a,b,min);
mincost+=min;
parent[v]=u;
}
cost[a][b]=cost[b][a]=999;
}
}
- Check whether a given graph is connected or not using DFS method.
#include<stdio.h>
void dfs(int);
int visited[10],adj[10][10],n,count;
void main()
{
int i,j;
printf(“\n\n********DFS METHOD***********\n\n”);
printf(“Enter the mumber of nodes:”);
scanf(“%d”,&n);
printf(“\n\nEnter the adjacency matrix\n”);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(“%d\t”,adj[i][j]);
}
printf(“\n”);
}
for(i=1;i<=n;i++)
{
count=0;
for(j=1;j<=n;j++)
visited[j]=0;
dfs(i);
if(count==n)
{
printf(“\nGraph is connected”);
printf(“\n\n******************”);
getch();
exit(0);
}
}
printf(“\nGraph is not connected”);
printf(“\n\n****************”);
}
void dfs(int i)
{
int w;
count++;
visited[i]=1;
for(w=1;w<=n;w++)
{
if(adj[i][w]==1 && visited[w]==0)
dfs(w);
}
}
- Find a subset of a given set S = {s1,s2,…..,sn} of n positive integers whose sum is equal to a given positive integer d. For example, if S= {1, 2, 5, 6, 8} and d = 9 there are two solutions {1,2,6} and {1,8}.A suitable message is to be displayed if the given problem instance doesn’t have a solution.
#include<stdio.h>
#include<stdlib.h>
void subset(int, int, int);
int w[10],n,d,i,cs,r,x[10],sum=0,k,c;
void main()
{
printf(“\n\n************SUBSET PROBLEM*********\n\n”);
printf(“Enter the number of elements:”);
scanf(“%d”,&n);
printf(“\n\n Enter the elements in increasing order:”);
for(i=0;i<n;i++)
scanf(“%d”,&w[i]);
printf(“\n\nEnter the value of d:”);
scanf(“%d”,&d);
for(i=0;i<n;i++)
sum=sum+w[i];
printf(“\n\nSUM=%d”,sum);
if(sum<d||w[0]>d)
{
printf(“\n\n Subset is not posssible!”);
printf(“\n\n*************** *********** **************\n\n”);
exit(0);
}
subset(0,0,sum);
if(c==0)
printf(“\n\nSubset is not possible !”);
printf(“\n\n********* ************ ************\n\n”);
}
void subset(int cs, int k, int r)
{
x[k]=1;
if(cs+w[k]==d)
{
printf(“\n\n Solutiion %d is={“,++c);
for(i=0;i<=k;i++)
if(x[i]==1)
{
printf(“%d”,w[i]);
}
printf(“\b}”);
}
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+1])<=d)
{
x[k]=0;
subset(cs,k+1,r-w[k]);
}
}
- Implement any scheme to find the optimal solution for the Traveling Salesperson problem and then solve the same problem instance using any approximation algorithm and determine the error in the approximation.
Approximation Method
#include<stdio.h>
void tspapp(int v);
int visited[10],city,cost[10][10],count,mincost,i,j;
void main()
{
printf(“\n\n******TSP APPROXIMATION PROBLEM**\n\n”);
printf(“Enter the number of cities:”);
scanf(“%d”,&city);
printf(“\n\nEnter the cost matrix\n\n”);
for(i=1;i<=city;i++)
{
for(j=1;j<=city;j++)
{
scanf(“%d”,&cost[i][j]);
}
}
printf(“\n\n The entered cost matrix is \n”);
for(i=1;i<=city;i++)
{
for(j=1;j<=city;j++)
{
printf(“%d\t”,cost[i][j]);
}
printf(“\n”);
}
printf(“\n\n The approximate path is \n”);
tspapp(1);
printf(“\n\n************* **************** ************\n”);
}
void tspapp(int v)
{
int k,min;
visited[v]=1;
printf(“%d->”,v);
if(count==city-1)
{
mincost=mincost+cost[v][1];
printf(“1″);
printf(“\n\nApproximate Mincost is %d”,mincost);
return;
}
min=999;
for(j=1;j<=city;j++)
{
if(cost[v][j]<min&&cost[v][j]!=0&&!visited[j])
{
min=cost[v][j];
k=j;
}
}
mincost=mincost+cost[v][k];
count++;
tspapp(k);
}
Dynamic Method
#include<stdio.h>
#include<stdlib.h>
int tspdp(int c[10][10], int tour[10], int start, int n);
void main()
{
int i,j,n,cost,c[10][10], tour[10];
printf(“\n\n*************TSP DYNAMIC PROGRAMMING************\n\n”);
printf(“\n\n Enter the number of cities:”);
scanf(“%d”,&n);
if(n==1)
{
printf(“\n Path is not possible\n\n”);
exit(0);
}
printf(“\n\n Enter the cost matrix\n”);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf(“%d”,&c[i][j]);
printf(“\n\n The entered cost matrix is\n”);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(“%d\t”,c[i][j]);
}
printf(“\n”);
}
for(i=1;i<=n;i++)
tour[i]=i;
cost=tspdp(c,tour,1,n);
printf(“\n\n The accurate path is \n”);
for(i=1;i<=n;i++)
printf(“%d->”,tour[i]);
printf(“1″);
printf(“\n\nThe accurate mincost is %d”,cost);
printf(“\n\n************ **************** ********** “);
}
int tspdp(int c[10][10], int tour[10], int start, int n)
{
int mintour[10],temp[10],mincost=999,ccost,i,j,k;
if(start==n-1)
{
return(c[tour[n-1]][tour[n]]+c[tour[n]][1]);
}
for(i=start+1;i<=n;i++)
{
for(j=1;j<=n;j++)
temp[j]=tour[j];
temp[start+1]=tour[i];
temp[i]=tour[start+1];
if((c[tour[start]][tour[i]]+(ccost=tspdp(c,temp,start+1,n)))<mincost)
{
mincost=c[tour[start]][tour[i]]+ccost;
for(k=1;k<=n;k++)
mintour[k]=temp[k];
}
}
for(i=1;i<=n;i++)
tour[i]=mintour[i];
return mincost;
}
- Find Minimum Cost Spanning Tree of a given undirected graph using Prim’s algorithm.
#include<stdio.h>
void prims();
int nearV[10],cost[10][10],t[10][2],i,j,n,k,min,u,mincost=0;
void main()
{
printf(“\n\n**********PRIMS ALGORITHM***********\n\n”);
printf(“Enter the number of nodes\n”);
scanf(“%d”,&n);
printf(“\n\nEnter the cost matrix\n”);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf(“%d”,&cost[i][j]);
}
}
printf(“\n\n The entered cost matrix is\n”);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(“%d\t”,cost[i][j]);
}
printf(“\n”);
}
printf(“\n\nMinimum spanning tree edges and their cost are\n”);
prims();
printf(“\n\nThe minimum spanning tree cost is %d”,mincost);
printf(“\n\n********* *********** ***********”);
}
void prims()
{
for(i=2;i<=n;i++)
nearV[i]=1;
nearV[1]=0;
for(i=1;i<n;i++)
{
min=999;
for(j=1;j<=n;j++)
{
if(nearV[j]!=0&&cost[j][nearV[j]]<min)
{
min=cost[j][nearV[j]];
u=j;
}
}
t[i][1]=u;
t[i][2]=nearV[u];
mincost+=min;
nearV[u]=0;
for(k=1;k<=n;k++)
{
if(nearV[k]!=0&&cost[k][nearV[k]]>cost[k][u])
nearV[k]=u;
}
printf(“%d)edge(%d,%d),cost%d\n”,i,t[i][1],t[i][2],min);
}
}
- Implement All-Pairs Shortest Paths Problem using Floyd’s algorithm. Parallelize this algorithm, implement it using OpenMP and determine the speed-up achieved.
#include<stdio.h>
#include<stdlib.h>
#include<omp.h>
#include<time.h>
void floyd();
int min(int,int);
int i,j,n,k,a[8][8];
clock_t start,end;
void main()
{
printf(“\n\n*********FLOYD’S PARALLELIZED ALGORITHM*********\n\n”);
printf(“Enter the number of vertices:”);
scanf(“%d”,&n);
printf(“\n\nEnter the adjacency matrix\n”);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf(“%d”,&a[i][j]);
printf(“\n\nEntered adjacency matrix is:\n”);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(“%d\t”,a[i][j]);
}
printf(“\n”);
}
start=clock();
floyd(a,n);
end=clock();
printf(“\nAll pair shortest path matrix:\n”);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf(“%2d”,a[i][j]);
printf(“\n”);
}
printf(“\n\nTime taken to execute is %f\n”,(double)(end-start)/CLOCKS_PER_SEC);
printf(“\n*****************************************************************”);
}
void floyd()
{
//omp_set_num_threads(4);
#pragma omp parallel for private(i,j,k)
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
}
}
int min(int a, int b)
{
if(a>b)
return b;
else
return a;
}
- Implement N Queen’s problem using Back Tracking.
#include<stdio.h>
#include<stdlib.h>
int place(int);
int X[10];
void main()
{
int i,j,n,k,count=0;
printf(“\n\n*************N-QUEEN PROBLEM***************\n\n”);
printf(“Enter the number of elements:”);
scanf(“%d”,&n);
if(n==0||n==2||n==3)
{
printf(“\n\n No solution\n”);
printf(“\n\n********** ************ **********\n\n”);
exit(0);
}
k=1;
X[k]=0;
while(k)
{
X[k]=X[k]+1;
while(X[k]<=n&&!place(k))
X[k]=X[k]+1;
if(X[k]<=n)
{
if(k==n)
{
printf(“\nSolution %d\n\n”,++count);
for(i=1;i<=n;i++)
{
for(j=1;j<X[i];j++)
printf(“*\t”);
printf(“Q\t”);
for(j=X[i]+1;j<=n;j++)
printf(“*\t”);
printf(“\n”);
}
}
else
{
k=k+1;
X[k]=0;
}
}
else
k=k-1;
}
printf(“\n\n******** ********* *********\n\n”);
}
int place(int p)
{
int i;
for(i=1;i<=p-1;i++)
{
if(X[i]==X[p]||abs(i-p)==abs(X[i]-X[p]))
return 0;
}
return 1;
}
OUTPUT:
Enter the number of elements:4
Solution 1
* Q * *
* * * Q
Q * * *
* * Q *
Solution 2
* * Q *
Q * * *
* * * Q
* Q * *
******* ******** ***********
