From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM
	autolearn=unavailable autolearn_force=no version=3.4.4
X-Received: by 10.224.3.131 with SMTP id 3mr6112515qan.5.1369671195808;
        Mon, 27 May 2013 09:13:15 -0700 (PDT)
X-Received: by 10.50.164.200 with SMTP id ys8mr203047igb.14.1369671195757;
 Mon, 27 May 2013 09:13:15 -0700 (PDT)
Path: 
 eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!news.eternal-september.org!news.eternal-september.org!mx05.eternal-september.org!feeder.eternal-september.org!usenet.blueworldhosting.com!npeer01.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!ch1no1362524qab.0!news-out.google.com!y6ni51517qax.0!nntp.google.com!ch1no1362517qab.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: comp.lang.ada
Date: Mon, 27 May 2013 09:13:15 -0700 (PDT)
Complaints-To: groups-abuse@google.com
Injection-Info: glegroupsg2000goo.googlegroups.com;
 posting-host=122.179.82.193;
 posting-account=D26rTAoAAADjIGLMQP9tokchs-Hg81ek
NNTP-Posting-Host: 122.179.82.193
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <66fb159e-c347-476a-9c80-5c2b1f74df97@googlegroups.com>
Subject: ADA Program
From: TASLEEM ARIF <tasleem139@gmail.com>
Injection-Date: Mon, 27 May 2013 16:13:15 +0000
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 29388
Xref: news.eternal-september.org comp.lang.ada:15656
Date: 2013-05-27T09:13:15-07:00
List-Id: <comp.lang.ada>

1. Sort a given set of elements using the Quicksort method and determine th=
e time required   =20
    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 ve=
rsus n. The elements
    can be read from a file or can be generated using the random number gen=
erator.

#include<iostream.h>
#include<conio.h>
#include<dos.h>
#include<stdlib.h>
#include<time.h>

int par(int a[],int low,int high)
{
int i=3Dlow,j=3Dhigh+1,temp,pivot=3Da[low];
while(i<=3Dj)
{
do
{ i++;}
while(pivot>=3Da[i]);
do
{j--;}
while(pivot<a[j]);
if(i<j)
{
temp=3Da[i];
a[i]=3Da[j];
a[j]=3Dtemp;
}
}
temp=3Da[j];
a[j]=3Da[low];
a[low]=3Dtemp;
return j;
}

void quick(int a[],int low,int high)
{
int mid;
if(low<high)
{
mid=3Dpar(a,low,high);
quick(a,low,mid-1);
quick(a,mid+1,high);
}
}

int main()
{
int a[2000];
int i,n;
clock_t start,end;
clrscr();
cout<<"Enter the number of elements \n";
cin>>n;
cout<<"The input elements are\n";
for(i=3D0;i<n;i++)
{
a[i]=3Drand()%20;
cout<<a[i]<<"\n";
}
start=3Dclock();
delay(2000);
quick(a,0,n-1);
end=3Dclock();
cout<<"The sorted elements are:\n";

for(i=3D0;i<n;i++)
{
cout<<a[i]<<endl;
}
cout<<endl;
cout<<"Time complexity:"<<(end-start)/CLK_TCK;
getch();
return 0;
}

/*
Enter the number of elements
5
The input elements are
6
10
2
10
16
The sorted elements are:
2
6
10
10
16
Time complexity:1.923077	*/
2. Using OpenMP, implement a parallelized Merge Sort algorithm to sort a gi=
ven set of
    elements and determine the time required to sort the elements. Repeat t=
he experiment for
    different values of n, the nnumber 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>
#include<stdlib.h>
#include<omp.h>

