comp.lang.ada
 help / color / mirror / Atom feed
* ADA Program
@ 2013-05-27 16:13 TASLEEM ARIF
  2013-05-27 17:33 ` Dennis Lee Bieber
  2013-05-27 17:44 ` Shark8
  0 siblings, 2 replies; 10+ messages in thread
From: TASLEEM ARIF @ 2013-05-27 16:13 UTC (permalink / raw)


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.

#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=low,j=high+1,temp,pivot=a[low];
while(i<=j)
{
do
{ i++;}
while(pivot>=a[i]);
do
{j--;}
while(pivot<a[j]);
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
temp=a[j];
a[j]=a[low];
a[low]=temp;
return j;
}

void quick(int a[],int low,int high)
{
int mid;
if(low<high)
{
mid=par(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=0;i<n;i++)
{
a[i]=rand()%20;
cout<<a[i]<<"\n";
}
start=clock();
delay(2000);
quick(a,0,n-1);
end=clock();
cout<<"The sorted elements are:\n";

for(i=0;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 given set of
    elements and determine the time required to sort the elements. Repeat the 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=low;
	i=low;
	j=mid+1;
   	 while((i<=mid)&&(j<=high))
    	{
		if(a[i]<a[j])
		c[k++]=a[i++];
		else
	    	c[k++]=a[j++];
    	}
	while(i<=mid)
		c[k++]=a[i++];
	while(j<=high)
		c[k++]=a[j++];
	sleep(1);

	for(i=low;i<=k-1;i++)
		a[i]=c[i];
}
void merge_sort(int low,int high)
{
int mid;

    	if(low<high)
    	{
		mid=(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;
		
	printf("Enter value of n\n");
	scanf("%d",&n);
	printf("\n Array values are:\n");
		 
	#pragma omp parallel for
	for(i=0;i<n;i++)
	{
		val=rand()%100;
		a[i]= val;
		printf(“%d \t “,a[i]);
	}  

	time(&st);

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

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

	time(&end);

	printf(“\n time taken is:%f \n”, 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 = 0, n;

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








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


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















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

#include<stdio.h>
#include<conio.h>
void warshal(int adjm[][10], int n)
{
	int j,i,k;
	for(k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
			adjm[i][j] = 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=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		scanf("%d", &adjm[i][j]);
	}
	warshal(adjm,n);
	printf("The transitive clousure of entered digraph\n");
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		printf("%d",adjm[i][j]);
		printf("\n");
	}
	getch();
}

/*Enter the no of vertices in the given digraph 4                                                                               
Enter the adjacency matrix of graph                                             
0 1 0 0                                                                         
0 0 0 1                                                                         
0 0 0 0                                                                         
1 0 1 0                                                                         
The transitive closure of entered digraph                                       
1111                                                                            
1111                                                                            
0000                                                                            
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 = myknsack(i-1,j,p,w,v);
		else
		val = max(myknsack(i-1,j,p,w,v),p[i]+myknsack(i-1,j-w[i],p,w,v));
		v[i][j] = 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=1;i<=n;i++)
	{
		scanf("%d",&p[i]);
	}
	printf("Enter the weight of the object\n") ;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&w[i]);
	}
	for(i=0;i<=n;i++)
	{
		for(j=0;j<=c;j++)
			if((i==0)||(j==0))
			v[i][j] = 0;
			else
			v[i][j] = -1;
	}
	val = 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=n;j=c;
	while(i>0)
	{
		if(v[i][j]!=v[i-1][j])
		{
			printf("%d\t",i);
			j = j-w[i];i--;
		}
		else
		i--;
	}
	getch();
}

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















5. From a given vertex in a weighted connected graph, find shortest paths to other   
    vertices using Dijkstra’s 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=1; i<=n; i++)
	{
		visit[i] = 0;
		dest[i] = cost[src][i];
	}
	visit[src] = 1; dest[src] = 0;
	for(i=1;i<=n;i++)
	{
		if(i==src) continue;
		min = 999;
		for(j=1;j<=n;j++)
			if((visit[j] == 0) && (min >dest[j]))
			{
				min = dest[j];
				u = j;
			}
		visit[u] = 1;
		for(j=1;j<=n;j++)
			if(visit[j] == 0)
			{
				if(dest[j] >dest[u] + cost[u][j])
				dest[j] = dest[u] + cost[u][j];
			}
	}
}

void main()
{
	int n, cost[10][10], dist[10] = {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=1;i<=n;i++)
		for(j=1;j<=n;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=1;i<=n;i++)
		printf(" to %d = %d\n",i,dist[i]);
	getch();
}

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

*/


















6. Find minimum cost spanning tree of a given undirected graph using Kruskal’s algorithm

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



void main()
{
	int i, j, n, cost[10][10], mst[10][10] = {0}, total =0;
	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=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			scanf("%d", &cost[i][j]);
	}
	kruskal(cost,n,mst);
	printf("A MST for the given graph is\n");
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			if((j>i) && (mst[i][j] != 0))
			{
				printf("%d --> %d\n",i,j);
				total = total + mst[i][j];
			}
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;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                                                                               
Enter the cost matrix of the graph , with 999 for no edges                     
0 10 999 999                                                                    
10 0 20 999                                                                     
999 20 0 30                                                                     
999 999 30 0                                                                    


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





































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

#include<stdio.h>
#include<conio.h>
void insertq(int q[], int node, int *f, int *r)
{
	if((*f==-1)&&(*r==-1))
	{
		(*f)++;
		(*r)++;
		q[*f] = node;
	}
	else
	{
		(*r)++;
		q[*r] = node;
	}
}
int deleteq(int q[], int *f, int *r)
{
	int temp;
	temp = q[*f];
	if(*f==*r)
		*f = *r = -1;
	else
		(*f)++;
	return temp;
}
void bfs(int n, int adj[][10], int src, int visited[])
{
	int q[20], f = -1, r = -1, v, i;
	insertq(q, src, &f, &r);
	while((f<=r)&&(f!=-1))
	{
		v = deleteq(q, &f, &r);
		if(visited[v]!=1)
		{
			visited[v] = 1;
			printf("%d",v);
		}
		for(i=1;i<=n;i++)
			if((adj[v][i]==1)&&(visited[i]!=1))
				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=1;i<=n;i++)
	{
		visited[i] = 0;
		for(j=1;j<=n;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                                                                               
enter the adjancecy matrix of the digraph for bfs
0 0 1 1 0                                                                       
0 0 0 0 0                                                                       
0 1 0 0 0                                                                       
0 0 0 0 1                                                                       
0 0 0 0 0                                                                       
enter source vertex 1                                                           
the nodes reachable from src
1       3       4       2       5                                               
*/















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

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

void main()
{
	int n,i,j,adjm[10][10],src,visited[10]={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=1;i<=n;i++)
		for(j=1;j<=n;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=1;i<=n;i++)
		if(visited[i]!=1)
			flag=1; p=i;
		if(flag == 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                                                                               
Enter the adjecency matrix                                                      
0 0 1 1 0                                                                       
0 0 0 0 0                                                                       
0 1 0 0 0                                                                       
0 0 0 0 1                                                                       
0 0 0 0 0                                                                       
Enter source verix from where to start DFS                                      
1                                                                               
1 -- 3                                                                          
3 -- 2                                                                          
1 -- 4                                                                          
4 -- 5                                                                          
The graph is connected              */                                                
































8. Find a subset of a given set S={s1,s2…..sn} of n positive integers whose sum is equal to a
   given positive integer d. For eg. If S={1, 2, 5, 6, 8} and d=9 there are two solutions { 1, 2, 6 }
   and { 1, 8 }. A suitable message is to be displayed if the given problem instance doesn’t have 
   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] = 1;
	if(s+w[k]==d)
	{
		printf("\n Subset %d=",++count);
		for(i=0;i<=k;i++)
			if(x[i])
				printf("%d\t",w[i]);
	}
	else if(s+w[k]+w[k+1] <= d)
		sum_of_subset(s+w[k],k+1,r-w[k]);
		if((s+r-w[k]>=d) && (s,w[k+1])<=d)
		{
			x[k] = 0;
			sum_of_subset(s,k+1,r-w[k]);
		}
}

void main()
{
	int sum=0,k;
	clrscr();
	printf("Enter the number of elements\n");
	scanf("%d",&n);
	printf("Enter the elements in ascending order:\n");
	for(i=0;i<n;i++)
	{
		scanf("%d",&w[i]);
	}
	printf("Enter the sum:\n");
	scanf("%d",&d);
		
	for(i=0;i<n;i++)
		x[i]=0;
	for(i=0;i<n;i++)
		sum = 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                                                                               
Enter the elements in ascending order:                                          
1 3 5 7 9                                                                       
Enter the sum:
8

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







































9. Implement any scheme to find the optimal solution for the Traveling Salesperson problem
    and then solve the same problem instance using any approximation algorithm 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 = 999;
	if( start == n-2 )
	return c[tour[n-2]][tour[n-1]] + c[tour[n-1]][0];
	for( int i = 0 ; i < n ; i++ )
	{
		for( int j = 0 ; j < n ; j++ )
			temp[j] = tour[j];
			temp[start + 1] = tour[i];
			temp[i] = tour[start + 1];
			if( c[tour[start]][i] + ( cost = tspdp(c,start+1,temp,n) ) < min )
			{
				min = c[tour[start]][i] + cost;
				for( int j = 0 ; j < n ; j++ )
					mintour[j] = temp[j];
			}
	}
	for( int j = 0 ; j < n ; j++ )
	tour[j] = mintour[j];
	return min;
}

void main()
{
	int c[10][10],tour[10],cost;
	int i=0,j=0;
	clrscr();
	cout<<"\nEnter the no cities : ";
	int n;
	cin>>n;
	for(i=0;i<n;i++)
	{
		c[i][i] = 999;
		for(j=i+1;j<n;j++)
		{
			cout<<"\nEnter the cost(integer) from "<<i<<" to "<<j<<" : ";
			cin>>c[i][j];
		}
	}
	for(i=0;i<n;i++)
	{
		for(j=0;j<i;j++)
		{
			c[i][j] = c[j][i];
		}
	}
	cout<<"\nCost Adj Matrix is \n";
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			cout<<c[i][j]<<"\t";
		}
		cout<<endl;
	}
	for(i=0;i<n;i++)
	tour[i] = i;
	cost = tspdp(c,0,tour,n);
	cout<<"\nTour : ";
	for(i=0;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’s algorithm.

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

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

void main()
{
	int i,j,n,cost[10][10],mst[10][10] = {0}, total = 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=1;i<=n;i++)
		for(j=1;j<=n;j++)
		scanf("%d",&cost[i][j]);
	prim(cost,n,mst);
	printf("A MST for the given graph is\n");
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if((j>i)&&(mst[i][j] != 0))
			{
				printf("%d -- %d\n",i,j);
				total = total + mst[i][j];
			}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;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                                                                               
Enter the cost matrix of the graph, with 999 for no. edges                      
0 10 999 40                                                                     
10 0 20 999                                                                     
999 20 0 30                                                                     
40 999 30 0                                                                     
A MST for the given graph is                                                    
1 -- 2                                                                          
2 -- 3                                                                          
3 -- 4                                                                          
0       10      0       0                                                       
10      0       20      0                                                       
0       20      0       30                                                      
0       0       30      0                                                       
The total cost of this MST is 60                                                
*/



















11. 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>
int a[10][10],n;

void floyd()
 {
 	 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][k]+a[k][j])<a[i][j])
			        a[i][j]=a[i][k]+a[k][j];
	        			else
			        a[i][j] = a[i][j];
		 	}
	   	}
     	}
 }

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




12. Implement N Queen’s problem using Back Tracking.

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

int x[20] = {0};

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

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

void nqueens(int k, int n)
{
	int i, j;
	for(i=1;i<=n;i++)
	{
		if(place(k,i))
		{
			x[k] = i;
			if(k==n)
			{
				for(j=1;j<=n;j++)
					printf("%d",x[j]);
				printf("\n");
			}
			else 
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                                                                               
2413                                                                            
3142                                                                            
*/

^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: ADA Program
  2013-05-27 16:13 ADA Program TASLEEM ARIF
@ 2013-05-27 17:33 ` Dennis Lee Bieber
  2013-05-28  6:47   ` Georg Bauhaus
  2013-05-27 17:44 ` Shark8
  1 sibling, 1 reply; 10+ messages in thread
From: Dennis Lee Bieber @ 2013-05-27 17:33 UTC (permalink / raw)


On Mon, 27 May 2013 09:13:15 -0700 (PDT), TASLEEM ARIF
<tasleem139@gmail.com> declaimed the following in comp.lang.ada:

> 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.
> 
> #include<iostream.h>
> #include<conio.h>
> #include<dos.h>
> #include<stdlib.h>
> #include<time.h>
>

	ADA: Americans with Disabilities Act -- and this post seems to
reveal what the disability is...

	Looks like someone posted a whole course load of homework
assignments written in unindented C...

-- 
	Wulfraed                 Dennis Lee Bieber         AF6VN
        wlfraed@ix.netcom.com    HTTP://wlfraed.home.netcom.com/

^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: ADA Program
  2013-05-27 16:13 ADA Program TASLEEM ARIF
  2013-05-27 17:33 ` Dennis Lee Bieber
@ 2013-05-27 17:44 ` Shark8
  2013-05-27 19:56   ` Ludovic Brenta
  1 sibling, 1 reply; 10+ messages in thread
From: Shark8 @ 2013-05-27 17:44 UTC (permalink / raw)


Ohhh, we have the privilege of doing your homework now, do we?
And that's not Ada.

^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: ADA Program
  2013-05-27 17:44 ` Shark8
@ 2013-05-27 19:56   ` Ludovic Brenta
  0 siblings, 0 replies; 10+ messages in thread
From: Ludovic Brenta @ 2013-05-27 19:56 UTC (permalink / raw)


Shark8 writes:
> Ohhh, we have the privilege of doing your homework now, do we?
> And that's not Ada.

We don't know that.  They forgot to ask a question.

-- 
Ludovic Brenta.

^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: ADA Program
  2013-05-27 17:33 ` Dennis Lee Bieber
@ 2013-05-28  6:47   ` Georg Bauhaus
  2013-05-28 22:39     ` Dennis Lee Bieber
  0 siblings, 1 reply; 10+ messages in thread
From: Georg Bauhaus @ 2013-05-28  6:47 UTC (permalink / raw)


On 27.05.13 19:33, Dennis Lee Bieber wrote:
> Looks like someone posted a whole course load of homework
> assignments written in unindented C...

To be fair, it is written in system-specific, outdated C++
without putting much of the language to use.



^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: ADA Program
  2013-05-28  6:47   ` Georg Bauhaus
@ 2013-05-28 22:39     ` Dennis Lee Bieber
  0 siblings, 0 replies; 10+ messages in thread
From: Dennis Lee Bieber @ 2013-05-28 22:39 UTC (permalink / raw)


On Tue, 28 May 2013 08:47:58 +0200, Georg Bauhaus
<rm.dash-bauhaus@futureapps.de> declaimed the following in
comp.lang.ada:

> On 27.05.13 19:33, Dennis Lee Bieber wrote:
> > Looks like someone posted a whole course load of homework
> > assignments written in unindented C...
> 
> To be fair, it is written in system-specific, outdated C++
> without putting much of the language to use.

	Ah... Well, I'd just done a fairly rapid scroll over the message
looking anything Ada, or a question maybe concerning how one might
convert such to Ada...
-- 
	Wulfraed                 Dennis Lee Bieber         AF6VN
        wlfraed@ix.netcom.com    HTTP://wlfraed.home.netcom.com/

^ permalink raw reply	[flat|nested] 10+ messages in thread

* ADA program
@ 2022-12-12 20:21 Dirrm
  2022-12-13  9:49 ` AdaMagica
  2022-12-13 14:24 ` Jeffrey R.Carter
  0 siblings, 2 replies; 10+ messages in thread
From: Dirrm @ 2022-12-12 20:21 UTC (permalink / raw)


I need help on writing this code? any pointers on where to begin 
" go through a set of .txt and use them to develop a pattern of appearances of letters.  You will need to make every lowercase letter into its uppercase equivalent and count the letter appearances.  Using your results, you are to go through an encrypted file and try to decrypt it using letter substitution.  Then decrypt the same encrypted file using the standard table. You also have access to the original text. Output should go to a .txt file"

^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: ADA program
  2022-12-12 20:21 ADA program Dirrm
@ 2022-12-13  9:49 ` AdaMagica
  2022-12-13 14:24 ` Jeffrey R.Carter
  1 sibling, 0 replies; 10+ messages in thread
From: AdaMagica @ 2022-12-13  9:49 UTC (permalink / raw)


First step:
So you need for each letter a number how often it occurs on average in (say) English texts. How do you do this. (Suppose fullstops, commas, question marks etc are ignored.)

^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: ADA program
  2022-12-12 20:21 ADA program Dirrm
  2022-12-13  9:49 ` AdaMagica
@ 2022-12-13 14:24 ` Jeffrey R.Carter
  2022-12-13 15:15   ` viviane ghada
  1 sibling, 1 reply; 10+ messages in thread
From: Jeffrey R.Carter @ 2022-12-13 14:24 UTC (permalink / raw)


On 2022-12-12 21:21, Dirrm wrote:
> I need help on writing this code? any pointers on where to begin
> " go through a set of .txt and use them to develop a pattern of appearances of letters.  You will need to make every lowercase letter into its uppercase equivalent and count the letter appearances.  Using your results, you are to go through an encrypted file and try to decrypt it using letter substitution.  Then decrypt the same encrypted file using the standard table. You also have access to the original text. Output should go to a .txt file"

First you need to know how to read a text file. Familiarity with the standard 
library (http://www.ada-auth.org/standards/aarm12_w_tc1/html/AA-A.html) is helpful.

-- 
Jeff Carter
"Measure before making 'efficiency' changes."
Elements of Programming Style
202

^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: ADA program
  2022-12-13 14:24 ` Jeffrey R.Carter
@ 2022-12-13 15:15   ` viviane ghada
  0 siblings, 0 replies; 10+ messages in thread
From: viviane ghada @ 2022-12-13 15:15 UTC (permalink / raw)


On Tuesday, December 13, 2022 at 2:24:59 PM UTC, Jeffrey R.Carter wrote:
> On 2022-12-12 21:21, Dirrm wrote: 
> > I need help on writing this code? any pointers on where to begin 
> > " go through a set of .txt and use them to develop a pattern of appearances of letters. You will need to make every lowercase letter into its uppercase equivalent and count the letter appearances. Using your results, you are to go through an encrypted file and try to decrypt it using letter substitution. Then decrypt the same encrypted file using the standard table. You also have access to the original text. Output should go to a .txt file"
> First you need to know how to read a text file. Familiarity with the standard 
> library (http://www.ada-auth.org/standards/aarm12_w_tc1/html/AA-A.html) is helpful. 
> 
> -- 
> Jeff Carter 
> "Measure before making 'efficiency' changes." 
> Elements of Programming Style 
> 202

^ permalink raw reply	[flat|nested] 10+ messages in thread

end of thread, other threads:[~2022-12-13 15:15 UTC | newest]

Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-12-12 20:21 ADA program Dirrm
2022-12-13  9:49 ` AdaMagica
2022-12-13 14:24 ` Jeffrey R.Carter
2022-12-13 15:15   ` viviane ghada
  -- strict thread matches above, loose matches on Subject: below --
2013-05-27 16:13 ADA Program TASLEEM ARIF
2013-05-27 17:33 ` Dennis Lee Bieber
2013-05-28  6:47   ` Georg Bauhaus
2013-05-28 22:39     ` Dennis Lee Bieber
2013-05-27 17:44 ` Shark8
2013-05-27 19:56   ` Ludovic Brenta

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox