---ADA---

//------------------------SELECTION SORT------------------------//


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void selection_sort(int arr[], int n) {
    int i, j, min_idx, temp;
    for(i = 0; i < n - 1; i++) {
        min_idx = i;
        for(j = i + 1; j < n; j++) {
            if(arr[j] < arr[min_idx])
                min_idx = j;
        }
        if(min_idx != i) {
            temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }
}
void printArray(int arr[], int size) {
    int i;
    for(i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
int main(void) {
    int i, n;
    clock_t start, end;
    double cpu_time_used;
    printf("Enter the value of n: ");
    scanf("%d", &n);
    int arr[n];

    for(i = 0; i < n; i++) {
        arr[i] = rand() % 1000;
        printf("%d", arr[i]);
    }

    start = clock();
    selection_sort(arr, n);
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("Sorted array:\n");
    printArray(arr, n);
    printf("Execution time: %f seconds\n", cpu_time_used);
    return 0;
}


//------------------------QUICK SORT------------------------//


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

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

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

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

int main(void) {
    int i, n;
    clock_t start, end;
    double cpu_time_used;
    printf("Enter the value of n: ");
    scanf("%d", &n);
    int arr[n];
    for(i = 0; i < n; i++) {
        arr[i] = rand() % 1000;
        printf("%d", arr[i]);
    }
    start = clock();
    quickSort(arr, 0, n - 1);
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("\nSorted array: ");
    for(i = 0; i < n; i++)
        printf("%d", arr[i]);

    printf("\nExecution time: %f seconds\n", cpu_time_used);
    return 0;
}


//------------------------MERGE SORT------------------------//


#include <stdio.h>
#include <stdlib.h>
#include <time.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++];
        } else {
            arr[k++] = R[j++];
        }
    }

    while(i < n1)
        arr[k++] = L[i++];
    while(j < n2)
        arr[k++] = R[j++];
}

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

int main(void) {
    int i, n;
    clock_t start, end;
    double cpu_time_used;
    printf("Enter the value of n: ");
    scanf("%d", &n);
    int arr[n];
    for(i = 0; i < n; i++) {
        arr[i] = rand() % 1000;
        printf("%d ", arr[i]);
    }
    start = clock();
    mergeSort(arr, 0, n - 1);
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("\nSorted array: ");
    for(i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\nExecution time: %f seconds\n", cpu_time_used);
    return 0;
}


//------------------------PRIM'S ALGORITHM------------------------//


#include <stdio.h>

void my_prim(int adj[][10], int N) {
    int i, j, nv, min, min_cost = 0, u = 0, v = 0;
    int visit[10] = {0};
    visit[0] = 1;
    nv = 1;
    while (nv < N) {
        min = 999;
        for (i = 0; i < N; i++) {
            if (visit[i] == 1) {
                for (j = 0; j < N; j++) {
                    if (!visit[j] && adj[i][j] < min) {
                        min = adj[i][j];
                        u = i;
                        v = j;
                        printf("\nConsidering edge (%d, %d) with weight %d", i, j, adj[i][j]);
                    }
                }
            }
        }
        adj[u][v] = 999;
        adj[v][u] = 999;

        if (visit[u] == 1 && visit[v] == 0) {
            visit[v] = 1;
            min_cost += min;
            nv++;
            printf("\nEdge %d --> %d : (%d)\n", u, v, min);
        }
    }
    printf("Minimum cost : %d\n", min_cost);
}

int main() {
    int adj[10][10], N, i, j;
    printf("Enter number of nodes in the graph: ");
    scanf("%d", &N);

    printf("Enter the adjacency matrix\n");
    printf("Enter 0 for no connection and weights for connection\n");

    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            scanf("%d", &adj[i][j]);
            if (adj[i][j] == 0) {
                adj[i][j] = 999;
            }
        }
    }
    my_prim(adj, N);
    return 0;
}


//------------------------KRUSKAL'S ALGORITHM------------------------//


#include <stdio.h>

