SET A

1 Sort a given set of elements using the Quicksort method and determine the time required
to sort the elements. Repeat the experiment for di erent values of n, the number of
elements in the list to be sorted and plot a graph of the time taken versus n. The elements
can be read from a le or can be generated using the random number generator.

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

// Function to swap two elements

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

// Partition function for Quicksort

int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Choose the rightmost element as pivot
int i = (low - 1); // Index of smaller element

for (int j = low; j <= high - 1; j++) {

// If current element is smaller than the pivot
if (arr[j] < pivot) {
i++; // Increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

// Quicksort function
void quicksort(int arr[], int low, int high) {
if (low < high) {
// Partition the array
int pi = partition(arr, low, high);

// Recursively sort elements before partition and after partition

quicksort(arr, low, pi - 1);
quicksort(arr, pi + 1, high);
}
}

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

// Dynamically allocate memory for the array

int *arr = (int*)malloc(n * sizeof(int));

// Generate random numbers and ll the array

srand(time(NULL));
for (int i = 0; i < n; i++) {
arr[i] = rand() % 100; // Generates random numbers between 0 and 99
}
fi
fi
ff
 // Perform Quicksort
clock_t start = clock();
quicksort(arr, 0, n - 1);
clock_t end = clock();

// Calculate the time taken

double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Time taken to sort %d elements: %lf seconds\n", n, time_taken);

// Free dynamically allocated memory

free(arr);

return 0;
}

Output:

2. Implement a parallelized Merge Sort algorithm to sort a given set of elements and
determine the time required to sort the elements. Repeat the experiment for di erent values
of n, the number of elements in the list to be sorted and plot a graph of the time taken
versus n. The elements can be read from a le or can be generated using the random
number generator.

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

// Function to merge two sorted subarrays arr[l..m] and arr[m+1..r]

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

// Create temporary arrays

int L[n1], R[n2];

// Copy data to temporary arrays L[] and R[]

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

// Merge the temporary arrays back into arr[l..r]

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

// Copy the remaining elements of L[], if any

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

// Copy the remaining elements of R[], if any

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

// Parallelized Merge Sort function

void mergeSort(int arr[], int l, int r) {
if (l < r) {
// Calculate mid point
int m = l + (r - l) / 2;

// Sort rst and second halves

#pragma omp task
mergeSort(arr, l, m);
#pragma omp task
mergeSort(arr, m + 1, r);

// Merge the sorted halves

#pragma omp taskwait
merge(arr, l, m, r);
}
}

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

// Dynamically allocate memory for the array

int *arr = (int*)malloc(n * sizeof(int));

// Generate random numbers and ll the array

srand(time(NULL));
for (int i = 0; i < n; i++) {
arr[i] = rand() % 100; // Generates random numbers between 0 and 99
}

// Start measuring time

double start_time = omp_get_wtime();

// Perform parallelized Merge Sort

#pragma omp parallel
{
#pragma omp single nowait
fi
fi
 mergeSort(arr, 0, n - 1);
}

// End measuring time

double end_time = omp_get_wtime();

// Calculate the time taken

double time_taken = end_time - start_time;
printf("Time taken to sort %d elements: %lf seconds\n", n, time_taken);

// Free dynamically allocated memory

free(arr);

return 0;
}

Output :

3. Obtain the Topological ordering of vertices in a given digraph. b. Compute the transitive
closure of a given directed graph using Warshall's algorithm

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

#de ne MAX_VERTICES 100

struct Node {
int data;
struct Node* next;
};

struct Graph {
int numVertices;
struct Node** adjLists;
int* visited;
};

// Create a new node

struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// Create a graph with 'numVertices' vertices

struct Graph* createGraph(int numVertices) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->numVertices = numVertices;
fi
 graph->adjLists = (struct Node**)malloc(numVertices * sizeof(struct Node*));
graph->visited = (int*)malloc(numVertices * sizeof(int));

for (int i = 0; i < numVertices; i++) {

graph->adjLists[i] = NULL;
graph->visited[i] = 0;
}

return graph;
}

// Add an edge to the graph

void addEdge(struct Graph* graph, int src, int dest) {
// Add edge from src to dest
struct Node* newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
}

