ada

1.mergesort***********************************************
import java.util.Scanner;
import java.util.Arrays;
public class Mergesort {

    public static void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);
            merge(array, left, mid, right);
        }
    }

    public static void merge(int[] array, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        for (int i = 0; i < n1; i++) {
            leftArray[i] = array[left + i];
        }
        for (int j = 0; j < n2; j++) {
            rightArray[j] = array[mid + 1 + j];
        }

        int i = 0, j = 0;
        int k = left;

        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                array[k] = leftArray[i];
                i++;
            } else {
                array[k] = rightArray[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            array[k] = leftArray[i];
            i++;
            k++;
        }

        while (j < n2) {
            array[k] = rightArray[j];
            j++;
            k++;
        }
    }

    

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        System.out.print("Enter the number of elements in the array: ");
        int n = scanner.nextInt();
        
        int[] array = new int[n];
        
        System.out.println("Enter the elements of the array:");
        for (int i = 0; i < n; i++) {
            array[i] = scanner.nextInt();
        }

        System.out.println("Original array:"+Arrays.toString(array));
       

        mergeSort(array, 0, array.length - 1);

        System.out.println("Sorted array:"+Arrays.toString(array));
      

        scanner.close();
    }
}

2.quicksort*****************************************************************
import java.util.Scanner;
import java.util.Arrays;
public class QuickSort {

    // Main method that sorts the array
    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            // Partition the array and get the pivot index
            int pivotIndex = partition(array, low, high);
            // Recursively sort the elements before and after partition
            quickSort(array, low, pivotIndex - 1);
            quickSort(array, pivotIndex + 1, high);
        }
    }

    // Partition method with the first element as pivot
    private static int partition(int[] array, int low, int high) {
        int pivot = array[low]; // Choosing the first element as pivot
        int i = low + 1; // Start from the element after the pivot

        for (int j = low + 1; j <= high; j++) {
            // If the current element is smaller than or equal to the pivot
            if (array[j] <= pivot) {
                swap(array, i, j);
                i++;
            }
        }
        // Swap the pivot element with the element at index i-1
        swap(array, low, i - 1);
        return i - 1; // Return the partitioning index
    }

    // Swap helper method
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    // Method to print the array
  

    // Main method to test the algorithm
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        System.out.print("Enter the number of elements in the array: ");
        int n = scanner.nextInt();
        
        int[] array = new int[n];
        
        System.out.println("Enter the elements of the array:");
        for (int i = 0; i < n; i++) {
            array[i] = scanner.nextInt();
        }

        System.out.println("Original array:"+Arrays.toString(array));
       
        quickSort(array, 0, array.length - 1);

        System.out.println("Sorted array:"+Arrays.toString(array));
        
        scanner.close();
    }
}
3.articulation point**************************************************************
import java.util.*;

public class Articulation {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter number of vertices: ");
        int v = sc.nextInt(); // Number of vertices
        int[][] adj = new int[v + 1][v + 1];

        // Input adjacency matrix
        System.out.println("Enter adjacency matrix:");
        for (int i = 1; i <= v; i++) {
            for (int j = 1; j <= v; j++) {
                adj[i][j] = sc.nextInt();
            }
        }

        System.out.println("Articulation points are:");

        // Finding articulation points
        for (int i = 1; i <= v; i++) {
            boolean[] visited = new boolean[v + 1];
            int components = 0;

            // Counting connected components when vertex i is ignored
            for (int j = 1; j <= v; j++) {
                if (j != i && !visited[j]) {
                    dfs(j, visited, adj, v, i);
                    components++;
                }
            }

            // If more than one component, i is an articulation point
            if (components > 1) {
                System.out.println(i);
            }
        }
    }

    private static void dfs(int curr, boolean[] visited, int[][] adj, int v, int ignore) {
        visited[curr] = true;

        for (int k = 1; k <= v; k++) {
            if (adj[curr][k] == 1 && k != ignore && !visited[k]) {
                dfs(k, visited, adj, v, ignore);
            }
        }
    }
}
4.prims*************************************************************************

import java.util.*;

public class Prims {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter number of vertices: ");
        int n = sc.nextInt();
        int[][] graph = new int[n][n];

        System.out.println("Enter adjacency matrix:");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                graph[i][j] = sc.nextInt();
            }
        }

        // Arrays to store the MST data
        boolean[] inMST = new boolean[n];
        int[] key = new int[n];
        int[] parent = new int[n];

        // Initialize keys as infinite, and select the first vertex to start
        Arrays.fill(key, Integer.MAX_VALUE);
        key[0] = 0;
        parent[0] = -1;

        // Prim's algorithm loop
        for (int i = 0; i < n - 1; i++) {
            int u = minKey(key, inMST, n); // Find vertex with minimum key value
            inMST[u] = true; // Include this vertex in MST

            // Update the key and parent arrays
            for (int v = 0; v < n; v++) {
                if (graph[u][v] != 0 && !inMST[v] && graph[u][v] < key[v]) {
                    parent[v] = u;
                    key[v] = graph[u][v];
                }
            }
        }

        // Output the edges of the MST
        int totalWeight = 0;
        System.out.println("Edge \tWeight");
        for (int i = 1; i < n; i++) {
            System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
            totalWeight += graph[i][parent[i]];
        }
        
        System.out.println("Total weight of MST: " + totalWeight);
    }

    // Function to find the vertex with the minimum key value
    static int minKey(int[] key, boolean[] inMST, int n) {
        int min = Integer.MAX_VALUE, minIndex = -1;

        for (int v = 0; v < n; v++) {
            if (!inMST[v] && key[v] < min) {
                min = key[v];
                minIndex = v;
            }
        }
        return minIndex;
    }
}

