Wednesday, November 24, 2010

DAA algorithms


Sr.
No.
INDEX
  
    NAME OF PROGRAM

DATE

REMARK

1.
Write a program to Implement Insertion Sort



 2.
 Write a program to Implemen Merge Sort



 3.
Write a program to implement Heap Sort



 4.
 Write a program to implement Bucket Sort



 5.
Write a program to implement Radix Sort



 6.
Write a program to implement Rabin Karp string matching algorithm



 7.
Write a program to implement counting Sort algo



 8.
Write a program to implement quick sort




 9.
Write a program to implement N Queen’s Problem.



10.
Writa a program to implement Brute Force String machine algorithm



                                                                          Faculty’s Signature
1.WAP to implement Insertion  sort.
#include<stdio.h> 
 #include<conio.h>  
void insertion(int a[],int n)  
   {  
  int i,j,x,k
;  
     for(i=1;i<=n-1;i++)  
        {  
             j=i;  
             x=a[i];  
     while(a[j-1]>x && j>0)  
          {  
                 a[j]=a[j-1];  
                  j=j-1; 
          }  
             a[j]=x; 
         printf("\n\n The array after pass no.%d: ",i);  
          for(k=0;k<=n-1;k++)  
                  printf("%4d",a[k]);  
       }  
  }
  void main()  
    {  
       int a[1000],n,i;  
       clrscr();  
     printf("\n\nEnter an integer value for total no.s of elements to be sorted: ");  
     scanf("%3d",&n);  
  
for(i=0;i<=n-1;i++)  
     {  
         printf("\n\nEnter an integer value for element no.%d: ",i+1);  
            scanf("%4d",&a[i]);  
   }  
    insertion(a,n);    
     printf("\n\n\nFinally sorted array is : ");  
        for(i=0;i<=n-1;i++)  
          printf("%4d",a[i]);  
}














2.WAP to implement Merge sort.
#include<stdio.h>
void getdata(int arr[],int n)
{
   int i;
   printf("enter the data:");
     for(i=0;i<n;i+
+)
      {
         scanf("%d",&arr[i]);
      }
   }
void display(int arr[],int n)
{
 int i;
 printf("");
 for(i=0;i<n;i++)
    {
     printf("%d ",arr[i]);
    }
 getchar();
}
void sort(int arr[],int low,int mid,int high)
{
 int i,j,k,l,b[20];
 l=low;
 i=low;
 j=mid+1;
while((l<=mid)&&(j<=high))
   {
    if(arr[l]<=arr[j])
      {
       b[i]=arr[l];
       l++;
      }
    else
      {
       b[i]=arr[j];
       j++;
      }
    i++;
   }
 if(l>mid)
   {
    for(k=j;k<=high;k++)
       {
        b[i]=arr[k];
        i++;
       }
   }
 else
   {
    for(k=l;k<=mid;k++)
       {
        b[i]=arr[k];
        i++;
       }
   }
 for(k=low;k<=high;k++)
    {
     arr[k]=b[k];
    }
}

void partition(int arr[],int low,int high)
{
 int mid;
 if(low<high)
   {
    mid=(low+high)/2;
    partition(arr,low,mid);
    partition(arr,mid+1,high);
    sort(arr,low,mid,high);
   }
}
void main()
{
 int arr[20];
 int n;
 printf("Enter number of data:");
 scanf("%d",&n);
 getdata(arr,n);
 partition(arr,0,n-1);
 display(arr,n);
 getchar();
}




