int a[20];
void simple_merge(int low,int mid,int high)
{
  	int i,j,k,c[20];
	k=3Dlow;
	i=3Dlow;
	j=3Dmid+1;
   	 while((i<=3Dmid)&&(j<=3Dhigh))
    	{
		if(a[i]<a[j])
		c[k++]=3Da[i++];
		else
	    	c[k++]=3Da[j++];
    	}
	while(i<=3Dmid)
		c[k++]=3Da[i++];
	while(j<=3Dhigh)
		c[k++]=3Da[j++];
	sleep(1);

	for(i=3Dlow;i<=3Dk-1;i++)
		a[i]=3Dc[i];
}
void merge_sort(int low,int high)
{
int mid;

    	if(low<high)
    	{
		mid=3D(low+high)/2;
		merge_sort(low,mid);
		merge_sort(mid+1,high);
		simple_merge(low,mid,high);
    	}
}
int main()
{
	int n,i,j,val;
	time_t end, st;
	=09
	printf("Enter value of n\n");
	scanf("%d",&n);
	printf("\n Array values are:\n");
		=20
	#pragma omp parallel for
	for(i=3D0;i<n;i++)
	{
		val=3Drand()%100;
		a[i]=3D val;
		printf(=93%d \t =93,a[i]);
	} =20

	time(&st);

	merge_sort(0,n-1);
	printf("sorted array is\n");

	#pragma omp parallel for
	for(i=3D0;i<n;i++)
	printf("%d, thread id=3D%d \n",a[i],omp_get_thread_num());

	time(&end);

	printf(=93\n time taken is:%f \n=94, difftime(end,st));
}




























3 a. Obtain the Topological ordering of vertices in a given digraph.

#include<stdio.h>
#include<conio.h>

void DFS(int);
int a[10][10], vir[10], exp[10], j =3D 0, n;

void main()
{
	int m, i, v, u, k;
	clrscr();
	printf("Enter the no. of Vertices\n");
	scanf("%d",&n);
	for(i=3D1;i<=3Dn;i++)
	{
		for(k=3D1;k<=3Dn;k++)
		a[i][k] =3D 0;
	}
	printf("Enter the no. of edges\n");
	scanf("%d",&m);
	for(i=3D1;i<=3Dm;i++)
	{
		printf("Enter an edge\n");
		scanf("%d%d",&u,&v);
		a[u][v] =3D 1;
	}
	for(i=3D1;i<=3Dn;i++)
		vir[i] =3D 0;
	for(i=3D1;i<=3Dn;i++)
	{
		if(vir[i]=3D=3D0)
			DFS(i);
	}
	printf("Topology Order\n");
	for(i=3Dn-1;i>=3D0;i--)
		printf("%d",exp[i]);
	getch();
}








void DFS(int v)
{
	int i;
	vir[v] =3D 1;
	for(i=3D1;i<=3Dn;i++)
	{
		if(a[v][i] =3D=3D 1 && vir[i] =3D=3D 0)
		DFS(i);
	}=20
	exp[j++] =3D v;
}


/*
Enter the no. of Vertices
5                                                                          =
    =20
Enter the no. of edges                                                     =
    =20
5                                                                          =
    =20
Enter an edge                                                              =
    =20
1 3                                                                        =
    =20
Enter an edge                                                              =
    =20
2 3                                                                        =
    =20
Enter an edge                                                              =
    =20
3 4                                                                        =
    =20
Enter an edge                                                              =
    =20
3 5                                                                        =
    =20
Enter an edge                                                              =
    =20
4 5                                                                        =
    =20
Topology Order                                                             =
    =20
21345                                                                      =
    =20
*/















3 b. Compute the transitive closure of a given directed graph using Warshal=
l's algorithm.

#include<stdio.h>
#include<conio.h>
void warshal(int adjm[][10], int n)
{
	int j,i,k;
	for(k=3D1;k<=3Dn;k++)
		for(i=3D1;i<=3Dn;i++)
			for(j=3D1;j<=3Dn;j++)
			adjm[i][j] =3D adjm[i][j] || (adjm[i][k] && adjm[k][j]);
}
void main()
{
	int n, i, j, adjm[10][10];
	clrscr();
	printf("Enter the no. of Vertics in the given Digraph\n");
	scanf("%d",&n);
	printf("Enter the adjacency matrix of graph\n");
	for(i=3D1;i<=3Dn;i++)
	{
		for(j=3D1;j<=3Dn;j++)
		scanf("%d", &adjm[i][j]);
	}
	warshal(adjm,n);
	printf("The transitive clousure of entered digraph\n");
	for(i=3D1;i<=3Dn;i++)
	{
		for(j=3D1;j<=3Dn;j++)
		printf("%d",adjm[i][j]);
		printf("\n");
	}
	getch();
}

