dl_codes

Ass7_OCR.ipynb

assignment6Dl.ipynb

assignment6Dl_updated.ipynb

Assignment_8.ipynb

bfs.cpp

#include <iostream>
#include <vector>
#include <queue>
#include <omp.h>

using namespace std;

struct Node {
  int id;
  vector<int> neighbors;
  bool visited;

  Node(int id) {
    this->id = id;
    visited = false;
  }
};

void bfs(vector<Node> &nodes, int start) {
  queue<int> queue;
  queue.push(start);

  while (!queue.empty()) {
    int current = queue.front();
    queue.pop();

    cout << current << " ";

    #pragma omp parallel for
    for (int neighbor : nodes[current].neighbors) {
      if (!nodes[neighbor].visited) {
        nodes[neighbor].visited = true;
        queue.push(neighbor);
      }
    }
  }
}

int main() {
  int n;
  cout << "Enter the number of nodes: ";
  cin >> n;

  vector<Node> nodes;

  for (int i = 0; i < n; i++) {
    nodes.push_back(Node(i));
  }

  for (int i = 0; i < n; i++) {
    int num_neighbors;
    cout << "Enter the number of neighbors for node " << i + 1 << ": ";
    cin >> num_neighbors;

    for (int j = 0; j < num_neighbors; j++) {
      int neighbor;
      cout << "Enter the neighbor " << j + 1 << " for node " << i + 1 << ": ";
      cin >> neighbor;

      nodes[i].neighbors.push_back(neighbor);
    }
  }

  nodes[0].visited = true;

  bfs(nodes, 0);

  cout << endl;

  return 0;
}

dfs.cpp

#include <iostream>
#include <vector>
#include <stack>
#include <omp.h>

void parallelDFS(const std::vector<std::vector<int> >& graph, int startVertex, std::vector<bool>& visited) {
    std::stack<int> dfsStack;
    dfsStack.push(startVertex);
    
    while (!dfsStack.empty()) {
        int currentVertex = dfsStack.top();
        dfsStack.pop();
        
        if (!visited[currentVertex]) {
            std::cout << "Visiting vertex: " << currentVertex << std::endl;
            visited[currentVertex] = true;
            
            #pragma omp parallel for num_threads(4)
            for (int i = 0; i < graph[currentVertex].size(); ++i) {
                int neighborVertex = graph[currentVertex][i];
                if (!visited[neighborVertex]) {
                    #pragma omp critical
                    dfsStack.push(neighborVertex);
                }
            }
        }
    }
}

int main() {
    int numVertices;
    std::cout << "Enter the number of vertices: ";
    std::cin >> numVertices;
    
    std::vector<std::vector<int> > graph(numVertices);
     
    std::cout << "Enter the adjacency list for each vertex:\n";
    for (int i = 0; i < numVertices; ++i) {
        int numNeighbors;
        std::cout << "Enter the number of neighbors for vertex " << i << ": ";
        std::cin >> numNeighbors;
        
        std::cout << "Enter the neighbors for vertex " << i << ": ";
        for (int j = 0; j < numNeighbors; ++j) {
            int neighborVertex;
            std::cin >> neighborVertex;
            graph[i].push_back(neighborVertex);
        }
    }
    
    int startVertex;
    std::cout << "Enter the start vertex: ";
    std::cin >> startVertex;
    
    std::vector<bool> visited(numVertices, false);
    
    #pragma omp parallel
    {
        #pragma omp single
        {
            parallelDFS(graph, startVertex, visited);
        }
    }
    
    return 0;
}

min_max.c

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

#define ARRAY_SIZE 1000