3. WAP to implement Heap Sort.
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
void main()
{
 int *x,i,n;
 int temp;
  void heap(int *,int);
     clrscr();
     fflush(stdin);
    printf("Heap Sort");
    printf("Enter How many Numbers : ");
       scanf("%d",&n);
  x = (int *)malloc(n * sizeof(int));
  for(i=0;i<n;i++)
   {
      fflush(stdin);
      scanf("%d",&x[i]);
}
      heap(x,n);
     for(i=n-1;i>=1;i--)
         {
            temp =  x[i];
            x[i] = x[0];
           x[0] = temp;
   heap(x,i-1);
}
  printf("Resultant Array");
  for(i=0;i<n;i++)
       printf("%d",x[i]);
      free(x);
 getch();
}
   void heap(int *a,int n)
{
   int i,temp;
   for(i=n/2;i>=0;i--)
 {
        if(a[(2*i)+1] < a[(2*i)+2] && (2*i+1)<=n && (2*i+2)<=n)
           {
                temp = a[(2*i)+1];
  a[(2*i)+1] = a[(2*i)+2];
             a[(2*i)+2] = temp;
         }
     if(a[(2*i)+1] > a[i] && (2*i+1)<=n && i<=n)
         {
             temp = a[(2*i)+1];
            a[(2*i)+1] = a[i];
            a[i] = temp;
      }
  }
}

4. WAP to implement bucket sort
#include <stdio.h>
#include <stdlib.h>
const int RANGE = 200;
enum SearchResult
 {
FOUND,
     NOT_FOUND
  };
   void initLookupTable(enum SearchResult lookup[], int array[], int sizeOfData, int RANGE)
     {
       int v;
         for(int m=0; m<RANGE; m++)
           {
                lookup[m] = NOT_FOUND;
            }
  for(int mm=0; mm<sizeOfData; mm++)
   {
      v = array[mm];
      lookup[v] = FOUND;
   }
 }
   enum SearchResult searchLookupTable(enum SearchResult lookup[], int key)
       {
           return lookup[key];
       }
    void fill_array(int array[], int sizeOfData)
{
   for (int i = 0; i<=sizeOfData; i++)
     {
       array[i] = rand() % RANGE;
     }
}
    void print_array(int array[], int sizeOfData)
     {
  for (int j = 0; j<=sizeOfData; j++)
    {
       printf("Item %d is %d\t", j, array[j]);
    }
}
 int main()
  {
        srand ( time (0) );
  for (int ij=0; ij <100; ij++)
    {
      const int arraySize = 100;
       int a [arraySize];
      enum SearchResult lookup[RANGE];
      enum SearchResult result;
      int searchKey = rand() % RANGE;
      fill_array(a, arraySize);
      print_array(a, arraySize);
      initLookupTable(lookup, a, arraySize, RANGE);
     result = searchLookupTable(lookup, searchKey);
 if (result == FOUND)
        printf("\nKEY %d FOUND \n", searchKey);
        else
           printf("\nKEY %d NOT  FOUND \n", searchKey);
  }
  return (0);
}

















5.WAP to implement Radix sort.
#include <stdio.h>
#define MAX 5
#define SHOWPASS
void print(int *a,int n)
{
  int i;              
  for(i=0;i<n;i++)
     printf("%d\t",a[i]);
}
   void radixsort(int *a,int n)
   {
      int i,b[MAX],m=0,exp=1;
         for(i=0;i<n;i++)
            {
              if(a[i]>m)
                    m=a[i];
              }
              while(m/exp>0)
                  {
                       int bucket[10]={0};
              for(i=0;i<n;i++)
                   bucket[a[i]/exp%10]++;
                        for(i=1;i<10;i++)
                             bucket[i]+=bucket[i-1];
                        for(i=n-1;i>=0;i--)
                            b[--bucket[a[i]/exp%10]]=a[i];
                  for(i=0;i<n;i++)
                   a[i]=b[i];
                   exp*=10;
#ifdef SHOWPASS
      printf("\nPASS   : ");
         print(a,n);
 #endif
        }             
            }
int main()
{
      int arr[MAX];
      int i,n;
      printf("Enter total elements (n < %d) : ",MAX);
         scanf("%d",&n);         
         printf("Enter %d Elements : ",n);
           for(i=0;i<n;i++)
                scanf("%d",&arr[i]);
                printf("\nARRAY  : ");
                print(&arr[0],n);
                radixsort(&arr[0],n);
            printf("\nSORTED : ");
              print(&arr[0],n);
                printf("\n");
return 0;
}

