import java.util.

*;

public class Merge {

public static void main(String[] args) {
// Define an array of different values of n
int[] nValues = { 1000, 5000, 10000, 20000, 30000 };
// Create a Random object for generating random numbers
Random random = new Random();
// Iterate through different values of n
for (int n : nValues) {
int[] arr = new int[n];
// Fill the array with random integers
for (int i = 0; i < n; i++) {
arr[i] = random.nextInt(100000); // Adjust the range as needed
}
// Record the start time
long startTime = System.nanoTime();
// Call the merge sort function
mergeSort(arr);
// Record the end time
long endTime = System.nanoTime();
// Calculate the time taken in milliseconds
long timeTaken = (endTime - startTime) / 1000000;
// Print the result
System.out.println("Time taken to sort " + n + " elements: " +
timeTaken + " ms");
}
}

public static void mergeSort(int[] arr) {

if (arr.length <= 1) {
return;
}
// Split the array into two halves
int mid = arr.length / 2;
int[] left = Arrays.copyOfRange(arr, 0, mid);
int[] right = Arrays.copyOfRange(arr, mid, arr.length);
// Recursively sort both halves
mergeSort(left);
mergeSort(right);
// Merge the sorted halves
merge(arr, left, right);
}

public static void merge(int[] arr, int[] left, int[] right) {

 int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < left.length) {
arr[k++] = left[i++];
}
while (j < right.length) {
arr[k++] = right[j++];
}
}
}

import java.util.Random;

public class Quick {

public static void main(String[] args) {
int[] nValues = {10, 100, 1000, 10000}; // Different values of n
for (int n : nValues) {
int[] arr = generateRandomArray(n);
long startTime = System.nanoTime();
QuickSort.quickSort(arr,0, n - 1);
long endTime = System.nanoTime();
long elapsedTime = endTime - startTime;
System.out.println("Time taken to sort " + n + " elements: " +
elapsedTime + " ns");
}
}

private static int[] generateRandomArray(int n) {

int[] arr = new int[n];
Random random = new Random();
for (int i = 0; i < n; i++) {
arr[i] = random.nextInt(10000); // Adjust the range as needed
}
return arr;
}
}
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}

private static 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 temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
}

class BST {
static class Node {
int key;
Node left, right;

public Node(int item) {

key = item;
left = right = null;
}
}

// Root of the BST

Node root;
BST() {
root = null;
}
// Insert a key into the BST
void insert(int key) {
root = insertRec(root, key);
}

Node insertRec(Node root, int key) {

if (root == null) {
root = new Node(key);
return root;
}
if (key < root.key) {
root.left = insertRec(root.left, key);
} else if (key > root.key) {
root.right = insertRec(root.right, key);
}
return root;
}

// Delete a key from the BST

void delete(int key) {
root = deleteRec(root, key);
}

Node deleteRec(Node root, int key) {

if (root == null) {
return root;
}
if (key < root.key) {
root.left = deleteRec(root.left, key);
} else if (key > root.key) {
root.right = deleteRec(root.right, key);
} else {
// Node with only one child or no child
if (root.left == null) {
return root.right;
} else if (root.right == null) {
return root.left;
}
// Node with two children root.key = minValue(root.right);
// Delete the in-order successor
root.right = deleteRec(root.right, root.key);
}
return root;
 }

int minValue(Node root) {

int minValue = root.key;
while (root.left != null) {
minValue = root.left.key;
root = root.left;
}
return minValue;
}

// Print the inorder traversal of the tree

void inorder() {
inorderRec(root);
}

void inorderRec(Node root) {

if (root != null) {
inorderRec(root.left);
System.out.print(root.key + " ");
inorderRec(root.right);
}
}

// Main method for testing the BST operations

public static void main(String[] args) {
BST tree = new BST();
// Insert elements
tree.insert(50); tree.insert(30); tree.insert(20);
// tree.insert(40); tree.insert(70);
tree.insert(60);
tree.insert(80);
System.out.println("Inorder traversal:");
tree.inorder();
System.out.println();
// Delete elements
System.out.println("Delete 20:"); tree.delete(20);
tree.inorder();
System.out.println();
System.out.println("Delete 30:");
tree.delete(30);
tree.inorder();
System.out.println();
}
}
import java.util.*;