int main() {
    int array[ARRAY_SIZE];
    int min, max, sum;
    double avg;
    double start_time, end_time;

    // Initialize the array with random values
    for (int i = 0; i < ARRAY_SIZE; i++) {
        array[i] = rand() % 1000;
    }

    // Initialize reduction variables
    min = array[0];
    max = array[0];
    sum = 0;

    // Start timing
    start_time = omp_get_wtime();

    // Compute reduction using parallel reduction pragma
    #pragma omp parallel for reduction(min:min) reduction(max:max) reduction(+:sum)
    for (int i = 0; i < ARRAY_SIZE; i++) {
        sum += array[i];
        if (array[i] < min) {
            min = array[i];
        }
        if (array[i] > max) {
            max = array[i];
        }
    }

    // Compute average
    avg = (double)sum / ARRAY_SIZE;

    // End timing
    end_time = omp_get_wtime();

    // Print the results
    printf("Array: ");
    for (int i = 0; i < ARRAY_SIZE; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    printf("Minimum: %d\n", min);
    printf("Maximum: %d\n", max);
    printf("Sum: %d\n", sum);
    printf("Average: %.2f\n", avg);

    printf("Execution time: %.6f seconds\n", end_time - start_time);

    return 0;
}

parallel_bsort.cpp

#include <iostream>
#include <vector>
#include <omp.h>
#include <chrono>

using namespace std;

void bubbleSort(vector<int>& arr) {
  int n = arr.size();

  #pragma omp parallel for
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

int main() {
  int n;
  cout << "Enter the number of elements: ";
  cin >> n;

  vector<int> arr(n);

  for (int i = 0; i < n; i++) {
    cout << "Enter element " << i + 1 << ": ";
    cin >> arr[i];
  }

  cout << "Unsorted array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;

  // Bubble sort.
  cout << "Sequential bubble sort: ";
  auto start = std::chrono::high_resolution_clock::now();
  bubbleSort(arr);
  auto end = std::chrono::high_resolution_clock::now();
  std::chrono::duration<double> elapsed = end - start;
  cout << elapsed.count() << " seconds" << endl;
  
  cout << "Sorted array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;

  // Parallel bubble sort.
  cout << "Parallel bubble sort: ";
  start = std::chrono::high_resolution_clock::now();
  #pragma omp parallel
  bubbleSort(arr);
  end = std::chrono::high_resolution_clock::now();
  elapsed = end - start;
  cout << elapsed.count() << " seconds" << endl;

  return 0;
}

parallel_msort.cpp

#include <iostream>
#include <vector>
#include <omp.h>
#include <chrono>

using namespace std;

bool isSorted(const vector<int>& arr) {
  int n = arr.size();
  for (int i = 1; i < n; i++) {
    if (arr[i] < arr[i - 1]) {
      return false;
    }
  }
  return true;
}

void merge(vector<int>& arr, int low, int mid, int high) {
  int i = low;
  int j = mid + 1;
  vector<int> merged(high - low + 1);

  for (int k = 0; k < merged.size(); k++) {
    if (i > mid) {
      merged[k] = arr[j++];
    } else if (j > high) {
      merged[k] = arr[i++];
    } else if (arr[i] <= arr[j]) {
      merged[k] = arr[i++];
    } else {
      merged[k] = arr[j++];
    }
  }

  for (int k = 0; k < merged.size(); k++) {
    arr[low + k] = merged[k];
  }
}

void mergeSort(vector<int>& arr, int low, int high) {
  if (low < high) {
    int mid = (low + high) / 2;

    // Recursively sort the left and right halves.
    mergeSort(arr, low, mid);
    mergeSort(arr, mid + 1, high);

    // Merge the sorted halves.
    #pragma omp parallel
    {
      #pragma omp for
      for (int i = low; i <= high; i++) {
        // Do nothing, just for parallelization.
      }

      merge(arr, low, mid, high);
    }
  }
}

int main() {
  int n;
  cout << "Enter the number of elements: ";
  cin >> n;

  vector<int> arr(n);

  for (int i = 0; i < n; i++) {
    cout << "Enter element " << i + 1 << ": ";
    cin >> arr[i];
  }

  cout << "Unsorted array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;

  // Merge sort.
  cout << "Sequential merge sort: ";
  auto start = std::chrono::high_resolution_clock::now();
  mergeSort(arr, 0, n - 1);
  auto end = std::chrono::high_resolution_clock::now();
  std::chrono::duration<double> elapsed = end - start;
  cout << elapsed.count() << " seconds" << endl;
  
  // Parallel merge sort.
  cout << "Parallel merge sort: ";
  start = std::chrono::high_resolution_clock::now();
  #pragma omp parallel
  {
    #pragma omp single
    mergeSort(arr, 0, n - 1);
  }
  end = std::chrono::high_resolution_clock::now();
  elapsed = end - start;
  cout << elapsed.count() << " seconds" << endl;

  cout << "Sorted array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;

  // Check if the array is sorted.
  if (isSorted(arr)) {
    cout << "The array is sorted." << endl;
  } else {
    cout << "The array is not sorted." << endl;
 
}
return 0;
}