6.Program to implement Rabin Karp String Matching Algorithm
#include<stdio.h>
#include<string.h>
#include<conio.H>
#include<math.H>
#include<iostream.h>

//Macro Defined
#define ToNum(c) (c >= 'A' && c <= 'Z' ? c - 'A' : c - 'a')  //converts alphabets to numbers

//Function Declaration :
int RabinKarp(char *T,char *P,int d,int q)  ;

void main()
{       char Text[]="Hello How are you. Fine. ";
        char Pattern[]="llo";
        int Radix=10; // Radix is 10 becoz we r using Decimal Number system.
        int Prime=17 ; // I have taken 17 as a Prime Number, can be anything like 31, 37, 43, 103, 117 etc.
        clrscr();

        int ans=RabinKarp(Text,Pattern,Radix, Prime);
        if(ans==-1)
                printf("\nNot Found !");  // ans =-1 means Unsuccessful search
        else
                printf("\nFound at Pos. %d", ans); //Successful search
getch();
}


int RabinKarp(char *T,char *P,int d,int q)
{   int i,j,p,t,n,m,h,found;
     n = strlen(T);
     m = strlen(P);
     h =  (int)pow(d,m) %q;

     cout<<endl<<d <<"  "<< m << "   " << q;
     cout<<endl<<h;
     h=Mod(d,m-1,q); //Please Check Is This OK ?
     cout<<endl<<h;

     p = t = 0;
     for (i=0; i<m; i++)
     {    p = (d*p + ToNum(P[i])) % q;
          t = (d*t + ToNum(T[i])) % q;
     }
     for (i=0; i<=n-m; i++)   //NOTE loop runs upto n-m
     {    if (p == t)
          {   found = 1;
               for (j=0; j<m; j++)
               {
                             if (P[j] != T[i+j])
                   {
                       found = 0;
                       break;
                   }
               }
               if (found)
                return i;  //found. Go back to main() with i
          }
          else
               t = (d*(t - ((ToNum(T[i])*h) % q)) + ToNum(T[i+m])) % q;
     }//end of for loop.
     return -1; // at end of loop, return 1, coz, not found
} //end of function RabinKarp()


 

 

 

 

 

 

 

 

 

 

 

 

7. WAP to impliment counting  sort algorithm.

#include <stdlib.h>
void  counting_sort(int array[], int size)
{
  int i, min, max;
  min = max = array[0];
  for(i = 1; i < size; i++)
    {
       if (array[i] < min)
          min = array[i];
      else if (array[i] > max)
        max = array[i];
    }
      int range = max - min + 1;
      int *count = malloc(range * sizeof(int));
     for(i = 0; i < range; i++)
       count[i] = 0;
     for(i = 0; i < size; i++)
      count[ array[i] - min ]++;
  int j, z = 0;
  for(i = min; i <= max; i++)
     for(j = 0; j < count[ i - min ]; j++)
        array[z++] = i;
  free(count);

  }

 void  single_pass_counting_sort(int *array, int size, int  range, int **output, int *next)
 {
   int key, i;
  *output = ReserveAddressSpace(range*size*sizeof(int));
  for(key = 0; key < range; key++)
    next[key] = key*size;
  for(i = 0; i < size; i++)
    (*output)[next[array[i]]++] = array[i];
}

void  iterate_over_sorted(int size, int range, int **output, int *next)
{
  int key, i;
  for(key = 0; key < range; key++)
    for(i = key*size; i < next[key]; i++)
      do_work((*output)[i]);
}










