Wednesday, September 19, 2012

Algorithm LAB_b) Write two recursive programs to compute Xn, where both X & n are integers, one computes it in O(n) time & the other in O(log n) time.

#include<stdio.h>
#include<stdlib.h>
long power(int, int);
int count;
int main()
{
    int x,y;
    long pow;
    printf("enter value of x\n");
    scanf("%d",&x);
    printf("enter power of x\n");
    scanf("%d",&y);
    count=0;
    pow=power(x,y);
    printf("the number of steps is %d\n",count);
    printf("the result is %ld\n",pow);
    return 0;
}
long power(int x, int y)
{
    count++;
    if(y==0)
        return 1;
    else if(y%2==0)
        return(power(x,y/2)*power(x,y/2));
    else
        return(x*power(x,y/2)*power(x,y/2));
}

Algorithm LAB _ WAP to solve Towers-of-Hanoi problem – one using Tail Recursion & another without using Tail Recursion

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void towers(int,char,char,char);
void towers(int n,char frompeg,char topeg,char auxpeg)
{
    if(n==1)
    {    printf("\n move disk 1 from peg %c to peg %c", frompeg,topeg);
    return;
    }
    towers(n-1,frompeg,auxpeg,topeg);
    printf("\n move disk %d from %c to peg %c",n,frompeg,topeg);
    towers(n-1,auxpeg,topeg,frompeg);
}
int main()
{
    int n;
    time_t start,end;
    double timetaken;
    printf("enter the no of disks:");
    scanf("%d",&n);
    printf("the tower of hanoi involves the moves: \n \n");
    start=clock();
    towers(n,'A','c','B');
    end=clock();
    timetaken=(double)(end-start)/(CLOCKS_PER_SEC);
    printf("the timetaken is %lf",timetaken);
    return 0;
}

Algorithm LAB _ WAP to implement INSERTION-SORT

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void sort(int *a,int n);

void sort(int *a,int n)
    {
    int i,j,c;
    for(j=1;j<n;j++)
        {
        c=a[j];
        i=j-1;
        while(i>=0 && a[i]>c)
            {
            a[i+1]=a[i];
            i=i-1;
            }
        a[i+1]=c;
        }
    }

int main()
    {
    FILE *f1,*f2,*f3;
    time_t start,end;
    double timetaken;
    srand(time(NULL));
    int *a,n,i,j;
    printf("enter the size of the array to be sorted\n");
    scanf("%d",&n);
    a=(int*)malloc(n*sizeof(int));
   
    f1=fopen("data1.txt","w+");
    for(i=0;i<n;i++)
        fprintf(f1,"%d\n",rand()%n);
    rewind(f1);
    i=0;
    while(fscanf(f1,"%d",&a[i])!=EOF)
        {
        i++;
        }
    fclose(f1);

    start=clock();
    sort(a,n);
    end=clock();
    timetaken=(double)(end-start)/(CLOCKS_PER_SEC);
    printf("the timetaken for average case is %lf",timetaken);

    f2=fopen("data2.txt","w+");
    for(i=0;i<n;i++)
        fprintf(f2,"%d\n",i);
    rewind(f2);
    i=0;
    while(fscanf(f2,"%d",&a[i])!=EOF)
        i++;
    fclose(f2);

    start=clock();
    sort(a,n);
    end=clock();
    timetaken =(double)(end-start)/(CLOCKS_PER_SEC);
    printf("\nthe time taken for the best case is %lf",timetaken);
   
    f3=fopen("data3.txt","w+");
    for(i=n;i>0;i--)
        fprintf(f3,"%d\n",i);
    rewind(f3);
    i=0;
    while(fscanf(f3,"%d",&a[i])!=EOF)
        i++;
    fclose(f3);

    start=clock();
    sort(a,n);
    end=clock();
    timetaken=(double)(end-start)/(CLOCKS_PER_SEC);
    printf("\n the time taken for the worst case is %lf",timetaken);

    return 0;
    }

Tuesday, September 6, 2011

Algo for Searching and Sorting


Linear Search
This is most frequently used search method. We simply traverse the list or array or records and
check if the identification number matches with the id number of our interest.

Algorithm:
Begin:
Found = false
Count = 0
Obtain the input array.
Obtain number of terms, key
Do
{ If array[count]== key
Found = true.
Else
Count ++
} while ( count <=N) && found==false)
if false declare the key is not present in the array
Else declare the position and value of the element
End

