making change using dynamic

#include<stdio.h>
int main()
{
    int n,C,d[10],i,j,V[15][15],b[15][15];
    printf("enter maximum change");
    scanf("%d",&C);
    printf("enter no. of elements");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&d[i]);
    }
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=C;j++)
        {
            if(i==0 || j==0)
            {
                //printf("A\n");
                if(i==0)
                    V[i][j]=65535;
                else
                    V[i][j]=0;
            }
            else if(j<d[i-1])
            {
                //printf("B\n");
                V[i][j]=V[i-1][j];
                b[i][j]=j;
            }
            else
            {
                //printf("C\n");
                if(V[i-1][j]<((V[i][j-d[i-1]])+1))
                {
                    V[i][j]=V[i-1][j];
                    b[i][j]=j;
                }
                else
                {
                    V[i][j]=V[i][j-d[i-1]]+1;
                    b[i][j]=j-d[i-1];
                }
            }
            //printf("%d %d %d\n",i,j,V[i][j]);
        }
    }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=C;j++)
            {
                printf("%d ",V[i][j]);
            }
            printf("\n");
        }
        printf("\nminimum coins used is %d\n",V[n][C]);
        i=n;
        j=C;
        while(j!=0)
        {
            if(V[i][j]==V[i-1][j])
                i--;
            else
            {
                printf("%d\t",d[i-1]);
                j=b[i][j];
              
            }
        }
    return 0;
}

matrix chain multiplication using dynamic

#include<stdio.h>
int p[10],m[10][10],s[10][10];
void matrix_chain_order(int n)
{
    int i,j,k,l,q;
//    n=p.length-1;
    for(i=1;i<n;i++)
    m[i][i]=0;
    for(l=2;l<=n;l++)
    {
        for(i=1;i<=n-l+1;i++)
        {
            j=i+l-1;
            m[i][j]=99999;
            //printf("%d\t%d\t%d\n",i,l,j);
            for(k=i;k<=j-1;k++)
            {
                q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                if(q<m[i][j])
                {
                    m[i][j]=q;
                    s[i][j]=k;
                    //printf("%d\t%d\t%d\t%d\n",i,j,k,m[i][j]);
                }
            }
        }
      
    }
    for(i=0;i<n;i++)
    {
        for(j=n;j>i;j--)
        {
            printf("%d %d\t",m[i][j],s[i][j]);
        }
        printf("\n");
    }
  
    printf("\n\n\n");
}

void PRINT_OPTIMAL_PARENS(i,j)
{
    if(i == j)
     printf("A%d",i);
    else
    {
        printf("(");
    PRINT_OPTIMAL_PARENS(i,s[i][j]);
    PRINT_OPTIMAL_PARENS(s[i][j]+1,j);
    printf(")");
    }

}
int main()
{
    int i,n;
    printf("enter no. of matrices");
    scanf("%d",&n);
    printf("enter sizes of matrix");
    for(i=0;i<=n;i++)
    scanf("%d",&p[i]);
    matrix_chain_order(n);
    PRINT_OPTIMAL_PARENS(1,6);
    return 0;
}

knapsack using dynamic

 //knapsack using dynamic
#include<stdio.h>
int main()
{
    int n,W,w[10],v[10],i,j,V[15][15];
    printf("enter capacity of knapsack");
    scanf("%d",&W);
    printf("enter no. of elements");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d %d",&w[i],&v[i]);
    }
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=W;j++)
        {
            if(i==0 || j==0)
            V[i][j]=0;
            else if((j-w[i-1])<0)
            V[i][j]=V[i-1][j] ;
            else
            {
                if(V[i-1][j]<V[i-1][j-w[i-1]]+v[i-1])
                V[i][j]=V[i-1][j-w[i-1]]+v[i-1];
                else
                V[i][j]=V[i-1][j];          
            }
        }
    }
        for(i=0;i<=n;i++)
        {
            for(j=0;j<=W;j++)
            {
                printf("%d ",V[i][j]);
            }
            printf("\n");
        }
        printf("\nmax profit earned is %d\n",V[n][W]);
    return 0;
}

Counting Sort

#include <stdio.h>
#include <stdlib.h>
void count(int A[],int k,int n)
{
    int i,j;
    int B[10],C[15];
    for(i=0;i<=k;i++)
    {
        C[i]=0;
    }
    for(j=1;j<=n;j++)
    {
        C[A[j]]= C[A[j]] +1;
    }

    for(i=1;i<=k;i++)
        C[i]= C[i]+C[i-1];

    for(j=n;j>=1;j--)
    {
        B[C[A[j]]] = A[j];
        C[A[j]] = C[A[j]] -1;
    }

    printf("Sorted array is:\n");
    for(i=1;i<=n;i++)
    {
        printf("%d ",B[i]);
    }

}