// Depth- rst search to perform topological sorting

void topologicalSortUtil(struct Graph* graph, int v, int* visited, struct Node** stack) {
visited[v] = 1;

struct Node* temp = graph->adjLists[v];

while (temp != NULL) {
int adjVertex = temp->data;
if (!visited[adjVertex]) {
topologicalSortUtil(graph, adjVertex, visited, stack);
}
temp = temp->next;
}

// Push current vertex to stack when all its adjacent vertices are visited
*stack = createNode(v);
(*stack)->next = graph->adjLists[v];
graph->adjLists[v] = *stack;
}

// Perform topological sorting using DFS

void topologicalSort(struct Graph* graph) {
struct Node* stack = NULL;

// Mark all the vertices as not visited

int* visited = (int*)calloc(graph->numVertices, sizeof(int));

// Call the recursive helper function to store topological

// sort starting from all vertices one by one
for (int i = 0; i < graph->numVertices; i++) {
if (!visited[i]) {
topologicalSortUtil(graph, i, visited, &stack);
}
}

// Print the contents of the stack

printf("Topological ordering of vertices: ");
while (stack != NULL) {
printf("%d ", stack->data);
stack = stack->next;
}
printf("\n");
fi
 free(visited);
}

int main() {
int numVertices, numEdges;
printf("Enter the number of vertices: ");
scanf("%d", &numVertices);
printf("Enter the number of edges: ");
scanf("%d", &numEdges);

struct Graph* graph = createGraph(numVertices);

printf("Enter the edges (source destination):\n");

for (int i = 0; i < numEdges; i++) {
int src, dest;
scanf("%d %d", &src, &dest);
addEdge(graph, src, dest);
}

// Perform topological sorting

topologicalSort(graph);

return 0;
}

Output:

4 Implement 0/1 Knapsack problem using Dynamic Programming.

#include<stdio.h>

// Function to nd maximum of two integers

int max(int a, int b) {
return (a > b) ? a : b;
}
fi
 // Function to solve 0/1 Knapsack problem using dynamic programming
int knapsack(int W, int wt[], int val[], int n) {
int i, w;
int K[n + 1][W + 1];

// Build K[][] table in bottom-up manner

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 val[] = {60, 100, 120};
int wt[] = {10, 20, 30};
int W = 50;
int n = sizeof(val) / sizeof(val[0]);

printf("Maximum value that can be obtained is %d\n", knapsack(W, wt, val, n));
return 0;
}

Output:

5 From a given vertex in a weighted connected graph, nd shortest paths to other vertices
using Dijkstra's algorithm.

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

#de ne V 6 // Number of vertices in the graph

// Function to nd the vertex with minimum distance value

int minDistance(int dist[], int visited[]) {
int min = INT_MAX, min_index;

for (int v = 0; v < V; v++) {

if (visited[v] == 0 && dist[v] <= min) {
min = dist[v];
min_index = v;
}
fi
fi
fi
 }

return min_index;
}

// Function to print the constructed distance array

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

// Function to implement Dijkstra's algorithm