int ne = 1, min_cost = 0;

int main(void) {
    int n, i, j, min, a, b, u, v, cost[20][20], parent[20];
    printf("Enter the number of vertices: ");
    scanf("%d", &n);
    printf("\nEnter the cost matrix: ");
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            scanf("%d", &cost[i][j]);
    for (i = 1; i <= n; i++)
        parent[i] = 0;
    printf("\nThe edges of spanning tree are\n");

    while (ne < n) {
        min = 999;
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                if (cost[i][j] < min && cost[i][j] != 0) {
                    min = cost[i][j];
                    a = u = i;
                    b = v = j;
                }
            }
        }
        while (parent[u]) u = parent[u];
        while (parent[v]) v = parent[v];
        if (u != v) {
            printf("Edge %d\t(%d --> %d) = %d\n", ne++, a, b, min);
            min_cost += min;
            parent[v] = u;
        }
        cost[a][b] = cost[b][a] = 999;
    }
    printf("\nMinimum cost = %d\n", min_cost);
}


//------------------------DIJKSTRA'S ALGORITHM------------------------//


#include <stdio.h>
#define infinity 999

void dij(int n, int v, int cost[10][10], int dist[10]) {
    int i, u, count, w, flag[10], min;
    for (i = 1; i <= n; i++) {
        flag[i] = 0;
        dist[i] = cost[v][i];
    }
    count = 2;
    while (count <= n) {
        min = infinity;
        for (w = 1; w <= n; w++) {
            if (dist[w] < min && !flag[w]) {
                min = dist[w];
                u = w;
            }
        }
        flag[u] = 1;
        count++;
        for (w = 1; w <= n; w++) {
            if ((dist[u] + cost[u][w] < dist[w]) && !flag[w])
                dist[w] = dist[u] + cost[u][w];
        }
    }
}

int main(void) {
    int n, v, i, j, cost[10][10], dist[10];
    printf("\nEnter the number of nodes: ");
    scanf("%d", &n);

    printf("Enter the cost 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] = infinity;
        }
    }
    printf("\nEnter the source vertex: ");
    scanf("%d", &v);
    dij(n, v, cost, dist);
    printf("\nShortest Path:\n");
    for (i = 1; i <= n; i++) {
        if (i != v)
            printf("%d --> %d, cost = %d\n", v, i, dist[i]);
    }
}


//-----------------PROGRAM 3a: Floyd's Algo.-----------------//

#include <stdio.h>

int min(int a, int b) {
    return (a < b) ? a : b;
}
void floyd(int p[10][10], int n) {
    int i, j, k;
    for (k = 1; k <= n; k++) {
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                p[i][j] = min(p[i][j], p[i][k] + p[k][j]);
            }
        }
    }
}
int main(void) {
    int a[10][10], n, i, j;
    printf("Enter value of n: ");
    scanf("%d", &n);
    printf("Enter the graph data:\n");
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]);
            if (i != j && a[i][j] == 0) a[i][j] = 999;
        }
    }
    floyd(a, n);
    printf("Shortest path matrix:\n");
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }
}

//-----------------PROGRAM 3b: Warshall's Algo.-----------------//

#include <stdio.h>

void warshall(int[10][10], int);

int main(void) {
    int a[10][10], i, j, n;
    printf("Enter the no. of nodes: ");
    scanf("%d", &n);
    printf("Enter the adjacency matrix:\n");
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);
    printf("The adjacency matrix is:\n");
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }
    warshall(a, n);
}

void warshall(int p[10][10], int n) {
    int i, j, k;
    for (k = 1; k <= n; k++) {
        for (j = 1; j <= n; j++) {
            for (i = 1; i <= n; i++) {
                if ((p[i][j] == 0) && (p[i][k] == 1) && (p[k][j] == 1))
                    p[i][j] = 1;
            }
        }
    }
    printf("The path matrix is:\n");
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            printf("%d ", p[i][j]);
        }
        printf("\n");
    }
}

//-----------------PROGRAM 5: Topological Sorting-----------------//

