SEDOC AAD

//toh
#include<stdio.h>
#include<time.h>

void toh(int n, char from_d, char to_d, char aux)
{
    if(n==1)
    {
        printf("Move disk 1 from %c to %c \n",from_d,to_d);
        return ;
    }

    toh(n-1,from_d,aux,to_d);
    printf("Move disk %d from %c to %c\n",n,from_d,to_d);
    toh(n-1,aux,to_d,from_d);
}

void main()
{
    int n;
    printf("Enter the number of disks\n");
    scanf("%d",&n);
    clock_t start=clock();
    toh(n,'A','C','B');
    clock_t end=clock();

    printf("Start time is %f",(double)start);
    printf("End time: %f",(double)end);
    printf("Time taken: %f", (double)(end-start));


}

//binarySearch
#include <stdio.h>
#include <time.h>

int binarySearch(int arr[], int l, int r, int x)
{
    if (r >= l)
    {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);
        return binarySearch(arr, mid + 1, r, x);
    }
    return -1;
}

int main()
{
    int n,x;
    printf("Enter size\n");
    scanf("%d",&n);
    int arr[n];
    printf("Enter array elements\n");
    for(int i=0;i<n;i++)
    {
        scanf("%d",&arr[i]);
    }
    printf("Enter key\n");
    scanf("%d",&x);
    clock_t start=clock();
    int result = binarySearch(arr, 0, n - 1, x);
    clock_t end=clock();
    if(result == -1)
        printf("Element is not present in array\n");
    else
        printf("Element is present at index %d\n", result);
    printf("\nStart time is %lf\n",(double)start);
    printf("\nEnd time is %lf\n",(double)end);
    printf("\nTotal time is %lf\n",(double)(end-start));
    return 0;
}

//MergeSort
#include <stdio.h>
#include <stdlib.h>


void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;


    int L[n1], R[n2];


    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];


    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }


    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }


    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}


void mergeSort(int arr[], int l, int r)
{
    if (l < r) {


        int m = l + (r - l) / 2;


        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}



void printArray(int A[], int size)
{
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", A[i]);
    printf("\n");
}


int main()
{
    int arr[50],arr_size,i;
    printf("Enter the number of elements in the array\n");
    scanf("%d",&arr_size);

    printf("Enter the elements\n");
    for(i=0;i<arr_size;i++)
    {
        scanf("%d",&arr[i]);
    }

    printf("Given array is \n");
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    printf("\nSorted array is \n");
    printArray(arr, arr_size);
    return 0;
}


//QuickSort
#include <stdio.h>
#include<time.h>


void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}


int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}


void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}


void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}


int main() {
    int arr[50],arr_size,i;
    printf("Enter the number of elements in the array\n");
    scanf("%d",&arr_size);

    printf("Enter the elements\n");
    for(i=0;i<arr_size;i++)
    {
        scanf("%d",&arr[i]);
    }
    clock_t start=clock();
    quickSort(arr, 0, arr_size - 1);
    clock_t end=clock();

    printf("Sorted array: \n");
    printArray(arr, arr_size);

    printf("Start time is %f",(double)start);
    printf("End time: %f",(double)end);
    printf("Time taken: %f", (double)(end-start));
    return 0;
}


//Prims
#include<stdio.h>
#include<time.h>

int visited[10]={0}, cost[10][10], min, mincost=0;
int i,j,ne=1, a, b, u, v;
int main()
{
    int num;
    printf("\n\t\t\tPrim's Algorithm");
    printf("\n\nEnter the number of nodes= ");
    scanf("%d", &num);
    printf("\nEnter the adjacency matrix\n\n");
    for(i=1; i<=num; i++)
    {
        for(j=1; j<=num; j++)
        {
            scanf("%d", &cost[i][j]);
            if(cost[i][j]==0)
                cost[i][j]=999;
        }
    }
    clock_t start=clock();
    visited[1]=1;
    while(ne < num)
    {
        for(i=1,min=999;i<=num;i++)
        for(j=1;j<=num;j++)
        if(cost[i][j]< min)
        if(visited[i]!=0)
        {
            min=cost[i][j];
            a=u=i;
            b=v=j;
        }

        printf("\n Edge %d:(%d - %d) cost:%d",ne++,a,b,min);
        mincost=mincost+min;
        visited[b]=1;
        cost[a][b]=cost[b][a]=999;
    }
    printf("\n\n\n Minimun cost=%d",mincost);
    clock_t end=clock();
    printf("\nStart time is %lf\n",(double)start);
    printf("End time is %lf\n",(double)end);
    printf("Total time is %lf\n",(double)(end-start));
    return 0;
}