/*Enter the no of vertices in the given digraph 4                          =
                                                    =20
Enter the adjacency matrix of graph                                        =
    =20
0 1 0 0                                                                    =
    =20
0 0 0 1                                                                    =
    =20
0 0 0 0                                                                    =
    =20
1 0 1 0                                                                    =
    =20
The transitive closure of entered digraph                                  =
    =20
1111                                                                       =
    =20
1111                                                                       =
    =20
0000                                                                       =
    =20
1111                          */
4. Implement 0/1 Knapsack problem using dynamic programming.

#include<stdio.h>
#include<conio.h>

int max(int a, int b)
{
	return (a>b)?a:b;
}

int myknsack(int i,int j,int p[],int w[],int v[][11])
{
	int val;
	if(v[i][j]<0)
	{
		if(j<w[i])
		val =3D myknsack(i-1,j,p,w,v);
		else
		val =3D max(myknsack(i-1,j,p,w,v),p[i]+myknsack(i-1,j-w[i],p,w,v));
		v[i][j] =3D val;
	}
	return v[i][j];
}

void main()
{
	int n,i,j,p[10],w[10],v[11][11],val,c;
	clrscr();
	printf("Enter no. of Objects\n");
	scanf("%d",&n);
	printf("Enter capacity of sack\n");
	scanf("%d",&c);
	printf("Enter the profit of each of %d objects\n",n);
	for(i=3D1;i<=3Dn;i++)
	{
		scanf("%d",&p[i]);
	}
	printf("Enter the weight of the object\n") ;
	for(i=3D1;i<=3Dn;i++)
	{
		scanf("%d",&w[i]);
	}
	for(i=3D0;i<=3Dn;i++)
	{
		for(j=3D0;j<=3Dc;j++)
			if((i=3D=3D0)||(j=3D=3D0))
			v[i][j] =3D 0;
			else
			v[i][j] =3D -1;
	}
	val =3D myknsack(n,c,p,w,v);
	printf("The total val of the objects in the Knapsack is %d\n",val);
	printf("The object packed up into the sack are\t");
	i=3Dn;j=3Dc;
	while(i>0)
	{
		if(v[i][j]!=3Dv[i-1][j])
		{
			printf("%d\t",i);
			j =3D j-w[i];i--;
		}
		else
		i--;
	}
	getch();
}

/*
enter number of objects:
4                                                                          =
    =20
enter capacity of knapsack                                                 =
    =20
5                                                                          =
    =20
Enter profit of each of 4 objects                                          =
    =20
12 10 20 15                                                                =
    =20
Enter the weight of each of 4 objects                                      =
    =20
2 1 3 2                                                                    =
    =20
The total value of the objects in the knapsack is:37
The objects picked up into the sack are:4       2       1                  =
    =20
*/















5. From a given vertex in a weighted connected graph, find shortest paths t=
o other  =20
    vertices using Dijkstra=92s algorithm.

#include<stdio.h>
#include<conio.h>

void Dijk(int src, int cost[][10], int dest[], int n)
{
	int visit[10], min, i ,j, u;
	for(i=3D1; i<=3Dn; i++)
	{
		visit[i] =3D 0;
		dest[i] =3D cost[src][i];
	}
	visit[src] =3D 1; dest[src] =3D 0;
	for(i=3D1;i<=3Dn;i++)
	{
		if(i=3D=3Dsrc) continue;
		min =3D 999;
		for(j=3D1;j<=3Dn;j++)
			if((visit[j] =3D=3D 0) && (min >dest[j]))
			{
				min =3D dest[j];
				u =3D j;
			}
		visit[u] =3D 1;
		for(j=3D1;j<=3Dn;j++)
			if(visit[j] =3D=3D 0)
			{
				if(dest[j] >dest[u] + cost[u][j])
				dest[j] =3D dest[u] + cost[u][j];
			}
	}
}

