Trend Posts
Author
View LUQMAN's profile
Showing posts with label 4th semester. Show all posts
Showing posts with label 4th semester. Show all posts
Monday, July 21, 2014
/* 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>
int a[10000000];
void swap1(int a[],int i,int j)
{
int temp;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
int partition(int a[],int m,int p)
{
int i,j,pi;
pi=a[m];
i=m;j=p;
while(i<=j)
{
while(a[i]<=pi)
i++;
while(a[j]>pi)
j--;
if(i<j)
swap1(a,i,j);
}
a[m]=a[j];
a[j]=pi;
return j;
}
void quicksort(int a[],int m,int p)
{
int j;
if(m<p)
{
j=partition(a,m,p);
quicksort(a,m,(j-1));
quicksort(a,(j+1),p);
}
}
void main()
{
int n,i,m,p;
double start,end,dur,maxm;
printf("\n\nEnter the number of elements\n\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
a[i]=rand()%100;
}
for(i=0;i<n;i++)
printf("\n\nRandom numbers are%d\t",a[i]);
start=clock();
for(k=0;k<maxm;k++)
quicksort(a,m,p);
end=clock();
dur=(end-start)/CLOCKS_PER_SEC;
printf("\n\nTime taken is:%lf\t\n\n",dur);
printf("\n\nSorted array is:");
for(i=0;i<n;i++)
printf("%d\t",a[i]);
printf("\n\n");
}
/*Computer the Transitive closure of a given directed graph using warshall’s algorithm*/
#include<stdio.h>
void warshall(int);
long int ad[10][10];
void main()
{
int i, j,n;
printf("\n****Warshalls Algorithm****\n");
printf("Enter the number of nodes\n\n");
scanf("%d",&n);
printf("\nEnter the graphs in the form of adjacency matrix\n\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%ld",&ad[i][j]);
printf("\n\nThe adjacency matrix is:\n\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%ld\t",ad[i][j]);
printf("\n");
}
warshall(n);
printf("\nThe transitive closure of given directed graph is\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%ld\t",ad[i][j]);
printf("\n");
}
}
void warshall(int n)
{
int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
ad[i][j]=ad[i][j]||ad[i][k]&&ad[k][j];
}
/*Obtain the Topological ordering of vertices in a given digraph*/
#include<stdio.h>
int ad[10][10];
void main()
{
int i,j,n,f=1,in=1,k,v[50000],count=0,flag;
printf("\n\nEnter the number of nodes\n\n");
scanf("%d",&n);
printf("\n\nEnter the graph in the form of adjacency matrix\n\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&ad[i][j]);
printf("\nThe adjacency matrix is:\n\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",ad[i][j]);
printf("\n");
}
while(f)
{
count++;
for(j=1;j<=n;j++)
{
flag=0;
for(i=1;i<=n;i++)
{
if(ad[i][j]==1||v[i]==j)
{
flag=1;
break;
}
}
if(flag==0)
{
v[in++]=j;
for(k=1;k<=n;k++)
ad[j][k]=0;
}
}
if(count==n)
f=0;
}
if(in<n)
printf("\nThere is no topological order\n\n");
else
{
printf("\nThere is a topological order and it is::\t");
for(i=1;i<=n;i++)
printf("%d\t",v[i]);
}
printf("\n\n");
}
/*Implement any scheme to find the optimal solution for the Traveling Salesperson problem*/
#include<stdio.h>
int tspda(int,int,int,int);
int n,c[1000][1000],start,n,temp[1000],mincost,ccost,tour[1000],mintour[1000],i,j,k;
void main()
{
printf("\nEnter the number of nodes\n");
scanf("%d",&n);
printf("\nEnter the cost matrix\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&c[i][j]);
printf("\nEntered cost matrix is:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",c[i][j]);
printf("\n");
}
printf("\nThe approximate tour is:\n");
tspda();
}
int tspda(int c[10][10],int tour[10],int start,int n)
{
if(start==n-1)
return(c[tour[n-1][tour[n]+c[tour[n][tour[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]=temp[start+1];
if(c[tour[start][tour[i]]+(ccost=tspdp(c,temp,start+1,n)))<min)
{
mincost=ccost+c[tour[start][tour[i]];
for(k=1;k<=n;k++)
mintour[k]=temp[k];
}
}
for(i=1;i<=n;i++)
tour[i]=mintour[i];
return mincost;
}
/*Implement any scheme to find the solution for the TravelingSalesperson in the approximation method*/
#include<stdio.h>
void tspaprx(int);
int n,cost[100][100],s,count=0,mincost,visited[100],u,i,j,min;
void main()
{
printf("\nEnter the number of nodes\n");
scanf("%d",&n);
printf("\nEnter the cost matrix\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
printf("\nEntered 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("\nThe approximate tour is:\n");
tspaprx(1);
}
void tspaprx(int s)
{
visited[s]=1;
count++;
printf("%d->",s);
if(count==n)
{
printf("1");
mincost+=cost[s][1];
printf("\nThe minimum tour cost is %d",mincost);
return;
}
min=999;
for(i=1;i<=n;i++)
{
if(cost[s][i]<min && !visited[i])
{
min=cost[s][i];
u=i;
}
}
mincost+=min;
tspaprx(u);
}
/*Find a subset of a given set S = {sl, s2,.....,sn} of n positive integerswhose 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}.Asuitable message is to be displayed if the given problem instancedoesn't have a solution.*/
#include<stdio.h>
void subset(int,int,int);
int i,w[10],n,sum=0,x[10],c=0,k,r,d;
void main()
{
printf("\nEnter the number of elements\n");
scanf("%d",&n);
printf("\nEnter the elements in the ascending order\n");
for(i=0;i<n;i++)
scanf("%d",&w[i]);
printf("\nEnter the sum:\n");
scanf("%d",&d);
for(i=0;i<n;i++)
sum=sum+w[i];
if(sum<d || d<w[0])
printf("\nSubset is not possible\n");
subset(0,0,sum);
if(c==0)
printf("\nSubset is not possible\n");
}
void subset(int cs,int k,int r)
{
x[k]=1;
if(cs+w[k]==d)
{
printf("\nSolution %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]);
}
}
/*From a given vertex in a weighted connected graph, find shortest paths to other vertices using Dijkstra's algorithm.*/
#include<stdio.h>
int cost[10][10],n,sv,i,j,v,count=0,w,min,t,w,dist[10],visited[10],path[10];
void dj();
void print();
void main()
{
printf("\n\nEnter the number of nodes\n\n");
scanf("%d",&n);
printf("\n\nEnter the cost matrix\n\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
printf("\nEntered 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("\nEnter the source node\n");
scanf("%d",&sv);
dj();
print();
}
void dj()
{
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 print()
{
for(w=1;w<=n;w++)
if(visited[w]==1 && w!=sv)
{
printf("\nThe sorted 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);
}
}
/* 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<omp.h>
#include<time.h>
void floyds(int);
int min(int,int);
int cost[10][10],n,i,j,k,a,b;
double start,end,dur;
void main()
{
printf("Enter the number of nodes\n\n");
scanf("%d",&n);
printf("\nEnter the cost matrix\n\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
printf("\n\nThe cost matrix is:\n\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",cost[i][j]);
printf("\n");
}
start=clock();
for(i=1;i<=100000;i++)
floyds(n);
end=clock();
dur=(end-start)/CLOCKS_PER_SEC;
printf("\nTime taken is:%f\t\n",dur);
printf("\nThe minimum cost matrix is:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",cost[i][j]);
printf("\n");
}
}
void floyds(int n)
{
omp_set_num_threads(4);
#pragma omp parallel for private(i,j,k)
for(k=1;k<=n;k++)
{
usleep(100);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j]);
}
}
int min(int a,int b)
{
if(a>b)
return b;
else
return a;
}
Subscribe to:
Posts (Atom)