[1] N-Queen
import java.u l.Scanner;
public class NQueens {
sta c int count = 0; // Solu on counter
sta c int fixedRow, fixedCol; // Posi on of the first queen
public sta c void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter n (size of the board): ");
int n = sc.nextInt();
char[][] board = new char[n][n];
// Ini alize the board with 'x'
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = 'x';
// Get first queen's posi on from the user
System.out.print("Enter the row for the first queen (0 to " + (n - 1) + "): ");
fixedRow = sc.nextInt();
System.out.print("Enter the column for the first queen (0 to " + (n - 1) + "): ");
fixedCol = sc.nextInt();
// Arrays to track if a column or diagonal is already occupied
boolean[] cols = new boolean[n];
boolean[] mainDiagonal = new boolean[2 * n - 1];
boolean[] an Diagonal = new boolean[2 * n - 1];
// Place the first queen
board[fixedRow][fixedCol] = 'Q';
cols[fixedCol] = true;
mainDiagonal[fixedRow - fixedCol + n - 1] = true;
an Diagonal[fixedRow + fixedCol] = true;
// Start solving from the next row a er fixedRow
nQueens(board, 0, cols, mainDiagonal, an Diagonal);
System.out.println("Total solu ons: " + count);
public sta c void nQueens(char[][] board, int row, boolean[] cols, boolean[] mainDiagonal,
boolean[] an Diagonal) {
// Base case: if all rows are processed
if (row == board.length) {
printBoard(board);
count++;
return;
// Skip the row of the fixed first queen
if (row == fixedRow) {
nQueens(board, row + 1, cols, mainDiagonal, an Diagonal);
return;
}
// Try placing a queen in each column of the current row
for (int col = 0; col < board.length; col++) {
if (cols[col] || mainDiagonal[row - col + board.length - 1] || an Diagonal[row + col]) {
con nue; // Skip if the posi on is under a ack
// Place queen
board[row][col] = 'Q';
cols[col] = mainDiagonal[row - col + board.length - 1] = an Diagonal[row + col] = true;
// Recurse to the next row
nQueens(board, row + 1, cols, mainDiagonal, an Diagonal);
// Backtrack by removing the queen
board[row][col] = 'x';
cols[col] = mainDiagonal[row - col + board.length - 1] = an Diagonal[row + col] = false;
public sta c void printBoard(char[][] board) {
System.out.println("-------------Solu on--------------");
for (char[] row : board) {
for (char cell : row) {
System.out.print(cell + " ");
System.out.println();
System.out.println("-----------------------------------");
}
[2]Fibonacci
import java.u l.*;
public class fib {
sta c Scanner sc = new Scanner(System.in);
public sta c int stepCount = 0;
public sta c int RecursiveFib(int n) {
stepCount++;
if (n <= 1) {
return n;
return RecursiveFib(n - 1) + RecursiveFib(n - 2);
public sta c int Itera veFib(int n) {
if (n <= 1) {
return n;
int a = 0, b = 1, c = 0;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
stepCount++;
}
return c;
public sta c void main(String args[]) {
System.out.println("Enter n : ");
int n = sc.nextInt();
System.out.println("Enter your choice : ");
System.out.println("1.Recursive ");
System.out.println("2.Itera ve ");
int choice = sc.nextInt();
switch (choice) {
case 1:
stepCount = 0;
System.out.println("Fibonacci of " + n + " is " + RecursiveFib(n));
System.out.println("Number of steps required to calculate Fibbonacci of " + n + " is " +
stepCount);
break;
case 2:
stepCount = 0;
System.out.println("Fibonacci of " + n + " is " + Itera veFib(n));
System.out.println("Number of steps required to calculate Fibbonacci of " + n + " is " +
stepCount);
break;
default:
System.out.println("Enter valid choice : ");
break;
}}}
[3]Frac onal Knapsack
import java.u l.*;
public class frac onalKnapsack {
public sta c void main(String args[]) {
Scanner sc = new Scanner(System.in);
// Taking number of items
System.out.print("Enter number of items: ");
int n = sc.nextInt();
// Taking values of items
int val[] = new int[n];
System.out.println("Enter the values of the items:");
for (int i = 0; i < n; i++) {
val[i] = sc.nextInt();
// Taking weights of items
int weight[] = new int[n];
System.out.println("Enter the weights of the items:");
for (int i = 0; i < n; i++) {
weight[i] = sc.nextInt();
// Taking capacity of knapsack
System.out.print("Enter the maximum capacity of the knapsack: ");
int w = sc.nextInt();
// Close scanner
sc.close();
// Calculate value-to-weight ra o
double ra o[][] = new double[n][2];
for (int i = 0; i < n; i++) {
ra o[i][0] = i;
ra o[i][1] = val[i] / (double) weight[i];
// Sort ra os in ascending order by value-to-weight ra o
Arrays.sort(ra o, Comparator.comparingDouble(o -> o[1]));
int capacity = w;
double finalVal = 0;
// Calculate maximum value that can be carried
for (int i = n - 1; i >= 0; i--) {
int idx = (int) ra o[i][0];
if (capacity >= weight[idx]) { // include full item
finalVal += val[idx];
capacity -= weight[idx];
} else {
// include frac onal item
finalVal += ra o[i][1] * capacity;
break;
System.out.println("Final Value: " + finalVal);
}}
[4]0/1 knapsack
import java.u l.Scanner;
import java.u l.PriorityQueue;
import java.u l.Arrays;
// Class to represent items in the knapsack
class KnapsackItem {
int weight;
int value;
KnapsackItem(int weight, int value) {
this.weight = weight;
this.value = value;
// Node class for branch and bound strategy
class Node {
int level, profit, weight;
double bound;
Node(int level, int profit, int weight, double bound) {
this.level = level;
this.profit = profit;
this.weight = weight;
this.bound = bound;
public class KnapsackSolver {
// Method to calculate upper bound for branch and bound node
private sta c double calculateBound(Node u, int n, int capacity, KnapsackItem[] items) {
if (u.weight >= capacity)
return 0;
double bound = u.profit;
int j = u.level + 1;
int totalWeight = u.weight;
while ((j < n) && (totalWeight + items[j].weight <= capacity)) {
totalWeight += items[j].weight;
bound += items[j].value;
j++;
if (j < n) {
bound += (capacity - totalWeight) * (double) items[j].value / items[j].weight;
return bound;
// Branch and Bound method for 0-1 Knapsack
public sta c int knapsackBranchAndBound(int[] weights, int[] values, int capacity) {
int n = weights.length;
KnapsackItem[] items = new KnapsackItem[n];
for (int i = 0; i < n; i++) {
items[i] = new KnapsackItem(weights[i], values[i]);
}
Arrays.sort(items, (i1, i2) -> Double.compare((double) i2.value / i2.weight, (double) i1.value /
i1.weight));
PriorityQueue<Node> queue = new PriorityQueue<>((n1, n2) -> Double.compare(n2.bound,
n1.bound));
Node u = new Node(-1, 0, 0, 0.0);
u.bound = calculateBound(u, n, capacity, items);
queue.add(u);
int maxProfit = 0;
while (!queue.isEmpty()) {
Node node = queue.poll();
if (node.level == -1) {
u.level = 0;
if (node.level == n - 1)
con nue;
Node v = new Node(node.level + 1, node.profit + items[node.level + 1].value,
node.weight + items[node.level + 1].weight, 0.0);
if (v.weight <= capacity && v.profit > maxProfit) {
maxProfit = v.profit;
v.bound = calculateBound(v, n, capacity, items);
if (v.bound > maxProfit) {
queue.add(v);
}
v = new Node(node.level + 1, node.profit, node.weight, 0.0);
v.bound = calculateBound(v, n, capacity, items);
if (v.bound > maxProfit) {
queue.add(v);
return maxProfit;
// Dynamic Programming method for 0-1 Knapsack
public sta c int knapsackDP(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 sta c void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// Example data
int[] weights = { 10, 20, 30 };
int[] values = { 60, 100, 120 };
int capacity = 50;
// User choice
System.out.println("Choose a method to solve the 0-1 Knapsack problem:");
System.out.println("1. Branch and Bound");
System.out.println("2. Dynamic Programming");
System.out.print("Enter choice (1 or 2): ");
int choice = scanner.nextInt();
int maxValue;
switch (choice) {
case 1:
maxValue = knapsackBranchAndBound(weights, values, capacity);
System.out.println("Maximum value in Knapsack using Branch and Bound = " + maxValue);
break;
case 2:
maxValue = knapsackDP(weights, values, capacity);
System.out.println("Maximum value in Knapsack using Dynamic Programming = " +
maxValue);
break;
default:
System.out.println("Invalid choice. Please choose 1 or 2.");
scanner.close();
}}
[5]QuickSort
import java.u l.Scanner;
import java.u l.Random;
public class QuickSortAnalysis {
// Determinis c variant of Quick Sort
public sta c void quickSortDeterminis c(int[] arr, int low, int high) {
if (low < high) {
int pi = par on(arr, low, high);
quickSortDeterminis c(arr, low, pi - 1);
quickSortDeterminis c(arr, pi + 1, high);
// Randomized variant of Quick Sort
public sta c void quickSortRandomized(int[] arr, int low, int high) {
if (low < high) {
int pi = randomizedPar on(arr, low, high);
quickSortRandomized(arr, low, pi - 1);
quickSortRandomized(arr, pi + 1, high);
// Par on func on for determinis c Quick Sort
private sta c int par on(int[] arr, int low, int high) {
int pivot = arr[high]; // last element as pivot
int i = (low - 1); // index of smaller element
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] (or pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
// Randomized par on func on
private sta c int randomizedPar on(int[] arr, int low, int high) {
Random rand = new Random();
int randomIndex = low + rand.nextInt(high - low);
int temp = arr[randomIndex];
arr[randomIndex] = arr[high];
arr[high] = temp;
return par on(arr, low, high);
// Func on to print the array
public sta c void printArray(int[] arr) {
for (int value : arr) {
System.out.print(value + " ");
System.out.println();
}
public sta c 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("Select Quick Sort Variant:");
System.out.println("1. Determinis c");
System.out.println("2. Randomized");
int choice = scanner.nextInt();
switch (choice) {
case 1:
System.out.println("Sor ng using Determinis c Quick Sort...");
quickSortDeterminis c(arr, 0, arr.length - 1);
break;
case 2:
System.out.println("Sor ng using Randomized Quick Sort...");
quickSortRandomized(arr, 0, arr.length - 1);
break;
default:
System.out.println("Invalid choice! Exi ng...");
return;
System.out.println("Sorted array:");
printArray(arr);
scanner.close();
}
[6]Huffman Coding
import java.u l.PriorityQueue;
class MinHeapNode {
char data;
int freq;
MinHeapNode le , right;
MinHeapNode(char data, int freq) {
le = right = null;
this.data = data;
this.freq = freq;
class HuffmanCoding {
// Func on to print Huffman Codes
public sta c void printCodes(MinHeapNode root, String str) {
if (root == null) {
return;
if (root.data != '$') {
System.out.println(root.data + ": " + str);
printCodes(root.le , str + "0");
printCodes(root.right, str + "1");
// Comparator class to order the nodes based on frequency
sta c class CompareNode implements java.u l.Comparator<MinHeapNode> {
public int compare(MinHeapNode a, MinHeapNode b) {
return a.freq - b.freq;
// Main func on to generate Huffman codes
public sta c void HuffmanCode(char[] data, int[] freq, int size) {
MinHeapNode le , right, temp;
// Create a priority queue to hold nodes of the Huffman tree
PriorityQueue<MinHeapNode> minHeap = new PriorityQueue<>(size, new CompareNode());
for (int i = 0; i < size; i++) {
minHeap.add(new MinHeapNode(data[i], freq[i]));
// Iterate un l size of heap is not 1
while (minHeap.size() > 1) {
le = minHeap.poll();
right = minHeap.poll();
temp = new MinHeapNode('$', le .freq + right.freq);
temp.le = le ;
temp.right = right;
minHeap.add(temp);
// Print Huffman codes
printCodes(minHeap.peek(), "");
}
public sta c void main(String[] args) {
char[] data = { 'A', 'B', 'C', 'D' };
int[] freq = { 23, 12, 34, 10 };
int size = data.length;
HuffmanCode(data, freq, size);
