DAA lab practical program (B.tech 6th sem)
DAA lab practical program PDF download DAA lab practical program b.tech 6th sem
1. 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.
Solution:-
#include<stdio.h>
#include<sys/time.h>
void swap(int *x,int *y)
{
int temp;
temp=*x;
*x=*y;
*y=temp;
}
void generate_random(int a[],int n)
{ int i;
srand(time(0));
for(i=0;i<n;i++)
a[i]=rand()%1000;
}
int Partition(int a[10],int l,int h)
{
int i,j,p;
i=l;j=h+1; p=l;
do{
do{
i=i+1;
}while(a[i]<a[p]);
do{
j=j-1;
}while(a[j]>a[p]);
swap(&a[i],&a[j]);
}while(i<=j);
swap(&a[i],&a[j]);
swap(&a[l],&a[j]);
return j;
}
int Quicksort(int a[10],int m,int n)
{
int s;
if(m<n+1)
{
s=Partition(a,m,n);
Quicksort(a,m,s-1);
Quicksort(a,s+1,n);
return a;
}
}
int main()
{
int a[100000],i,ch,n;
struct timeval t;
double start,end;
FILE *fp;
printf("Enter the type of operation\n");
printf("1-Randomly generate numbers and quicksort\n");
printf("2-Enter the number of values to generate and sort\n");
scanf("%d",&ch);
switch(ch)
{case 1:
fp=fopen("quicksort.txt","w");
for(i=10000;i<100000;i=i+5000)
{
generate_random(a,i);
gettimeofday(&t,NULL);
start=t.tv_sec+(t.tv_usec/1000000.0);
Quicksort(a,0,i-1);
gettimeofday(&t,NULL);
end=t.tv_sec+(t.tv_usec/1000000.0);
printf("%d\t%lf\n",i,end-start);
fprintf(fp,"%d\t%lf\n",i,end-start);
}
fclose(fp); break;
case 2:printf("Enter the number of values to be generated\n");
scanf("%d",&i);
generate_random(a,i);
gettimeofday(&t,NULL);
start=t.tv_sec+(t.tv_usec/1000000.0);
Quicksort(a,0,i-1);
gettimeofday(&t,NULL);
end=t.tv_sec+(t.tv_usec/1000000.0);
printf("%d\t%lf\n",i,end-start);
printf("Sorted numbers are\n");
printf("The sorted array is\n");
for(n=0;n<i;n++)
printf("%d\t",a[n]);
break;
default: printf("Invalid choice\n");
}
return 0; }
2. 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.
Solution:-
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <omp.h>
void simplemerge(int a[],int low,int mid,int high)
{
int i,j,k,c[10000];
i=low;
j=mid+1;
k=low;
int tid;
omp_set_num_threads(5);
{
#pragma omp parallel
tid=omp_get_thread_num();
#pragma omp while
while(i<=mid&&j<=high)
{
if(a[i]<a[j])
{
c[k]=a[i];
i++;
k++;
}
else
{
c[k]=a[j];
j++;
k++;
}
}
}
while(i<=mid)
{
c[k]=a[i];
i++;
k++;
}
while(j<=high)
{
c[k]=a[j];
j++;
k++;
}
for(k=low;k<=high;k++)
a[k]=c[k];
}
void merge(int a[],int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
merge(a,low,mid);
merge(a,mid+1,high);
simplemerge(a,low,mid,high);
}
}
void getnumber(int a[],int n)
{
int i;
for(i=0;i<n;i++)
a[i]=rand()%10000;
}
int main()
{
FILE *fp;
int a[10000],i;
struct timeval tv;
double start,end,elapse;
fp=fopen("m.txt","w");
printf("Num. time");
for(i=0;i<9999;i+=100)
{
getnumber(a,i);
gettimeofday(&tv,NULL);
start=tv.tv_sec+(tv.tv_usec/100000.0);
merge(a,0,i-1);
gettimeofday(&tv,NULL);
end=tv.tv_sec+(tv.tv_usec/100000.0);
elapse=end-start;
if(elapse>=0)
fprintf(fp,"%d\t%lf\n",i,elapse);
}
fclose(fp);
system("gnuplot");
return 0; }
3. i. Obtain the Topological ordering of vertices in a given digraph.
Solution:-
#include<stdio.h>
#include<stdlib.h>
int main()
{
int array[20][20],v,i,j,count=0;
int job[10],z,sum,indegree[20],flag;
printf("Enter the number of vertices\n");
scanf("%d",&v);
printf("Enter the adjacency matrix\n");
for(i=0;i<v;i++)
{
for(j=0;j<v;j++)
{
scanf("%d",&array[i][j]);
}
}
while(count<v)
{
for(i=0;i<v;i++)
{
sum=0;
if(indegree[i]!=-1)
{
for(j=0;j<v;j++)
{
sum+=array[j][i];
}
indegree[i]=sum;
}
}
flag=0;
for(i=0;i<v;i++)
{
if(indegree[i]==0)
{
z=i;
flag=1;
break;
}
}
if(!flag)
{
printf("The above graph cannot be sorting using topology sort");
exit(0);
}
for(j=0;j<v;j++)
array[z][j]=0;
indegree[z]=-1;
job[count]=z+1;
count++;
}
printf("The Topological order is \n");
for(i=0;i<count;i++)
printf("%d\t",job[i]);
printf("\n");
return 0;
}
ii. Compute the transitive closure of a given directed graph using Warshall's algorithm.
Solution:-
#include<iostream>
using namespace std;
int a[10][10],n;
void warshall()
{
int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(a[i][j]!=1)
{
if(a[i][k]==1 && a[k][j]==1)
a[i][j]=1;
}
}
int main()
{
int i,j;
cout<<"Enter no of nodes : ";
cin>>n;
cout<<"Enter adjacency matrix : \n";
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cin>>a[i][j];
warshall();
cout<<"Transitive closure :\n";
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
cout<<a[i][j]<<"\t";
cout<<endl;
}
return 0;
}
4. Implement 0/1 Knapsack problem using Dynamic Programming.
#include <stdio.h>
#include <stdlib.h>
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
void Knapsack(int table[10][10],int weight[10],int value[10],int items,int W)
{
int i,j,count=0,Knapsack[items];
for(i=0;i<=items;i++)
table[i][0]=0;
for(j=0;j<=W;j++)
table[0][j]=0;
for(i=1;i<=items;i++)
{
for(j=1;j<=W;j++)
{
if(j<weight[i])
table[i][j]=table[i-1][j];
else
table[i][j]=max(table[i-1][j],(table[i-1][j-weight[i]]+value[i]));
}
}
printf("Profit Table\n");
for(i=0;i<=items;i++)
{
for(j=0;j<=W;j++)
{
printf("%d\t",table[i][j]);
}
printf("\n");
}
i=items;
j=W;
while(i>0 && j>0)
{
if(table[i][j]!=table[i-1][j])
{
Knapsack[count++]=i;
j=j-weight[i];
}
i=i-1;
}
if(!count)
printf("The Knapsack Is Empty\n");
else
{
printf("Elements of the most valuable subset are ");
for(i=count-1;i>=0;i--)
printf("%d ",Knapsack[i]);
}
printf("\n");
printf("Value is %d",table[items][W]);
}
int main(void)
{
int table[10][10],weight[10],value[10],items,i,W;
printf("Enter number of items\n");
scanf("%d",&items);
printf("Enter weight of the items\n");
for(i=1;i<=items;i++)
scanf("%d",&weight[i]);
printf("Enter value of the items\n");
for(i=1;i<=items;i++)
scanf("%d",&value[i]);
printf("Enter the Knapsack capacity\n");
scanf("%d",&W);
Knapsack(table,weight,value,items,W);
return 0;
}
5. From a given vertex in a weighted connected graph, find shortest paths to other vertices
using Dijkstra's algorithm.
#include<iostream>
#define INFINITY 999
using namespace std;
void dijkstra(int n,int source,int cost[10][10],int distance[])
{
int i,v,u,visited[10],min,count=2;
for(i=1;i<=n;i++)
visited[i]=0,distance[i]=cost[source][i];
while(count<=n)
{
min=INFINITY;
for(u=1;u<=n;u++)
if(distance[u]<min && !visited[u])
min=distance[u],v=u;
visited[v]=1;
count++;
for(u=1;u<=n;u++)
if((distance[v]+cost[v][u]<distance[u]) && !visited[u])
distance[u]=distance[v]+cost[v][u];
}
}
int main()
{
int n,source,i,j,cost[10][10],distance[10];
cout<<"Enter the number of nodes : ";
cin>>n;
cout<<"Enter the cost matrix :\n";
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
cin>>cost[i][j];
if(cost[i][j]==0) cost[i][j]=INFINITY;
}
cout<<"Enter the source : ";
cin>>source;
dijkstra(n,source,cost,distance);
cout<<"Shortest path from given source are :\n";
for(i=1;i<=n;i++)
if(i!=source)
cout<<source<<" --> "<<i<<" : cost = "<<distance[i]<<endl;
return 0;
}
6. Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal's
algorithm.
#include<iostream>
using namespace std;
void kruskal(int cost[10][10], int n)
{
int parent[10],i,j,a,b,u,v,min,count=1,sum=0;
for(i=1;i<=n;i++)
parent[i]=0;
while(count!=n)
{
min=9999;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]<min)
{
min=cost[i][j];
u=a=i;
v=b=j;
}
while(parent[u]!=0)
u=parent[u];
while(parent[v]!=0)
v=parent[v];
if(u!=v)
{
count++;
sum=sum+cost[a][b];
cout<<"\nEdge ("<<a<<","<<b<<") : "<<cost[a][b];
parent[v]=u;
}
cost[a][b]=cost[b][a]=9999;
}
cout<<"\nWeight of minimum spanning tree = "<<sum<<endl;
}
int main()
{
int cost[10][10],i,j,n;
cout<<"\nEnter the number of vertices : ";
cin>>n;
cout<<"\nEnter the cost matrix : \n";
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cin>>cost[i][j];
kruskal(cost,n);
return 0;
}
Comments
Post a Comment