class Graph {
private int V; // Number of vertices
private LinkedList<Integer> adjList[];

Graph(int v) {
V = v;
adjList = new LinkedList[v];
for (int i = 0; i < v; ++i)
adjList[i] = new LinkedList();
}

void addEdge(int v, int w) {

adjList[v].add(w);
}

void BFS(int s) {
boolean visited[] = new boolean[V];
LinkedList<Integer> queue = new LinkedList<>();
visited[s] = true;
queue.add(s);
while (queue.size() != 0) {
s = queue.poll();
System.out.print(s + " ");
Iterator<Integer> i = adjList[s].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n]) {
visited[n] = true;
queue.add(n);
}
}
}
}
}

public class Main {

public static void main(String args[]) {
Graph g = new Graph(7); // Change the number of vertices as needed
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 5);
 g.addEdge(2, 6);
int startNode = 2; // Change the starting node as needed
System.out.println("Nodes reachable from node " + startNode + "
usingBFS:");
g.BFS(startNode);
}
}

import java.util.*;

class Graph {
private int V; // Number of vertices
private LinkedList<Integer>[] adj; // Adjacency list

Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; i++) {
adj[i] = new LinkedList<>();
}
}

void addEdge(int v, int w) {

adj[v].add(w);
}

void topologicalSortUtil(int v, boolean[] visited, Stack<Integer> stack) {

visited[v] = true;
for (Integer neighbor : adj[v]) {
if (!visited[neighbor]) {
topologicalSortUtil(neighbor, visited, stack);
}
}
stack.push(v);
}

void topologicalSort() {
Stack<Integer> stack = new Stack<>();
boolean[] visited = new boolean[V];
for (int i = 0; i < V; i++) {
if (!visited[i]) {
topologicalSortUtil(i, visited, stack);
}
 }
while (!stack.isEmpty()) {
System.out.print(stack.pop() + " ");
}
}
}

public class Topo {

public static void main(String[] args) {
Graph g = new Graph(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
System.out.println("Topological Sort: ");
g.topologicalSort();
}
}

import java.util.*;

class WarshallTransitiveClosure {
private int V;
private boolean[][] tc;

WarshallTransitiveClosure(int vertices) {
V = vertices;
tc = new boolean[vertices][vertices];
}

void addEdge(int from, int to) {

tc[from][to] = true;
}

void computeTransitiveClosure() {
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
tc[i][j] = tc[i][j] || (tc[i][k] && tc[k][j]);
}
}
 }
}

void printTransitiveClosure() {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
System.out.print(tc[i][j] ? "1 " : "0 ");
}
System.out.println();
}
}
}

public class Wtc {

public static void main(String[] args) {
int vertices = 4;
WarshallTransitiveClosure g = new WarshallTransitiveClosure(vertices);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
System.out.println("Transitive Closure:");
g.computeTransitiveClosure();
g.printTransitiveClosure();
}
}

import java.util.Scanner;

public class GraphDFS {

private int vertices;
private int[][] adjacencyMatrix;

public GraphDFS(int v) {
vertices = v;
adjacencyMatrix = new int[v][v];
}

public void addEdge(int start, int end) {

adjacencyMatrix[start][end] = 1;
adjacencyMatrix[end][start] = 1;
 }

public void dfs(int startVertex, boolean[] visited) {

System.out.print(startVertex + " ");
visited[startVertex] = true;
for (int i = 0; i < vertices; i++) {
if (adjacencyMatrix[startVertex][i] == 1 && !visited[i]) {
dfs(i, visited);
}
}
}

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);
System.out.print("Enter the number of vertices: ");
int v = scanner.nextInt();
GraphDFS graph = new GraphDFS(v);
System.out.println("Enter the adjacency matrix:");
for (int i = 0; i < v; i++) {
for (int j = 0; j < v; j++) {
graph.adjacencyMatrix[i][j] = scanner.nextInt();
}
}
System.out.print("Enter the starting vertex for DFS: ");
int startVertex = scanner.nextInt();
boolean[] visited = new boolean[v];
System.out.print("DFS traversal starting from vertex " + startVertex + ":
");
graph.dfs(startVertex, visited);
scanner.close();
}
}

