Q1) Implement Insertion Sort (show output after every pass)

import java.util.Scanner;

public class InsertionSort {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // Get array size from user
        System.out.print("Enter the number of elements: ");
        int n = scanner.nextInt();
        
        // Create array of specified size
        int[] arr = new int[n];
        
        // Get array elements from user
        System.out.println("Enter the elements:");
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        
        System.out.println("\\nOriginal array:");
        printArray(arr);
        
        insertionSort(arr);
        
        System.out.println("\\nSorted array:");
        printArray(arr);
        
        scanner.close();
    }
    
    // Insertion sort implementation with pass-by-pass output
    static void insertionSort(int[] arr) {
        int n = arr.length;
        
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            
            // Move elements of arr[0..i-1] that are greater than key
            // to one position ahead of their current position
            
            //check karta hai ki piche koi uthaye hue se bada hai ki nai , 
            //agar bada mila toh usko aage bhej dega and
            // agar koi bada nahi mila toh fir wo jaga
            //par uthaya hua swap kardega
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
            
            // Display array after each pass
            System.out.println("\\nAfter pass " + i + ":");
            printArray(arr);
        }
    }
    
    // Utility method to print an array
    static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

Q2) Implement Selection Sort (show output after every pass)

import java.util.Scanner;

public class SelectionSort {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // Get array size from user
        System.out.print("Enter the number of elements: ");
        int n = scanner.nextInt();
        
        // Create array of specified size
        int[] arr = new int[n];
        
        // Get array elements from user
        System.out.println("Enter the elements:");
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        
        System.out.println("\\nOriginal array:");
        printArray(arr);
        
        selectionSort(arr);
        
        System.out.println("\\nSorted array:");
        printArray(arr);
        
        scanner.close();
    }
    
    // Selection sort implementation with pass-by-pass output
    static void selectionSort(int[] arr) {
        int n = arr.length;
        
        // One by one move boundary of unsorted subarray
        for (int i = 0; i < n-1; i++) {
            // Find the minimum element in unsorted array
            int minIdx = i;
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            
            // Swap the found minimum element with the first element
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
            
            // Display array after each pass
            System.out.println("\\nAfter pass " + (i+1) + ":");
            printArray(arr);
        }
    }
    
    // Utility method to print an array
    static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

Q3) Implement Quick Sort (Print number of calls to quick sort procedure)

import java.util.Scanner;

public class QuickSort {
    // Counter for the number of calls to quick sort procedure
    private static int callCount = 0;
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // Get array size from user
        System.out.print("Enter the number of elements: ");
        int n = scanner.nextInt();
        
        // Create array of specified size
        int[] arr = new int[n];
        
        // Get array elements from user
        System.out.println("Enter the elements:");
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        
        System.out.println("\\nOriginal array:");
        printArray(arr);
        
        // Reset the call counter before sorting
        callCount = 0;
        
        // Perform quick sort
        quickSort(arr, 0, n - 1);
        
        System.out.println("\\nSorted array:");
        printArray(arr);
        
        System.out.println("\\nNumber of calls to quick sort procedure: " + callCount);
        
        scanner.close();
    }
    
    // Quick sort implementation
    static void quickSort(int[] arr, int low, int high) {
        // Increment call counter
        callCount++;
        
        if (low < high) {
            // Partition the array and get the pivot index
            int pi = partition(arr, low, high);
            
            // Recursively sort elements before and after partition
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }
    
    // Partition function for quick sort
    static int partition(int[] arr, int low, int high) {
        // Select the rightmost element as pivot
        int pivot = arr[high];
        
        // Index of smaller element
        int i = (low - 1);
        
        for (int j = low; j < high; j++) {
            // If current element is smaller than or equal to pivot
            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;
    }
    
    // Utility method to print an array
    static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

Q4) Implement Merge Sort (Print number of calls to merge sort procedure)

import java.util.*;

public class MergeSort {
    private static int callCount = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("Enter number of elements: ");
        int n = sc.nextInt();
        int[] arr = new int[n];

        System.out.println("Enter the elements:");
        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();

        System.out.println("\\nOriginal array: " + Arrays.toString(arr));

        callCount = 0;
        mergeSort(arr, 0, n - 1);

        System.out.println("Sorted array: " + Arrays.toString(arr));
        System.out.println("Number of calls to mergeSort: " + callCount);

        sc.close();
    }

    static void mergeSort(int[] arr, int left, int right) {
        callCount++;
        if (left >= right) return;

        int mid = (left + right) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }

    static void merge(int[] arr, int left, int mid, int right) {
        int[] merged = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;

        while (i <= mid && j <= right) {
            merged[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
        }
        while (i <= mid) merged[k++] = arr[i++];
        while (j <= right) merged[k++] = arr[j++];

        // Copy merged result back to original array
        for (i = 0; i < merged.length; i++) arr[left + i] = merged[i];
    }
}

Q5) Implement minimum spanning tree using Prim’s algorithm. (Print minimum cost and edges in MST)