void main()
{
	int n, cost[10][10], dist[10] =3D {0}, i, j, src;
	clrscr();
	printf("Enter the no. of Vertices\n");
	scanf("%d",&n);
	printf("Enter the Adjacency matrix of the graph with 999 for infinity\n");
	for(i=3D1;i<=3Dn;i++)
		for(j=3D1;j<=3Dn;j++)
			scanf("%d",&cost[i][j]);
	printf("enter the source vertix\n");
	scanf("%d", &src);
	Dijk(src,cost,dist,n);
	printf("The shortest path from the %d to all the vertix are \n", src);
	for(i=3D1;i<=3Dn;i++)
		printf(" to %d =3D %d\n",i,dist[i]);
	getch();
}

/*
Enter the no. of Vertices
6                                                                          =
    =20
Enter the Adjacency matrix of the graph with 999 for infinity              =
    =20
0 15 10 999 45 999                                                         =
    =20
999 0 15 999 20 999
20 999 0 20 999 999                                                        =
    =20
999 10 999 0 35 999                                                        =
    =20
999 999 999 30 0 999                                                       =
    =20
999 999 999 4 999 0                                                        =
    =20
enter the source vertix
5                                                                          =
    =20
The shortest path from the 5 to all the vertix are
to 1 =3D 75                                                                =
     =20
to 2 =3D 40                                                                =
     =20
to 3 =3D 55                                                                =
     =20
to 4 =3D 30                                                                =
     =20
to 5 =3D 0                                                                 =
     =20
to 6 =3D 999                                                               =
     =20

*/


















6. Find minimum cost spanning tree of a given undirected graph using Kruska=
l=92s algorithm

#include<stdio.h>
#include<conio.h>
void kruskal(int cost[][10], int n, int mst[][10])
{
	int min_edge_weight =3D 999, u, v, i, j, k, l, parent[10], edge =3D 0, tem=
p;
	for(i=3D1;i<=3Dn;i++)
	{
		cost[i][i] =3D 999;
		for(j=3D1;j<=3Dn;j++)
			if((j>i) && (cost[i][j] !=3D 999)) edge++;
	}
	for(i=3D1;i<=3Dn;i++) parent[i] =3D i;
	while(edge !=3D 0)
	{
		for(i=3D1;i<=3Dn;i++)
			for(j=3D1;j<=3Dn;j++)
				if((j>i) && (cost[i][j] <min_edge_weight))
				{
					min_edge_weight =3D cost[i][j];
					u =3D i, v =3D j;
				}
		i =3D parent[u], j =3D parent[v];
		if(i !=3D j)
		{
			mst[u][v] =3D mst[v][u] =3D cost[u][v];
			if(i < j)
			{
				for(k=3D1;k<=3Dn;k++)
					if(parent[k] =3D=3Dj) parent[k] =3D i;
			}
			else
			{
				for(k=3D1;k<=3Dn;k++)
					if(parent[k] =3D=3Di) parent[k] =3D j;
			}
		}
		cost[u][v] =3D cost[v][u] =3D 999;
		edge--;
		min_edge_weight =3D 999;
	}
}



void main()
{
	int i, j, n, cost[10][10], mst[10][10] =3D {0}, total =3D0;
	clrscr();
	printf("Enter the no. of vertices in the undirected graphs\n");
	scanf("%d", &n);
	printf("Enter the cost matrix of the graph , with 999 for no edges\n");
	for(i=3D1;i<=3Dn;i++)
	{
		for(j=3D1;j<=3Dn;j++)
			scanf("%d", &cost[i][j]);
	}
	kruskal(cost,n,mst);
	printf("A MST for the given graph is\n");
	for(i=3D1;i<=3Dn;i++)
	{
		for(j=3D1;j<=3Dn;j++)
			if((j>i) && (mst[i][j] !=3D 0))
			{
				printf("%d --> %d\n",i,j);
				total =3D total + mst[i][j];
			}
	}
	for(i=3D1;i<=3Dn;i++)
	{
		for(j=3D1;j<=3Dn;j++)
			printf("%d\t", mst[i][j]);
		printf("\n");
	}
	printf("The total cost of the MST is %d\n", total);
	getch();
}




