N-Queen Problem

   Implement N Queen’s problem using Back Tracking


#include<stdio.h>
#include<stdlib.h>
int place(int);

int X[10];

void main()
{
   int i,j,n,k,count=0;
   printf("\n\n*************N-QUEEN PROBLEM***************\n\n");
   printf("Enter the number of elements:");
   scanf("%d",&n);
   if(n==0||n==2||n==3)
    {
        printf("\n\n No solution\n");
        printf("\n\n********** ************ **********\n\n");
        exit(0);
    }
   k=1;
   X[k]=0;
   while(k)
   {
       X[k]=X[k]+1;
       while(X[k]<=n&&!place(k))
             X[k]=X[k]+1;
       if(X[k]<=n)
         {
             if(k==n)
              {
                 printf("\nSolution %d\n\n",++count);
                 for(i=1;i<=n;i++)
                    {
                       for(j=1;j<X[i];j++)
                            printf("*\t");
                       printf("Q\t");
                       for(j=X[i]+1;j<=n;j++)
                              printf("*\t");
                            printf("\n");
                    }
              }
              else
              {
                   k=k+1;
                   X[k]=0;
              }
         }
         else
                 k=k-1;
     }
     printf("\n\n******** ********* *********\n\n");
} 
int place(int p)
{
    int i;
    for(i=1;i<=p-1;i++)
     {
       if(X[i]==X[p]||abs(i-p)==abs(X[i]-X[p]))
         return 0;
     }
     return 1;
}







OUTPUT:

Enter the number of elements:4

Solution 1
*    Q    *    *
*    *    *    Q
Q    *    *    *
*    *    Q    *

Solution 2
*    *    Q    *
Q    *    *    *
*    *    *    Q
*    Q    *    *

******* ******** ***********

Read More

Floyd's Parallelized Algorithm

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>
#include<stdlib.h>
#include<omp.h>
#include<time.h>
void floyd();
int min(int,int);
int i,j,n,k,a[8][8];
clock_t start,end;
void main()
{
  printf("\n\n*********FLOYD'S PARALLELIZED ALGORITHM*********\n\n");
  printf("Enter the number of vertices:");
  scanf("%d",&n);
  printf("\n\nEnter the adjacency matrix\n");
  for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
          scanf("%d",&a[i][j]);
  printf("\n\nEntered adjacency matrix is:\n");
  for(i=1;i<=n;i++)
  {
      for(j=1;j<=n;j++)
      {
          printf("%d\t",a[i][j]);
      }
      printf("\n");
  }
  start=clock();
  floyd(a,n);
  end=clock();
  printf("\nAll pair shortest path matrix:\n");
  for(i=1;i<=n;i++)
  {
    for(j=1;j<=n;j++)
          printf("%2d",a[i][j]);
    printf("\n");
  }
  printf("\n\nTime taken to execute is %f\n",(double)(end-start)/CLOCKS_PER_SEC);
  printf("\n*****************************************************************");
}
void floyd()
{
 //omp_set_num_threads(4);
  #pragma omp parallel for private(i,j,k)
      for(k=1;k<=n;k++)
       {
        for(i=1;i<=n;i++)
          for(j=1;j<=n;j++)
               a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
       }
 }
 int min(int a, int b)
{
  if(a>b)
       return b;
   else
       return a;
}



OUTPUT:
Enter the number of vertices:4

Enter the adjacency matrix
0  1  8  5  1  0  2  999  8  2  0  3  5  999  3  0

Entered adjacency matrix is:
0      1        8      5
1      0        2      999
8      2        0      3
5      999    3     0

All pair shortest path matrix :
0    1    3    5
1    0    2    5
3    2    0    3
5    5    3    0

Time taken to execute is 0.000104

*********** ************ **************

Read More

Prims Algorithm

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

#include<stdio.h>

void prims();

int nearV[10],cost[10][10],t[10][2],i,j,n,k,min,u,mincost=0;

void main()
{
  printf("\n\n**********PRIMS ALGORITHM***********\n\n");
  printf("Enter the number of nodes\n");
  scanf("%d",&n);
  printf("\n\nEnter the cost matrix\n");
  for(i=1;i<=n;i++)
    {
       for(j=1;j<=n;j++)
         {
             scanf("%d",&cost[i][j]);
         }
    }
  printf("\n\n The entered 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("\n\nMinimum spanning tree edges and their cost are\n");
prims();
printf("\n\nThe minimum spanning tree cost is %d",mincost);
printf("\n\n********* *********** ***********");
}

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);
   }
}


OUTPUT:

Enter the number of nodes
3

Enter the cost matrix
0  2  3  2  0  1  3  1  0

Read More

TSP Dynamic Programming

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<stdio.h>
#include<stdlib.h>

int tspdp(int c[10][10], int tour[10], int start, int n);

void main()
{
  int i,j,n,cost,c[10][10], tour[10];
  printf("\n\n*************TSP DYNAMIC PROGRAMMING************\n\n");
  printf("\n\n Enter the number of cities:");
  scanf("%d",&n);
  if(n==1)
  {
        printf("\n Path is not possible\n\n");
        exit(0);
  }
  printf("\n\n Enter the cost matrix\n");
  for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        scanf("%d",&c[i][j]);
  printf("\n\n The entered cost matrix is\n");
  for(i=1;i<=n;i++)
  {
   for(j=1;j<=n;j++)
    {
      printf("%d\t",c[i][j]);
    }
    printf("\n");
  }
  for(i=1;i<=n;i++)
       tour[i]=i;
  cost=tspdp(c,tour,1,n);
  printf("\n\n The accurate path is \n");
  for(i=1;i<=n;i++)
      printf("%d->",tour[i]);
  printf("1");
  printf("\n\nThe accurate mincost is %d",cost);
  printf("\n\n************ **************** ********** ");
}