import java.util.Scanner;

public class Floyd {

void floyd(int[][] w, int n) {
int i, j, k;
for (k = 1; k <= n; k++)
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
w[i][j] = Math.min(w[i][j], w[i][k] + w[k][j]);
}
 public static void main(String[] args) {
int a[][] = new int[10][10];
int n, i, j;
Scanner sc = new Scanner(System.in);

System.out.println("Enter the number of vertices");

n = sc.nextInt();

System.out.println("Enter the weighted matrix");

for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
a[i][j] = sc.nextInt();

Floyd f = new Floyd();

f.floyd(a, n);

System.out.println("The shortest path matrix is");

for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
System.out.print(a[i][j] + " ");
}
System.out.println();
}

sc.close();
}
}

import java.util.Arrays;
import java.util.Scanner;

public class HeapSort {

public static void heapSort(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
 heapify(arr, i, 0);
}
}

public static void heapify(int[] arr, int n, int i) {

int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);
System.out.print("Enter the number of elements: ");
int n = scanner.nextInt();
int[] arr = new int[n];
System.out.println("Enter the elements:");
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
System.out.println("Original array: " + Arrays.toString(arr));
long startTime = System.nanoTime();
heapSort(arr);
long endTime = System.nanoTime();
System.out.println("Sorted array: " + Arrays.toString(arr));
double timeElapsed = (endTime - startTime) / 1e6; // Convert nanoseconds
to milliseconds
System.out.println("Time complexity: " + timeElapsed + " milliseconds");
scanner.close();
}
}
import java.util.Scanner;

public class Horsepool {

public static int[] shiftTable(String pattern) {
int[] table = new int[256];
int m = pattern.length();
for (int i = 0; i < 256; i++) {
table[i] = m;
}
for (int i = 0; i < m - 1; i++) {
table[pattern.charAt(i)] = m - 1 - i;
}
return table;
}

public static int horspoolSearch(String text, String pattern) {

int n = text.length();
int m = pattern.length();
int[] table = shiftTable(pattern);
int i = m - 1;
while (i < n) {
int k = 0;
while (k < m && pattern.charAt(m - 1 - k) == text.charAt(i - k)) {
k++;
}
if (k == m) {
return i - m + 1; // Pattern found at index i - m + 1
} else {
i += table[text.charAt(i)];
}
}
return -1; // Pattern not found
}

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);
System.out.print("Enter the text: ");
String text = scanner.nextLine();
System.out.print("Enter the pattern to search for: ");
String pattern = scanner.nextLine();
long startTime = System.nanoTime();
int index = horspoolSearch(text, pattern);
long endTime = System.nanoTime();
if (index != -1) {
System.out.println("Pattern found at index: " + index);
 } else {
System.out.println("Pattern not found.");
}
double timeElapsed = (endTime - startTime) / 1e6; // Convert nanoseconds
to milliseconds
System.out.println("Time complexity: " + timeElapsed + " milliseconds");
scanner.close();
}
}

import java.util.Scanner;