// A Java program for Prim's Minimum Spanning Tree (MST)
// algorithm. The program is for adjacency matrix
// representation of the graph

import java.io.*;
import java.lang.*;
import java.util.*;

class MST {

    // A utility function to find the vertex with minimum
    // key value, from the set of vertices not yet included
    // in MST
    int minKey(int key[], Boolean mstSet[])
    {
        // Initialize min value
        int min = Integer.MAX_VALUE, min_index = -1;

        for (int v = 0; v < mstSet.length; v++)
            if (mstSet[v] == false && key[v] < min) {
                min = key[v];
                min_index = v;
            }

        return min_index;
    }

    // A utility function to print the constructed MST
    // stored in parent[]
    void printMST(int parent[], int graph[][])
    {
        int sum = 0;
        System.out.println("Edge \\tWeight");
        for (int i = 1; i < graph.length; i++){
            System.out.println(parent[i] + " - " + i + "\\t"
                               + graph[parent[i]][i]);
            sum += graph[parent[i]][i];
        }
        
        System.out.println("\\n\\nTotal Cost is " + sum);
                               
        
    }

    // Function to construct and print MST for a graph
    // represented using adjacency matrix representation
    void primMST(int graph[][])
    {
        int V = graph.length;
        
        // Array to store constructed MST
        int parent[] = new int[V];

        // Key values used to pick minimum weight edge in
        // cut
        int key[] = new int[V];

        // To represent set of vertices included in MST
        Boolean mstSet[] = new Boolean[V];

        // Initialize all keys as INFINITE
        for (int i = 0; i < V; i++) {
            key[i] = Integer.MAX_VALUE;
            mstSet[i] = false;
        }

        // Always include first 1st vertex in MST.
        // Make key 0 so that this vertex is
        // picked as first vertex
        key[0] = 0;
      
        // First node is always root of MST
        parent[0] = -1;

        // The MST will have V vertices
        for (int count = 0; count < V - 1; count++) {
            
            // Pick the minimum key vertex from the set of
            // vertices not yet included in MST
            int u = minKey(key, mstSet);

            // Add the picked vertex to the MST Set
            mstSet[u] = true;

            // Update key value and parent index of the
            // adjacent vertices of the picked vertex.
            // Consider only those vertices which are not
            // yet included in MST
            for (int v = 0; v < V; v++)

                // graph[u][v] is non zero only for adjacent
                // vertices of m mstSet[v] is false for
                // vertices not yet included in MST Update
                // the key only if graph[u][v] is smaller
                // than key[v]
                if (graph[u][v] != 0 && mstSet[v] == false
                    && graph[u][v] < key[v]) {
                    parent[v] = u;
                    key[v] = graph[u][v];
                }
        }

        // Print the constructed MST
        printMST(parent, graph);
    }

    public static void main(String[] args)
    {
        MST t = new MST();
        int graph[][] = new int[][] { { 0, 2, 0, 6, 0 },
                                      { 2, 0, 3, 8, 5 },
                                      { 0, 3, 0, 0, 7 },
                                      { 6, 8, 0, 0, 9 },
                                      { 0, 5, 7, 9, 0 } };

        // Print the solution
        t.primMST(graph);
    }
}

Q6) Implement minimum spanning tree using Kruskals algorithm. (Print minimum cost and edges in MST)

import java.util.*;

public class SimpleKruskal {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // Step 1: Take input
        System.out.print("Enter number of vertices: ");
        int V = sc.nextInt();

        System.out.print("Enter number of edges: ");
        int E = sc.nextInt();

        int[][] edges = new int[E][3]; // {u, v, weight}

        System.out.println("Enter edges (u v weight):");
        for (int i = 0; i < E; i++) {
            edges[i][0] = sc.nextInt(); // u
            edges[i][1] = sc.nextInt(); // v
            edges[i][2] = sc.nextInt(); // weight
        }