8.WAP to implement quicksort algorithm.
#include<stdio.h> 
#include<conio.h>
void main() 
{ 
     int arr[5],sarr[5],i,j,k; 
     int flag=0; 
     clrscr();
     printf("Enter the Elements : \n"); 
        for(i=0; i<5; i++) 
           { 
               scanf("%d",&arr[i]); 
           }
               printf("\n\nEntered Elements are : \n\n"); 
                  for(i=0; i<5; i++) 
                      { 
                         printf("%d\t",arr[i]); 
                       }
             printf("\n\nSorted Elements are : \n\n"); 
            sarr[0]=arr[0]; 
     for(i=1; i<5; i++) 
       { 
          flag=0; 
          for(j=0; j<=i; j++) 
            { 
               if(arr[i]<sarr[j]) 
                { 
                   for(k=i; k>j; k--) 
                     { 
                        sarr[k]=sarr[k-1]; 
                     } 
                       sarr[j]=arr[i]; 
                       flag=1; 
                       break; 
                } 
              else if(arr[i]>sarr[j] && arr[i]<sarr[j+1]) 
              { 
         for(k=i; k>j+1; k--) 
      { 
       sarr[k]=sarr[k-1]; 
      } 
          sarr[j+1]=arr[i]; 
          flag=1; 
           break; 
      } 
      } 
         f(flag==0) 
         { 
           sarr[i]=arr[i]; 
        } 
     }
  for(i=0; i<5; i++) 
{ 
   printf("%d\t",sarr[i]); 
}
   getch(); 
}

















9.WAP to implement N-Queen Problem using backtracking approach.
#include< stdio.h>
#include< conio.h>
#include< math.h>
 char a[10][10];
int n;
void printmatrix()
{
 int i,j;
 printf("\n");
 for(i=0;i < n;i++)
       {
       for(j=0;j < n;j++)
            printf("%c\t",a[i][j]);
       printf("\n\n");
       }
}
int getmarkedcol(int row)
{
 int i,j;
 for(i=0;i < n;i++)
     if(a[row][i]=='Q')
     {
     return(i);
break;
     }
}
int feasible(int row, int col)
{
 int i,tcol;
 for(i=0;i < n;i++)
     {
     tcol=getmarkedcol(i);
         if(col==tcol || abs(row-i)==abs(col-tcol))
              return 0;
     }
 return 1;
}
void nqueen(int row)
{
 int i,j;
 if(row < n)
 {
  for(i=0;i < n;i++)
   if(feasible(row,i))
      a[row][i]='Q';
         nqueen(row+1);
         a[row][i]='.';
        }
     }
 }
 else
 {
 printf("\nThe solution is:- ");
 printmatrix();
 }
}
void main()
{
 int i,j;
 clrscr();
printf("\n Enter the no. of queens:- ");
 scanf("%d",&n);
for(i=0;i < n;i++)
for(j=0;j < n;j++)
  a[i][j]=' ,’;
nqueen(0);
getch();
}











10.WAP to implement brute force string matching algorithm.

#include<stdio.h>
#include<conio.h>
int main(void)
{
    long int p,q,e,n,inv,s=0,d=1,C[100],M;
    char m[100];
    unsigned long int c;
    int i,j,t;
    printf("Enter the value of p and q: ");
    scanf("%d%d",&p,&q);
    n=p*q;
    inv=(p-1)*(q-1);
    printf("\nEnter the e value: ");
    scanf("%d",&e);
    do
    {
                   s=(d*e)%inv;
                   d++;
    }while(s!=1);
    d=d-1;
    printf("\nEnter the message to encrypt:");
    scanf("%s",&m);
    for(j=0;j<strlen(m);j++)
    {
                            m[j]=tolower(m[j]);
                            t=m[j]-96;
                            c=1;
                            for(i=0;i<e;i++)
                            c=c*t%n;
                            c=c%n;
                            printf("%d ",c);
    }
    printf("\n\nEnter encrypted message to decrpyt :\n");
    for(i=0;i<strlen(m);i++)
    scanf("%d",&C[i]);
    printf("\n\nDecrypted (original) message: ");
    for(j=0;j<strlen(m);j++)
    {
                            M=1;
                            for(i=0;i<d;i++)
                            M=M*C[j]%n;
                            M=M%n;
                            M=M+96;
                            printf("%c",M);
    }
    getch();
    return 0;
}


Posted by at No comments:
Subscribe to: Posts (Atom)