/*
Enter the no. of vertices in the undirected graphs
4                                                                          =
    =20
Enter the cost matrix of the graph , with 999 for no edges                 =
   =20
0 10 999 999                                                               =
    =20
10 0 20 999                                                                =
    =20
999 20 0 30                                                                =
    =20
999 999 30 0                                                               =
    =20


A MST for the given graph is                                               =
    =20
1 --> 2                                                                    =
    =20
2 --> 3                                                                    =
    =20
3 --> 4                                                                    =
    =20
0       10      0       0                                                  =
    =20
10      0       20      0                                                  =
    =20
0       20      0       30                                                 =
    =20
0       0       30      0                                                  =
    =20
The total cost of the MST is 60                                            =
    =20
*/





































7 a. Print all the nodes reachable from a given starting node in a digraph =
using Breadth first  =20
       Search (BFS) method.

#include<stdio.h>
#include<conio.h>
void insertq(int q[], int node, int *f, int *r)
{
	if((*f=3D=3D-1)&&(*r=3D=3D-1))
	{
		(*f)++;
		(*r)++;
		q[*f] =3D node;
	}
	else
	{
		(*r)++;
		q[*r] =3D node;
	}
}
int deleteq(int q[], int *f, int *r)
{
	int temp;
	temp =3D q[*f];
	if(*f=3D=3D*r)
		*f =3D *r =3D -1;
	else
		(*f)++;
	return temp;
}
void bfs(int n, int adj[][10], int src, int visited[])
{
	int q[20], f =3D -1, r =3D -1, v, i;
	insertq(q, src, &f, &r);
	while((f<=3Dr)&&(f!=3D-1))
	{
		v =3D deleteq(q, &f, &r);
		if(visited[v]!=3D1)
		{
			visited[v] =3D 1;
			printf("%d",v);
		}
		for(i=3D1;i<=3Dn;i++)
			if((adj[v][i]=3D=3D1)&&(visited[i]!=3D1))
				insertq(q,i,&f,&r);
	}
}

void main()
{
	int n,i,j,adj[10][10],src,visited[10];
	clrscr();
	printf("Enter number of vertices\n");
	scanf("%d",&n);
	printf("Enter the adj matrix of digraph for BFS\n");
	for(i=3D1;i<=3Dn;i++)
	{
		visited[i] =3D 0;
		for(j=3D1;j<=3Dn;j++)
			scanf("%d",&adj[i][j]);
	}
	printf("Enter Starting Vertix\n");
	scanf("%d",&src);
	printf("The nodes reachable from src are\n");
	bfs(n,adj,src,visited);
	getch();
}
/*
enter the no. verticess
5                                                                          =
    =20
enter the adjancecy matrix of the digraph for bfs
0 0 1 1 0                                                                  =
    =20
0 0 0 0 0                                                                  =
    =20
0 1 0 0 0                                                                  =
    =20
0 0 0 0 1                                                                  =
    =20
0 0 0 0 0                                                                  =
    =20
enter source vertex 1                                                      =
    =20
the nodes reachable from src
1       3       4       2       5                                          =
    =20
*/















7 b. Check whether a given graph is connected or not using Depth First Sear=
ch (DFS) method.

#include<stdio.h>
#include<conio.h>
void dfs(int adjm[][10], int visited[], int n, int src)
{
	int w;
	visited[src]=3D1;
	for(w=3D1;w<=3Dn;w++)
	{
		if((adjm[src][w]=3D=3D1)&&(visited[w]=3D=3D0))
		{
			printf("%d -- %d\n", src,w);
			dfs(adjm,visited,n,w);
		}
	}
}