#include <stdio.h>
int a[10][10], n, indegree[10];

void find_indegree() {
    int j, i, sum;
    for (j = 0; j < n; j++) {
        sum = 0;
        for (i = 0; i < n; i++)
            sum += a[i][j];
        indegree[j] = sum;
    }
}

void topology() {
    int i, u, v, t[10], s[10], top = -1, k = 0;
    find_indegree();
    for (i = 0; i < n; i++) {
        if (indegree[i] == 0) s[++top] = i;
    }

    while (top != -1) {
        u = s[top--];
        t[k++] = u;
        for (v = 0; v < n; v++) {
            if (a[u][v] == 1) {
                indegree[v]--;
                if (indegree[v] == 0) s[++top] = v;
            }
        }
    }
    printf("The topological sequence is:\n");
    for (i = 0; i < n; i++)
        printf("%d ", t[i]);
    printf("\n");
}

int main(void) {
    int i, j;
    printf("Enter number of nodes: ");
    scanf("%d", &n);
    printf("Enter adjacency matrix:\n");
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            scanf("%d", &a[i][j]);
    topology();
}

//-----------------PROGRAM 6: Knapsack 0/1-----------------//

#include <stdio.h>

int w[10], p[10], v[10][10], n, i, j, cap, x[10] = {0};

int max(int i, int j) {
    return (i > j ? i : j);
}

int knap(int i, int j) {
    int value;
    if (v[i][j] < 0) {
        if (j < w[i])
            value = knap(i - 1, j);
        else
            value = max(knap(i - 1, j), p[i] + knap(i - 1, j - w[i]));
        v[i][j] = value;
    }
    return v[i][j];
}

int main(void) {
    int profit, count = 0;
    printf("\nEnter the number of elements: ");
    scanf("%d", &n);
    printf("Enter the profits and weights of the elements:\n");
    for (i = 1; i <= n; i++) {
        printf("For item no. %d\n", i);
        scanf("%d%d", &p[i], &w[i]);
    }
    printf("\nEnter the capacity: ");
    scanf("%d", &cap);
    for (i = 0; i <= n; i++) {
        for (j = 0; j <= cap; j++) {
            if ((i == 0) || (j == 0))
                v[i][j] = 0;
            else
                v[i][j] = -1;
        }
    }

    profit = knap(n, cap);
    i = n;
    j = cap;
    while (j != 0 && i != 0) {
        if (v[i][j] != v[i - 1][j]) {
            x[i] = 1;
            j = j - w[i];
            i--;
        }
        else
            i--;
    }
    printf("Items included are:\n");
    printf("S.no.\tWeight\tProfit\n");
    for (i = 1; i <= n; i++)
        if (x[i])
            printf("%d\t%d\t%d\n", ++count, w[i], p[i]);
    printf("Total profit = %d\n", profit);
}

//-----------------PROGRAM 7: Knapsack Continuous & Discrete-----------------//

#include <stdio.h>
void knapsack(int n, float weight[], float profit[], float capacity)
{
    float x[20], tp = 0;
    int i, j, u;
    u = capacity;

    for(i = 0; i < n; i++) x[i] = 0.0;

    for (i = 0; i < n; i++) {
        if (weight[i] > u)
            break;
        else {
            x[i] = 1.0;
            tp = tp + profit[i];
            u = u - weight[i];
        }
    }
    if (i < n)
        x[i] = u / weight[i];

    tp = tp + (x[i] * profit[i]);
    printf("\nThe result vector is: ");
    for (i = 0; i < n; i++)
        printf("%f\t", x[i]);

    printf("\nMaximum profit is: %f\n", tp);
}

void Dknapsack(int n, float weight[], float profit[], float capacity) {
    float x[20], tp = 0;
    int i, j, u;
    u = capacity;
    for (i = 0; i < n; i++) x[i] = 0.0;
    for (i = 0; i < n; i++) {
        if (weight[i] > u)
            continue;
        else {
            x[i] = 1.0;
            tp = tp + profit[i];
            u = u - weight[i];
        }
    }
    printf("\nThe result vector is: ");
    for (i = 0; i < n; i++) printf("%f\t", x[i]);
    printf("\nMaximum profit is: %f\n", tp);
}

