dijktras.......

#include<stdio.h>
int **cost,n,*parent,v,*s;
void dijk(int []);
int min(int []);
int main()
{
        int i,j;
        system("clear");
        printf("Enter no.of vertices in graph\n");
        scanf("%d",&n);
        cost=(int **)malloc(n*sizeof(int *));
        for(i=0;i<n;i++)
        cost[i]=(int *)malloc(n*sizeof(int));
        for(i=0;i<n;i++)
        {
                for(j=0;j<n;j++)
                {
                        printf("Enter distance between %d and %d\n",i+1,j+1);
                        scanf("%d",&cost[i][j]);
                }
        }
        int *dist=(int *)malloc(n*sizeof(int));
        s=(int *)malloc(n*sizeof(int));
        parent=(int *)malloc(n*sizeof(int));
        printf("Enter starting vertex\n");
        scanf("%d",&j);
        v=j-1;
        dijk(dist);
}
int min(int a[])
{
        int temp=10000,i,j;
        for(i=0;i<n;i++)
        {
                if(a[i]==0)
                continue;
                else if(a[i]<temp&&s[i]!=1)
                {
                        temp=a[i];
                        j=i;
                }
        }
        return j;
}

void dijk(int dist[])
{
        int i,num,j;
        for(i=0;i<n;i++)
        {
                s[i]=0;
                dist[i]=cost[v][i];
                if(dist[i]!=1000)
                parent[i]=v+1;
                else
                parent[i]=1000;
        }
        int ver;
        s[v]=1;
        dist[v]=0;
        for(num=2;num<=n;num++)
        {
                ver=min(dist);
                s[ver]=1;
                for(i=0;i<n;i++)
                {
                        if(s[i]==0&&(dist[i]>(dist[ver]+cost[ver][i])))
                        {
                                dist[i]=dist[ver]+cost[ver][i];
                                parent[i]=ver+1;
                        }
                }
        }
        printf("Paths\n");
        printf("PATH\tCOST\n");
        for(i=0;i<n;i++)
        {
                if(parent[i]==v+1)
                printf("%d\t%d\n",parent[i],dist[i]);
                else if(parent[i]!=1000)
                {
                        printf("%d ",parent[i]);
                        j=parent[i]-1;
                        while(parent[j]!=v+1)
                        {
                                printf("<- %d ",parent[i]);
                                j=parent[j]-1;
                        }
                        printf("<- %d\t%d\n",parent[i],dist[i]);
                }
                else
                printf("%d node cannot be reachedi\n",i+1);
        }
}

lcs

#include<stdio.h>
#include<string.h>
char **b;
void print(char *x,int m,int n)
{
        if(m==0||n==0)
        return;
        if(b[m][n]=='!')
        {
                print(x,m-1,n-1);
                printf("%c",x[m-1]);
        }
        else if(b[m][n]=='@')
        print(x,m-1,n);
        else
        print(x,m,n-1);
}
void lcs(char *x,char *y)
{
        int m,n,**c,i,j;
        m=strlen(x);
        n=strlen(y);
        c=(int **)malloc((m+1)*sizeof(int *));
        for(i=0;i<m+1;i++)
        c[i]=(int *)malloc((n+1)*sizeof(int));
        b=(char **)malloc((m+1)*sizeof(char *));
        for(i=0;i<m+1;i++)
        b[i]=(char *)malloc((n+1)*sizeof(char));
        for(i=0;i<m;i++)
        {
                c[i][0]=0;
                b[i][0]=0;
        }
        for(i=0;i<n;i++)
        {
                c[0][i]=0;
                b[0][i]=0;
        }
        for(i=0;i<m;i++)
        {
                for(j=0;j<n;j++)
                {
                        if(x[i]==y[j])
                        {
                                c[i+1][j+1]=c[i][j]+1;
                                b[i+1][j+1]='!';
                        }
                        else if(c[i][j+1]>=c[i+1][j])
                        {
                                c[i+1][j+1]=c[i][j+1];
                                b[i+1][j+1]='@';
                        }
                        else
                        {
                                c[i+1][j+1]=c[i+1][j];
                                b[i+1][j+1]='#';
                        }
                }
        }
        printf("\nLength of LCS=%d\nSubsequence is\n",c[m][n]);
        print(x,m,n);
        printf("\n");
}