void main()
{
	int n,i,j,adjm[10][10],src,visited[10]=3D{0},flag,p;
	clrscr();
	printf("Enter number of nodes for the undirected graph for DFS\n");
	scanf("%d",&n);
	printf("Enter the adjecency matrix\n");
	for(i=3D1;i<=3Dn;i++)
		for(j=3D1;j<=3Dn;j++)
			scanf("%d",&adjm[i][j]);
	printf("Enter source verix from where to start DFS\n");
	scanf("%d",&src);
	dfs(adjm,visited,n,src);
	for(i=3D1;i<=3Dn;i++)
		if(visited[i]!=3D1)
			flag=3D1; p=3Di;
		if(flag =3D=3D 1)
			printf("The node %d is isolated and graph is unconnected\n",p);
		else
			printf("The graph is connected\n");
	getch();
}






/*
Enter number of nodes for the undirected graph for DFS
5                                                                          =
    =20
Enter the adjecency matrix                                                 =
    =20
0 0 1 1 0                                                                  =
    =20
0 0 0 0 0                                                                  =
    =20
0 1 0 0 0                                                                  =
    =20
0 0 0 0 1                                                                  =
    =20
0 0 0 0 0                                                                  =
    =20
Enter source verix from where to start DFS                                 =
    =20
1                                                                          =
    =20
1 -- 3                                                                     =
    =20
3 -- 2                                                                     =
    =20
1 -- 4                                                                     =
    =20
4 -- 5                                                                     =
    =20
The graph is connected              */                                     =
          =20
































8. Find a subset of a given set S=3D{s1,s2=85..sn} of n positive integers w=
hose sum is equal to a
   given positive integer d. For eg. If S=3D{1, 2, 5, 6, 8} and d=3D9 there=
 are two solutions { 1, 2, 6 }
   and { 1, 8 }. A suitable message is to be displayed if the given problem=
 instance doesn=92t have=20
   a solution.

#include<stdio.h>
int w[10],d,n,count,x[10],i;

void sum_of_subset(int s,int k,int r)
{
	x[k] =3D 1;
	if(s+w[k]=3D=3Dd)
	{
		printf("\n Subset %d=3D",++count);
		for(i=3D0;i<=3Dk;i++)
			if(x[i])
				printf("%d\t",w[i]);
	}
	else if(s+w[k]+w[k+1] <=3D d)
		sum_of_subset(s+w[k],k+1,r-w[k]);
		if((s+r-w[k]>=3Dd) && (s,w[k+1])<=3Dd)
		{
			x[k] =3D 0;
			sum_of_subset(s,k+1,r-w[k]);
		}
}

void main()
{
	int sum=3D0,k;
	clrscr();
	printf("Enter the number of elements\n");
	scanf("%d",&n);
	printf("Enter the elements in ascending order:\n");
	for(i=3D0;i<n;i++)
	{
		scanf("%d",&w[i]);
	}
	printf("Enter the sum:\n");
	scanf("%d",&d);
	=09
	for(i=3D0;i<n;i++)
		x[i]=3D0;
	for(i=3D0;i<n;i++)
		sum =3D sum+w[i];
		if(sum<d || w[0]>d)
			printf("No subset possible");
			else
			sum_of_subset(0,0,sum);
	getch();
}


/*
Enter the number of elements
5                                                                          =
    =20
Enter the elements in ascending order:                                     =
    =20
1 3 5 7 9                                                                  =
    =20
Enter the sum:
8

 Subset 1=3D1	7
 Subset 2=3D3	5
*/







































9. Implement any scheme to find the optimal solution for the Traveling Sale=
sperson problem
    and then solve the same problem instance using any approximation algori=
thm and
   determine the error in the approximation.

#include<iostream.h>
#include<iomanip.h>
#include<conio.h>

