Design And Analysis Of Algorithm
Implement following algorithm in iterative and recursive manner:
A. GCD algorithm
B. Factorial algorithm
C. Fibonacci algorithm
Factorial Algorithm
import java.util.Scanner;
public class Factorial {
public static void main(String[] args) {
int choice;
Scanner scanner = new Scanner(System.in);
do{
System.out.print("Enter a number: ");
int number = scanner.nextInt();
System.out.println("Select an approach:");
System.out.println("1. Iterative");
System.out.println("2. Recursive");
System.out.println("3.Stop the Program");
System.out.print("Enter your choice: ");
choice = scanner.nextInt();
long startTime = System.nanoTime(); // Start execution time
long result;
switch (choice) {
case 1:
result = factorialIterative(number);
System.out.println("Factorial (Iterative): " + result);
break;
case 2:
result = factorialRecursive(number);
System.out.println("Factorial (Recursive): " + result);
break;
case 3:
break;
default:
System.out.println("Invalid choice!");
}
long endTime = System.nanoTime(); // End execution time
long executionTime = endTime - startTime;
System.out.println("Execution Time: " + executionTime + " nanoseconds");
}while(choice!=3);
}
private static long factorialIterative(int number) {
long result = 1;
for (int i = 1; i <= number; i++) {
result *= i;
}
return result;
}
private static long factorialRecursive(int number) {
if (number == 0 || number == 1) {
return 1;
} else {
return number * factorialRecursive(number - 1);
}
}
}
Output:
Enter a number: 5
Select an approach:
1. Iterative
2. Recursive
3.Stop the Program
Enter your choice: 1
Factorial (Iterative): 120
Execution Time: 12608400 nanoseconds
Enter a number: 5
Select an approach:
1. Iterative
2. Recursive
3.Stop the Program
Enter your choice: 2
Factorial (Recursive): 120
Execution Time: 666000 nanoseconds
Enter a number: 5
Select an approach:
1. Iterative
2. Recursive
3.Stop the Program
Enter your choice: 3
Execution Time: 700 nanoseconds
Fibonacci Algorithm
import java.util.Scanner;
public class fibonacci {
public static void main(String[] args) {
int choice;
Scanner scanner = new Scanner(System.in);
do{
System.out.print("Enter the number of terms: ");
int n = scanner.nextInt();
System.out.println("Select an approach:");
System.out.println("1. Iterative");
System.out.println("2. Recursive");
System.out.println("3.Stop The Program");
System.out.print("Enter your choice: ");
choice = scanner.nextInt();
long startTime = System.nanoTime();
switch(choice){
case 1:
System.out.println("Fibonacci series (Iterative):");
for (int i = 0; i < n; i++) {
System.out.print(fibonacciIterative(i) + " ");
}
break;
case 2:
System.out.println("\n\nFibonacci series (Recursive):");
for (int i = 0; i < n; i++) {
System.out.print(fibonacciRecursive(i) + " ");
}
break;
case 3:
break;
default:
System.out.println("Invalid choice!");
}
long endTime = System.nanoTime(); // End execution time
long executionTime = endTime - startTime;
System.out.println("\nExecution Time: " + executionTime + " nanoseconds");
}while(choice!=3);
}
public static int fibonacciIterative(int n) {
switch (n) {
case 0:
return 0;
case 1:
return 1;
default:
int prev1 = 0;
int prev2 = 1;
int fib = 0;
for (int i = 2; i <= n; i++) {
fib = prev1 + prev2;
prev1 = prev2;
prev2 = fib;
}
return fib;
}
}
public static int fibonacciRecursive(int n) {
switch (n) {
case 0:
return 0;
case 1:
return 1;
default:
return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}
}
}
Output:
Enter the number of terms: 10
Select an approach:
1. Iterative
2. Recursive
3.Stop The Program
Enter your choice: 1
Fibonacci series (Iterative):
0 1 1 2 3 5 8 13 21 34
Execution Time: 10342800 nanoseconds
Enter the number of terms: 10
Select an approach:
1. Iterative
2. Recursive
3.Stop The Program
Enter your choice: 2
Fibonacci series (Recursive):
0 1 1 2 3 5 8 13 21 34
Execution Time: 1811500 nanoseconds
Enter the number of terms: 34
Select an approach:
1. Iterative
2. Recursive
3.Stop The Program
Enter your choice: 3
Execution Time: 500 nanoseconds
3. GCD Algorithm
import java.util.Scanner;
public class GCDAlgorithm {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int choice;
do{
System.out.print("Enter the first number: ");
int num1 = scanner.nextInt();
System.out.print("Enter the second number: ");
int num2 = scanner.nextInt();
System.out.println("1.Iterative");
System.out.println("2.Recursive");
System.out.println("3.Stop the Program");
System.out.println("Enter Your choice: ");
choice=scanner.nextInt();
long startTime=System.nanoTime();
switch(choice){
case 1:
System.out.println("\nGCD (Iterative): " + gcdIterative(num1, num2));
break;
case 2:
System.out.println("GCD (Recursive): " + gcdRecursive(num1, num2));
break;
case 3:
break;
default:
System.out.println("Invalid choice!");
}
long endTime = System.nanoTime(); // End execution time
long executionTime = endTime - startTime;
System.out.println("\nExecution Time: " + executionTime + " nanoseconds");
}while(choice!=3);
}
public static int gcdIterative(int num1, int num2) {
int gcd = 0;
switch (num1) {
case 0:
gcd = num2;
break;
default:
while (num2 != 0) {
int temp = num2;
num2 = num1 % num2;
num1 = temp;
}
gcd = num1;
break;
}
return gcd;
}
public static int gcdRecursive(int num1, int num2) {
switch (num2) {
case 0:
return num1;
default:
return gcdRecursive(num2, num1 % num2);
}
}
}
Output:
Enter the first number: 33
Enter the second number: 33
1.Iterative
2.Recursive
3.Stop the Program
Enter Your choice:
1
GCD (Iterative): 33
Execution Time: 719600 nanoseconds
Enter the first number: 33
Enter the second number: 12
1.Iterative
2.Recursive
3.Stop the Program
Enter Your choice:
2
GCD (Recursive): 3
Execution Time: 387000 nanoseconds
Enter the first number: 12
Enter the second number: 4
1.Iterative
2.Recursive
3.Stop the Program
Enter Your choice:
3
Execution Time: 600 nanoseconds
HuffmanCode
import java.util.*;
class HuffmanNode implements Comparable<HuffmanNode> {
char character;
int frequency;
HuffmanNode left;
HuffmanNode right;
public HuffmanNode(char character, int frequency) {
this.character = character;
this.frequency = frequency;
}
public boolean isLeaf() {
return (left == null && right == null);
}
@Override
public int compareTo(HuffmanNode node) {
return this.frequency - node.frequency;
}
}
public class HuffmanCode {
public static Map<Character, String> generateHuffmanCodes(String input) {
// Calculate the frequency of each character
Map<Character, Integer> frequencyMap = new HashMap<>();
for (char c : input.toCharArray()) {
frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
}
// Create a priority queue (min heap) of Huffman nodes
PriorityQueue<HuffmanNode> queue = new PriorityQueue<>();
for (Map.Entry<Character, Integer> entry : frequencyMap.entrySet()) {
HuffmanNode node = new HuffmanNode(entry.getKey(), entry.getValue());
queue.add(node);
}
// Build the Huffman tree
while (queue.size() > 1) {
HuffmanNode leftChild = queue.poll();
HuffmanNode rightChild = queue.poll();
HuffmanNode parentNode = new HuffmanNode('\0', leftChild.frequency + rightChild.frequency);
parentNode.left = leftChild;
parentNode.right = rightChild;
queue.add(parentNode);
}
HuffmanNode root = queue.poll();
// Generate Huffman codes for each character
Map<Character, String> huffmanCodes = new HashMap<>();
generateCodes(root, "", huffmanCodes);
return huffmanCodes;
}
private static void generateCodes(HuffmanNode node, String code, Map<Character, String> huffmanCodes) {
if (node == null) {
return;
}
if (node.isLeaf()) {
huffmanCodes.put(node.character, code);
}
generateCodes(node.left, code + "0", huffmanCodes);
generateCodes(node.right, code + "1", huffmanCodes);
}
public static void main(String[] args) {
if (args.length == 0) {
System.out.println("No input provided!");
return;
}
String input = args[0];
Map<Character, String> huffmanCodes = generateHuffmanCodes(input);
System.out.println("Huffman Codes:");
for (Map.Entry<Character, String> entry : huffmanCodes.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
}
}
Comments
Post a Comment
Give your Feedback