Trend Posts
Author
View LUQMAN's profile
Showing posts with label engineering syllabus. Show all posts
Showing posts with label engineering syllabus. 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;
}
Subscribe to:
Posts (Atom)