Rabin Karp

#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<math.h>
#define d 10
voidRabinKarpStringMatch(char *, char *, int);
void main()
{
char *Text, *Pattern;
int Number = 11; //Prime Number
clrscr();
printf("\nEnter Text String : ");
gets(Text);
printf("\nEnter Pattern String : ");
gets(Pattern);

RabinKarpStringMatch(Text,Pattern,Number);
getch();
}

voidRabinKarpStringMatch(char *Text, char *Pattern, int Number)
{
intM,N,h,P=0,T=0, TempT, TempP;
inti,j;
       M = strlen(Pattern);
       N = strlen(Text);
       h = (int)pow(d,M-1) % Number;
       for(i=0;i<M;i++)
       {
            P = ((d*P) + ((int)Pattern[i])) % Number;
            TempT = ((d*T) + ((int)Text[i]));
            T =  TempT % Number;
       }
      for(i=0;i<=N-M;i++)
 {
if(P==T)
{
for(j=0;j<M;j++)
if(Text[i+j] != Pattern[j])
break;
if(j == M)
printf("\nPattern Found at Position :  %d",i+1);
        }
TempT=((d*(T - Text[i]*h)) + ((int)Text[i+M]));
        T = TempT % Number;
if(T<0)
            T=T+Number;
      }
}

Divide and Conquer

#include<stdio.h>

#define ARRAY_SIZE(array) (sizeof(array) / sizeof(array[0]))

int tempmax, tempmin;

int* maxmin(const int list[], const int low, const int high, int max, int min)

{

    int mid,max1,min1;

    static int maxAndMin[2]; // to hold the max and min value of list

    if (low == high)

    {

        max = list[low];

        min = list[low];

    }          

    else if (low == high-1)

    {

        if (list[low] < list[high])

        {

            tempmax = getMax(tempmax, list[high]);

            tempmin = getMin(tempmin, list[low]);

        }

        else

        {

            tempmax = getMax(tempmax, list[low]);

            tempmin = getMin(tempmin, list[high]);

        }

    }

   else

   {

       mid = (low + high) / 2;

       max1 = list[mid+1];

       min1 = list[mid+1];

       maxmin(list, low, mid, max, min);

       maxmin(list, mid+1, high, max1, min1);

       tempmax = getMax(tempmax, max1);

       tempmin = getMin(tempmin, min1);

   }

    maxAndMin[0] = tempmax;

    maxAndMin[1] = tempmin;

    return maxAndMin;

}

int getMax(int first, int second)

{

    return first > second ? first : second;

}

int getMin(int  first, int second)

{

    return  first < second ?  first : second;

}

int main(void)

{

    int list[] = {10, 23, 24, 56, 67, 78, 90};

    int *values;

    int size = ARRAY_SIZE(list);

    tempmax = tempmin = list[0];

    values = maxmin(list, 0, size-1, list[0], list[0]);

    printf("The maximum value is = %2d \n", *values);

    printf("The minimum value is = %2d \n", *(values+1));

    return 0;

}

0/1 Knapsack problem

#include<stdio.h>

#include<conio.h>

#define MAX 20

voidknapsackDP(int,int);

int max(int,int);

void backtracking();

int weight[MAX],value[MAX],W,no,*x;

int v[MAX][MAX];

void main()

{

inti,j;

clrscr();

printf("\n Enter number of Object you want:");

scanf("%d",&no);

printf("\n Enter weight and values in ascending order of vales");;

for(i=1;i<=no;i++)

 {

printf("\n Enter Weight and Value for Object %d:",i);

scanf("%d %d",&weight[i],&value[i]);

 }

printf("\n Enter knapsack Capacity:");

scanf("%d",&W);

knapsackDP(no,W);

backtracking();

getch();

}

voidknapsackDP(intno,int W)

{

inti,j;

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

            v[0][i]=0;

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

v[i][0]=0;

for(i=1;i<= no;i++)

 {

for(j=1;j<= W;j++)

  {

if((j-weight[i])< 0)

v[i][j]=v[i-1][j];

else

    v[i][j]=max(v[i-1][j],v[i-1][j-weight[i]]+value[i]);

  }

 }

printf("\n \t      ");

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

printf("%2d  ",i);

printf("\n-----------------------------------------------------------------------------");

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

 {

printf("\n w%d=%2d v%d=%2d |",i,weight[i],i,value[i]);

for(j=0;j<= W;j++)

printf("%2d  ",v[i][j]);

 }

printf("\n-----------------------------------------------------------------------------");

printf("\n Maximum value carry by knapsack is:%2d",v[no][W]);

printf("\n-----------------------------------------------------------------------------");

}

int max(inta,int b)

{

return (a >b)?a:b;

}

void backtracking()

{

int j1,i;

 j1=W;

printf("\nIncluded Object \t weight \t value");

printf("\n-----------------------------------------------------------------------------");

for(i=no;i>=0;i--)

 {

  if(v[i][j1]!=v[i-1][j1] && (v[i][j1]==v[i-1][j1-weight[i]]+value[i]))

  {

printf("\n%2d \t\t\t  %2d   \t\t %2d",i,weight[i],value[i]);

   j1=j1-weight[i];

  }

 }

}

Making Change Solution

#include <stdio.h>

#include<conio.h>

int change(float total, int *hundred, int *fifty, int *twenty, int *ten, int *five, int *one);

void print(float total, int hundred, int fifty, int twenty, int ten, int five, int one);

int main(void)

{

             int hundred,fifty, twenty, ten, five, one,sum=0;

             float total;

             clrscr();

             printf("\nPlease enter an amount of money: \n");

             scanf("%f", &total);

             change(total,&hundred, &fifty, &twenty, &ten, &five, &one);

             print(total, hundred, fifty, twenty, ten, five, one);

             sum=hundred+fifty+twenty+ten+five+one;

             printf("No of cions are:%d ",sum);

             getch();

}