Binary Search Algorithm
Algorithm
begin :
max=length-1
min=0;
success=false
while ((!success) && max>=min)
{
mid=max+min/2
if ( mid==key)
declare the result. Mid is the position. success=true;
else
if key < array[mid]
// adjust max to left sub array
Max = Mid-1
Else
Min=min+1
end

Bubble Sort
Algorithm
Procedure bubblesort(sort[],len)
for i=1 to len-1 do
begin
for j=0 to len-i do
begin
if [sort[j] > sort[j+1]
swap (sort[i],sort[j+1])
end
end
return

Selection Sort
Algorithm :
Selectsort(sort[],len)
for i=0 to i<len-1 do
begin
min=i
for j=i+1 j<len do
begin
if[sort[j] < sort[min]
min=j
end
if(min != i)
swap(sort[min],sort[i])
end

INSERTION SORT
Algorithm for Insertion Sort
for i=1 to i<len
begin
temp = sort[i]
for j=I to j=1
for j=i to j=1
begin
if [sort[j-1] > temp]
sort[j] = sort[j-1] // shift one position to the right
end
sort[j] = temp
end

QUICK SORT
Procedure QSort[int sort[], int lo, int hi]
Where sort[] is the input array which has to be sorted, ‘lo’ and ‘hi’ are indexes to the first and last
elements of the sub array that has to be sorted.
If (lo >= hi)
Return;
Initialize :
i = lo-1
j = hi
pivot = sort[hi] // set pivot element to print to last element of the array
while (i < j)
{
while (Sort[++i] < pivot);
while (j>=0 && sort[—j] > pivot);
if (i<j)
swap(sort[i],sort[j])
}



Thursday, May 26, 2011

notes on calloc and malloc

calloc() allocates memory for an array of nmemb elements of sizebytes each and returns a pointer to the allocated memory. The memory is set to zero.


malloc() allocates size bytes and returns a pointer to the allocated memory. The memory is not cleared.

free() frees the memory space pointed to by ptr, which must have been returned by a previous call to malloc(),


calloc() orrealloc(). Otherwise, or if free(ptr)has already been called before, undefined behaviour occurs. If ptr is NULL, no operation is performed.

realloc() changes the size of the memory block pointed to by ptr to size bytes. The contents will be unchanged to the minimum of the old and new sizes; newly allocated memory will be uninitialized. If ptr is NULL, the call is equivalent to malloc(size); if size is equal to zero, the call is equivalent to free(ptr). Unlessptr is NULL, it must have been returned by an earlier call to malloc(), calloc() or realloc(). If the area pointed to was moved, a free(ptr) is done.

Saturday, May 7, 2011

Java program for display difference between two date

class date_difference
{
int r=0;
public int datechk(int d,int m,int y)
{
if((y>100)&&(y<9999))
{
if((m==2)&&(y%4==0))
{
if((d>=1)&&(d<=29))
 
      r=1;
  else
  r=0;
    }
    else if((m==2)&&(y%4!=0))
    {
        if((d>=1)&&(d<=28))
       
            r=1;
            else
            r=0;
       
    }
   
    else if((m==1)||(m==3)||(m==5)||(m==7)||(m==8)||(m==10)||(m==12))
    {
        if((d>=1)&&(d<=31))
       
            r=1;
            else
            r=0;
       
    }
    else if((m==4)||(m==6)||(m==9)||(m==11))
    {
        if((d>=1)&&(d<=30))
       
            r=1;
            else
            r=0;
       
    }   
    else
       r=0;
      
    }
    return r;
}
      
       public void main(int d1,int d2, int m1,int m2,int y1,int y2)
       {
           int mo[]={31,28,31,30,31,30,31,31,30,31,30,31};
           int f,f1,i,tot=0;
           f=datechk(d1,m1,y1);
           f1=datechk(d2,m2,y2);
          
          
           if(f==1 && f1==1)
        {
            if(y1==y2)
            {
                if(y1%4==0)
                mo[1]=29;
                for(i=m1+1;i<m2;i++)
                    tot+=mo[i];
                if(m1 == m2)
                    tot+=d2-d1;
                else
                    {
                    tot+=((mo[m1-1]-d1)+1);
                    tot+=d2;
                    }
                System.out.println(tot);
                }
            else if(y1<y2)
            {
                for(i=(y1+1);i<y2;i++)
                {
                    tot+=(i%4==0?366:365);
                }
                if(y1%4==0)
                mo[1]=0;
                for(i=m1;i<12;i++)
                tot+=mo[i];
                tot+=((mo[m1-1]-d1)+1);
                if(y2%4==0)
                mo[1]=29;
                for(i=0;i<m2-1;i++)
                tot+=mo[i];
                tot+=d2;
                System.out.println(tot);
            }
            else
            System.out.println("invalid years");
            }
        }
    }