int tspdp(int c[10][10], int tour[10], int start, int n)
 {
   int mintour[10],temp[10],mincost=999,ccost,i,j,k;
   if(start==n-1)
    {
      return(c[tour[n-1]][tour[n]]+c[tour[n]][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]=tour[start+1];
      if((c[tour[start]][tour[i]]+(ccost=tspdp(c,temp,start+1,n)))<mincost)
       {
          mincost=c[tour[start]][tour[i]]+ccost;
          for(k=1;k<=n;k++)
             mintour[k]=temp[k];
       }
 }
for(i=1;i<=n;i++)
   tour[i]=mintour[i];
return mincost;
}



OUTPUT:

Enter the number of cities:4

Enter the cost matrix
0  1  3  6  1  0  2  3  3  2  0  1  6  3  1  0
    

Read More

TSP Approximation Algorithm

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<stdio.h>

void tspapp(int v);

int visited[10],city,cost[10][10],count,mincost,i,j;

void main()
{
  printf("\n\n******TSP APPROXIMATION PROBLEM**\n\n");
  printf("Enter the number of cities:");
  scanf("%d",&city);
  printf("\n\nEnter the cost matrix\n\n");
  for(i=1;i<=city;i++)
   {
      for(j=1;j<=city;j++)
       {
          scanf("%d",&cost[i][j]);
       }
   }
  printf("\n\n The entered cost matrix is \n");
  for(i=1;i<=city;i++)
   {
      for(j=1;j<=city;j++)
       {
          printf("%d\t",cost[i][j]);
       }
       printf("\n");
   }
  printf("\n\n The approximate path is \n");
  tspapp(1);
  printf("\n\n************* **************** ************\n");
}

void tspapp(int v)
{
  int k,min;
  visited[v]=1;
  printf("%d->",v);
  if(count==city-1)
   {
     mincost=mincost+cost[v][1];
     printf("1");
     printf("\n\nApproximate Mincost is %d",mincost);
     return;
   }
  min=999;
  for(j=1;j<=city;j++)
   {
     if(cost[v][j]<min&&cost[v][j]!=0&&!visited[j])
      {
         min=cost[v][j];
         k=j;
      }
   }
  mincost=mincost+cost[v][k];
  count++;
  tspapp(k);
}



OUTPUT:

Enter the number of cities:4

Enter the cost matrix
0  1  3  6  1  0  2  3  3  2  0  1  6  3  1  0

Read More

Subset Problem

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 example, 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>
#include<stdlib.h>

void subset(int, int, int);

int w[10],n,d,i,cs,r,x[10],sum=0,k,c;

void main()
{
  printf("\n\n************SUBSET PROBLEM*********\n\n");
  printf("Enter the number of elements:");
  scanf("%d",&n);
  printf("\n\n Enter the elements in increasing order:");
  for(i=0;i<n;i++)
      scanf("%d",&w[i]);
  printf("\n\nEnter the value of d:");
  scanf("%d",&d);
  for(i=0;i<n;i++)
        sum=sum+w[i];
  printf("\n\nSUM=%d",sum);
  if(sum<d||w[0]>d)
  {
     printf("\n\n Subset is not posssible!");
     printf("\n\n*************** *********** **************\n\n");
     exit(0);
  }
  subset(0,0,sum);
  if(c==0)
      printf("\n\nSubset is not possible !");
  printf("\n\n********* ************ ************\n\n");
}
void subset(int cs, int k, int r)
 {
      x[k]=1;
      if(cs+w[k]==d)
       {
         printf("\n\n Solutiion %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]);
        }
 }



OUTPUT:

Enter the number of elements:5

Enter the elements in increasing order:  1  2  3  6  8

Enter the value of d:9

Read More

DFS

7. Check whether a given graph is connected or not using DFS method.

#include<stdio.h>
void dfs(int);
int visited[10],adj[10][10],n,count;
void main()
{
 int i,j;
 printf("\n\n********DFS METHOD***********\n\n");
 printf("Enter the mumber of nodes:");
 scanf("%d",&n);
 printf("\n\nEnter the adjacency matrix\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++)
            visited[j]=0;
    dfs(i);
    if(count==n)
     {
       printf("\nGraph is connected");
       printf("\n\n******************");
       getch();
       exit(0);
     }
  }
 printf("\nGraph is not connected");
 printf("\n\n****************");
}
void dfs(int i)
{
  int w;
  count++;
  visited[i]=1;
  for(w=1;w<=n;w++)
   {
     if(adj[i][w]==1 && visited[w]==0)
           dfs(w);
   }
}



OUTPUT:

Enter the number of nodes:4

Enter the adjacency matrix
0  1  1  0  0  0  1  0  0  0  0  1  0  0  0  0




Enter the number of nodes:4

Enter the adjacency matrix
0  1  1  0  0  0  1  0  0  0  0  0  0  0  0  0

Read More