################### 1. Implement Matrix Multiplication algorithm through i) Sequential Algorithm, ii) Parallel Algorithm using OpenMP #############

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

#define IDX(i, j, n) ((i) * (n) + (j))

void fill_random(double *A, int n) {
    for (int i = 0; i < n * n; i++) {
        A[i] = (double)(rand() % 10);
    }
}

void matmul_serial(const double *A, const double *B, double *C, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            double sum = 0.0;
            for (int k = 0; k < n; k++) {
                sum += A[IDX(i, k, n)] * B[IDX(k, j, n)];
            }
            C[IDX(i, j, n)] = sum;
        }
    }
}

void matmul_parallel(const double *A, const double *B, double *C, int n) {
    #pragma omp parallel for
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            double sum = 0.0;
            for (int k = 0; k < n; k++) {
                sum += A[IDX(i, k, n)] * B[IDX(k, j, n)];
            }
            C[IDX(i, j, n)] = sum;
        }
    }
}

int main() {
    srand(42);

    int n = 4;
    double *A = (double *)malloc(n * n * sizeof(double));
    double *B = (double *)malloc(n * n * sizeof(double));
    double *C = (double *)malloc(n * n * sizeof(double));

    fill_random(A, n);
    fill_random(B, n);
    matmul_parallel(A, B, C, n);

    free(A);
    free(B);
    free(C);

    int sizes[] = {100, 200, 300, 400};
    int count = sizeof(sizes) / sizeof(sizes[0]);

    for (int s = 0; s < count; s++) {
        n = sizes[s];

        A = (double *)malloc(n * n * sizeof(double));
        B = (double *)malloc(n * n * sizeof(double));
        double *C1 = (double *)malloc(n * n * sizeof(double));
        double *C2 = (double *)malloc(n * n * sizeof(double));

        fill_random(A, n);
        fill_random(B, n);

        double t1 = omp_get_wtime();
        matmul_serial(A, B, C1, n);
        double t2 = omp_get_wtime();

        double t3 = omp_get_wtime();
        matmul_parallel(A, B, C2, n);
        double t4 = omp_get_wtime();

        printf("Size %d x %d: Sequential = %.6f s, Parallel = %.6f s\n",
               n, n, t2 - t1, t4 - t3);

        free(A);
        free(B);
        free(C1);
        free(C2);
    }

    return 0;
}


gcc -fopenmp matmul_openmp.c -o matmul_openmp
./matmul_openmp


#################### 2. Implement Circuit Satisfiability Problem and comment on NP-Hard by increasing number of input to Boolean circuit######################

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

int circuit(unsigned long long value, int n) {
    int result = 0;

    for (int i = 0; i < n - 1; i += 2) {
        int xi = (value >> i) & 1;
        int xj = (value >> (i + 1)) & 1;
        result = result || (xi && !xj);
    }

    return result;
}

int main() {
    int n;
    printf("Enter number of Boolean variables: ");
    scanf("%d", &n);

    unsigned long long total = 1ULL << n;
    int found = 0;

    double start = omp_get_wtime();

    #pragma omp parallel for reduction(||:found)
    for (unsigned long long i = 0; i < total; i++) {
        if (circuit(i, n)) {
            found = 1;
        }
    }

    double end = omp_get_wtime();

    printf("Circuit SAT Result: %s\n", found ? "SATISFIABLE" : "UNSATISFIABLE");
    printf("Execution Time: %.6f seconds\n", end - start);

    return 0;
}



gcc -fopenmp circuit_sat_openmp.c -o circuit_sat

export OMP_NUM_THREADS=8
./circuit_sat


################## 3. Quick Sort Algorithm using OpenMP ######################

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <omp.h>

#define CUTOFF 100

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

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

void quicksort_parallel(int arr[], int low, int high) {
    if (low < high) {
        if (high - low < CUTOFF) {
            quicksort_serial(arr, low, high);
            return;
        }

        int pi = partition(arr, low, high);

        #pragma omp task shared(arr)
        quicksort_parallel(arr, low, pi - 1);

        #pragma omp task shared(arr)
        quicksort_parallel(arr, pi + 1, high);

        #pragma omp taskwait
    }
}

void fill_random(int arr[], int n) {
    for (int i = 0; i < n; i++) arr[i] = rand() % 10000;