vtu ada lab programs 1

#include<stdio.h>
#include<conio.h>
#define infinity 999
void dij(int n,int v,int cost[10][10],int dist[])
{
 int i,u,count,w,flag[10],min;
  for(i=1;i<=n;i++)
  flag[i]=0,dist[i]=cost[v][i];
 count=2;
 while(count<=n)
 {
  min=99;
  for(w=1;w<=n;w++)
   if(dist[w]<min && !flag[w])
    min=dist[w],u=w;
    flag[u]=1;
    count++;
  for(w=1;w<=n;w++)
   if((dist[u]+cost[u][w]<dist[w]) && !flag[w])
    dist[w]=dist[u]+cost[u][w];
 }
}
void main()
{
 int n,v,i,j,cost[10][10],dist[10];
 clrscr();
 printf("\n Enter the number of nodes:");
 scanf("%d",&n);
 printf("\n Enter the cost matrix:\n");
 for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
   {
    scanf("%d",&cost[i][j]);
    if(cost[i][j]==0)
     cost[i][j]=infinity;
   }
 printf("\n Enter the source matrix:");
 scanf("%d",&v);
 dij(n,v,cost,dist);
 printf("\n Shortest path:\n");
 for(i=1;i<=n;i++)
  if(i!=v)
   printf("%d->%d,cost=%d\n",v,i,dist[i]);
 getch();
}

#include<stdio.h>
#include<conio.h>
#define MAX 20
int root[MAX],n=0;
struct edge
{
 int u,v,w;
};
int finds(int x)
{
 return(root[x]);
}
void unions(int x,int y)
{
 int i;
 if(x<y)
 {
  for(i=1;i<=n;i++)
   if(root[i]==y)
    root[i]=x;
 }
 else
 {
  for(i=1;i<=n;i++)
   if(root[i]==x)
    root[i]=y;
 }
}
void main()
{
 int ed=0,i,j,k=0,a,b,weight=0;
 struct edge e[MAX],temp;
 clrscr();
 printf("\n Enter the number of vertices:");
 scanf("%d",&n);
 for(i=1;i<=n;i++)
  root[i]=i;
 printf("\n Enter the number of edges:");
 scanf("%d",&ed);
 for(i=1;i<=ed;i++)
 {
  printf("\n Enter the end vertices & cost of edge %d:",i);
  scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
 }
 for(i=1;i<=ed;i++)
 for(j=1;j<=ed;j++)
 if(e[j].w>e[j+1].w)
 {
  temp=e[j];
  e[j]=e[j+1];
  e[j+1]=temp;
 }
 printf("\n The weights in ascending order are:\n");
 for(i=1;i<=ed;i++)
  printf("%d \t",e[i].w);
   printf("\n");
 i=1;
 while(ed && k!=n-1)
 {
  a=finds(e[i].u);
  b=finds(e[i].v);
  if(a!=b)
  {
   printf("<%d,%d>",e[i].u,e[i].v);
   unions(a,b);
   weight+=e[i].w;
   k++;
  }
  ed--;
  i++;
 }
 if(k<n-1)
  printf("\n No network exists");
 else
  printf("\n Network exists \n The weight of tree is %d",weight);
 getch();
}

#include<stdio.h>
#include<conio.h>
#define TRUE 1
#define FALSE 0
int inc[50],w[50],sum,n;
int promising(int i,int wt,int total)
{
 return(((wt+total)>=sum)&&((wt==sum)||(wt+w[i+1]<=sum)));
}
void sumset(int i,int wt,int total)
{
 int j;
 if(promising(i,wt,total))
 {
  if(wt==sum)
  {
   printf("\n{\t");
   for(j=0;j<=i;j++)
    if(inc[j])
     printf("%d\t",w[j]);
      printf("}\n");
  }
  else
  {
   inc[i+1]=TRUE;
   sumset(i+1,wt+w[i+1],total-w[i+1]);
   inc[i+1]=FALSE;
   sumset(i+1,wt,total-w[i+1]);
  }
 }
}
void main()
{
 int i,j,n,temp,total=0;
 clrscr();
 printf("\n Enter how many numbers:");
 scanf("%d",&n);
 printf("\n Enter %d numbers:",n);
 for(i=0;i<n;i++)
 {
  scanf("%d",&w[i]);
  total+=w[i];
 }
 printf("\n Input the sum value:");
 scanf("%d",&sum);
 for(i=0;i<=n;i++)
  for(j=0;j<n-1;j++)
   if(w[j]>w[j+1])
   {
    temp=w[j];
    w[j]=w[j+1];
    w[j+1]=temp;
   }
 printf("\n The given %d numbers in ascending order:\n",n);
 for(i=0;i<n;i++)
  printf("%d \t",w[i]);
 if((total<sum))
   printf("\n Subset construction is not possible");
  else
 {
  for(i=0;i<n;i++)
   inc[i]=0;
  printf("\n The solution using backtracking is:\n");
  sumset(-1,0,total);
  }
 getch();
}