public class Knap {

public static int knapsack(int[] weights, int[] values, int capacity) {
int n = weights.length;
int[][] dp = new int[n + 1][capacity + 1];

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

for (int w = 1; w <= capacity; w++) {
if (weights[i - 1] <= w) {
dp[i][w] = Math.max(values[i - 1] + dp[i - 1][w - weights[i -
1]], dp[i - 1][w]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}

return dp[n][capacity];
}

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

System.out.println("Enter the number of items:");

int n = scanner.nextInt();

int[] weights = new int[n];

int[] values = new int[n];

System.out.println("Enter the weights of the items:");

for (int i = 0; i < n; i++) {
weights[i] = scanner.nextInt();
 }

System.out.println("Enter the values of the items:");

for (int i = 0; i < n; i++) {
values[i] = scanner.nextInt();
}

System.out.println("Enter the capacity of the knapsack:");

int capacity = scanner.nextInt();

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

System.out.println("The maximum value that can be obtained is: " +
maxValue);
}
}

=====================================================================================

import java.util.Scanner;

public class Prim {

public static void main(String[] args) {
int w[][] = new int[10][10];
int n, i, j, s, k = 0;
int min;
int sum = 0;
int u = 0, v = 0;
int flag = 0;
int sol[] = new int[10];
System.out.println("Enter the number of vertices");
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (i = 1; i <= n; i++)
sol[i] = 0;
System.out.println("Enter the weighted graph");
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
w[i][j] = sc.nextInt();
System.out.println("Enter the source vertex");
s = sc.nextInt();
sol[s] = 1;
k = 1;
 while (k <= n - 1) {
min = 99;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (sol[i] == 1 && sol[j] == 0)
if (i != j && min > w[i][j]) {
min = w[i][j];
u = i;
v = j;
}
sol[v] = 1;
sum = sum + min;
k++;
System.out.println(u + "->" + v + "=" + min);
}
for (i = 1; i <= n; i++)
if (sol[i] == 0)
flag = 1;
if (flag == 1)
System.out.println("No spanning tree");
else
System.out.println("The cost of minimum spanning tree is" + sum);
sc.close();
}
}

import java.util.Scanner;

public class Krus {

int parent[] = new int[10];

int find(int m) {
int p = m;
while (parent[p] != 0)
p = parent[p];
return p;
}

void union(int i, int j) {

if (i < j)
parent[i] = j;
else
parent[j] = i;
 }

void krkl(int[][] a, int n) {

int u = 0, v = 0, min, k = 0, i, j, sum = 0;
while (k < n - 1) {
min = 99;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (a[i][j] < min && i != j) {
min = a[i][j];
u = i;
v = j;
}
i = find(u);
j = find(v);
if (i != j) {
union(i, j);
System.out.println("(" + u + "," + v + ")" + "=" + a[u][v]);
sum = sum + a[u][v];
k++;
}
a[u][v] = a[v][u] = 99;
}
System.out.println("The cost of minimum spanning tree = " + sum);
}

public static void main(String[] args) {

int a[][] = new int[10][10];
int i, j;
System.out.println("Enter the number of vertices of the graph");
Scanner sc = new Scanner(System.in);
int n;
n = sc.nextInt();
System.out.println("Enter the wieghted matrix");
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
a[i][j] = sc.nextInt();
Krus k = new Krus();
k.krkl(a, n);
sc.close();
}
}

=====================================================================================
import java.util.Scanner;

public class Dik {

int d[] = new int[10];
int p[] = new int[10];
int visited[] = new int[10];

public void dijk(int[][] a, int s, int n) {

int u = -1, v, i, j, min;
for (v = 0; v < n; v++) {
d[v] = 99;
p[v] = -1;
}
d[s] = 0;
for (i = 0; i < n; i++) {
min = 99;
for (j = 0; j < n; j++) {
if (d[j] < min && visited[j] == 0) {
min = d[j];
u = j;
}
}
visited[u] = 1;
for (v = 0; v < n; v++) {
if ((d[u] + a[u][v] < d[v]) && (u != v) && visited[v] == 0) {
d[v] = d[u] + a[u][v];
p[v] = u;
}
}
}
}

void path(int v, int s) {

if (p[v] != -1)
path(p[v], s);
if (v != s)
System.out.print("->" + v + " ");
}

void display(int s, int n) {

int i;
for (i = 0; i < n; i++) {
if (i != s) {
System.out.print(s + " ");
path(i, s);
 }
if (i != s)
System.out.print("=" + d[i] + " ");
System.out.println();
}
}

public static void main(String[] args) {

int a[][] = new int[10][10];
int i, j, n, s;
System.out.println("enter the number of vertices");
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
System.out.println("enter the weighted matrix");
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
a[i][j] = sc.nextInt();
System.out.println("enter the source vertex");
s = sc.nextInt();
Dik tr = new Dik();
tr.dijk(a, s, n);
System.out.println("the shortest path between source" + s + "to remaining
vertices are");
tr.display(s, n);
sc.close();
}
}

import java.util.Arrays;

public class TSP {

private static int tsp(int[][] graph, int start, int mask, int current,
int[][] memo) {
int n = graph.length;

if (mask == (1 << n) - 1) {
return graph[current][start];
}

if (memo[mask][current] != -1) {
return memo[mask][current];
}
 int minCost = Integer.MAX_VALUE;

for (int city = 0; city < n; city++) {

if ((mask & (1 << city)) == 0) {
int newMask = mask | (1 << city);
int cost = graph[current][city] + tsp(graph, start, newMask,
city, memo);

minCost = Math.min(minCost, cost);

}
}

memo[mask][current] = minCost;
return minCost;
}

public static int solveTSP(int[][] graph) {

int n = graph.length;
int[][] memo = new int[1 << n][n];
for (int[] row : memo) {
Arrays.fill(row, -1);
}

int start = 0; // Assuming starting from vertex 0

int mask = 1; // Marking the starting vertex as visited

return tsp(graph, start, mask, start, memo);

}

public static void main(String[] args) {

int[][] graph = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
};

int minCost = solveTSP(graph);

System.out.println("Minimum cost for the Travelling Salesman Problem: " +
minCost);
}
}

=====================================================================================
import java.util.Scanner;

public class NQueen {

private static boolean isSafe(int[][] board, int row, int col, int N) {
for (int i = 0; i < col; i++) {
if (board[row][i] == 1) {
return false;
}
}
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 1) {
return false;
}
}
for (int i = row, j = col; i < N && j >= 0; i++, j--) {
if (board[i][j] == 1) {
return false;
}
}
return true;
}