5.knapsack*****************************************************************
import java.util.*;

public class Knapsack1 {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the number of objects");
        int n = sc.nextInt();

        int[] p = new int[n];
        int[] w = new int[n];

        System.out.println("Enter the item weight and value:");
        for (int i = 0; i < n; i++) {
            System.out.println("Item " + (i + 1) + " weight:");
            w[i] = sc.nextInt();
            System.out.println("Item " + (i + 1) + " profit:");
            p[i] = sc.nextInt();
        }

        System.out.println("Enter maximum knapsack capacity:");
        int m = sc.nextInt();

        sort(w, p);

        double maxProfit = 0;
        double remainingCapacity = m;

        System.out.println("Selected items:");
        for (int i = 0; i < w.length; i++) {
            if (remainingCapacity >= w[i]) {
                maxProfit += p[i];
                remainingCapacity -= w[i];
                System.out.println("Added item with weight " + w[i] + " and profit " + p[i]);
            } else {
                double fraction = remainingCapacity / (double) w[i];
                maxProfit += p[i] * fraction;
                System.out.println(
                        "Added fraction: " + fraction + " of item with weight " + w[i] + " and profit " + p[i]);
                break;
            }
        }

        System.out.println("Maximum profit: " + maxProfit);
    }

    public static void sort(int[] w, int[] p) {
        // Sort items based on profit-to-weight ratio in descending order
        for (int i = 0; i < w.length - 1; i++) {
            for (int j = i + 1; j < w.length; j++) {
                double ratio1 = (double) p[i] / w[i];
                double ratio2 = (double) p[j] / w[j];

                if (ratio1 < ratio2) {
                    // Swap weights
                    int tempW = w[i];
                    w[i] = w[j];
                    w[j] = tempW;

                    // Swap profits
                    int tempP = p[i];
                    p[i] = p[j];
                    p[j] = tempP;
                }
            }
        }
    }
}

6.job sequencing*********************************************************
import java.util.Scanner;

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

        System.out.println("Enter the number of jobs: ");
        int n = sc.nextInt();
        
        int[] d = new int[n + 1];
        int[] profits = new int[n + 1];
        for (int i = 0; i < n; i++) 
        {
            System.out.println("Enter the profits and deadlines of Job: " + (i + 1));
            profits[i + 1] = sc.nextInt();
            d[i + 1] = sc.nextInt();
        }

        // Arranging profits in descending order- therefore swaping deadlines too
        for (int i = 1; i < n; i++) 
        {
            for (int j = 1; j < n; j++) 
            {
                if (profits[j] < profits[j + 1]) 
                {
                	int temp = profits[j];
                    profits[j] = profits[j + 1];
                    profits[j + 1] = temp;
                    
                    temp = d[j];
                    d[j] = d[j + 1];
                    d[j + 1] = temp;
                }
            }
        }
        
        // optimal sol logic
        int[] j = new int[n + 1];
        j[0] = 0;
        d[0] = 0;
        j[1] = 1;
        int k = 1;
        for (int i = 2; i <= n; i++) 
        {
            int r = k;
            while ((d[j[r]] > d[i]) && d[j[r]] != r) 
            {
                r--;
            }
            if ((d[j[r]] <= d[i]) && d[i] > r) 
            {
                for (int x = k; x >= r + 1; x--) 
                {
                    j[x + 1] = j[x];
                }
                j[r + 1] = i;
                k++;
            }
        }
        int profit = 0;
        System.out.println("Final Job Sequence: ");
        for (int i = 1; i < n + 1; i++) 
        {
            System.out.println(j[i] + " ");
            profit +=profits[j[i]];
        }
        System.out.println(profit);
    }
}
7.shortestpath ****************************************************************
import java.util.*;

public class Source {
    private static final int INF = Integer.MAX_VALUE; // Constant for infinity

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
       
        System.out.print("Enter the number of vertices: ");
        int n = scanner.nextInt(); // Number of vertices
       
        int[][] graph = new int[n][n]; // Initialize the adjacency matrix
       
        // Input graph values from the user
        System.out.println("Enter the adjacency matrix (0 for no edge):");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                graph[i][j] = scanner.nextInt();
            }
        }
       
        single(graph, n, 0); // Start from vertex 0
        scanner.close();
    }

    public static void single(int[][] graph, int n, int start) {
        int[] dist = new int[n]; // Distance from source to each vertex
        boolean[] s = new boolean[n]; // Track visited vertices

        // Initialize distances based on direct edges from the start vertex
        for (int i = 0; i < n; i++) {
            dist[i] = (graph[start][i] != 0) ? graph[start][i] : INF;
            s[i] = false;
        }
        dist[start] = 0; // Distance to the source is 0
        s[start] = true; // Mark the starting vertex as visited

        int count = 0;
        do {
            int u = minDistance(dist, s, n);
            s[u] = true; // Mark the vertex as visited

            // Update the distance of the adjacent vertices
            for (int v = 0; v < n; v++) {
                if (!s[v] && graph[u][v] != 0 && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }

            count++;
        } while (count < n - 1);

        // Print the distances and calculate the sum
        int totalDistance = 0;
        System.out.println("Vertex Distance from Source");
        for (int i = 0; i < n; i++) {
            if (dist[i] != INF) {
                totalDistance += dist[i];
            }
        }

        // Print the total distance
        System.out.println("Total distance from source: " + totalDistance);
    }

    // Function to find the vertex with the minimum distance value
    private static int minDistance(int[] dist, boolean[] s, int n) {
        int min = INF, minIndex = -1;

        for (int v = 0; v < n; v++) {
            if (!s[v] && dist[v] <= min) {
                min = dist[v];
                minIndex = v;
            }
        }
        return minIndex;
    }
}