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


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


void floyd(int a[10][10], int n)
{
    for(int k=0;k<n;k++)
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(a[i][j]>a[i][k]+a[k][j])
                {
                    a[i][j]=a[i][k]+a[k][j];
                }
            }
        }
    }
    printf("All Pairs Shortest Path is :\n");
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            printf("%d ",a[i][j]);
        }
        printf("\n");
    }
}

int main()
{
    int cost[10][10],n;
    printf("Enter the number of vertices\n");
    scanf("%d",&n);
    printf("Enter the cost adjacency matrix\n");
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            scanf("%d",&cost[i][j]);
        }
    }

clock_t start=clock();
floyd(cost,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;
}


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


//DIJIKSTRAS 2.0
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#include <time.h>

#define MAX_V 10

int minDistance(int dist[], bool sptSet[], int V) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;
    return min_index;
}

void printSolution(int dist[], int V) {
    printf("Vertex \t\t Distance from Source\n");
    for (int i = 0; i < V; i++)
        printf("%d \t\t\t\t %d\n", i, dist[i]);
}

void dijkstra(int graph[MAX_V][MAX_V], int V, int src) {
    int dist[MAX_V];
    bool sptSet[MAX_V];
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = false;
    dist[src] = 0;
    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet, V);
        sptSet[u] = true;
        for (int v = 0; v < V; v++)
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }

    printSolution(dist, V);
}

int main() {
    int V, p, q;
    printf("Enter the number of vertices: ");
    scanf("%d", &V);

    int graph[MAX_V][MAX_V];
    printf("Enter the matrix elements:\n");
    for (p = 0; p < V; p++) {
        for (q = 0; q < V; q++) {
            scanf("%d", &graph[p][q]);
        }
    }

    clock_t start = clock();
    dijkstra(graph, V, 0);
    clock_t end = clock();

    printf("Start time is %lf\n", (double)start / CLOCKS_PER_SEC);
    printf("End time is %lf\n", (double)end / CLOCKS_PER_SEC);
    printf("Total time is %lf\n", (double)(end - start) / CLOCKS_PER_SEC);

    return 0;
}


//TSP:
#include <stdio.h>
#include<time.h>
int tsp_g[10][10];/* = {
    {12, 30, 33, 10, 45},
    {56, 22, 9, 15, 18},
    {29, 13, 8, 5, 12},
    {33, 28, 16, 10, 3},
    {1, 4, 30, 24, 20}
};*/
int visited[10], n, cost = 0;


void travellingsalesman(int c){
    int k, adj_vertex = 999;
    int min = 999;


    visited[c] = 1;


    printf("%d ", c + 1);


    for(k = 0; k < n; k++) {
        if((tsp_g[c][k] != 0) && (visited[k] == 0)) {
            if(tsp_g[c][k] < min) {
            min = tsp_g[c][k];
            }
            adj_vertex = k;
        }
    }
    if(min != 999) {
        cost = cost + min;
    }
    if(adj_vertex == 999) {
        adj_vertex = 0;
        printf("%d", adj_vertex + 1);
        cost = cost + tsp_g[c][adj_vertex];
        return;
    }
    travellingsalesman(adj_vertex);
}


int main(){
    int p,q,m;
    printf("Enter the size of adjacency matrix\n");
    scanf("%d",&m);
    printf("Enter the matrix elements\n");
    for(p=0;p<m;p++)
        for(q=0;q<m;q++)
            {
                scanf("%d",&tsp_g[p][q]);
            }
    int i, j;
    n = 5;
    for(i = 0; i < n; i++) {
        visited[i] = 0;
    }
    printf("\n\nShortest Path:\t");
    clock_t start=clock();
    travellingsalesman (0);
    clock_t end=clock();
    printf("\n minimum Cost: \t");
    printf("%d\n", cost);
    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;

}


//TSP_2
#include <stdio.h>

int tsp_g[10][10];
int visited[10], n, cost = 0;

void travellingsalesman(int c) {
  int k, adj_vertex = 999;
  int min = 999;

  visited[c] = 1;
  printf("%d ", c + 1);

  for (k = 0; k < n; k++) {
    if ((tsp_g[c][k] != 0) && (visited[k] == 0)) {
      if (tsp_g[c][k] < min) {
        min = tsp_g[c][k];
      }
      adj_vertex = k;
    }
  }
  if (min != 999) {
    cost = cost + min;
  }
  if (adj_vertex == 999) {
    adj_vertex = 0;
    printf("%d", adj_vertex + 1);
    cost = cost + tsp_g[c][adj_vertex];
    return;
  }
  travellingsalesman(adj_vertex);
}

int main() {
  int i, j;
  printf("Enter the number of vertices: \n");
  scanf("%d", &n);
  printf("Enter matrix elements:\n");
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      //printf("Enter the cost between vertex %d and vertex %d: ", i + 1, j + 1);
      scanf("%d", &tsp_g[i][j]);
    }
  }
  for (i = 0; i < n; i++) {
    visited[i] = 0;
  }
  printf("\n\nShortest Path:\t");
  travellingsalesman(0);
  printf("\n\nminimum Cost: \t");
  printf("%d\n", cost);
  return 0;
}