Practical 1

import java.util.Arrays;
import java.util.Random;

public class QuickMerge {
public static void main(String[] args) {

// Generate an array of 500 random values

int values[] = new int[500];

Random random = new Random();
for (int i = 0; i < values.length; i++) {
values[i] = random.nextInt(1000);
}

// Display the unsorted array

System.out.println("Unsorted values for quick sort: " + Arrays.toString(values));

// Measure the time taken to sort the array using Quicksort

long startTime = System.nanoTime();
// System.out.println("Start time :"+startTime);
quicksort(values, 0, values.length - 1);
long endTime = System.nanoTime();
// System.out.println("End time :"+endTime);

long qst = endTime - startTime;

// Display the sorted array
System.out.println("\nSorted Array : " + Arrays.toString(values));

// Display the time taken for sorting
System.out.println("\nTime taken by Quick sort: " + qst + " nanoseconds");

int[] valuesForMerge = Arrays.copyOf(values, values.length);

startTime = System.nanoTime();
divide(valuesForMerge, 0, valuesForMerge.length - 1);
endTime = System.nanoTime();

long ms = endTime - startTime;
System.out.println("\nTime taken by Mergesort: " + ms + " nanoseconds");

}

public static void quicksort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);

// Recursively sort the sub-arrays
quicksort(arr, low, pivotIndex - 1);
quicksort(arr, pivotIndex + 1, high);
}
}

public 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++;
swap(arr, i, j);
}
}

swap(arr, i + 1, high);
return i + 1;
}

public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

public static void divide(int arr[], int L, int R) {

if (L <= R) {

int mid = L + (R - L) / 2;

divide(arr, L, mid - 1);
divide(arr, mid + 1, R);
merge(arr, L, mid, R);

}

}

public static void merge(int arr[], int L, int mid, int R) {
int arr1[] = new int[R - L + 1];
int N1 = L; //left sub Array
int N2 = mid + 1; //right sub array
int x = 0;

while (N1 <= mid && N2 <= R) {
if (arr[N1] <= arr[N2]) {
arr1[x++] = arr[N1++];
} else {
arr1[x++] = arr[N2++];
}
}

while (N1 <= mid) {
arr1[x++] = arr[N1++]; //Check for remaining elements
}

while (N2 <= R) {
arr1[x++] = arr[N2++]; //Check for remaining elements
}

for (int i = 0, j = L; i < arr1.length; i++, j++) {

arr[j] = arr1[i];
}

}

}
---------------------------------------------------------------------------------------------------------------------
Practical 2
import java.util.Arrays;
import java.util.Scanner;

public class QuickMerge {
public static void main(String[] args) {

int values[]= new int[10];

Scanner sc=new Scanner(System.in);

System.out.println("Enter 10 elements to sort");

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

// Display the unsorted array

System.out.println("Unsorted values: " + Arrays.toString(values));

long startTime = System.nanoTime();
quicksort(values, 0, values.length - 1);
long endTime = System.nanoTime();

System.out.println("Sorted values: " + Arrays.toString(values));

System.out.println("\nTime taken by quick sort: " + (endTime - startTime) + " milliseconds");

//For Merge Sort

int valuesmerge[]= new int[10];

System.out.println("Enter 10 elements to sort");

for(int i=0;i<valuesmerge.length;i++)
{
valuesmerge[i]=sc.nextInt();
}

// Display the unsorted array

System.out.println("Unsorted values: " + Arrays.toString(valuesmerge));

startTime = System.nanoTime();
divide(valuesmerge, 0, valuesmerge.length- 1);
endTime = System.nanoTime();

System.out.println("Sorted values: " + Arrays.toString(valuesmerge));

long ms = endTime - startTime;
System.out.println("\nTime taken By Merge Sort: " + ms + " milliseconds");

}

public static void quicksort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);

// Recursively sort the sub-arrays
quicksort(arr, low, pivotIndex - 1);
quicksort(arr, pivotIndex + 1, high);
}
}

public 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++;
swap(arr, i, j);
}
}

swap(arr, i + 1, high);
return i + 1;
}

public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