//Kruskals
#include <stdio.h>
#include <time.h>
int i, j, k, a, b, u, v, n, ne = 1;
int min, mincost = 0, cost[9][9], parent[9];
int find(int);
int uni(int, int);
void main()
{
    printf("\n\tImplementation of Kruskal's algorithm\n");
    printf("\nEnter the no. of vertices:");
    scanf("%d", &n);
    printf("\nEnter the cost adjacency matrix:\n");
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
        {
            scanf("%d", &cost[i][j]);
            if (cost[i][j] == 0)
                cost[i][j] = 999;
        }
    }
    printf("The edges of Minimum Cost Spanning Tree are\n");
    clock_t start = clock();
    while (ne < n)
    {
        for (i = 1, min = 999; i <= n; i++)
        {
            for (j = 1; j <= n; j++)
            {
                if (cost[i][j] < min)
                {
                    min = cost[i][j];
                    a = u = i;
                    b = v = j;
                }
            }
        }
        u = find(u);
        v = find(v);
        if (uni(u, v))
        {
            printf("%d edge (%d,%d) =%d\n", ne++, a, b, min);
            mincost += min;
        }
        cost[a][b] = cost[b][a] = 999;
    }
    printf("\n\tMinimum cost = %d\n", mincost);
    clock_t end = clock();
    printf("Start time is %lf\n", (double)start);
    printf("End time is %lf\n", (double)end);
    printf("Total time is %lf\n", (double)(end - start));
}
int find(int i)
{
    while (parent[i])
        i = parent[i];
    return i;
}
int uni(int i, int j)
{
    if (i != j)
    {
        parent[j] = i;
        return 1;
    }
    return 0;
}

//0/1 Knapsack
    #include<stdio.h>
    #include<time.h>
    int max(int a, int b)
    {
        return (a > b)? a : b;
    }

    int knapSack(int W, int wt[], int val[], int n)
    {
    int i, w;
    int K[n+1][W+1];
    for (i = 0; i <= n; i++)
        {
            for (w = 0; w <= W; w++)
            {
            if (i==0 || w==0)
                K[i][w] = 0;
            else if (wt[i-1] <= w)
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
            else
                K[i][w] = K[i-1][w];
            }
        }
    return K[n][W];
    }


    int main()
    {
    int i, n, val[20], wt[20], W;
    printf("Enter number of items:");
    scanf("%d", &n);
    printf("Enter value and weight of items:\n");
    for(i = 0;i < n; ++i)
        {
            scanf("%d%d", &val[i], &wt[i]);
        }
    printf("Enter size of knapsack:");
    scanf("%d", &W);
    clock_t start=clock();
    printf("The maximum profit is %d\n", knapSack(W, wt, val, n));
    clock_t end=clock();
    printf("Start time is %lf\n",(double)start);
    printf("End time is %lf\n",(double)end);
    printf("Total time is %lf\n",(double)(end-start));
    return 0;
    }


//DIJIKSTRAS
#include <stdio.h>
#include<time.h>
#define INFINITY 999
#define MAX 10

void Dijkstra(int Graph[MAX][MAX], int n, int start);

void Dijkstra(int Graph[MAX][MAX], int n, int start) {
 int cost[MAX][MAX], distance[MAX], pred[MAX];
 int visited[MAX], count, mindistance, nextnode, i, j;

 // Creating cost matrix
 for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
        if (Graph[i][j] == 0)
            cost[i][j] = INFINITY;
        else
            cost[i][j] = Graph[i][j];

 for (i = 0; i < n; i++) {
    distance[i] = cost[start][i];
    pred[i] = start;
    visited[i] = 0;
 }
 distance[start] = 0;
 visited[start] = 1;
 count = 1;

 while (count < n - 1) {
 mindistance = INFINITY;
    for (i = 0; i < n; i++)
        if (distance[i] < mindistance && !visited[i]) {
            mindistance = distance[i];
        nextnode = i;
    }

 visited[nextnode] = 1;
 for (i = 0; i < n; i++)
    if (!visited[i])
        if (mindistance + cost[nextnode][i] < distance[i]) {
            distance[i] = mindistance + cost[nextnode][i];
            pred[i] = nextnode;
        }
 count++;
 }
 // Printing the distance
 for (i = 0; i < n; i++)
    if (i != start) {
        printf("\nDistance from source to %d: %d", i, distance[i]);
 }
}

int main() {
 int Graph[MAX][MAX], i, j, n, u;
 printf("Enter number of nodes:\n");
 scanf("%d",&n);
 printf("Enter Matrix Elements( Cost Adjacency Matrix):");
 for (i=0;i<n;i++)
    {
    for(j=0;j<n;j++)
        {
        scanf("%d",&Graph[i][j]);
 //printf("%d",Graph[i][j]);
        }
    }
printf("Select source vertex:\n");
 scanf("%d",&u);
 clock_t start=clock();
 Dijkstra(Graph, n, u);
 clock_t end=clock();

 printf("\n Start time is %lf\n",(double)start);
 printf("End time is %lf\n",(double)end);
 printf("Total time is %lf\n",(double)(end-start));
 return 0;
}