Trend Posts
Author
View LUQMAN's profile
Showing posts with label subset. Show all posts
Showing posts with label subset. Show all posts
Monday, July 21, 2014
/*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;
}
/*Check whether a given graph is connected or not using DFSmethod.*/
#include<stdio.h>
void dfs(int i);
int i,j,adj[1000][1000],v[1000],w,n,count;
void main()
{
printf("\nEnter the number of nodes\n");
scanf("%d",&n);
printf("\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",&adj[i][j]);
printf("\n\nThe adjacency matrix is:\n\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++)
v[j]=0;
dfs(i);
if(count==n)
{
printf("\nThe entered graph is connected\n");
return;
}
}
printf("\nThe entered graph is not connected\n");
}
void dfs(int i)
{
int w;
count++;
v[i]=1;
for(w=1;w<=n;w++)
if(adj[i][w]==1 && !v[w])
dfs(w);
}
/*Print all the nodes reachable from a given starting node in a digraph using BFS method.*/
#include<stdio.h>
int i,j,s,a[100][100],q[100],visited[100],u,rear,front,n;
void bfs();
void main()
{
printf("\nEnter the number of nodes:\n");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
printf("\nThe entered adjacency matrix is:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",a[i][j]);
printf("\n");
}
printf("\nEnter the source vertex:\n");
scanf("%d",&s);
bfs();
for(i=1;i<=n;i++)
{
if(visited[i])
printf("\nNode %d is reachable from source node %d",i,s);
else
printf("\nNode %d is not reachable from source node %d",i,s);
}
}
void bfs()
{
q[rear]=s;
visited[s]=1;
while(front<=rear)
{
u=q[front];
front=front+1;
for(i=1;i<=n;i++)
if(a[u][i] && !visited[i])
{
rear=rear+1;
q[rear]=i;
visited[i]=1;
}
}
}
/*Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal's algorithm.*/
#include<stdio.h>
int ne,i,j,min,u,v,cost[100][100],n,a,b,parent[100],mincost=0;
void kruskal()
{
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",ne++,a,b,min);
mincost+=min;
parent[v]=u;
}
cost[a][b]=cost[b][a]=999;
}
}
void main()
{
printf("\nEnter the number of nodes\n");
scanf("%d",&n);
printf("\nEnter the weight of each nodes\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
printf("\nEntered weights are:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",cost[i][j]);
printf("\n");
}
kruskal();
}
/*Find Minimum Cost Spanning Tree of a given undirected graph using Prim’s algorithm.*/
#include<stdio.h>
int i,j,min,nearv[100],cost[100][100],t[100][100],s,n,u,mincost=0,k;
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);
}
}
void main()
{
printf("\nEnter the number of nodes\n");
scanf("%d",&n);
printf("\nEnter the weight of each nodes\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
printf("\nEntered weights are:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t",cost[i][j]);
printf("\n");
}
prims();
}
Subscribe to:
Posts (Atom)