private static boolean solveNQueensUtil(int[][] board, int col, int N) {

if (col >= N) {
return true;
}
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col, N)) {
board[i][col] = 1;
if (solveNQueensUtil(board, col + 1, N)) {
return true;
}
board[i][col] = 0;
}
}
return false;
}

public static boolean solveNQueens(int N) {

int[][] board = new int[N][N];
if (!solveNQueensUtil(board, 0, N)) {
return false;
}
displayBoard(board, N);
return true;
 }

public static void displayBoard(int[][] board, int N) {

for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);
System.out.print("Enter the value of N: ");
int N = scanner.nextInt();
long startTime = System.nanoTime();
boolean solutionExists = solveNQueens(N);
long endTime = System.nanoTime();
if (!solutionExists) {
System.out.println("No solution exists for N = " + N);
}
double timeElapsed = (endTime - startTime) / 1e6; // Convert nanoseconds
to milliseconds
System.out.println("\nTime complexity: " + timeElapsed + "
milliseconds");
scanner.close();
}
}

import java.util.ArrayList;
import java.util.Arrays;

public class Subset {

public static void main(String[] args) {
int[] set = {3, 34, 4, 12, 5, 2};
int sum = 17;

ArrayList<Integer> subset = findSubsetSum(set, sum);

System.out.println("Input Set: " + Arrays.toString(set));

System.out.println("Target Sum: " + sum);
System.out.println("Subset with Sum: " + subset);
}
 private static ArrayList<Integer> findSubsetSum(int[] set, int sum) {
int n = set.length;
boolean[][] dp = new boolean[n + 1][sum + 1];

// Initialize the first column as true, since the sum 0 is always

possible
for (int i = 0; i <= n; i++) {
dp[i][0] = true;
}

// Fill the dp array using bottom-up dynamic programming

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
dp[i][j] = dp[i - 1][j];

if (j >= set[i - 1]) {

dp[i][j] = dp[i][j] || dp[i - 1][j - set[i - 1]];
}
}
}

// Reconstruct the subset

ArrayList<Integer> subset = new ArrayList<>();
int i = n, j = sum;
while (i > 0 && j > 0) {
if (dp[i][j] && !dp[i - 1][j]) {
subset.add(set[i - 1]);
j -= set[i - 1];
}
i--;
}

return subset;
}
}