int tspdp(int c[10][10],int start,int tour[10],int n)
{
	int temp[10],mintour[10],cost;
	int min =3D 999;
	if( start =3D=3D n-2 )
	return c[tour[n-2]][tour[n-1]] + c[tour[n-1]][0];
	for( int i =3D 0 ; i < n ; i++ )
	{
		for( int j =3D 0 ; j < n ; j++ )
			temp[j] =3D tour[j];
			temp[start + 1] =3D tour[i];
			temp[i] =3D tour[start + 1];
			if( c[tour[start]][i] + ( cost =3D tspdp(c,start+1,temp,n) ) < min )
			{
				min =3D c[tour[start]][i] + cost;
				for( int j =3D 0 ; j < n ; j++ )
					mintour[j] =3D temp[j];
			}
	}
	for( int j =3D 0 ; j < n ; j++ )
	tour[j] =3D mintour[j];
	return min;
}

void main()
{
	int c[10][10],tour[10],cost;
	int i=3D0,j=3D0;
	clrscr();
	cout<<"\nEnter the no cities : ";
	int n;
	cin>>n;
	for(i=3D0;i<n;i++)
	{
		c[i][i] =3D 999;
		for(j=3Di+1;j<n;j++)
		{
			cout<<"\nEnter the cost(integer) from "<<i<<" to "<<j<<" : ";
			cin>>c[i][j];
		}
	}
	for(i=3D0;i<n;i++)
	{
		for(j=3D0;j<i;j++)
		{
			c[i][j] =3D c[j][i];
		}
	}
	cout<<"\nCost Adj Matrix is \n";
	for(i=3D0;i<n;i++)
	{
		for(j=3D0;j<n;j++)
		{
			cout<<c[i][j]<<"\t";
		}
		cout<<endl;
	}
	for(i=3D0;i<n;i++)
	tour[i] =3D i;
	cost =3D tspdp(c,0,tour,n);
	cout<<"\nTour : ";
	for(i=3D0;i<n;i++)
	cout<<tour[i]+1<<"\t";
	cout<<"\nMin Cost : "<<cost<<endl;
	getch();
}
/*
Enter the no cities : 4

Enter the cost(integer) from 0 to 1 : 20

Enter the cost(integer) from 0 to 2 : 10

Enter the cost(integer) from 0 to 3 : 50

Enter the cost(integer) from 1 to 2 : 60

Enter the cost(integer) from 1 to 3 : 70

Enter the cost(integer) from 2 to 3 : 40

Cost Adj Matrix is
999     20      10      50
20      999     60      70
10      60      999     40
50      70      40      999

Tour : 2        3       1       4
Min Cost : 120
*/







10. Find Minimum Cost Spanning Tree of a given undirected graph using Prim=
=92s algorithm.

#include<stdio.h>
#include<conio.h>

void prim(int cost[][10], int n, int mst[][10])
{
	int visit[10] =3D {0}, min_edge_weight =3D 999, v, u, i, j, vertices =3D 0=
;
	visit[1] =3D 1;
	vertices++;
	while(vertices < n)
	{
		for(i=3D1;i<=3Dn;i++)
			for(j=3D1;j<=3Dn;j++)
			{
				if((visit[i] =3D=3D 1) && (visit[j] !=3D 1) && (cost[i][j] <min_edge_we=
ight))
				{
					min_edge_weight =3D cost[i][j];
					u=3Di, v=3Dj;
				}
			}
		visit[v] =3D 1;
		vertices++;
		mst[u][v] =3D mst[v][u] =3D min_edge_weight;
		min_edge_weight =3D 999;
	}
}