int main()
{
    int n,A[15],k=0,i;
    printf("Enter n\n");
    scanf("%d",&n);
    printf("\nEnter ele:");
    for(i=1;i<=n;i++)
    {
        scanf("%d",&A[i]);
        if(A[i]>k)
            k=A[i];
    }
    count(A,k,n);

    return 0;
}

Merge Sort

#include<stdio.h>
#include<math.h>
#include<sys/time.h>
#include<stdlib.h>
#include<iostream>

using namespace std;

long int n=100000,a[100000];

void merge(long int begin,long int mid, long int end,long int a[])
{
long int i=begin,j=mid+1,temp[end],cnt=0;
while(cnt<(end-begin+1))
{
if(i==mid+1)
{
temp[cnt++]=a[j];
j++;
}
else if(j==end+1)
{
temp[cnt++]=a[i];
i++;
}
else
{
if(a[i]<a[j])
{
temp[cnt++]=a[i];
i++;
}
else
{
temp[cnt++]=a[j];
j++;
}
}
}
for(i=begin;i<=end;i++)
a[i]=temp[i-begin];
}

void divide(long int a,long int b,long int y[])
{
long int mid=(b-a)/2+a;
if((b-a)>1)
{
divide(a,mid,y);
divide(mid+1,b,y);
}
merge(a,mid,b,y);
}

int main()
{
struct timeval  tv1, tv2;
 
long int mid;
for(long int i=0;i<n;i++)
a[i]=rand();

gettimeofday(&tv1, NULL);

mid=(n-1)/2;
divide(0,mid,a);
divide(mid+1,n-1,a);
merge(0,mid,n-1,a);

gettimeofday(&tv2, NULL);
printf("Time taken in execution = %f micro-seconds\n",
    (double) (tv2.tv_usec - tv1.tv_usec));
    return 0;
}

Insertion Sort

#include<stdio.h>
#include<math.h>
#include<sys/time.h>
#include<stdlib.h>
#include<iostream>

using namespace std;

int main()
{
long timedif;
struct timeval tpstart;
struct timeval tpend;
struct timeval now;
int rc;

now.tv_sec=000000000;
now.tv_usec=000000;

rc=settimeofday(&now, NULL);

if(rc==0)
{
printf("settimeofday() failed.\n");
}
else
{
printf("\nsettimeofday() Succesful\n");
printf("\nTime Set sec=%ld Msec=%ld\n",now.tv_sec,now.tv_usec);
}

gettimeofday(&tpstart, NULL);

long int n=100000;
long int a[n];

for(long int i=0;i<n;i++)
{
long int temp=random(),flag=1;
for(long int j=0;j<i;j++)
{
if(temp<a[j])
{
for(long int k=i;k>=j;k--)
a[k]=a[k-1];
a[j]=temp;
flag=0;
break;
}
}
if(flag==1)
a[i]=temp;
}

gettimeofday(&tpend, NULL);
timedif = 1000000 * (tpend.tv_sec - tpstart.tv_sec) + tpend.tv_usec - tpstart.tv_usec;

printf("\nTime difference is:%ld\n",timedif);
}

Selection sort

#include<stdio.h>
#include<math.h>
#include<sys/time.h>
#include<stdlib.h>
#include<iostream>

using namespace std;

long int n=100000,a[100000];

int main()
{
struct timeval  tv1, tv2;
   
for(long int i=0;i<n;i++)
a[i]=rand();

gettimeofday(&tv1, NULL);

for(long int i=0;i<n;i++)
{
long long int min=a[i],ind=i;
for(long int j=i+1;j<n;j++)
{
if(min>a[j])
{
min=a[j];
ind=j;
}
}
a[ind]=a[i];
a[i]=min;
//cout << a[i] << endl;
}

gettimeofday(&tv2,NULL);
printf("Time taken in execution = %f micro-seconds\n",
    (double) (tv2.tv_usec - tv1.tv_usec));
    return 0;
}

Bubble Sort

#include<stdio.h>
#include<math.h>
#include<sys/time.h>
#include<stdlib.h>
#include<iostream>

using namespace std;

long int n=100000,a[100000];

int main()
{
     struct timeval tv1, tv2;

     for(long int i=0;i<n;i++)
     a[i]=rand();

     gettimeofday(&tv1, NULL);

     for(long int i=0;i<n;i++)
     {
           for(long int j=i;j<n;j++)
           {
                 if(a[i]>a[j])
                 {
                        long int temp;
                        temp=a[i];
                        a[i]=a[j];
                        a[j]=temp;
                  }
           }
     }

     gettimeofday(&tv2, NULL);
     printf("Time taken in execution = %f micro-seconds\n",(double) (tv2.tv_usec - tv1.tv_usec));
     return 0;
}