public static void divide(int arr[], int L, int R) {

if (L <= R) {

int mid = L + (R - L) / 2;

divide(arr, L, mid - 1);
divide(arr, mid + 1, R);
merge(arr, L, mid, R);

}

}

public static void merge(int arr[], int L, int mid, int R) {
int arr1[] = new int[R - L + 1];
int N1 = L;
int N2 = mid + 1;
int x = 0;

while (N1 <= mid && N2 <= R) {
if (arr[N1] <= arr[N2]) {
arr1[x++] = arr[N1++];
} else {
arr1[x++] = arr[N2++];
}
}

while (N1 <= mid) {
arr1[x++] = arr[N1++];
}

while (N2 <= R) {
arr1[x++] = arr[N2++];
}

for (int i = 0, j = L; i < arr1.length; i++, j++) {

arr[j] = arr1[i];
}

}

}
------------------------------------------------------------------------------------------------------------------------
Practical 3(A)
import java.util.Arrays;
import java.util.Random;

public class Quicksort {
public static void main(String[] args) {

// Generate an array of 500 random values

int values[]=new int[500];

Random random = new Random();
for (int i = 0; i < values.length; i++) {
values[i] = random.nextInt(1000);
}

// Display the unsorted array

System.out.println("Unsorted values: " + Arrays.toString(values));

// Measure the time taken to sort the array using Quicksort

long startTime = System.currentTimeMillis();
System.out.println("Start time :"+startTime);
quicksort(values, 0, values.length - 1);
long endTime = System.currentTimeMillis();
System.out.println("End time :"+endTime);

// Display the sorted array
System.out.println("Sorted values: " + Arrays.toString(values));

// Display the time taken for sorting
System.out.println("Time taken for sorting: " + (endTime - startTime) + " milliseconds");
}

public static void quicksort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);

// Recursively sort the sub-arrays
quicksort(arr, low, pivotIndex - 1);
quicksort(arr, pivotIndex + 1, high);
}
}

public 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++;
swap(arr, i, j);
}
}

swap(arr, i + 1, high);
return i + 1;
}

public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
Practical 3(B)

import java.util.Random;

public class TSPMutation1 {

public static void mutatedchromosome(int[][] chromosome) {
Random random=new Random();

//select the randomly two index
int index1=random.nextInt(chromosome.length);
int index2=random.nextInt(chromosome.length);

//swap them
int [] temp=chromosome[index1];
chromosome[index1]=chromosome[index2];
chromosome[index2]=temp;

}

public static void printchromosome(int[][] chromosome) {
// for(int []city:chromosome) {
// System.out.println("city"+" "+city[0]+" x:"+city[1]+" y:"+city[2]);
// }
for (int[] row : chromosome) {
for (int cell : row) {
System.out.print(cell + "\t");
}
System.out.println();
}

}

public static void main(String[] args) {
int[][] chromosome= {{0,10,15,20},
{5,0,9,10},
{6,13,0,12},
{8,8,9,0}};

System.out.println("Original chromosome:");
printchromosome(chromosome);

//mutation
mutatedchromosome(chromosome);

System.out.println("Mutatechromosome:");
printchromosome(chromosome);

}

}
--------------------------------------------------------------------------------------------------------------------
Practical 5
import java.util.Arrays;

public class knspack {

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

for (int i = 0; i <= n; i++) {
for (int w = 0; w <= capacity; w++) {
if (i == 0 || w == 0) {
dp[i][w] = 0;
} else 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) {
int[] values = {10, 10, 12,18};
int[] weights = {2, 4, 6,9};
int capacity = 15;

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

System.out.println("profits are :"+Arrays.toString(values));
System.out.println("Weights are :"+Arrays.toString(weights));
System.out.println("capacity is :"+capacity);

System.out.println("Maximum value in the knapsack: " + maxValue);
}
}
--------------------------------------------------------------------------------------------------------------
Practical 6
public class NQueens {
public static void main(String[] args) {
for (int n = 4; n <= 8; n++) {
long startTime = System.nanoTime();
solveNQueens(n);
long endTime = System.nanoTime();
System.out.println("Time taken for " + n + "-Queens: " + (endTime - startTime)+" seconds\n");
}
}

private static void solveNQueens(int n) {
char[][] board = new char[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = '.';
}
}

if (!solveNQueensUtil(board, 0, n)) {
System.out.println("No solution exists for " + n + "-Queens.");
return;
}

System.out.println("Solutions for " + n + "-Queens:");
printSolution(board);
}

private static boolean solveNQueensUtil(char[][] board, int row, int n) {
if (row == n) {
return true;
}

for (int col = 0; col < n; col++) {
if (isSafe(board, row, col, n)) {
board[row][col] = 'Q';
if (solveNQueensUtil(board, row + 1, n)) {
return true;
}
board[row][col] = '.'; // Backtrack if placing a queen doesn't lead to a solution
}
}

return false;
}

private static boolean isSafe(char[][] board, int row, int col, int n) {
// Check if there is a queen in the same column
for (int i = 0; i < row; i++) {
if (board[i][col] == 'Q') {
return false;
}
}

// Check upper left diagonal
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') {
return false;
}
}