void dijkstra(int graph[V][V], int src) {
int dist[V]; // The output array. dist[i] will hold the shortest distance from src to i
int visited[V]; // visited[i] will be true if vertex i is included in the shortest path tree or shortest
distance from src to i is nalized

// Initialize all distances as INFINITE and visited[] as false

for (int i = 0; i < V; i++) {
dist[i] = INT_MAX;
visited[i] = 0;
}

// Distance of source vertex from itself is always 0

dist[src] = 0;

// Find shortest path for all vertices

for (int count = 0; count < V - 1; count++) {
// Pick the minimum distance vertex from the set of vertices not yet processed.
// u is always equal to src in the rst iteration.
int u = minDistance(dist, visited);

// Mark the picked vertex as processed

visited[u] = 1;

// Update dist value of the adjacent vertices of the picked vertex.

for (int v = 0; v < V; v++) {
// Update dist[v] only if is not in visited[], there is an edge from u to v, and total weight of
path from src to v through u is smaller than current value of dist[v]
if (!visited[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
{
dist[v] = dist[u] + graph[u][v];
}
}
}

// Print the constructed distance array

printSolution(dist);
}

int main() {
fi
fi
 // Sample graph represented as an adjacency matrix
int graph[V][V] = {
{0, 10, 0, 5, 0, 0},
{0, 0, 1, 2, 0, 0},
{0, 0, 0, 0, 4, 0},
{0, 3, 9, 0, 2, 8},
{0, 0, 0, 0, 0, 6},
{0, 0, 0, 0, 0, 0}
};

int src = 0; // Source vertex

dijkstra(graph, src);

return 0;
}

Output:

6 Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal's algorithm.

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

#de ne MAX_VERTICES 100

#de ne MAX_EDGES 100

// Structure to represent an edge in the graph

struct Edge {
int src, dest, weight;
};

// Structure to represent a subset for union- nd

struct Subset {
int parent;
int rank;
};

// Function to create a graph

struct Edge* createGraph(int numVertices, int numEdges) {
fi
fi
fi
 struct Edge* graph = (struct Edge*)malloc(numEdges * sizeof(struct Edge));
return graph;
}

// Function to nd the set of an element i (uses path compression technique)

int nd(struct Subset subsets[], int i) {
if (subsets[i].parent != i)
subsets[i].parent = nd(subsets, subsets[i].parent);
return subsets[i].parent;
}

// Function to perform union of two sets (uses union by rank)

void Union(struct Subset subsets[], int x, int y) {
int xroot = nd(subsets, x);
int yroot = nd(subsets, y);

if (subsets[xroot].rank < subsets[yroot].rank)

subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}

// Function to compare two edges based on their weights

int compare(const void* a, const void* b) {
struct Edge* a1 = (struct Edge*)a;
struct Edge* b1 = (struct Edge*)b;
return a1->weight - b1->weight;
}

// Function to nd the Minimum Cost Spanning Tree using Kruskal's algorithm

void KruskalMST(struct Edge* graph, int numVertices, int numEdges) {
struct Edge result[numVertices]; // Array to store the resultant MST
int e = 0; // Index variable for result[]
int i = 0; // Index variable for sorted edges
int cost = 0; // Initialize result

// Sort all the edges in non-decreasing order of their weight

qsort(graph, numEdges, sizeof(graph[0]), compare);

// Allocate memory for creating V subsets

struct Subset* subsets = (struct Subset*)malloc(numVertices * sizeof(struct Subset));

// Create V subsets with single elements

for (int v = 0; v < numVertices; ++v) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
fi
fi
fi
fi
fi
fi
 // Number of edges to be taken is equal to numVertices-1
while (e < numVertices - 1 && i < numEdges) {
// Pick the smallest edge and increment the index for the next iteration
struct Edge next_edge = graph[i++];

int x = nd(subsets, next_edge.src);

int y = nd(subsets, next_edge.dest);

// If including this edge doesn't cause cycle, include it in the result and increment the index for
result[]
if (x != y) {
result[e++] = next_edge;
Union(subsets, x, y);
}
}

// Print the contents of result[] to display the MST

printf("Edges of Minimum Cost Spanning Tree:\n");
for (i = 0; i < e; ++i) {
printf("%d -- %d == %d\n", result[i].src, result[i].dest, result[i].weight);
cost += result[i].weight;
}
printf("Minimum Cost Spanning Tree Weight: %d\n", cost);

free(subsets);
}

int main() {
int numVertices, numEdges;
printf("Enter the number of vertices and edges: ");
scanf("%d %d", &numVertices, &numEdges);

struct Edge* graph = createGraph(numVertices, numEdges);

printf("Enter the source, destination, and weight of each edge:\n");

for (int i = 0; i < numEdges; ++i) {
scanf("%d %d %d", &graph[i].src, &graph[i].dest, &graph[i].weight);
}

KruskalMST(graph, numVertices, numEdges);

free(graph);
return 0;
}

Output:

7. a. Print all the nodes reachable from a given starting node in a digraph using BFS method.
fi
fi
 #include <stdio.h>
#include <stdlib.h>

#de ne MAX_VERTICES 100

// Structure to represent a node in adjacency list

struct Node {
int data;
struct Node* next;
};

// Structure to represent the graph

struct Graph {
int numVertices;
struct Node** adjLists;
int* visited;
};

// Function to create a new node

struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// Function to create a graph with 'numVertices' vertices

struct Graph* createGraph(int numVertices) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->numVertices = numVertices;
graph->adjLists = (struct Node**)malloc(numVertices * sizeof(struct Node*));
graph->visited = (int*)malloc(numVertices * sizeof(int));

for (int i = 0; i < numVertices; i++) {

graph->adjLists[i] = NULL;
graph->visited[i] = 0;
}

return graph;
}
fi
// Function to add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
// Add edge from src to dest
struct Node* newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
}