#include<stdio.h>
#include<string.h>
#include<conio.h>
#define MAX 500
int t[MAX];
void shifttable(char p[])
{
 int i,j,m;
 m=strlen(p);
 for(i=0;i<MAX;i++)
  t[i]=m;
 for(j=0;j<m-1;j++)
  t[p[j]]=m-1-j;
}
int horspool(char src[],char p[])
{
 int i,j,k,m,n;
 n=strlen(src);
 m=strlen(p);
 printf("\nLength of text=%d",n);
 printf("\n Length of pattern=%d",m);
 i=m-1;
 while(i<n)
 {
  k=0;
  while((k<m)&&(p[m-1-k]==src[i-k]))
   k++;
  if(k==m)
   return(i-m+1);
  else
   i+=t[src[i]];
 }
 return -1;
}
void main()
{
 char src[100],p[100];
 int pos;
 clrscr();
 printf("Enter the text in which pattern is to be searched:\n");
 gets(src);
 printf("Enter the pattern to be searched:\n");
 gets(p);
 shifttable(p);
 pos=horspool(src,p);
 if(pos>=0)
  printf("\n The desired pattern was found starting from position %d",pos+1);
 else
  printf("\n The pattern was not found in the given text\n");
 getch();
}

#include<stdio.h>
#include<conio.h>
void main()
{
 int i,j,n,k,min,c[20][20]={0};
 clrscr();
 printf("\n Enter the value of n:");
 scanf("%d",&n);
 printf("\n Enter the value of k:");
 scanf("%d",&k);
 if(n>=k)
 {
  for(i=0;i<=n;i++)
  {
   min=(i<k)?i:k;
   for(j=0;j<=min;j++)
    if(j==k || j==0)
     c[i][j]=1;
    else
     c[i][j]=c[i-1][j-1]+c[i-1][j];
  }
  for(i=0;i<=n;i++)
  {
   for(j=0;j<=n;j++)
   {
    if(i>=j)
     printf("%d\t",c[i][j]);
   }
   printf("\n");
  }
 }
 else
  printf("\n Invalid input \n Enter value n>=k \n");
 getch();
}

#include<stdio.h>
#include<conio.h>
int a,b,u,v,n,i,j,ne=1;
int visited[10]={0},min,mincost=0,cost[10][10];
void main()
{
 clrscr();
 printf("\n Enter the number of nodes:");
 scanf("%d",&n);
 printf("\n Enter the adjacency matrix:\n");
 for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
  {
   scanf("%d",&cost[i][j]);
   if(cost[i][j]==0)
    cost[i][j]=999;
  }
  visited[1]=1;
  printf("\n");
  while(ne<n)
  {
   for(i=1,min=999;i<=n;i++)
    for(j=1;j<=n;j++)
     if(cost[i][j]<min)
      if(visited[i]!=0)
      {
       min=cost[i][j];
       a=u=i;
       b=v=j;
      }
      if(visited[u]==0 || visited[v]==0)
      {
       printf("\n Edge %d:(%d %d) cost:%d",ne++,a,b,min);
       mincost+=min;
       visited[b]=1;
      }
     cost[a][b]=cost[b][a]=999;
   }
  printf("\n Minimun cost=%d",mincost);
 getch();
}

#include<stdio.h>
#include<conio.h>
#include<math.h>
int max(int,int);
void warshal(int p[10][10],int n)
{
 int i,j,k;
 for(k=1;k<=n;k++)
  for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
    p[i][j]=max(p[i][j],p[i][k]&&p[k][j]);
}
int max(int a,int b)
{                                                       ;
 if(a>b)
  return(a);
 else
  return(b);
}
void main()
{
 int p[10][10]={0},n,e,u,v,i,j;
 clrscr();
 printf("\n Enter the number of vertices:");
 scanf("%d",&n);
 printf("\n Enter the number of edges:");
 scanf("%d",&e);
 for(i=1;i<=e;i++)
 {
  printf("\n Enter the end vertices of edge %d:",i);
  scanf("%d%d",&u,&v);
  p[u][v]=1;
 }
 printf("\n Matrix of input data: \n");
 for(i=1;i<=n;i++)
 {
  for(j=1;j<=n;j++)
   printf("%d\t",p[i][j]);
   printf("\n");
 }
 warshal(p,n);
 printf("\n Transitive closure: \n");
 for(i=1;i<=n;i++)
 {
  for(j=1;j<=n;j++)
   printf("%d\t",p[i][j]);
   printf("\n");
 }
 getch();
}

#include <stdio.h>
#define N 10



void bfs(int adj[][N],int visited[],int start)