// Check upper right diagonal
for (int i = row, j = col; i >= 0 && j < n; i--, j++) {
if (board[i][j] == 'Q') {
return false;
}
}

return true;
}

private static void printSolution(char[][] board) {
for (char[] row : board) {
System.out.println(new String(row));
}
System.out.println();
}
}
----------------------------------------------------------------------------------------------------------------
Practical 7(use either approach 1 or 2)

Approach 1

import java.util.Scanner;
public class TSP {

private static int[][] graph;
private static int[] path;
private static boolean[] visited;
private static int n;
private static int minCost;
private static int[] bestPath;

public static void main(String[] args) {
Scanner input = new Scanner(System.in);

System.out.print("Enter the number of cities: ");
n = input.nextInt();

graph = new int[n][n];
path = new int[n];
visited = new boolean[n];
bestPath = new int[n];
minCost = Integer.MAX_VALUE;

System.out.println("Enter the cost matrix (0 for diagonal elements):");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = input.nextInt();
}
}

input.close();

path[0] = 0; // Start from the first city (0)
visited[0] = true; // Mark the first city as visited

tspBranchAndBound(1, 0, 0, path);

System.out.println("Minimum cost: " + minCost);
System.out.print("Optimal Path: ");
for (int i = 0; i < n; i++) {
System.out.print(bestPath[i] + " ");
}
}

public static void tspBranchAndBound(int level, int cost, int pos, int[] path) {
if (level == n) {
if (graph[path[level - 1]][0] != 0 && cost + graph[path[level - 1]][0] < minCost) {
minCost = cost + graph[path[level - 1]][0];
System.arraycopy(path, 0, bestPath, 0, n);
}
return;
}

for (int i = 0; i < n; i++) {
if (!visited[i] && graph[path[level - 1]][i] != 0) {
visited[i] = true;
path[level] = i;
tspBranchAndBound(level + 1, cost + graph[path[level - 1]][i], i, path);
visited[i] = false;
}
}
}
}
Approach 2

import java.util.*;

class Node {
public int cost;
public int idx;
public int[][] matrix;

public static int[][] deepCopy(int[][] matrix, int N) {
int[][] matrixCopy = new int[N][N];

for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
matrixCopy[i][j] = matrix[i][j];
}
}

return matrixCopy;
}

Node() {
cost = 0;
}

Node(int[][] matrix, int idx, int N) {
this.matrix = deepCopy(matrix, N);
this.idx = idx;
cost = 0;
}
}

public class TSP {

public static int reduceMatrix(int[][] matrix, boolean byCol, int N) {
int cost = 0;

for (int i = 0; i < N; i++) {
int min_value = Integer.MAX_VALUE;

for (int j = 0; j < N; j++) {
int curr_value = byCol ? matrix[j][i] : matrix[i][j];
if (curr_value == Integer.MAX_VALUE)
continue;
min_value = Math.min(min_value, curr_value);
}

for (int j = 0; j < N; j++) {
int curr_value = byCol ? matrix[j][i] : matrix[i][j];
if (curr_value == Integer.MAX_VALUE)
continue;
if (byCol)
matrix[j][i] -= min_value;
else
matrix[i][j] -= min_value;
}

if (min_value != Integer.MAX_VALUE)
cost += min_value;
}

return cost;
}

public static void display(int[][] matrix, int N) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (matrix[i][j] == Integer.MAX_VALUE)
System.out.print("$ ");
else
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
System.out.println();
}