int main(void) {
    float weight[20], profit[20], capacity;
    int num, i, j;
    float ratio[20], temp;

    printf("\nEnter the no. of objects: ");
    scanf("%d", &num);
    printf("\nEnter the weights of each object:\n");
    for (i = 0; i < num; i++) scanf("%f", &weight[i]);

    printf("Enter the profits of each object:\n");
    for (i = 0; i < num; i++) scanf("%f", &profit[i]);

    printf("Enter the capacity of knapsack: ");
    scanf("%f", &capacity);

    for (i = 0; i < num; i++) ratio[i] = profit[i] / weight[i];

    for (i = 0; i < num; i++) {
        for (j = i + 1; j < num; j++) {
            if (ratio[i] < ratio[j]) {
                temp = ratio[j];
                ratio[j] = ratio[i];
                ratio[i] = temp;

                temp = weight[j];
                weight[j] = weight[i];
                weight[i] = temp;

                temp = profit[j];
                profit[j] = profit[i];
                profit[i] = temp;
            }
        }
    }
    knapsack(num, weight, profit, capacity);
    Dknapsack(num, weight, profit, capacity);
    return 0;
}

//-----------------PROGRAM 8: Subset Sum-----------------//

#include <stdio.h>

int s[10], x[10], d;
void sumofsub(int, int, int);

int main(void) {
    int i, n, sum = 0;
    printf("Enter the size of the set: ");
    scanf("%d", &n);
    printf("Enter the set in increasing order:\n");
    for (i = 1; i <= n; i++)
        scanf("%d", &s[i]);
    printf("Enter the value of d: ");
    scanf("%d", &d);

    for (i = 1; i <= n; i++) sum = sum + s[i];
    if (sum < d || s[1] > d)
        printf("\nNo subset possible");
    else {
        sumofsub(0, 1, sum);
    }
}

void sumofsub(int m, int k, int r) {
    int i = 1;
    x[k] = 1;
    if ((m + s[k]) == d)
    {
        printf("Subset: ");
        for(i = 1; i <= k; i++)
            if (x[i] == 1)
                printf("%d ", s[i]);
        printf("\n");
    } else {
        if (m + s[k] + s[k + 1] <= d)
            sumofsub(m + s[k], k + 1, r - s[k]);
    }
    if ((m + r - s[k] >= d) && (m + s[k + 1] <= d)) {
        x[k] = 0;
        sumofsub(m, k + 1, r - s[k]);
    }
}

//-----------------PROGRAM 12: N Queens-----------------//

#include <stdio.h>
#include <stdlib.h>
#define MAX 50
int can_place(int c[], int r) {
    int i;
    for (i = 0; i < r; i++) {
        if (c[i] == c[r] || (abs(c[i] - c[r]) == abs(i - r)))
            return 0;
    }
    return 1;
}

void display(int c[], int n) {
    int i, j;
    char cb[10][10];
    for (i = 0; i < n; i++ )
        for (j = 0; j < n; j++)
            cb[i][j] = '-';
    for (i = 0; i < n; i++)
        cb[i][c[i]] = 'Q';

    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++)
            printf("%c", cb[i][j]);
        printf("\n");
    }
}

void n_queens(int n) {
    int r;
    int c[MAX];
    c[0] = -1;
    r = 0;
    while ( r >= 0) {
        c[r]++;
        while (c[r] < n && !can_place(c, r))
            c[r]++;
        if (c[r] < n) {
            if (r == n - 1) {
                display(c, n);
                printf("\n\n");
            }
            else {
                r++;
                c[r] = -1;
            }
        }
        else r--;
    }
}

int main(void) {
    int n;
    printf("\nEnter the number of queens: ");
    scanf("%d", &n);
    n_queens(n);
}