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

popular post

OOPJ PROGRAMS

-
Image
Practicals 1. Write a program to print “Hello CGPIT” on the console . public class pr1 {     public static void main ( String args [])     {         System . out . println ( "Hello CGPIT" );     } } output: 2. Write a program to print inputs given from command line arguments on the console. public class pr2 {     public static void main ( String args [])     {         for ( int i = 0 ;i< args . length ;i++)         {         System . out . println (args[i]);         }     } } output: 3. Write a program to check whether given number is Armstrong or not. import java.util.Scanner; public class ars {     public static void main ( String args [])     {         int n , temp , sum = 0 ,r;         Scanner s1 = new Scanner ( System . in );    ...
Read more