public static int[][] deepCopy(int[][] matrix, int N) {
int[][] matrixCopy = new int[N][N];

for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
matrixCopy[i][j] = matrix[i][j];
}
}

return matrixCopy;
}

public static void markInfinity(int[][] matrix, int r, int c, int N) {
for (int i = 0; i < N; i++) {
matrix[r][i] = Integer.MAX_VALUE;
matrix[i][c] = Integer.MAX_VALUE;
}
matrix[c][r] = Integer.MAX_VALUE;
}

public static void solveTSP(int[][] matrix, int N) {
String path = "1";

Queue<Node> q = new LinkedList<>();

Node node = new Node(matrix, 0, N);
boolean[][] visited = new boolean[N][N];

for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
visited[i][j] = false;
if (i == j)
visited[i][j] = true;
}
}

q.add(node);

while (q.size() > 0) {
System.out.println();
Node n1 = q.poll();

n1.cost += reduceMatrix(n1.matrix, false, N);
n1.cost += reduceMatrix(n1.matrix, true, N);

int overallMinCost = Integer.MAX_VALUE;
Node n3 = new Node();

System.out.println(n1.cost + " | " + n1.idx + " () \n");

boolean gotThisTime = false;

for (int i = 0; i < N; i++) {
if (!visited[n1.idx][i]) {
visited[n1.idx][i] = true;
visited[i][n1.idx] = true;

Node n2 = new Node(n1.matrix, i, N);

markInfinity(n2.matrix, n1.idx, i, N);

n2.cost += reduceMatrix(n2.matrix, false, N);
n2.cost += reduceMatrix(n2.matrix, true, N);

int totalCost = n1.matrix[n1.idx][i] + n1.cost + n2.cost;

System.out.println(n1.cost + " " + n2.cost + " | " + n1.idx + " " + i + " () " + totalCost);

if (totalCost < overallMinCost) {
overallMinCost = totalCost;
gotThisTime = true;
n3 = n2;
}
}
}

if (gotThisTime) {
n3.cost = overallMinCost;
q.add(n3);
path += "->" + (n3.idx + 1);
}
}

System.out.println(path);
}

public static void main(String[] args) {
int MAX = Integer.MAX_VALUE;

int[][] matrix = {
{ MAX, 20, 30, 10, 11 },
{ 15, MAX, 16, 4, 2 },
{ 3, 5, MAX, 2, 4 },
{ 19, 6, 18, MAX, 3 },
{ 16, 4, 7, 16, MAX }
};

int N = 5;

solveTSP(matrix, N);
}
}

----------------------------------------------------------------------------------------------------------------
Practical 11

import java.util.concurrent.Semaphore;

