ada.java

public class LCS {
    public static int lcs(String X, String Y, int m, int n) {
        // Base case: If either string is empty, LCS is 0
        if (m == 0 || n == 0) return 0;
        // If last characters match, include in LCS and recurse
        if (X.charAt(m-1) == Y.charAt(n-1))
            return 1 + lcs(X, Y, m-1, n-1);
        // If they don't match, take max of excluding last char from X or Y
        else
            return Math.max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
    }
    
    public static void main(String[] args) {
        String X = "AGGTAB";
        String Y = "GXTXAYB";
        System.out.println("LCS length: " + lcs(X, Y, X.length(), Y.length()));
    }
}

public class MCM {
    public static int mcm(int[] p, int i, int j) {
        // Base case: Single matrix (no multiplication needed)
        if (i == j) return 0;
        int min = Integer.MAX_VALUE;
        // Try all possible splits between i and j
        for (int k = i; k < j; k++) {
            // Cost = left partition + right partition + cost of multiplying them
            int count = mcm(p, i, k) + mcm(p, k+1, j) + p[i-1]*p[k]*p[j];
            if (count < min) min = count;
        }
        return min;
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};
        System.out.println("Min multiplications: " + mcm(arr, 1, arr.length-1));
    }
}

public class Knapsack {
    public static int knapsack(int W, int[] wt, int[] val, int n) {
        // Base case: No items left or no capacity left
        if (n == 0 || W == 0) return 0;

        // If current item's weight > remaining capacity, skip it
        if (wt[n-1] > W) return knapsack(W, wt, val, n-1);

        // Else, choose max between including or excluding the item
        else return Math.max(
            val[n-1] + knapsack(W - wt[n-1], wt, val, n-1), // Include
            knapsack(W, wt, val, n-1) // Exclude
        );
    }
    
    public static void main(String[] args) {
        int[] val = {60, 100, 120};
        int[] wt = {10, 20, 30};
        int W = 50;
        System.out.println("Max value: " + knapsack(W, wt, val, val.length));
    }
}

public class FloydWarshall {
    final static int INF = 9999;
    
    public static void floydWarshall(int[][] graph, int V) {
        // For every intermediate vertex k
        for (int k = 0; k < V; k++)
            // For every source vertex i
            for (int i = 0; i < V; i++)
                // For every destination vertex j
                for (int j = 0; j < V; j++)
                    // If path i→k→j is shorter than i→j, update
                    if (graph[i][k] + graph[k][j] < graph[i][j])
                        graph[i][j] = graph[i][k] + graph[k][j];
    }
    
    public static void main(String[] args) {
        int V = 4;
        int[][] graph = {{0, 5, INF, 10}, 
                         {INF, 0, 3, INF}, 
                         {INF, INF, 0, 1}, 
                         {INF, INF, INF, 0}};
        floydWarshall(graph, V);
        System.out.println("Shortest distances between every pair:");
        for (int[] row : graph) System.out.println(Arrays.toString(row));
    }
}

public class NQueens {
    public static boolean isSafe(int[][] board, int row, int col, int N) {
        // Check left side of the row
        for (int i = 0; i < col; i++) if (board[row][i] == 1) return false;
        // Check upper diagonal
        for (int i=row, j=col; i>=0 && j>=0; i--, j--) if (board[i][j] == 1) return false;
        // Check lower diagonal
        for (int i=row, j=col; i<N && j>=0; i++, j--) if (board[i][j] == 1) return false;
        return true;
    }

    public static boolean solveNQUtil(int[][] board, int col, int N) {
        // Base case: All queens placed
        if (col >= N) return true;

        // Try placing queen in each row of current column
        for (int i = 0; i < N; i++) {
            if (isSafe(board, i, col, N)) {
                board[i][col] = 1; // Place queen
                if (solveNQUtil(board, col + 1, N)) return true;
                board[i][col] = 0; // Backtrack (remove queen)
            }
        }
        return false;
    }
    
    public static void main(String[] args) {
        int N = 4;
        int[][] board = new int[N][N];
        if (solveNQUtil(board, 0, N))
            for (int[] row : board) System.out.println(Arrays.toString(row));
    }
}