        // Step 2: Sort edges by weight
        Arrays.sort(edges, Comparator.comparingInt(a -> a[2]));

        // Step 3: Initialize parent array for cycle detection
        int[] parent = new int[V];
        for (int i = 0; i < V; i++) parent[i] = i;

        // Step 4: Kruskal's Algorithm
        int minCost = 0;
        System.out.println("\\nEdges in MST:");
        for (int i = 0; i < E; i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            int wt = edges[i][2];

            // Find parent
            while (parent[u] != u) u = parent[u];
            while (parent[v] != v) v = parent[v];

            // If adding edge doesn't form a cycle
            if (u != v) {
                System.out.println(edges[i][0] + " - " + edges[i][1] + " : " + wt);
                minCost += wt;
                parent[u] = v; // Union
            }
        }

        System.out.println("\\nMinimum Cost: " + minCost);
    }
}

Q7) Implement 0/1 Knapsack algorithm (Print length, total profit earned and matrix)

import java.util.ArrayList;
import java.util.Scanner;

public class KnapsackProblem {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // Get knapsack capacity
        System.out.print("Enter the capacity of the knapsack: ");
        int capacity = scanner.nextInt();
        
        // Get number of items
        System.out.print("Enter the number of items: ");
        int n = scanner.nextInt();
        
        int[] weights = new int[n];
        int[] profits = new int[n];
        
        // Get weights of items
        System.out.println("Enter the weights of the items:");
        for (int i = 0; i < n; i++) {
            System.out.print("Weight of item " + (i + 1) + ": ");
            weights[i] = scanner.nextInt();
        }
        
        // Get profits of items
        System.out.println("Enter the profits of the items:");
        for (int i = 0; i < n; i++) {
            System.out.print("Profit of item " + (i + 1) + ": ");
            profits[i] = scanner.nextInt();
        }
        
        // Solve the knapsack problem
        KnapsackResult result = knapsack01(weights, profits, capacity);
        
        // Print capacity
        System.out.println("\\nKnapsack Capacity: " + capacity);
        
        // Print maximum profit
        System.out.println("Maximum Profit: " + result.maxProfit);
        
        // Print selected items
        System.out.print("Selected Items (indices): ");
        for (int index : result.selectedItems) {
            System.out.print((index + 1) + " "); // Adding 1 to make it 1-indexed for user
        }
        System.out.println();
        
        System.out.print("Selected Items (weights): ");
        for (int index : result.selectedItems) {
            System.out.print(weights[index] + " ");
        }
        System.out.println();
        
        System.out.print("Selected Items (profits): ");
        for (int index : result.selectedItems) {
            System.out.print(profits[index] + " ");
        }
        System.out.println();
        
        // Print DP matrix
        System.out.println("\\nDP Matrix:");
        for (int i = 0; i <= n; i++) {
            for (int w = 0; w <= capacity; w++) {
                System.out.print(result.dpMatrix[i][w] + "\\t");
            }
            System.out.println();
        }
        
        scanner.close();
    }
    
    public static KnapsackResult knapsack01(int[] weights, int[] profits, int capacity) {
        int n = weights.length;
        
        // Initialize the DP matrix with 0's
        int[][] dp = new int[n + 1][capacity + 1];
        
        // Fill the DP table
        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= capacity; w++) {
                // If current item weight is less than or equal to the current capacity
                if (weights[i-1] <= w) {
                    // Take maximum of including or excluding the current item
                    dp[i][w] = Math.max(profits[i-1] + dp[i-1][w-weights[i-1]], dp[i-1][w]);
                } else {
                    // Current item weight exceeds capacity, so exclude it
                    dp[i][w] = dp[i-1][w];
                }
            }
        }
        
        // Determine which items are included in the optimal solution
        ArrayList<Integer> selectedItems = new ArrayList<>();
        int i = n, j = capacity;
        while (i > 0 && j > 0) {
            if (dp[i][j] != dp[i-1][j]) {
                selectedItems.add(0, i-1); // Add at the beginning to maintain order
                j -= weights[i-1];
            }
            i--;
        }
        
        // Create and return the result
        KnapsackResult result = new KnapsackResult();
        result.maxProfit = dp[n][capacity];
        result.selectedItems = selectedItems;
        result.dpMatrix = dp;
        
        return result;
    }
    
    static class KnapsackResult {
        int maxProfit;
        ArrayList<Integer> selectedItems;
        int[][] dpMatrix;
    }
}