// Function to perform Breadth-First Search (BFS)

void BFS(struct Graph* graph, int startVertex) {
// Create a queue for BFS
int queue[MAX_VERTICES];
int front = -1, rear = -1;

// Mark the current node as visited and enqueue it

graph->visited[startVertex] = 1;
queue[++rear] = startVertex;

printf("Nodes reachable from vertex %d using BFS: ", startVertex);

while (front != rear) {

// Dequeue a vertex from queue
int currentVertex = queue[++front];
printf("%d ", currentVertex);

// Get all adjacent vertices of the dequeued vertex currentVertex

// If an adjacent vertex has not been visited, then mark it visited and enqueue it
struct Node* temp = graph->adjLists[currentVertex];
while (temp) {
int adjVertex = temp->data;
if (!graph->visited[adjVertex]) {
graph->visited[adjVertex] = 1;
queue[++rear] = adjVertex;
}
temp = temp->next;
}
}
printf("\n");
}

int main() {
int numVertices, numEdges;
printf("Enter the number of vertices: ");
scanf("%d", &numVertices);

struct Graph* graph = createGraph(numVertices);

printf("Enter the number of edges: ");

scanf("%d", &numEdges);

printf("Enter the edges (source destination):\n");

 for (int i = 0; i < numEdges; i++) {
int src, dest;
scanf("%d %d", &src, &dest);
addEdge(graph, src, dest);
}

int startVertex;
printf("Enter the starting vertex for BFS: ");
scanf("%d", &startVertex);

BFS(graph, startVertex);

return 0;
}

Output:

8. Find Minimum Cost Spanning Tree of a given undirected graph using Prim’s algorithm.

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

#de ne MAX_VERTICES 100

// Function to nd the vertex with minimum key value, from the set of vertices not yet included in
MST
int minKey(int key[], int mstSet[], int numVertices) {
int min = INT_MAX, min_index;

for (int v = 0; v < numVertices; v++) {

if (mstSet[v] == 0 && key[v] < min) {
min = key[v];
min_index = v;
}
}
fi
fi
 return min_index;
}

// Function to print the MST using the constructed parent array

void printMST(int parent[], int graph[MAX_VERTICES][MAX_VERTICES], int numVertices) {
printf("Edge \tWeight\n");
for (int i = 1; i < numVertices; i++) {
printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
}
}

// Function to construct and print MST for a graph represented using adjacency matrix
void primMST(int graph[MAX_VERTICES][MAX_VERTICES], int numVertices) {
int parent[MAX_VERTICES]; // Array to store constructed MST
int key[MAX_VERTICES]; // Key values used to pick minimum weight edge in cut
int mstSet[MAX_VERTICES]; // To represent set of vertices included in MST

// Initialize all keys as INFINITE

for (int i = 0; i < numVertices; i++) {
key[i] = INT_MAX;
mstSet[i] = 0;
}

// Always include rst vertex in MST. Make key 0 so that this vertex is picked as rst vertex.
key[0] = 0;
parent[0] = -1; // First node is always root of MST

// The MST will have V vertices

for (int count = 0; count < numVertices - 1; count++) {
// Pick the minimum key vertex from the set of vertices not yet included in MST
int u = minKey(key, mstSet, numVertices);

// Add the picked vertex to the MST set

mstSet[u] = 1;

// Update key value and parent index of the adjacent vertices of the picked vertex
// Consider only those vertices which are not yet included in MST
for (int v = 0; v < numVertices; v++) {
// graph[u][v] is non-zero only for adjacent vertices of u
// mstSet[v] is false for vertices not yet included in MST
// Update the key only if graph[u][v] is smaller than key[v]
if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}

// Print the constructed MST

printMST(parent, graph, numVertices);
}
fi
fi
 int main() {
int numVertices;
printf("Enter the number of vertices: ");
scanf("%d", &numVertices);

int graph[MAX_VERTICES][MAX_VERTICES];
printf("Enter the adjacency matrix:\n");
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
scanf("%d", &graph[i][j]);
}
}

