Q.

1 : Sort a given set of elements using the Quicksort method and determine the me required to sort the elements.
Repeat the experiment for different valuesof n, the number of elements in the list to be sorted and plot a graph of the
me taken versus n. The elements can be read from a file or can be generatedusing the random number generator.

Solu on :

import java.u l.Arrays;

import java.u l.Random;

public class QuicksortPerformance {

public sta c void main(String[] args) {

int[] sizes = {1000, 5000, 10000, 20000, 50000, 100000}; // Array sizes to test

long[] mes = new long[sizes.length]; // To store execu on mes

for (int i = 0; i < sizes.length; i++) {

int n = sizes[i];

int[] array = generateRandomArray(n);

long startTime = System.nanoTime();

quicksort(array, 0, array.length - 1);

long endTime = System.nanoTime();

mes[i] = endTime - startTime; // Store me in nanoseconds

System.out.println("Sorted " + n + " elements in " + mes[i] + " nanoseconds.");

System.out.println("Sizes: " + Arrays.toString(sizes));

System.out.println("Times (nanoseconds): " + Arrays.toString( mes));

// Export sizes and mes for graph plo ng in external tools

// Quicksort method

public sta c void quicksort(int[] arr, int low, int high) {

if (low < high) {

int pi = par on(arr, low, high);

quicksort(arr, low, pi - 1);

quicksort(arr, pi + 1, high);

// Par on method

public sta c int par on(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++;

// Swap arr[i] and arr[j]

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

// Swap arr[i+1] and arr[high] (pivot)

int temp = arr[i + 1];

arr[i + 1] = arr[high];

arr[high] = temp;

return i + 1;

// Generate a random array

public sta c int[] generateRandomArray(int size) {

Random random = new Random();

int[] array = new int[size];

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

array[i] = random.nextInt(100000); // Random number between 0 and 100000

return array;

} }
Q.2 : Implement a parallelized Merge Sort algorithm to sort a given set of elementsand determine the me required to
sort the elements. Repeat the experiment for different values of n, the number of elements in the list to be sorted
andplot a graph of the me taken versus n. The elements can be read from a file orcan be generated using the random
number generator.

import java.u l.Arrays;

import java.u l.Random;

import java.u l.concurrent.RecursiveTask;

import java.u l.concurrent.ForkJoinPool;

public class ParallelMergeSort {

public sta c void main(String[] args) {

int[] sizes = {1000, 5000, 10000, 20000, 50000, 100000}; // Array sizes to test

long[] mes = new long[sizes.length]; // To store execu on mes

ForkJoinPool pool = new ForkJoinPool(); // ForkJoinPool for parallel execu on

for (int i = 0; i < sizes.length; i++) {

int n = sizes[i];

int[] array = generateRandomArray(n);

long startTime = System.nanoTime();

pool.invoke(new MergeSortTask(array));

long endTime = System.nanoTime();

mes[i] = endTime - startTime; // Store me in nanoseconds

System.out.println("Sorted " + n + " elements in " + mes[i] + " nanoseconds.");

System.out.println("Sizes: " + Arrays.toString(sizes));

System.out.println("Times (nanoseconds): " + Arrays.toString( mes));

// Export sizes and mes for graph plo ng in external tools

}
// Merge Sort Task for parallel execu on

sta c class MergeSortTask extends RecursiveTask<int[]> {

private final int[] array;

MergeSortTask(int[] array) {

this.array = array;

@Override

protected int[] compute() {

if (array.length <= 1) {

return array;

int mid = array.length / 2;

MergeSortTask le Task = new MergeSortTask(Arrays.copyOfRange(array, 0, mid));

MergeSortTask rightTask = new MergeSortTask(Arrays.copyOfRange(array, mid, array.length));

le Task.fork(); // Start le task asynchronously

int[] rightResult = rightTask.compute(); // Compute right task synchronously

int[] le Result = le Task.join(); // Wait for le task to complete

return merge(le Result, rightResult);

// Merge two sorted arrays

public sta c int[] merge(int[] le , int[] right) {

int[] result = new int[le .length + right.length];

int i = 0, j = 0, k = 0;

while (i < le .length && j < right.length) {

if (le [i] <= right[j]) {

result[k++] = le [i++];
 } else {

result[k++] = right[j++];

while (i < le .length) {

result[k++] = le [i++];

while (j < right.length) {

result[k++] = right[j++];

return result;

// Generate a random array

public sta c int[] generateRandomArray(int size) {

Random random = new Random();

int[] array = new int[size];

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

array[i] = random.nextInt(100000); // Random number between 0 and 100000

return array;

}
Q.3 : Obtain the Topological ordering of ver ces in a given digraph. b. Computethe transi ve closure of a given directed
graph using Warshall's algorithm.

import java.u l.*;

public class TopologicalSort {

private int ver ces; // Number of ver ces

private LinkedList<Integer>[] adjacencyList; // Adjacency list

public TopologicalSort(int ver ces) {

this.ver ces = ver ces;

adjacencyList = new LinkedList[ver ces];

for (int i = 0; i < ver ces; i++) {

adjacencyList[i] = new LinkedList<>();

// Add an edge to the graph

public void addEdge(int from, int to) {

adjacencyList[from].add(to);

// Perform topological sort

public void topologicalSort() {

boolean[] visited = new boolean[ver ces];

Stack<Integer> stack = new Stack<>();

for (int i = 0; i < ver ces; i++) {

if (!visited[i]) {

topologicalSortU l(i, visited, stack);

System.out.println("Topological Ordering: ");

while (!stack.isEmpty()) {
 System.out.print(stack.pop() + " ");

System.out.println();

// U lity func on for DFS

private void topologicalSortU l(int current, boolean[] visited, Stack<Integer> stack) {

visited[current] = true;

for (int neighbor : adjacencyList[current]) {

if (!visited[neighbor]) {

topologicalSortU l(neighbor, visited, stack);

stack.push(current);

public sta c void main(String[] args) {

TopologicalSort graph = new TopologicalSort(6);

graph.addEdge(5, 2);

graph.addEdge(5, 0);

graph.addEdge(4, 0);

graph.addEdge(4, 1);

graph.addEdge(2, 3);

graph.addEdge(3, 1);

graph.topologicalSort();

}
Q.4 : Implement 0/1 Knapsack problem using Dynamic Programming.

public class Knapsack {

// Method to solve the 0/1 Knapsack problem

public sta c int knapsack(int[] weights, int[] values, int capacity) {

int n = values.length;

int[][] dp = new int[n + 1][capacity + 1];

// Build the DP table

for (int i = 1; i <= n; i++) {

for (int w = 0; w <= capacity; w++) {

if (weights[i - 1] <= w) {

dp[i][w] = Math.max(

dp[i - 1][w], // Exclude the current item

dp[i - 1][w - weights[i - 1]] + values[i - 1] // Include the current item

);

} else {

dp[i][w] = dp[i - 1][w]; // Exclude the current item

// The maximum value is in the last cell of the DP table

return dp[n][capacity];

public sta c void main(String[] args) {

// Example data

int[] weights = {1, 2, 3};

int[] values = {10, 15, 40};

int capacity = 5;

int maxValue = knapsack(weights, values, capacity);

System.out.println("Maximum value in the knapsack: " + maxValue);

}
Q.5 : From a given vertex in a weighted connected graph, find shortest paths toother ver ces using Dijkstra's algorithm.

import java.u l.*;

class Dijkstra {

private int V; // Number of ver ces

private int[][] graph; // Adjacency matrix

public Dijkstra(int V) {

this.V = V;

graph = new int[V][V];

// Func on to add an edge to the graph

public void addEdge(int u, int v, int w) {

graph[u][v] = w;

graph[v][u] = w;

int minDistance(int dist[], Boolean sptSet[]) {

int min = Integer.MAX_VALUE, min_index = -1;

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

if (sptSet[v] == false && dist[v] <= min) {

min = dist[v];

min_index = v;

return min_index;

// Func on to print the constructed distance array

void printSolu on(int dist[], int n) {

System.out.println("Vertex \t Distance from Source");

for (int i = 0; i < V; i++)

System.out.println(i + " \t\t " + dist[i]);

}
void dijkstra(int src) {

int dist[] = new int[V]; // The output array. dist[i] will hold

// the shortest distance from src to i

// sptSet[i] will true if vertex i is included in shortest path

// tree or shortest distance from src to i is finalized

Boolean sptSet[] = new Boolean[V];

// Ini alize all distances as INFINITE and stpSet[] as false

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

dist[i] = Integer.MAX_VALUE;

sptSet[i] = false;

// Distance of source vertex from itself is 0

dist[src] = 0;

// Find shortest path for all ver ces

for (int count = 0; count < V - 1; count++) {

// Pick the minimum distance vertex from the set of ver ces not

// yet processed. u is always equal to src in the first itera on.

int u = minDistance(dist, sptSet);

// Mark the picked vertex as processed

sptSet[u] = true;

// Update dist value of the adjacent ver ces of the picked vertex.

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

if (!sptSet[v] && graph[u][v] != 0 &&

dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v])

dist[v] = dist[u] + graph[u][v];

// print the constructed distance array

printSolu on(dist, V);

}
 public sta c void main(String[] args) {

int V = 9;

Dijkstra graph = new Dijkstra(V);

graph.addEdge(0, 1, 4);

graph.addEdge(0, 7, 8);

graph.addEdge(1, 2, 8);

graph.addEdge(1, 7, 11);

graph.addEdge(2, 3, 7);

graph.addEdge(2, 8, 2);

graph.addEdge(2, 5, 4);

graph.addEdge(3, 4, 9);

graph.addEdge(4, 5, 10);

graph.addEdge(5, 6, 2);

graph.addEdge(6, 7, 1);

graph.addEdge(6, 8, 6);

graph.addEdge(7, 8, 7);

graph.dijkstra(0);

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

import java.u l.*;

class Edge implements Comparable<Edge> {

int src, dest, weight;

// Constructor

public Edge(int src, int dest, int weight) {

this.src = src;

this.dest = dest;

this.weight = weight;

// Sor ng edges by weight

public int compareTo(Edge compareEdge) {

return this.weight - compareEdge.weight;

class Subset {

int parent, rank;

public class KruskalMST {

int ver ces, edges; // Number of ver ces and edges

Edge[] edge; // Array of all edges

// Constructor

public KruskalMST(int ver ces, int edges) {

this.ver ces = ver ces;

this.edges = edges;

edge = new Edge[edges];

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

edge[i] = new Edge(0, 0, 0);

} }

// Find set of an element u (uses path compression)

int find(Subset[] subsets, int u) {

if (subsets[u].parent != u)

subsets[u].parent = find(subsets, subsets[u].parent);

return subsets[u].parent;
}

// Union of two sets x and y (uses union by rank)

void union(Subset[] subsets, int x, int y) {

int rootX = find(subsets, x);

int rootY = find(subsets, y);

if (subsets[rootX].rank < subsets[rootY].rank) {

subsets[rootX].parent = rootY;

} else if (subsets[rootX].rank > subsets[rootY].rank) {

subsets[rootY].parent = rootX;

} else {

subsets[rootY].parent = rootX;

subsets[rootX].rank++;

// Kruskal's algorithm to find MST

void kruskalMST() {

Edge[] result = new Edge[ver ces - 1]; // Resultant MST

int e = 0; // Index for result[]

int i = 0; // Index for sorted edges

for (int j = 0; j < ver ces - 1; ++j) {

result[j] = new Edge(0, 0, 0);

// Sort edges by weight

Arrays.sort(edge);

// Allocate memory for subsets

Subset[] subsets = new Subset[ver ces];

for (i = 0; i < ver ces; ++i) {

subsets[i] = new Subset();

subsets[i].parent = i;

subsets[i].rank = 0;

i = 0; // Reset edge index

while (e < ver ces - 1) {

 Edge nextEdge = edge[i++];

int x = find(subsets, nextEdge.src);

int y = find(subsets, nextEdge.dest);

// If including this edge does not cause a cycle

if (x != y) {

result[e++] = nextEdge;

union(subsets, x, y);

} }

// Print the result

System.out.println("Edges in the MST:");

int minimumCost = 0;

for (i = 0; i < e; ++i) {

System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);

minimumCost += result[i].weight;

System.out.println("Minimum Cost: " + minimumCost);

public sta c void main(String[] args) {

int ver ces = 4; // Number of ver ces

int edges = 5; // Number of edges

KruskalMST graph = new KruskalMST(ver ces, edges);

// Adding edges: src, dest, weight

graph.edge[0] = new Edge(0, 1, 10);

graph.edge[1] = new Edge(0, 2, 6);

graph.edge[2] = new Edge(0, 3, 5);

graph.edge[3] = new Edge(1, 3, 15);

graph.edge[4] = new Edge(2, 3, 4);

graph.kruskalMST();

} }
Q.7 : a. Print all the nodes reachable from a given star ng node in a digraph using BFS method

import java.u l.*;

public class GraphBFS {

private int ver ces; // Number of ver ces

private LinkedList<Integer>[] adj; // Adjacency list

// Constructor

public GraphBFS(int ver ces) {

this.ver ces = ver ces;

adj = new LinkedList[ver ces];

for (int i = 0; i < ver ces; i++) {

adj[i] = new LinkedList<>();

// Add an edge to the graph

void addEdge(int src, int dest) {

adj[src].add(dest);

// Perform BFS and print reachable nodes

void bfs(int start) {

boolean[] visited = new boolean[ver ces];

Queue<Integer> queue = new LinkedList<>();

visited[start] = true;

queue.add(start);

System.out.println("Nodes reachable from node " + start + ":");

while (!queue.isEmpty()) {

int node = queue.poll();

System.out.print(node + " ");

for (int neighbor : adj[node]) {

if (!visited[neighbor]) {
 visited[neighbor] = true;

queue.add(neighbor);

System.out.println();

public sta c void main(String[] args) {

GraphBFS graph = new GraphBFS(6);

// Adding edges to the digraph

graph.addEdge(0, 1);

graph.addEdge(0, 2);

graph.addEdge(1, 3);

graph.addEdge(2, 3);

graph.addEdge(3, 4);

graph.addEdge(4, 5);

graph.bfs(0); // Star ng node

b. Check whether a given graph is connected or not using DFS method

import java.u l.*;

public class GraphDFS {

private int ver ces; // Number of ver ces

private LinkedList<Integer>[] adj; // Adjacency list

// Constructor

public GraphDFS(int ver ces) {

this.ver ces = ver ces;

 adj = new LinkedList[ver ces];

for (int i = 0; i < ver ces; i++) {

adj[i] = new LinkedList<>();

// Add an edge to the graph

void addEdge(int src, int dest) {

adj[src].add(dest);

adj[dest].add(src); // Since it's an undirected graph

// Perform DFS to check connec vity

void dfs(int v, boolean[] visited) {

visited[v] = true;

for (int neighbor : adj[v]) {

if (!visited[neighbor]) {

dfs(neighbor, visited);

// Check if the graph is connected

boolean isConnected() {

boolean[] visited = new boolean[ver ces];

// Start DFS from the first vertex

dfs(0, visited);

// Check if all ver ces were visited

for (boolean v : visited) {

if (!v) return false;

return true;

}
 public sta c void main(String[] args) {

GraphDFS graph = new GraphDFS(5);

// Adding edges to the undirected graph

graph.addEdge(0, 1);

graph.addEdge(1, 2);

graph.addEdge(2, 3);

graph.addEdge(3, 4);

if (graph.isConnected()) {

System.out.println("The graph is connected.");

} else {

System.out.println("The graph is not connected.");

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

import java.u l.*;

public class PrimsMST {

// Func on to find the vertex with the minimum key value that is not yet included in the MST

int minKey(int[] key, boolean[] mstSet, int ver ces) {

int min = Integer.MAX_VALUE, minIndex = -1;

for (int v = 0; v < ver ces; v++) {

if (!mstSet[v] && key[v] < min) {

min = key[v];

minIndex = v;

return minIndex;

// Func on to print the MST and its total cost

void printMST(int[] parent, int[][] graph, int ver ces) {

int totalCost = 0;

System.out.println("Edge \tWeight");

for (int i = 1; i < ver ces; i++) {

System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);

totalCost += graph[i][parent[i]];

System.out.println("Total Minimum Cost: " + totalCost);

// Prim's algorithm

void primMST(int[][] graph) {

int ver ces = graph.length;

// Array to store the MST

int[] parent = new int[ver ces];

 // Key values used to pick the minimum weight edge

int[] key = new int[ver ces];

// To represent the set of ver ces included in the MST

boolean[] mstSet = new boolean[ver ces];

// Ini alize all keys as infinite and MST set as false

Arrays.fill(key, Integer.MAX_VALUE);

Arrays.fill(mstSet, false);

// Start from the first vertex

key[0] = 0; // Make key 0 so this vertex is picked first

parent[0] = -1; // First node is always the root of MST

// MST will have (ver ces - 1) edges

for (int count = 0; count < ver ces - 1; count++) {

int u = minKey(key, mstSet, ver ces);

// Add the selected vertex to the MST set

mstSet[u] = true;

// Update key and parent arrays

for (int v = 0; v < ver ces; v++) {

// Update the key only if graph[u][v] is smaller and v is not yet in MST

if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {

parent[v] = u;

key[v] = graph[u][v];

// Print the constructed MST

printMST(parent, graph, ver ces);

}
 public sta c void main(String[] args) {

// Graph representa on using adjacency matrix

int[][] graph = {

{0, 2, 0, 6, 0},

{2, 0, 3, 8, 5},

{0, 3, 0, 0, 7},

{6, 8, 0, 0, 9},

{0, 5, 7, 9, 0}

};

PrimsMST mst = new PrimsMST();

mst.primMST(graph);

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

import java.u l.*;

public class FloydWarshall {

final sta c int INF = 99999; // Represents infinity for unreachable nodes

// Func on to implement Floyd-Warshall Algorithm

void floydWarshall(int[][] graph) {

int ver ces = graph.length;

int[][] dist = new int[ver ces][ver ces];

// Ini alize the solu on matrix same as the input graph matrix

for (int i = 0; i < ver ces; i++) {

for (int j = 0; j < ver ces; j++) {

dist[i][j] = graph[i][j];

// Update the solu on matrix

for (int k = 0; k < ver ces; k++) {

for (int i = 0; i < ver ces; i++) {

for (int j = 0; j < ver ces; j++) {

// Update dist[i][j] if a shorter path is found via vertex k

if (dist[i][k] + dist[k][j] < dist[i][j]) {

dist[i][j] = dist[i][k] + dist[k][j];

// Print the shortest distances

printSolu on(dist);

// Func on to print the shortest distance matrix

void printSolu on(int[][] dist) {

int ver ces = dist.length;

System.out.println("Shortest distances between every pair of ver ces:");

for (int i = 0; i < ver ces; i++) {

for (int j = 0; j < ver ces; j++) {

if (dist[i][j] == INF) {

System.out.print("INF ");

} else {

System.out.print(dist[i][j] + " ");

System.out.println();

public sta c void main(String[] args) {

FloydWarshall fw = new FloydWarshall();

// Graph represented as adjacency matrix

int[][] graph = {

{0, 3, INF, 7},

{8, 0, 2, INF},

{5, INF, 0, 1},

{2, INF, INF, 0}

};

fw.floydWarshall(graph);

} }
Q.10 : Implement N Queen's problem using Back Tracking.

public class NQueens {

int N;

// Constructor to ini alize N

public NQueens(int N) {

this.N = N;

// Method to print the solu on board

public void printSolu on(int[][] board) {

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

for (int j = 0; j < N; j++) {

System.out.print(board[i][j] == 1 ? "Q " : ". ");

System.out.println();

// Method to check if a queen can be placed at board[row][col]

public boolean isSafe(int[][] board, int row, int col) {

// Check column

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

if (board[i][col] == 1) {

return false;

// Check upper le diagonal

for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {

if (board[i][j] == 1) {

return false;

}
 // Check upper right diagonal

for (int i = row, j = col; i >= 0 && j < N; i--, j++) {

if (board[i][j] == 1) {

return false;

return true;

// Method to solve the N-Queens problem using backtracking

public boolean solveNQueensU l(int[][] board, int row) {

// Base case: If all queens are placed

if (row >= N) {

return true;

// Try all columns in the current row

for (int col = 0; col < N; col++) {

if (isSafe(board, row, col)) {

board[row][col] = 1; // Place the queen

// Recur to place rest of the queens

if (solveNQueensU l(board, row + 1)) {

return true;

// If placing queen in board[row][col] doesn't lead to a solu on

board[row][col] = 0; // Backtrack

// If the queen cannot be placed in any column in this row

return false;

}
 // Method to solve the N-Queens problem

public boolean solveNQueens() {

int[][] board = new int[N][N];

// Call the recursive u lity func on to solve the problem

if (!solveNQueensU l(board, 0)) {

System.out.println("Solu on does not exist");

return false;

// If a solu on is found, print the board

printSolu on(board);

return true;

public sta c void main(String[] args) {

int N = 8; // Size of the chessboard

NQueens queens = new NQueens(N);

if (queens.solveNQueens()) {

System.out.println("Solu on for " + N + " Queens:");