int change(float total, int *hundred, int *fifty, int *twenty, int *ten, int *five, int *one)

{

            if( total >= 100.00)

                        *hundred =(total /100.00);

            if( total >= 50.00 )

                        *fifty = (total- (*hundred * 100.00))/50.00;

             if( total >= 20.00 )

                        *twenty = (total - (*hundred * 100.00)- (*fifty * 50.00)) / 20.00;

             if( total >= 10.00 )

*ten = (total - (*hundred * 100.00) - (*fifty * 50.00) - (*twenty *     20.00)) / 10.00;

             if( total >= 5.00 )

*five = (total - (*hundred * 100.00) - (*fifty * 50.00) - (*twenty * 20.00) - (*ten * 10.00)) / 5.00;

            if( total >= 1.00 )

*one = (total - (*hundred * 100.00) - (*fifty * 50.00) - (*twenty * 20.00) - (*ten * 10.00)-(*five * 5)) / 1.00;

                        return 0;

}

void print(float total, int hundred, int fifty, int twenty, int ten, int five ,int one)

{

            printf("\nTOTAL VALUE ENTERED: Rs %.2f", total);

            printf("\n%3d No of 100 Rs coin \n", hundred);

            printf("\n%3d  No of 50 Rs coin \n", fifty);

            printf("\n%3d No of 20 Rs coin \n", twenty);

            printf("\n%3d No of 10 Rs coin \n", ten);

            printf("\n%3d No of 5 Rs coin \n", five);

           printf("\n%3d No of 1 Rs coin \n", one);

}

Insertion Sort Algorithm

#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;

          }

 

    } 

  

    void main() 

    { 

                  int a[100],n,i; 

                  clrscr(); 

           

                  printf("\n\nEnter an integer value for total no.s of elements to be sorted: "); 

                  scanf("%d",&n); 

  

                   for(i=0;i<=n-1;i++) 

                   { 

                         printf("\n\nEnter an integer value for element no.%d: ",i+1); 

                         scanf("%d",&a[i]); 

                    } 

    

                    insertion(a,n); 

    

                    printf("\n\n\nFinally sorted array is : "); 

                   

                    for(i=0;i<=n-1;i++)

                   {

                        printf("%4d",a[i]); 

                   }

    }

Best-Case

The best case occurs if the array is already sorted. For each j = 2, 3, ..., n, we find that A[i] less than or equal to the key when i has its initial value of (j − 1). In other words, when i = j −1, always find the key A[i] upon the first time the WHILE loop is run.

Therefore, t_j = 1 for j = 2, 3, ..., n and the best-case running time can be computed using equation (1) as follows:

T(n) = c₁n + c₂ (n − 1) + c₄ (n − 1) + c₅ ∑_{2 ≤ j ≤ n} (1) + c₆ ∑_{2 ≤ j ≤ n} (1 − 1) + c₇ ∑_{2 ≤ j ≤ n} (1 − 1) + c₈ (n − 1)

T(n) = c₁n + c₂ (n − 1) + c₄ (n − 1) + c₅ (n − 1) + c₈ (n − 1)

T(n) = (c₁ + c₂ + c₄  + c₅  + c₈ ) n + (c₂  + c₄  + c₅  + c₈)

This running time can be expressed as an + b for constants a and b that depend on the statement costs c_i. Therefore, T(n) it is a linear function of n.

The punch line here is that the while-loop in line 5 executed only once for each j. This happens if given array A is already sorted.

T(n) = an + b = O(n)

It is a linear function of n.

Worst-Case

The worst-case occurs if the array is sorted in reverse order i.e., in decreasing order. In the reverse order, we always find that A[i] is greater than the key in the while-loop test. So, we must compare each element A[j] with each element in the entire sorted subarray A[1 .. j − 1] and so t_j = j for j = 2, 3, ..., n. Equivalently, we can say that since the while-loop exits because i reaches to 0, there is one additional test after (j − 1) tests. Therefore, t_j = j for j = 2, 3, ..., n and the worst-case running time can be computed using equation (1) as follows:

T(n) = c₁n + c₂ (n − 1) + c₄  (n − 1) + c₅ ∑_{2 ≤ j ≤ n} ( j ) + c₆ ∑_{2 ≤ j ≤ n}(j − 1) + c₇ ∑_{2 ≤ j ≤ n}(j − 1) + c₈ (n − 1)

And using the summations in CLRS on page 27, we have

T(n) = c₁n + c₂ (n − 1) + c₄  (n − 1) + c₅ ∑_{2 ≤ j ≤ n} [n(n +1)/2 + 1] + c₆ ∑_{2 ≤ j ≤ n} [n(n − 1)/2] + c₇ ∑_{2 ≤ j ≤ n} [n(n − 1)/2] + c₈ (n − 1)

T(n) = (c₅/2 + c₆/2 + c₇/2) n² + (c₁ + c₂ + c₄ + c₅/2 − c₆/2 − c₇/2 + c₈) n − (c₂ + c₄ + c₅ + c₈)

This running time can be expressed as (an² + bn + c) for constants a, b, and c that again depend on the statement costs c_i. Therefore, T(n) is a quadratic function of n.

Here the punch line is that the worst-case occurs, when line 5 executed j times for each j. This can happens if array A starts out in reverse order

T(n) = an² + bn + c = O(n²)

Average Case

On average, the key in A[j] is less than half the elements in A[1 .. j − 1] and it is greater than the other half. It implies that on average, the while loop has to look halfway through the sorted subarray A[1 .. j − 1] to decide where to drop key. This means that t_j  = j/2.

Although the average-case running time is approximately half of the worst-case running time, it is still a quadratic function of n.