class Philosopher extends Thread {
private final int id;
private final Semaphore leftFork;
private final Semaphore rightFork;

public Philosopher(int id, Semaphore leftFork, Semaphore rightFork) {
this.id = id;
this.leftFork = leftFork;
this.rightFork = rightFork;
}

public void run() {
try {
while (true) {
think();
leftFork.acquire();
rightFork.acquire();
eat();
leftFork.release();
rightFork.release();
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}

private void think() throws InterruptedException {
System.out.println("Philosopher " + id + " is thinking");
Thread.sleep(1000); // Simulating thinking time
}

private void eat() throws InterruptedException {
System.out.println("Philosopher " + id + " is eating");
Thread.sleep(1000); // Simulating eating time
}
}

public class DiningPhilosophers {
public static void main(String[] args) {
final int numPhilosophers = 5;
Semaphore[] forks = new Semaphore[numPhilosophers];
Philosopher[] philosophers = new Philosopher[numPhilosophers];

for (int i = 0; i < numPhilosophers; i++) {
forks[i] = new Semaphore(1); // Each fork is a semaphore
}

for (int i = 0; i < numPhilosophers; i++) {
philosophers[i] = new Philosopher(i, forks[i], forks[(i + 1) % numPhilosophers]);
philosophers[i].start();
}
}
}
-------------------------------------------------------------------------------------------------------------------
Practical 12
import java.util.Scanner;

public class MatrixMultiplication {

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);

System.out.print("Enter the number of rows for matrix A: ");
int rowsA = scanner.nextInt();

System.out.print("Enter the number of columns for matrix A: ");
int colsA = scanner.nextInt();

System.out.print("Enter the number of rows for matrix B: ");
int rowsB = scanner.nextInt();

System.out.print("Enter the number of columns for matrix B: ");
int colsB = scanner.nextInt();

// Check if multiplication is possible
if (colsA != rowsB) {
System.out.println("Matrix multiplication is not possible. Number of columns in A must be equal to the number of rows in B.");
scanner.close();
return;
}

int[][] matrixA = readMatrix(rowsA, colsA, scanner, "A");
int[][] matrixB = readMatrix(rowsB, colsB, scanner, "B");

// Sequential multiplication
long startTimeSequential = System.nanoTime();
int[][] resultSequential = multiplyMatrixSequential(matrixA, matrixB);
long endTimeSequential = System.nanoTime();
System.out.println("Sequential Matrix Multiplication Time: " + (endTimeSequential - startTimeSequential) + " nanoseconds");

// Multithreaded multiplication
int numThreads = 4; // You can adjust the number of threads
long startTimeMultithreaded = System.nanoTime();
int[][] resultMultithreaded = multiplyMatrixMultithreaded(matrixA, matrixB, numThreads);
long endTimeMultithreaded = System.nanoTime();
System.out.println("Multithreaded Matrix Multiplication Time: " + (endTimeMultithreaded - startTimeMultithreaded) + " nanoseconds");

// Print results
System.out.println("\nMatrix A:");
printMatrix(matrixA);

System.out.println("\nMatrix B:");
printMatrix(matrixB);

System.out.println("\nSequential Result:");
printMatrix(resultSequential);

System.out.println("\nMultithreaded Result:");
printMatrix(resultMultithreaded);

// Check if the results are the same
System.out.println("\nResults are equal: " + arraysEqual(resultSequential, resultMultithreaded));
}

private static int[][] readMatrix(int rows, int cols, Scanner scanner, String name) {
System.out.println("Enter elements for matrix " + name + ":");
int[][] matrix = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
matrix[i][j] = scanner.nextInt();
}
}
return matrix;
}

private static int[][] multiplyMatrixSequential(int[][] matrixA, int[][] matrixB) {
int rowsA = matrixA.length;
int colsA = matrixA[0].length;
int colsB = matrixB[0].length;

int[][] result = new int[rowsA][colsB];

for (int i = 0; i < rowsA; i++) {
for (int j = 0; j < colsB; j++) {
for (int k = 0; k < colsA; k++) {
result[i][j] += matrixA[i][k] * matrixB[k][j];
}
}
}

return result;
}

private static int[][] multiplyMatrixMultithreaded(int[][] matrixA, int[][] matrixB, int numThreads) {
int rowsA = matrixA.length;
int colsA = matrixA[0].length;
int colsB = matrixB[0].length;

int[][] result = new int[rowsA][colsB];
Thread[] threads = new Thread[numThreads];

for (int i = 0; i < numThreads; i++) {
final int startRow = i * rowsA / numThreads;
System.out.println("Start row " + startRow);
final int endRow = (i + 1) * rowsA / numThreads;
System.out.println("End row " + endRow);

threads[i] = new Thread(() -> {
for (int row = startRow; row < endRow; row++) {
for (int j = 0; j < colsB; j++) {
for (int k = 0; k < colsA; k++) {
result[row][j] += matrixA[row][k] * matrixB[k][j];
}
}
}
});

threads[i].start();
}

// Wait for all threads to finish
try {
for (Thread thread : threads) {
thread.join();
}
} catch (InterruptedException e) {
e.printStackTrace();
}

return result;
}

private static boolean arraysEqual(int[][] array1, int[][] array2) {
for (int i = 0; i < array1.length; i++) {
for (int j = 0; j < array1[0].length; j++) {
if (array1[i][j] != array2[i][j]) {
return false;
}
}
}
return true;
}

private static void printMatrix(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
}