void main()
{
	int i,j,n,cost[10][10],mst[10][10] =3D {0}, total =3D 0;
	clrscr();
	printf("Enter the no. of vertices in the undirected graph\n");
	scanf("%d",&n);
	printf("Enter the cost matrix of the graph, with 999 for no. edges\n");
	for(i=3D1;i<=3Dn;i++)
		for(j=3D1;j<=3Dn;j++)
		scanf("%d",&cost[i][j]);
	prim(cost,n,mst);
	printf("A MST for the given graph is\n");
	for(i=3D1;i<=3Dn;i++)
		for(j=3D1;j<=3Dn;j++)
			if((j>i)&&(mst[i][j] !=3D 0))
			{
				printf("%d -- %d\n",i,j);
				total =3D total + mst[i][j];
			}
	for(i=3D1;i<=3Dn;i++)
	{
		for(j=3D1;j<=3Dn;j++)
			printf("%d\t",mst[i][j]);
		printf("\n");
	}
	printf("The total cost of this MST is %d\n",total);
	getch();
}

/*
Enter the no. of vertices in the undirected graph
4                                                                          =
    =20
Enter the cost matrix of the graph, with 999 for no. edges                 =
    =20
0 10 999 40                                                                =
    =20
10 0 20 999                                                                =
    =20
999 20 0 30                                                                =
    =20
40 999 30 0                                                                =
    =20
A MST for the given graph is                                               =
    =20
1 -- 2                                                                     =
    =20
2 -- 3                                                                     =
    =20
3 -- 4                                                                     =
    =20
0       10      0       0                                                  =
    =20
10      0       20      0                                                  =
    =20
0       20      0       30                                                 =
    =20
0       0       30      0                                                  =
    =20
The total cost of this MST is 60                                           =
    =20
*/



















11. Implement All-Pairs Shortest Paths Problem using Floyd's algorithm. Par=
allelize this
      algorithm, implement it using OpenMP and determine the speed-up achie=
ved.

#include<stdio.h>
int a[10][10],n;

void floyd()
 {
 	 int i,j,k;

 for(k=3D1;k<=3Dn;k++)
    	{
		 for(i=3D1;i<=3Dn;i++)
	   	{
	     		for(j=3D1;j<=3Dn;j++)
	      		{
			        if((a[i][k]+a[k][j])<a[i][j])
			        a[i][j]=3Da[i][k]+a[k][j];
	        			else
			        a[i][j] =3D a[i][j];
		 	}
	   	}
     	}
 }

int main( )
{
int i,j;
    	time_t st,end;
   =20
    	printf("\n enter the number of nodes: ");   =20
    	scanf("%d",&n);
    	printf("\n enter the cost adjancency matrix:\n");
    	for(i=3D1;i<=3Dn;i++)
       		for(j=3D1;j<=3Dn;j++)
            			scanf("%d",&a[i][j]);
time (&st);
  	floyd();
printf("\n the shortest path matrix is:\n");
   	for(i=3D1;i<=3Dn;i++)
      	{
         		for(j=3D1;j<=3Dn;j++)
               	printf("%d\t",a[i][j]);
         		printf("\n");
      	}
time(&end);
printf(=93\n time taken is : %f \n=94, difftime(end,st));
}




12. Implement N Queen=92s problem using Back Tracking.

#include<stdio.h>
#include<conio.h>

int x[20] =3D {0};

int abs(int y)
{
	int i=3D0;
	if(y>=3D0) return y;
	else
	{
		while(y<=3D0)
			y++, i++;
		return --i;
	}
}

int place(int k, int i)
{
	int j;
	for(j=3D1;j<=3Dk-1;j++)
		if((x[j] =3D=3D i) || (abs(x[j]-i) =3D=3D abs(j-k))) return 0;
	return 1;
}

void nqueens(int k, int n)
{
	int i, j;
	for(i=3D1;i<=3Dn;i++)
	{
		if(place(k,i))
		{
			x[k] =3D i;
			if(k=3D=3Dn)
			{
				for(j=3D1;j<=3Dn;j++)
					printf("%d",x[j]);
				printf("\n");
			}
			else=20
nqueens(k+1,n);
		}
	}
}

void main()
{
	int n;
	clrscr();
	printf("Enter the no. of queens to place\n");
	scanf("%d", &n);
	nqueens(1,n);
	getch();
}

/*
Enter the no. of queens to place
4                                                                          =
    =20
2413                                                                       =
    =20
3142                                                                       =
    =20
*/