{

        int q[N],rear=-1,front=-1,i;

        q[++rear]=start;

        visited[start]=1;

        while(rear != front)

        {

               start = q[++front];

                if(start==9)

                        printf("10\t");

                else

                        printf("%c \t",start+49);



                for(i=0;i<N;i++)

                {

                        if(adj[start][i] && !visited[i])

                        {

                                q[++rear]=i;

                                visited[i]=1;

                        }

                }

        }
int main()

{

        int visited[N]={0};

        int adj[N][N]={{0,1,1,0,0,0,0,0

        {0,0,0,0,1,0,0,0,0,1},

        {0,0,0,0,1,0,1,0,0,0},

        {1,0,1,0,0,1,1,0,0,1},

        {0,0,0,0,0,0,1,1,0,0},

        {0,0,0,1,0,0,0,1,0,0},

        {0,0,0,0,0,0,0,1,1,1},

        {0,0,1,0,0,0,0,0,0,0},

        {0,0,0,1,0,0,0,0,0,0},

        {0,0,1,0,0,0,0,1,1,0}};


        bfs(adj,visited,0);
       return 0;
}

#include<stdio.h>
#include<stdlib.h>

void dfs(int n,int cost[10][10],int u,int t[10][10],int s[10])
{int v,k=0;
 s[v]=1;
 for(v=0;v<n;v++)
 {
 if(cost[u][v]==1&&s[v]==0)
 {
  t[k][0]=u;
  t[k][1]=v;
  k++;
  dfs(n,cost,v,t,s);
 }
 }
}
 int main()
{
 int n,i,j,source,cost[10][10],s[10],t[10][10];
 printf("\nEnter the no. of nodes:");
 scanf("%d",&n);
 printf("Enter the cost adjacency matrix:\n");
 for(i=0;i<n;i++)
 {
  for(j=0;j<n;j++)
  scanf("%d",&cost[i][j]);
 }
 printf("\nenter the source:");
 scanf("%d",&source);
  for(i=0;i<n;i++)
   s[i]=0;
   dfs(n,cost,source,t,s);
   for(i=0;i<n;i++)
  {
   if(s[i]==1)
   printf("%d is reachable",i);
  else
   printf("%d is not reachble\n",i);
  return 0;
 }
}

#include<stdio.h>
struct floyd
{
        int n,cost[10][10],d[10][10];
};

typedef struct floyd Floyd;

int min(int a,int b)
{
        return a<b? a:b;
}

void writeData(Floyd *f)
{
        int i,j;

        printf("Distance matrix:\n");

        for(i=0;i< f->n;i++)
        {

                for(j=0;j< f->n;j++)
                {

                        printf("%d\t",f->d[i][j]);
                }

                printf("\n");
        }
}

void readData(Floyd *f)
{

        int i,j;

        printf("Enter number of nodes:\n");
                scanf("%d",&f->n);

        printf("Enter cost adjacency matrix\n");

        for(i=0;i<f->n;i++)
        {
                for(j=0;j<f->n;j++)
                {
                        scanf("%d",&f->cost[i][j]);
                }
        }
}

void dist(Floyd *f)
{

        int i,j,k;

        for(i=0;i<f->n;i++)
                for(j=0;j<f->n;j++)
                        f->d[i][j]=f->cost[i][j];

        for(k=0;k<f->n;k++)
        {
                for(i=0;i<f->n;i++)
                {
                        for(j=0;j<f->n;j++)
                        f->d[i][j]=min(f->d[i][j],f->d[i][k]+f->d[k][j]);
                }

                #ifdef DEBUG
                        writeData(f);
                #endif
        }


}

int main()
{
        Floyd f;

        readData(&f);
        dist(&f);
        writeData(&f);

        return 0;
}

#include<stdio.h>
int main()
{
        int i,j,k,n,a[10][10],indeg[10],flag[10],count=0;
        printf("enter the no of vertices");
        scanf("%d",&n);
        printf("enter the adjacency matrix");
        for(i=0;i<n;i++)
                {
                for(j=0;j<n;j++)
                        {
                        scanf("%d",&a[i][j]);
                        }
                }
        for(i=0;i<n;i++)
                {
                indeg[i]=0;
                flag[i]=0;
                }
        for(i=0;i<n;i++)
                {
                for(j=0;j<n;j++)
                {
                indeg[i]=indeg[i]+a[j][i];
                }

               }
        printf("the topological order is\n");
        while(count<n)
        {
                for(k=0;k<n;k++)
                {
                        if(indeg[k]==0 && (flag[k]==0))
                        {
                        printf("%d\t",k+1);
                        flag[k]=1;
                        }
                for(i=0;i<n;i++)
                {
                        if(a[i][k]==1)
                        indeg[k]--;
                }
        }
        count++;
        }
        return 0;
}

#include<stdio.h>
#include<stdlib.h>

int n,capacity,w[50],p[50],m,i,j;

int maximum(int a,int b)
{
        return a > b ? a:b;
}
int knapsack(int i,int j)
{
        if(i<=n)
        {
                if(j < w[i])
                        return p[i];


        if(j < w[i])
                return knapsack(i+1,j);
        else
                return maximum(knapsack((i+1),j),knapsack(i+1,(j-w[i] + p[i])));

        }

}

int main()
{
        printf("enter no. of objects:");
                scanf("%d",&n);

        printf("enter weight:");
        for(i=0;i<n;i++)
        {
                scanf("%d",&w[i]);

        }

        printf("enter profits:");
        for(i=0;i<n;i++)
        {
                scanf("%d",&p[i]);
        }

        printf("enter capacity:");
                scanf("%d",&capacity);

        m=knapsack(0,capacity);

        printf("profit=%d",m);

        return 0;
}