// Fibonacci Series

import java.util.Scanner;

public class Main {

static int rSteps = 0;

static int iSteps = 0;

public static int rStepFibonacci(int n) {

rSteps++;

if (n < 0)

return 0;

if (n == 1 || n == 0)

return 1;

return rStepFibonacci(n - 1) + rStepFibonacci(n - 2);

public static void iStepFibonacci(int n) {

int[] f = new int[n];

f[0] = 0;

f[1] = 1;

iSteps = 1;

System.out.print("Fibonacci Series (Iterative): ");

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

iSteps++;

f[i] = f[i - 1] + f[i - 2];

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

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

}
 System.out.println();

public static void printFibonacciSeries(int n) {

System.out.print("Fibonacci Series (Recursive): ");

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

System.out.print(rStepFibonacci(i) + " ");

System.out.println();

public static void main(String[] args) {

int choice;

int n;

Scanner scanner = new Scanner(System.in);

while (true) {

System.out.println("Fibonacci Series Menu:");

System.out.println("1. Calculate Iteratively");

System.out.println("2. Calculate Recursively");

System.out.println("3. Quit");

System.out.print("Enter your choice: ");

choice = scanner.nextInt();

if (choice == 1 || choice == 2) {

System.out.print("Enter the number of Fibonacci numbers to generate: ");

n = scanner.nextInt();

if (n <= 0) {
 System.out.println("Invalid input. Please enter a positive number.");

continue;

if (choice == 1) {

iSteps = 0;

long startTime = System.currentTimeMillis();

iStepFibonacci(n);

long endTime = System.currentTimeMillis();

double elapsedTime = endTime - startTime;

System.out.println("Iterative function called " + iSteps + " times.");

System.out.println("Time taken: " + elapsedTime + " milliseconds");

} else if (choice == 2) {

rSteps = 0;

long startTime = System.currentTimeMillis();

printFibonacciSeries(n);

long endTime = System.currentTimeMillis();

double elapsedTime = endTime - startTime;

System.out.println("Recursive function called " + rSteps + " times.");

System.out.println("Time taken: " + elapsedTime + " milliseconds");

} else if (choice == 3) {

System.out.println("Successfully Exited.");

break;

} else {

System.out.println("Invalid choice. Please select a valid option.");

}
 }

scanner.close();

/*

output:

Fibonacci Series Menu:

1. Calculate Iteratively

2. Calculate Recursively

3. Quit

Enter your choice: 1

Enter the number of Fibonacci numbers to generate: 5

Fibonacci Series (Iterative): 0 1 1 2 3

Iterative function called 4 times.

Time taken: 17.0 milliseconds

Fibonacci Series Menu:

1. Calculate Iteratively

2. Calculate Recursively

3. Quit

Enter your choice: 2

Enter the number of Fibonacci numbers to generate: 6

Fibonacci Series (Recursive): 1 1 2 3 5 8

Recursive function called 34 times.

Fibonacci Series Menu:

1. Calculate Iteratively

2. Calculate Recursively

3. Quit

Enter your choice: 3

Successfully Exited.

*/
// HuffMann Encoding using greedy

import java.util.Scanner;

import java.util.PriorityQueue;

import java.util.HashMap;

class TreeNode {

char data;

float freq;

TreeNode left;

TreeNode right;

public TreeNode(char data, float freq) {

this.data = data;

this.freq = freq;

this.left = null;

this.right = null;

public class Main {

static int n = 0;

static char[] alphabets = new char[30];

static String[] codes = new String[30];

static TreeNode createHuffmanTree() {

Scanner scanner = new Scanner(System.in);

TreeNode root = null;

PriorityQueue<TreeNode> minHeap = new PriorityQueue<>((a, b) -> Float.compare(a.freq, b.freq));

int numAlphabets = scanner.nextInt();

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

System.out.print("\nEnter alphabet: ");

char alphabet = scanner.next().charAt(0);

System.out.print("\nEnter frequency: ");

float frequency = scanner.nextFloat();

TreeNode node = new TreeNode(alphabet, frequency);

minHeap.add(node);

while (minHeap.size() > 1) {

TreeNode left = minHeap.poll();

TreeNode right = minHeap.poll();

TreeNode newNode = new TreeNode('\0', left.freq + right.freq);

newNode.left = left;

newNode.right = right;

minHeap.add(newNode);

root = minHeap.poll();

return root;

static void encode() {

Scanner scanner = new Scanner(System.in);

System.out.print("\nEnter a Message: ");

String message = scanner.next();

for (char c : message.toCharArray()) {

int index = findCharIndex(c);

if (index >= 0) {

encodedMessage.append(codes[index]);

System.out.println("\nEncoded Message = " + encodedMessage);

static void decode(TreeNode root) {

Scanner scanner = new Scanner(System.in);

System.out.print("\nEnter an Encoded message: ");

String encodedMessage = scanner.next();

TreeNode current = root;

StringBuilder decodedMessage = new StringBuilder();

for (char bit : encodedMessage.toCharArray()) {

if (bit == '0') {

current = current.left;

} else {

current = current.right;

if (current.left == null && current.right == null) {

decodedMessage.append(current.data);
 current = root;

System.out.println("\nDecoded Message = " + decodedMessage);

static int findCharIndex(char c) {

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

if (alphabets[i] == c) {

return i;

return -1;

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

TreeNode root = null;

while (true) {

System.out.println("\nHuffman Coding Menu:");

System.out.println("1. Create Huffman Tree");

System.out.println("2. Encode a Message");

System.out.println("3. Decode a Message");

System.out.println("4. Exit");

System.out.print("Enter Your Choice: ");

int choice = scanner.nextInt();

case 1:

root = createHuffmanTree();

System.out.println("\nPrefix codes:");

n = 0;

preorder(root, 0, new char[30]);

break;

case 2:

encode();

break;

case 3:

decode(root);

break;

case 4:

System.out.println("Successfully Exited.");

scanner.close();

return;

default:

System.out.println("Invalid choice. Please select a valid option.");

static void preorder(TreeNode p, int i, char[] word) {

if (p != null) {

if (p.left == null && p.right == null) {

word[i] = 0;

System.out.println(p.data + " --- " + new String(word));

alphabets[n] = p.data;
 codes[n++] = new String(word);

word[i] = '0';

preorder(p.left, i + 1, word);

word[i] = '1';

preorder(p.right, i + 1, word);

/*

output:

Huffman Coding Menu:

1. Create Huffman Tree

2. Encode a Message

3. Decode a Message

4. Exit

Enter Your Choice: 1

Enter No. of alphabets: 6

Enter alphabet: A

Enter frequency: 0.2

Enter alphabet: B

Enter frequency: 0.15

Enter alphabet: C

Enter frequency: 0.25

Enter frequency: 0.1

Enter alphabet: E

Enter frequency: 0.3

Enter alphabet: F

Enter frequency: 0.05

Huffman Coding Menu:

1. Create Huffman Tree

2. Encode a Message

3. Decode a Message

4. Exit

Enter Your Choice: 2

Enter a Message: CAFE

Encoded Message = 11100

Huffman Coding Menu:

1. Create Huffman Tree

2. Encode a Message

3. Decode a Message

4. Exit

Enter Your Choice: 3

Enter an Encoded message: 11100

Decoded Message = CAFE

1. Create Huffman Tree

2. Encode a Message

3. Decode a Message

4. Exit

Enter Your Choice: 4

Successfully Exited.

*/
// Fractional Knapsack

//Fractional Knapsack

import java.util.ArrayList;

import java.util.Collections;

import java.util.List;

import java.util.Scanner;

class Item {

int profit;

int weight;

public Item(int profit, int weight) {

this.profit = profit;

this.weight = weight;

public class Main{

static class Pair {

double first;

double second;

Pair(double first, double second) {

this.first = first;

this.second = second;

}
static boolean compare(Pair p1, Pair p2) {

return p1.first > p2.first;

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int n;

System.out.print("Enter Number of Objects: ");

n = scanner.nextInt();

System.out.println("Enter Profit and Weight (P W): ");

List<Item> items = new ArrayList<>();

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

int profit = scanner.nextInt();

int weight = scanner.nextInt();

items.add(new Item(profit, weight));

System.out.print("Enter the Capacity: ");

int w = scanner.nextInt();

List<Pair> a = new ArrayList<>();

for (Item item : items) {

a.add(new Pair((double) item.profit / item.weight, (double) item.weight));

}
 Collections.sort(a, (p1, p2) -> Double.compare(p2.first, p1.first));

List<Double> solution = new ArrayList(Collections.nCopies(n, 0.0));

double ans = 0.0;

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

if (w >= a.get(i).second) {

ans += items.get(i).profit;

w -= a.get(i).second;

solution.set(i, 1.0);

} else {

double vw = (double) items.get(i).profit / items.get(i).weight;

ans += vw * w;

solution.set(i, (double) w / items.get(i).weight);

w = 0;

break;

System.out.println("\nOptimal Solution Vector: (" + solution + ")");

System.out.println("\nOptimal Value: " + ans);

scanner.close();

/*
Enter Number of Objects: 5

Enter Profit and Weight (P W):

60 10

100 20

120 30

90 5

50 15

Enter the Capacity: 50

Optimal Solution Vector: ([1.0, 1.0, 1.0, 3.0, 0.0])

Optimal Value: 550.0

*/
// 0-1 Knapsack

import java.util.Scanner;

public class Main {

public static int knapsack(int[] values, int[] weights, int capacity, int[] solution) {

int n = values.length;

// Create a 2D table to store the results of subproblems.

// dp[i][w] represents the maximum value that can be obtained with i items and a knapsack of
capacity w.

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

// Fill in the table using dynamic programming.

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(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);

} else {

dp[i][w] = dp[i - 1][w];

// Trace the solution to get the included items.

int i = n, w = capacity;

while (i > 0 && w > 0) {

solution[i - 1] = 1; // Item is included

w -= weights[i - 1];

i--;

// The value in the bottom-right corner of the table represents the maximum value that can be
obtained.

return dp[n][capacity];

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

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

int n = scanner.nextInt();

int[] values = new int[n];

int[] weights = new int[n];

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

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

values[i] = scanner.nextInt();

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

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

weights[i] = scanner.nextInt();
 }

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

int capacity = scanner.nextInt();

int[] solution = new int[n];

// Measure the time taken by the algorithm

long startTime = System.currentTimeMillis();

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

long endTime = System.currentTimeMillis();

System.out.println("\nMaximum value: " + maxValue);

System.out.print("\nSolution vector (1 for included, 0 for not included): ");

for (int item : solution) {

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

System.out.println();

System.out.println("Time taken: " + (endTime - startTime) + " milliseconds");

/*

Output:

Enter the number of items: 3

Enter the weights of items: 10 20 30

Enter the knapsack capacity: 50

Maximum value: 220

Solution vector (1 for included, 0 for not included): 1 1 1

Time taken: 0 milliseconds

*/
// N-Queen

import java.util.*;

public class Main {

static boolean[] col, d1, d2;

static boolean[][] board;

public static void solve(int r, int n) {

if (r == n) {

// Solution found, print the board

printBoard(board);

return;

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

if (!col[c] && !d1[r - c + n - 1] && !d2[r + c]) {

col[c] = d1[r - c + n - 1] = d2[r + c] = true;

board[r][c] = true;

solve(r + 1, n);

col[c] = d1[r - c + n - 1] = d2[r + c] = false;

board[r][c] = false;

public static void printBoard(boolean[][] board) {

int n = board.length;

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

if (board[i][j]) {

System.out.print("Q ");

} else {

System.out.print(". ");

System.out.println();

System.out.println();

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

scanner.close();

col = new boolean[n];

d1 = new boolean[2 * n - 1];

d2 = new boolean[2 * n - 1];

board = new boolean[n][n];

solve(0, n);

}
/*

output:

.Q..

...Q

Q...

..Q.

..Q.

Q...

...Q

.Q..

*/