int main()
{
        int i,j;
        char x[50],y[50];
        system("clear");
        printf("Enter first sequence\n");
        scanf("%s",&x);
        printf("Enter second sequence\n");
        scanf("%s",&y);
        lcs(x,y);
}

nqueens

#include<stdio.h>
#include<math.h>
int x[10],c=0;
void nqueens(int,int);
int place(int,int);
main()
{
int n,i;
printf("enter the no of qeens on the board");
scanf("%d",&n);
nqueens(1,n);
printf("%d",c);
}
void nqueens(int k,int n)
{
int i;
        for(i=1;i<=n;i++)
        {
                if(place(k,i))
                {
                x[k]=i;
                if(k==n)
                {
                        c++;
                for(i=1;i<=n;i++)
                printf("%d",x[i]);
                printf("\n");
                }
                else
                nqueens(k+1,n);
                }
        }
}
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;
}

prims

#include<stdio.h>
int **cost,n,**t,v,*s;
int find(int *);
int prim(int *);
int main()
{
        int i,j,temp;
        printf("Enter no.of vertices in graph\n");
        scanf("%d",&n);
        cost=(int **)malloc(n*sizeof(int *));
        for(i=0;i<n;i++)
        cost[i]=(int *)malloc(n*sizeof(int));
        printf("Enter distances\n");
        for(i=0;i<n;i++)
        {
                for(j=0;j<n;j++)
                {
                        if(i==j)
                        cost[i][j]=1000;
                        else
                        cost[i][j]=10000;
                }
        }
        for(i=0;i<n;i++)
        {
                for(j=0;j<n;j++)
                {
                        if(cost[i][j]==10000)
                        {
                                scanf("%d",&temp);
                                cost[j][i]=temp;
                                cost[i][j]=temp;
                        }
                }
        }
        int *near=(int *)malloc(n*sizeof(int *));
        t=(int **)malloc(n*sizeof(int *));
        for(i=0;i<n;i++)
        t[i]=(int *)malloc(2*sizeof(int));
        printf("\nMinimum cost=%d\n",prim(near));
        for(i=0;i<n;i++)
        printf("%d      %d\n",t[i][0]+1,t[i][1]+1);
}
int find(int *near)
{
        int i,min=10000,j;
        for(i=0;i<n;i++)
        {
                if(near[i]!=-1&&(cost[i][near[i]]<min))
                {
                        j=i;
                        min=cost[i][near[i]];
                }
        }
        return j;
}
int prim(int *near)
{
        int mincost=0,j,k,i;
        for(i=1;i<n;i++)
        near[i]=0;
        near[0]=-1;
        for(i=1;i<n;i++)
        {
                j=find(near);
                t[i][0]=j;
                t[i][1]=near[j];
                mincost+=cost[j][near[j]];
                near[j]=-1;
                for(k=1;k<n;k++)
                {
                        if(near[k]!=-1&&(cost[k][near[k]]>cost[k][j]))
                        near[k]=j;
                }
        }
        return mincost;
}

quick sort

#include<stdio.h>
void quicksort(int *a,int left,int right)
{
        if(left<right)
        {
        int pivot,t,i,j;
        pivot=left;
        i=left;
        j=right;
        while(i<j)
        {
                while(a[i]<=a[pivot]&&i<right)
                i++;
                while(a[j]>a[pivot])
                j--;
                if(i<j)
                {
                        t=a[i];
                        a[i]=a[j];
                        a[j]=t;
                }
        }
        t=a[j];
        a[j]=a[pivot];
        a[pivot]=t;
        quicksort(a,left,j-1);
        quicksort(a,j+1,right);
        }
}
int main()
{
        int *a,n,i;
        printf("Enter no.of elements\n");
        scanf("%d",&n);
        a=(int *)malloc(n*sizeof(int));
        printf("Enter elements");
        for(i=0;i<n;i++)
        scanf("%d",&a[i]);
        quicksort(a,0,n-1);
        printf("After sorting\n");
        for(i=0;i<n;i++)
        printf("%d  ",a[i]);
}