// Print the Minimum Cost Spanning Tree (MST) using Prim's algorithm
primMST(graph, numVertices);

return 0;
}

Output:

9. Implement All-Pairs Shortest Paths Problem using Floyd's algorithm.

#include <stdio.h>
#include <limits.h>

#de ne MAX_VERTICES 100

// Function to nd the shortest paths between all pairs of vertices using Floyd's algorithm
void oydWarshall(int graph[MAX_VERTICES][MAX_VERTICES], int numVertices) {
int dist[MAX_VERTICES][MAX_VERTICES];

// Initialize the distance matrix with the given graph

for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
dist[i][j] = graph[i][j];
fi
fl
fi
 }
}

// Find shortest paths between all pairs of vertices

for (int k = 0; k < numVertices; k++) {
// Pick all vertices as source one by one
for (int i = 0; i < numVertices; i++) {
// Pick all vertices as destination for the above picked source
for (int j = 0; j < numVertices; j++) {
// If vertex k is on the shortest path from i to j, then update the value of dist[i][j]
if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][k] + dist[k][j] < dist[i]
[j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}

// Print the shortest distances between all pairs of vertices

printf("Shortest distances between all pairs of vertices:\n");
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
if (dist[i][j] == INT_MAX) {
printf("INF ");
} else {
printf("%d ", dist[i][j]);
}
}
printf("\n");
}
}

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

int graph[MAX_VERTICES][MAX_VERTICES];
printf("Enter the adjacency matrix:\n");
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
scanf("%d", &graph[i][j]);
}
}

// Find and print shortest paths between all pairs of vertices

oydWarshall(graph, numVertices);

return 0;
}

Output:
fl
 10. Implement N Queen's problem using Back Tracking.

#include <stdio.h>
#include <stdbool.h>

#de ne N 8 // De ne the number of queens (8x8 chessboard)

// Function to print the solution matrix

void printSolution(int board[N][N]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
printf("%d ", board[i][j]);
}
printf("\n");
}
}

// Function to check if it's safe to place a queen at position (row, col)

bool isSafe(int board[N][N], int row, int col) {
int i, j;

// Check this row on the left side

for (i = 0; i < col; i++) {
if (board[row][i]) {
return false;
}
}

// Check upper diagonal on left side

for (i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j]) {
return false;
}
fi
fi
 }

// Check lower diagonal on left side

for (i = row, j = col; j >= 0 && i < N; i++, j--) {
if (board[i][j]) {
return false;
}
}

return true;
}

// Recursive function to solve N Queen problem

bool solveNQueens(int board[N][N], int col) {
// If all queens are placed then return true
if (col >= N) {
return true;
}

// Consider this column and try placing this queen in all rows one by one
for (int i = 0; i < N; i++) {
// Check if the queen can be placed on board[i][col]
if (isSafe(board, i, col)) {
// Place this queen in board[i][col]
board[i][col] = 1;

// Recur to place rest of the queens

if (solveNQueens(board, col + 1)) {
return true;
}

// If placing queen in board[i][col] doesn't lead to a solution, then remove queen from
board[i][col]
board[i][col] = 0; // BACKTRACK
}
}

// If the queen can't be placed in any row in this column col then return false
return false;
}

// Wrapper function to solve N Queen problem

void solveNQueensWrapper() {
int board[N][N] = {0}; // Initialize all values to 0

if (solveNQueens(board, 0) == false) {
printf("Solution does not exist");
return;
}

printSolution(board);
}
int main() {
solveNQueensWrapper();
return 0;
}

Output: