[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);