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