Abdul

Assignment 1

1. Write a program to print the Fibonacci series (Recursive and Non-recursive)

import java.util.Scanner;

public class Fibo {

public static int Recf(int n) {
    if (n == 0) return 0;
    else if (n == 1) return 1;
    else return Recf(n - 1) + Recf(n - 2);
}

public static void Irecf() {
    Scanner sc = new Scanner(System.in);
    int n1 = 0, n2 = 1, n;
    System.out.print("Enter Size of Fibonacci: ");
    n = sc.nextInt();

    System.out.print(n1 + "," + n2 + ",");
    for (int i = 2; i < n; i++) {
        int n3 = n1 + n2;
        n1 = n2;
        n2 = n3;
        if (i < n - 1) System.out.print(n3 + ",");
        else System.out.print(n3 + ".");
    }
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter Your Choice:");
    System.out.println("1. Recursion");
    System.out.println("2. Non Recursion");
    int choice = sc.nextInt();

    switch (choice) {
        case 1:
            System.out.print("Enter Size Of Fibonacci: ");
            int num = sc.nextInt();
            if (num <= 0) System.out.println("Enter Positive Number!!");
            else {
                for (int i = 0; i < num; i++) System.out.print(Recf(i) + ",");
            }
            break;
        case 2:
            Irecf();
            break;
        default:
            System.out.println("Enter Valid Choice");
    }
    sc.close();
}

}

2. Write a program to find Maximum and Minimum number from an array (Recursive and Non-recursive)

import java.util.Scanner;

public class Minmax {

public static int RMax(int arr[], int index) {
    if (index == arr.length - 1) return arr[index];
    int max = RMax(arr, index + 1);
    return arr[index] > max ? arr[index] : max;
}

public static int RMin(int arr[], int index) {
    if (index == arr.length - 1) return arr[index];
    int min = RMin(arr, index + 1);
    return arr[index] < min ? arr[index] : min;
}

public static void minmax() {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter the Size of the array");
    int size = sc.nextInt();
    int a[] = new int[size];
    System.out.print("Enter the Elements in the Array: ");
    for (int i = 0; i < size; i++) a[i] = sc.nextInt();

    int max = a[0], min = a[0];
    for (int i = 1; i < size; i++) {
        if (a[i] > max) max = a[i];
        if (a[i] < min) min = a[i];
    }

    System.out.println("Max: " + max);
    System.out.println("Min: " + min);
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter Your Choice");
    System.out.println("1. Recursive");
    System.out.println("2. Non-recursive");
    int choice = sc.nextInt();

    switch (choice) {
        case 1:
            int arr[] = {55, 54, 88, 90, 14, 13};
            System.out.println("Maximum is " + RMax(arr, 0));
            System.out.println("Minimum is " + RMin(arr, 0));
            break;
        case 2:
            minmax();
            break;
        default:
            System.out.println("Enter a valid choice");
    }
}

}

3. Write a program to find the factorial of a number (Recursive and Non-recursive)

import java.util.Scanner;

public class Sfact {

public static int Rfact(int num) {
    if (num == 0 || num == 1) return 1;
    return num * Rfact(num - 1);
}

public static void IFact() {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter Number for Factorial: ");
    int num = sc.nextInt();
    if (num < 0) System.out.println("Enter Positive Number");
    else {
        int fact = 1;
        for (int i = 1; i <= num; i++) fact *= i;
        System.out.println("Factorial of " + num + " is " + fact);
    }
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter Your Choice:");
    System.out.println("1. Recursive Factorial");
    System.out.println("2. Non Recursive Factorial");
    int choice = sc.nextInt();

    switch (choice) {
        case 1:
            System.out.println("Factorial is: " + Rfact(5));
            break;
        case 2:
            IFact();
            break;
        default:
            System.out.println("Enter Valid Choice");
    }
}

}

4. Write a program to find the sum of the first N odd & even numbers (Recursive and Non-recursive)

import java.util.Scanner;

public class Oe {

public static int sumodd(int n, int curr) {
    if (curr > n) return 0;
    return curr + sumodd(n, curr + 2);
}

public static int sumeven(int n, int curr) {
    if (curr > n) return 0;
    return curr + sumeven(n, curr + 2);
}

public static void Oe(int n) {
    int sum = 0;
    if (n % 2 == 0) {
        for (int i = 0; i <= n; i += 2) sum += i;
        System.out.println("Even Sum is: " + sum);
    } else {
        for (int i = 1; i <= n; i += 2) sum += i;
        System.out.println("Odd Sum is: " + sum);
    }
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter Your Choice:");
    System.out.println("1. Recursive");
    System.out.println("2. Non Recursive");
    int choice = sc.nextInt();
    System.out.println("Enter Range:");
    int n = sc.nextInt();

    switch (choice) {
        case 1:
            if (n % 2 == 0) 
                System.out.println("Even Sum (Recursive): " + sumeven(n, 0));
            else 
                System.out.println("Odd Sum (Recursive): " + sumodd(n, 1));
            break;
        case 2:
            Oe(n);
            break;
        default:
            System.out.println("Enter Valid Choice");
    }
}

}

4. Sum of the First N Odd & Even Numbers (Recursive and Non-recursive) import java.util.Scanner;

public class Oe {

public static int sumodd(int n, int curr) {
    if (curr > n) return 0;
    return curr + sumodd(n, curr + 2);
}

public static int sumeven(int n, int curr) {
    if (curr > n) return 0;
    return curr + sumeven(n, curr + 2);
}

public static void Oe(int n) {
    int sum = 0;
    if (n % 2 == 0) {
        for (int i = 0; i <= n; i += 2) {
            sum += i;
        }
        System.out.println("Even Sum is : " + sum);
    } else {
        for (int i = 1; i <= n; i += 2) {
            sum += i;
        }
        System.out.println("Odd Sum is : " + sum);
    }
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter Your Choice ");
    System.out.println("1. Recursive");
    System.out.println("2. Non Recursive ");
    int choice = sc.nextInt();

    System.out.println("Enter Your Range: ");
    int n = sc.nextInt();

    switch (choice) {
        case 1:
            if (n % 2 == 0) {
                int evensum = sumeven(n, 0);
                System.out.println("Even Sum (Recursive) is " + evensum);
            } else {
                int oddsum = sumodd(n, 1);
                System.out.println("Odd Sum (Recursive) is " + oddsum);
            }
            break;

        case 2:
            Oe(n);
            break;

        default:
            System.out.println("Enter Valid Choice ");
            break;
    }
    sc.close();
}

}

5. Matrix Operations: Add, Multiply, and Transpose (Recursive and Non-recursive) import java.util.Scanner;

public class MatrixOperations {

// Non-recursive matrix addition
public static int[][] addMatricesNonRecursive(int[][] A, int[][] B, int rows, int cols) {
    int[][] sum = new int[rows][cols];
    for (int i = 0; i < rows; i++) 
        for (int j = 0; j < cols; j++) 
            sum[i][j] = A[i][j] + B[i][j];
    return sum;
}

// Recursive matrix addition
public static void addMatricesRecursive(int[][] A, int[][] B, int[][] result, int i, int j, int rows, int cols) {
    if (i >= rows) return;
    result[i][j] = A[i][j] + B[i][j];
    if (j < cols - 1) addMatricesRecursive(A, B, result, i, j + 1, rows, cols);
    else addMatricesRecursive(A, B, result, i + 1, 0, rows, cols);
}

// Non-recursive matrix multiplication
public static int[][] multiplyMatricesNonRecursive(int[][] A, int[][] B, int rowsA, int colsA, int colsB) {
    int[][] product = new int[rowsA][colsB];
    for (int i = 0; i < rowsA; i++) {
        for (int j = 0; j < colsB; j++) {
            for (int k = 0; k < colsA; k++) {
                product[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return product;
}

// Recursive matrix multiplication
public static void multiplyMatricesRecursive(int[][] A, int[][] B, int[][] result, int i, int j, int k, int rowsA, int colsA, int colsB) {
    if (i >= rowsA) return;
    if (j >= colsB) {
        multiplyMatricesRecursive(A, B, result, i + 1, 0, 0, rowsA, colsA, colsB);
        return;
    }
    if (k < colsA) {
        result[i][j] += A[i][k] * B[k][j];
        multiplyMatricesRecursive(A, B, result, i, j, k + 1, rowsA, colsA, colsB);
    } else {
        multiplyMatricesRecursive(A, B, result, i, j + 1, 0, rowsA, colsA, colsB);
    }
}

// Non-recursive matrix transpose
public static int[][] transposeMatrixNonRecursive(int[][] matrix, int rows, int cols) {
    int[][] transposed = new int[cols][rows];
    for (int i = 0; i < rows; i++) 
        for (int j = 0; j < cols; j++) 
            transposed[j][i] = matrix[i][j];
    return transposed;
}

// Recursive matrix transpose
public static void transposeMatrixRecursive(int[][] matrix, int[][] result, int i, int j, int rows, int cols) {
    if (i >= rows) return;
    result[j][i] = matrix[i][j];
    if (j < cols - 1) transposeMatrixRecursive(matrix, result, i, j + 1, rows, cols);
    else transposeMatrixRecursive(matrix, result, i + 1, 0, rows, cols);
}

// Utility method to print a matrix
public static void printMatrix(int[][] matrix, int rows, int cols) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            System.out.print(matrix[i][j] + " ");
        }
        System.out.println();
    }
}

// Main method
public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    System.out.print("Enter number of rows and columns for matrices: ");
    int rows = scanner.nextInt();
    int cols = scanner.nextInt();

    int[][] A = new int[rows][cols];
    int[][] B = new int[rows][cols];

    System.out.println("Enter elements of Matrix A:");
    for (int i = 0; i < rows; i++) 
        for (int j = 0; j < cols; j++) 
            A[i][j] = scanner.nextInt();

    System.out.println("Enter elements of Matrix B:");
    for (int i = 0; i < rows; i++) 
        for (int j = 0; j < cols; j++) 
            B[i][j] = scanner.nextInt();

    // Addition Non-recursive
    int[][] addResult = addMatricesNonRecursive(A, B, rows, cols);
    System.out.println("\nMatrix Addition A + B (Non-Recursive):");
    printMatrix(addResult, rows, cols);

    // Addition Recursive
    int[][] addResultRecursive = new int[rows][cols];
    addMatricesRecursive(A, B, addResultRecursive, 0, 0, rows, cols);
    System.out.println("\nMatrix Addition A + B (Recursive):");
    printMatrix(addResultRecursive, rows, cols);

    // Multiplication (only if square matrices)
    if (cols == rows) {
        int[][] mulResult = multiplyMatricesNonRecursive(A, B, rows, cols, cols);
        System.out.println("\nMatrix Multiplication A * B (Non-Recursive):");
        printMatrix(mulResult, rows, cols);

        int[][] mulResultRecursive = new int[rows][cols];
        multiplyMatricesRecursive(A, B, mulResultRecursive, 0, 0, 0, rows, cols, cols);
        System.out.println("\nMatrix Multiplication A * B (Recursive):");
        printMatrix(mulResultRecursive, rows, cols);
    } else {
        System.out.println("Matrix A and B dimensions do not match for multiplication.");
    }

    // Transpose Non-recursive
    int[][] transposeResult = transposeMatrixNonRecursive(A, rows, cols);
    System.out.println("\nMatrix Transposition (Non-Recursive) of A:");
    printMatrix(transposeResult, cols, rows);

    // Transpose Recursive
    int[][] transposeResultRecursive = new int[cols][rows];
    transposeMatrixRecursive(A, transposeResultRecursive, 0, 0, rows, cols);
    System.out.println("\nMatrix Transposition (Recursive) of A:");
    printMatrix(transposeResultRecursive, cols, rows);

    scanner.close();
}

}

6. Binary Search (Recursive) import java.util.Scanner;

public class BinarySearchRecursive { public static int binarySearch(int[] arr, int left, int right, int target) { if (left > right) { return -1; // Element not found }

    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target) {
        return mid; // Element found
    }
    
    if (arr[mid] > target) {
        return binarySearch(arr, left, mid - 1, target); // Search left subarray
    } else {
        return binarySearch(arr, mid + 1, right, target); // Search right subarray
    }
}

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    
    System.out.print("Enter size of array: ");
    int size = sc.nextInt();
    
    int[] arr = new int[size];
    System.out.print("Enter elements of array (sorted): ");
    for (int i = 0; i < size; i++) {
        arr[i] = sc.nextInt();
    }
    
    System.out.print("Enter element to be searched: ");
    int target = sc.nextInt();
    
    int result = binarySearch(arr, 0, arr.length - 1, target);
    
    if (result != -1) {
        System.out.println("Element found at index: " + result);
    } else {
        System.out.println("Element not found in the array.");
    }
    
    sc.close();
}

} 7. Merge Sort (Divide and Conquer) import java.util.Scanner;

public class MergeSort { public static Scanner sc = new Scanner(System.in);

public static void print(int[] array) { 
    for (int i : array) {
        System.out.print(i + " ");
    }
    System.out.println();
}

public static int[] mergeSort(int[] array) {
    if (array.length <= 1) {
        return array;
    }
    
    int midpoint = array.length / 2;
    int[] left = new int[midpoint];
    int[] right = (array.length % 2 == 0) ? new int[midpoint] : new int[midpoint + 1];
    
    for (int i = 0; i < midpoint; i++) {
        left[i] = array[i];
    }
    
    for (int j = 0; j < right.length; j++) {
        right[j] = array[midpoint + j];
    }
    
    left = mergeSort(left);
    right = mergeSort(right);
    
    return merge(left, right);
}

public static int[] merge(int[] left, int[] right) {
    int[] result = new int[left.length + right.length];
    int leftPointer = 0, rightPointer = 0, resultPointer = 0;
    
    while (leftPointer < left.length && rightPointer < right.length) {
        if (left[leftPointer] < right[rightPointer]) {
            result[resultPointer++] = left[leftPointer++];
        } else {
            result[resultPointer++] = right[rightPointer++];
        }
    }
    
    while (leftPointer < left.length) {
        result[resultPointer++] = left[leftPointer++];
    }
    
    while (rightPointer < right.length) {
        result[resultPointer++] = right[rightPointer++];
    }
    
    return result;
}

public static void main(String[] args) {
    System.out.print("Enter the array length: ");
    int size = sc.nextInt();
    
    int[] array = new int[size];
    System.out.print("Enter the array elements: ");
    for (int i = 0; i < size; i++) {
        array[i] = sc.nextInt();
    }
    
    System.out.println("Unsorted array:");
    print(array);
    
    array = mergeSort(array);
    
    System.out.println("Sorted array:");
    print(array);
    
    sc.close();
}

} 8. Quick Sort (Divide and Conquer) import java.util.Scanner;

public class QuickSort { public static Scanner sc = new Scanner(System.in);

static int partition(int[] array, int start, int end) {
    int pivot = array[start];
    int i = start + 1;
    int j = end;
    
    while (i <= j) {
        while (i <= j && array[i] <= pivot) {
            i++;
        }
        while (i <= j && array[j] > pivot) {
            j--;
        }
        if (i <= j) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
    
    int temp = array[start];
    array[start] = array[j];
    array[j] = temp;
    
    return j;
}

static void quickSort(int[] array, int start, int end) {
    if (start < end) {
        int partitionIndex = partition(array, start, end);
        quickSort(array, start, partitionIndex - 1);
        quickSort(array, partitionIndex + 1, end);
    }
}

public static void main(String[] args) {
    System.out.print("Enter size of array: ");
    int size = sc.nextInt();
    
    int[] array = new int[size];
    System.out.print("Enter elements of array: ");
    for (int i = 0; i < size; i++) {
        array[i] = sc.nextInt();
    }
    
    quickSort(array, 0, size - 1);
    
    System.out.print("Sorted array: ");
    for (int data : array) {
        System.out.print(data + " ");
    }
    System.out.println();
    
    sc.close();
}

} 9. Heap Sort (Divide and Conquer) import java.util.Arrays; import java.util.Scanner;

public class HeapSort { public static Scanner sc = new Scanner(System.in);

public static void heapSort(int[] arr) { int n = arr.length;

// Build max heap
for (int i = n / 2 - 1; i >= 0; i--) {
    heapify(arr, n, i);
}

// Extract elements one by one from heap
for (int i = n - 1; i > 0; i--) {
    // Swap current root to end
    int temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;
    
    // Call max heapify on reduced heap
    heapify(arr, i, 0);
}

}

private static void heapify(int[] arr, int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child

// If left child is larger than root
if (left < n && arr[left] > arr[largest]) {
    largest = left;
}

// If right child is larger than largest so far
if (right < n && arr[right] > arr[largest]) {
    largest = right;
}

// If largest is not root
if (largest != i) {
    int swap = arr[i];
    arr[i] = arr[largest];
    arr[largest] = swap;
    
    // Recursively heapify the affected sub-tree
    heapify(arr, n, largest);
}

}

public static void main(String[] args) { System.out.print("Enter size of array: "); int size = sc.nextInt();

int[] array = new int[size];
System.out.print("Enter elements of array: ");
for (int i = 0; i < size; i++) {
    array[i] = sc.nextInt();
}

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

heapSort(array);

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

sc.close();

}

}

10. Multiplication of Large Integers Using Divide and Conquer (Karatsuba Algorithm) import java.util.Scanner;

public class LargeIntMultiply { public static Scanner sc = new Scanner(System.in);

public static long karatsubaMultiply(long x, long y) {
    // Base case for recursion
    if (x < 10 || y < 10) {
        return x * y;
    }
    
    int n = Math.max(Long.toString(x).length(), Long.toString(y).length());
    int half = n / 2;
    
    long highX = x / (long) Math.pow(10, half);
    long lowX = x % (long) Math.pow(10, half);
    long highY = y / (long) Math.pow(10, half);
    long lowY = y % (long) Math.pow(10, half);
    
    long z0 = karatsubaMultiply(lowX, lowY);
    long z1 = karatsubaMultiply(lowX + highX, lowY + highY);
    long z2 = karatsubaMultiply(highX, highY);
    
    return (z2 * (long) Math.pow(10, 2 * half)) +
           ((z1 - z2 - z0) * (long) Math.pow(10, half)) +
           z0;
}

public static void main(String[] args) {
    System.out.print("Enter the first number: ");
    long num1 = sc.nextLong();
    
    System.out.print("Enter the second number: ");
    long num2 = sc.nextLong();
    
    long result = karatsubaMultiply(num1, num2);
    
    System.out.println("The product of " + num1 + " and " + num2 + " is: " + result);
    
    sc.close();
}

}

11. Knapsack Problem using Greedy Method (Fractional Knapsack)

import java.util.Arrays; import java.util.Scanner;

class Item { double value, weight, ratio;

public Item(double value, double weight) {
    this.value = value;
    this.weight = weight;	
    this.ratio = value / weight;
}

}

public class Knapsack { public static double fractionalKnapsack(double capacity, Item[] items) { // Sort items by value-to-weight ratio in descending order Arrays.sort(items, (i1, i2) -> Double.compare(i2.ratio, i1.ratio));

    double totalValue = 0.0;

    for (Item item : items) {
        if (capacity <= 0) break;

        if (item.weight <= capacity) {
            totalValue += item.value;
            capacity -= item.weight;
        } else {
            // Take fraction of the last item
            totalValue += item.ratio * capacity;
            capacity = 0;
        }
    }
    return totalValue;
}

public static void main(String[] args) {
    Item[] items = {
        new Item(20, 5),
        new Item(30, 20),
        new Item(40, 15),
        new Item(50, 25),
        new Item(60, 30)
    };
    
    Scanner sc = new Scanner(System.in);
    System.out.print("Enter the Capacity: ");
    double capacity = sc.nextDouble();
    sc.close();

    double maxValue = fractionalKnapsack(capacity, items);
    System.out.printf("Total Profit is = %.2f%n", maxValue);
}

} 12. Minimum Cost Spanning Tree (MST) using Greedy Technique

A. Prim’s Algorithm

import java.util.Arrays;

public class PrimsAlgorithm { static int V = 6;

static int primMST(int[][] graph) {
    boolean[] visited = new boolean[V];
    int[] minEdge = new int[V];
    Arrays.fill(minEdge, Integer.MAX_VALUE);
    minEdge[0] = 0;
    int totalWeight = 0;

    for (int i = 0; i < V; i++) {
        int u = -1;
        for (int v = 0; v < V; v++) {
            if (!visited[v] && (u == -1 || minEdge[v] < minEdge[u])) {
                u = v;
            }
        }
        visited[u] = true;
        totalWeight += minEdge[u];

        for (int v = 0; v < V; v++) {
            if (graph[u][v] != 0 && !visited[v] && graph[u][v] < minEdge[v]) {
                minEdge[v] = graph[u][v];
            }
        }
    }
    return totalWeight;
}

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

    System.out.println("Minimum Spanning Tree Cost (Prim's Algorithm): " + primMST(graph));
}

} B. Kruskal’s Algorithm import java.util.Arrays;

class KruskalAlgorithm { static int V = 5, E = 6; static int[][] edges = { {0, 1, 7}, {0, 2, 5}, {1, 3, 8}, {1, 4, 6}, {2, 3, 9}, {3, 4, 4} };

static int findParent(int[] parent, int i) {
    if (parent[i] == i) return i;
    return parent[i] = findParent(parent, parent[i]);  // Path compression
}

static void union(int[] parent, int[] rank, int x, int y) {
    int rootX = findParent(parent, x);
    int rootY = findParent(parent, y);

    if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
    else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
    else {
        parent[rootY] = rootX;
        rank[rootX]++;
    }
}

static int kruskalMST() {
    // Sort edges by weight ascending
    Arrays.sort(edges, (a, b) -> a[2] - b[2]);

    int[] parent = new int[V];
    int[] rank = new int[V];

    for (int i = 0; i < V; i++) parent[i] = i;

    int totalWeight = 0, edgeCount = 0;

    System.out.println("Edges in MST (Kruskal's Algorithm):");
    for (int[] edge : edges) {
        if (edgeCount == V - 1) break;

        int src = edge[0], dest = edge[1], weight = edge[2];

        if (findParent(parent, src) != findParent(parent, dest)) {
            union(parent, rank, src, dest);
            totalWeight += weight;
            edgeCount++;
            System.out.println(src + " - " + dest + " : " + weight);
        }
    }
    return totalWeight;
}

public static void main(String[] args) {
    System.out.println("Total MST Cost (Kruskal's Algorithm): " + kruskalMST());
}

} 13. Single Source Shortest Path (Dijkstra’s Algorithm) Using Greedy Method

import java.util.Arrays;

public class DijkstraAlgorithm { static final int INF = Integer.MAX_VALUE;

public static void dijkstraAlgo(int[][] graph, int source) {
    int n = graph.length;
    int[] distance = new int[n];
    boolean[] visited = new boolean[n];

    Arrays.fill(distance, INF);
    distance[source] = 0;

    for (int count = 0; count < n - 1; count++) {
        int u = minDistance(distance, visited);
        visited[u] = true;

        for (int v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] != 0 && distance[u] != INF &&
                distance[u] + graph[u][v] < distance[v]) {
                distance[v] = graph[u][v] + distance[u];
            }
        }
    }
    printSolution(distance, source);
}

private static int minDistance(int[] distance, boolean[] visited) {
    int min = INF, minIndex = -1;

    for (int v = 0; v < distance.length; v++) {
        if (!visited[v] && distance[v] <= min) {
            min = distance[v];
            minIndex = v;
        }
    }
    return minIndex;
}

private static void printSolution(int[] distance, int source) {
    System.out.println("Shortest Distances from node " + source + ":");
    for (int i = 0; i < distance.length; i++) {
        System.out.println("To " + i + " : " + distance[i]);
    }
}

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

    dijkstraAlgo(graph, 2);
}

}

14. Knapsack (0/1) Problem Using Dynamic Programming

public class Knapsack_dynamic {

// Returns maximum value that can be put in knapsack of capacity 'capacity'
public static int knapsack(int[] wt, int[] val, int capacity) {
    int n = val.length;

    // dp[i][w] stores max value for first i items with capacity w
    int[][] dp = new int[n][capacity + 1];

    for (int i = 0; i < n; i++) {
        for (int w = 0; w <= capacity; w++) {
            if (i == 0) {
                // Base case: only one item
                dp[i][w] = wt[0] <= w ? val[0] : 0;
            } else {
                int notTake = dp[i - 1][w];  // Skip current item
                int take = Integer.MIN_VALUE;

                if (wt[i] <= w) {
                    // Take current item and add value of remaining capacity
                    take = val[i] + dp[i - 1][w - wt[i]];
                }
                // Choose max of taking or not taking item
                dp[i][w] = Math.max(take, notTake);
            }
        }
    }
    return dp[n - 1][capacity];
}

public static void main(String[] args) {
    int[] values = {30, 40, 60};
    int[] weights = {3, 2, 5};
    int capacity = 6;

    int maxValue = knapsack(weights, values, capacity);
    System.out.println("Maximum value that can be obtained: " + maxValue);
}

} Output:

Maximum value that can be obtained: 100 15. Matrix Chain Multiplication Using Dynamic Programming

public class MatrixChainMultiplication { private int[][] m; // Cost matrix private int[][] s; // Matrix to store split points private int n; // Number of matrices

public MatrixChainMultiplication(int[] dimensions) {
    n = dimensions.length - 1;
    m = new int[n + 1][n + 1];
    s = new int[n + 1][n + 1];
    matrixChainOrder(dimensions);
}

private void matrixChainOrder(int[] dimensions) {
    // Cost is zero when multiplying one matrix
    for (int i = 1; i <= n; i++) {
        m[i][i] = 0;
    }

    // chainLength is length of matrix chain
    for (int chainLength = 2; chainLength <= n; chainLength++) {
        for (int i = 1; i <= n - chainLength + 1; i++) {
            int j = i + chainLength - 1;
            m[i][j] = Integer.MAX_VALUE;

            for (int k = i; k <= j - 1; k++) {
                // Cost = cost of splitting + cost of multiplying two parts
                int cost = m[i][k] + m[k + 1][j] + 
                           dimensions[i - 1] * dimensions[k] * dimensions[j];

                if (cost < m[i][j]) {
                    m[i][j] = cost;
                    s[i][j] = k;  // Store split point
                }
            }
        }
    }
}

// Recursively prints optimal parenthesization
public String printOptimalParens(int i, int j) {
    if (i == j) {
        return "A[" + i + "]";
    }
    return "(" + printOptimalParens(i, s[i][j]) + " x " + 
                  printOptimalParens(s[i][j] + 1, j) + ")";
}

@Override
public String toString() {
    return printOptimalParens(1, n);
}

public static void main(String[] args) {
    int[] dimensions = {30, 35, 15, 5};
    MatrixChainMultiplication mcm = new MatrixChainMultiplication(dimensions);

    System.out.println("Optimal parenthesization: " + mcm.toString());
    System.out.println("Minimum number of scalar multiplications: " + 
                       mcm.m[1][dimensions.length - 1]);
}

} Output:

Optimal parenthesization: (A[1] x (A[2] x A[3])) Minimum number of scalar multiplications: 2625

16. Graph Coloring Using Backtracking public class Graph_colouring {

    // Check if it's safe to color 'vertex' with color 'c' public static boolean isSafe(int vertex, int[][] graph, int[] color, int c) { for (int i = 0; i < graph.length; i++) { if (graph[vertex][i] == 1 && color[i] == c) { return false; // Adjacent vertex has same color } } return true; }

    // Recursive utility to solve coloring problem public static boolean solve(int vertex, int[][] graph, int m, int[] color) { if (vertex == graph.length) { return true; // All vertices colored }

    for (int c = 1; c <= m; c++) {
        if (isSafe(vertex, graph, color, c)) {
            color[vertex] = c;  // Assign color
    
            if (solve(vertex + 1, graph, m, color)) {
                return true;  // Success
            }
            color[vertex] = 0;  // Backtrack
        }
    }
    return false;  // No color can be assigned
    

    }

    public static boolean graphColoring(int[][] graph, int m) { int[] color = new int[graph.length]; return solve(0, graph, m, color); }

    public static void main(String[] args) { int[][] graph = { {0, 1, 1, 1}, {1, 0, 1, 0}, {1, 1, 0, 1}, {1, 0, 1, 0} }; int m = 3;

    if (graphColoring(graph, m)) {
        System.out.println("Solution exists: Coloring is possible.");
    } else {
        System.out.println("Solution does not exist: Coloring is not possible.");
    }
    

    } } Output:

Solution exists: Coloring is possible. 17. Hamiltonian Cycle Using Backtracking import java.util.Arrays;

public class Hamilton_Graph_Cycle { private int v; private int[][] graph;

public Hamilton_Graph_Cycle(int[][] graph) {
    this.v = graph.length;
    this.graph = graph;
}

public void findHamiltonianCycle() {
    int[] path = new int[v];
    Arrays.fill(path, -1);
    path[0] = 0;  // Start from vertex 0

    if (!hamiltonCycleUtil(path, 1)) {
        System.out.println("No Hamilton Cycle Exists.");
    } else {
        System.out.println("Hamiltonian Cycle:");
        for (int i = 0; i < v; i++) {
            System.out.print(path[i] + " ");
        }
        System.out.println(path[0]);  // To show cycle back to start
    }
}

private boolean hamiltonCycleUtil(int[] path, int pos) {
    if (pos == v) {
        return graph[path[pos - 1]][path[0]] == 1;  // Check edge back to start
    }

    for (int vertex = 1; vertex < v; vertex++) {
        if (isSafe(vertex, path, pos)) {
            path[pos] = vertex;

            if (hamiltonCycleUtil(path, pos + 1)) {
                return true;
            }

            path[pos] = -1;  // Backtrack
        }
    }
    return false;
}

private boolean isSafe(int vertex, int[] path, int pos) {
    // Check edge exists between last added vertex and current vertex
    if (graph[path[pos - 1]][vertex] == 0) {
        return false;
    }
    // Check vertex is not already included
    for (int i = 0; i < pos; i++) {
        if (path[i] == vertex) {
            return false;
        }
    }
    return true;
}

public static void main(String[] args) {
    int[][] graph1 = {
        {0, 1, 1, 0, 0, 0, 0},
        {1, 0, 1, 0, 0, 0, 0},
        {0, 1, 0, 1, 0, 1, 0},
        {1, 0, 1, 0, 1, 0, 0},
        {0, 0, 0, 1, 0, 1, 1},
        {0, 1, 1, 0, 1, 0, 1},
        {0, 0, 0, 0, 1, 1, 0}
    };
    Hamilton_Graph_Cycle g = new Hamilton_Graph_Cycle(graph1);
    g.findHamiltonianCycle();
}

} Output:

Hamiltonian Cycle: 0 1 2 3 4 6 5 0 18. Travelling Salesman Problem Using Branch and Bound (DFS) import java.util.Arrays;

public class TravellingSalesman { static int n = 4; static int bestCost = Integer.MAX_VALUE; static int[] bestPath = new int[n + 1];

public static void main(String[] args) {
    int[][] adjMatrix = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };

    branchBoundTSP(adjMatrix);

    System.out.println("Best Path: " + Arrays.toString(bestPath));
    System.out.println("Best Cost: " + bestCost);
}

static void branchBoundTSP(int[][] adjMatrix) {
    for (int start = 0; start < n; start++) {
        boolean[] visited = new boolean[n];
        int[] currPath = new int[n + 1];
        visited[start] = true;
        currPath[0] = start;
        dfs(start, 0, 0, visited, currPath, adjMatrix);
    }
}

static void dfs(int currCity, int depth, int currCost, boolean[] visited, int[] currPath, int[][] adjMatrix) {
    if (depth == n - 1) {
        int totalCost = currCost + adjMatrix[currPath[depth]][currPath[0]];
        if (totalCost < bestCost) {
            bestCost = totalCost;
            System.arraycopy(currPath, 0, bestPath, 0, n);
            bestPath[n] = currPath[0];
        }
        return;
    }

    for (int nextCity = 0; nextCity < n; nextCity++) {
        if (!visited[nextCity]) {
            visited[nextCity] = true;
            currPath[depth + 1] = nextCity;
            dfs(nextCity, depth + 1, currCost + adjMatrix[currPath[depth]][nextCity], visited, currPath, adjMatrix);
            visited[nextCity] = false;  // Backtrack
        }
    }
}

} Output:

Best Path: [0, 1, 3, 2, 0] Best Cost: 80

20. Brute Force String Matching

package Assign6;

public class BruteForce_Satvik { public static void main(String[] args) { String str = "Hey I am Satvik !!!"; String pattern = "Satvik"; System.out.println("Text: " + str); System.out.println("Pattern: " + pattern); search(str, pattern); }

public static void search(String text, String pattern) {
    int n = text.length();
    int m = pattern.length();
    boolean flag = false;

    for (int i = 0; i <= n - m; i++) {
        int j;
        for (j = 0; j < m; j++) {
            if (text.charAt(i + j) != pattern.charAt(j))
                break;
        }
        if (j == m) {
            System.out.println("Pattern found at index " + i);
            flag = true;
        }
    }
    if (!flag) System.out.println("Pattern not found");
}

} Output:

Positive input:

Text: Hey I am Satvik !!! Pattern: Satvik Pattern found at index 9 Negative input (e.g. pattern = "Satik"):

Text: Hey I am Satvik !!! Pattern: Satik Pattern not found 21. KMP (Knuth-Morris-Pratt) Algorithm

package Assign6;

import java.util.ArrayList;

public class KMP_Satvik { public static void main(String[] args) { String str = "SIESCOMS_MCA24078_MCA24073"; String pattern = "MCA24078"; System.out.println("Text: " + str); System.out.println("Pattern: " + pattern);

    ArrayList<Integer> res = search(pattern, str);
    if (res.size() > 0) {
        System.out.print("Pattern found at indexes: ");
        for (int i : res)
            System.out.print(i + " ");
    } else {
        System.out.println("Pattern not found");
    }
}

public static void constructLps(String pat, int[] lps) {
    int len = 0;
    lps[0] = 0;
    int i = 1;
    while (i < pat.length()) {
        if (pat.charAt(i) == pat.charAt(len)) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0)
                len = lps[len - 1];
            else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

public static ArrayList<Integer> search(String pat, String txt) {
    int n = txt.length();
    int m = pat.length();
    int[] lps = new int[m];
    ArrayList<Integer> res = new ArrayList<>();
    constructLps(pat, lps);

    int i = 0, j = 0;
    while (i < n) {
        if (txt.charAt(i) == pat.charAt(j)) {
            i++;
            j++;
            if (j == m) {
                res.add(i - j);
                j = lps[j - 1];
            }
        } else {
            if (j != 0)
                j = lps[j - 1];
            else
                i++;
        }
    }
    return res;
}

} Output:

Positive input:

Text: SIESCOMS_MCA24078_MCA24073 Pattern: MCA24078 Pattern found at indexes: 8 Negative input (pattern = "MCA24079"):

Text: SIESCOMS_MCA24078_MCA24073 Pattern: MCA24079 Pattern not found 22. Rabin-Karp Algorithm

package Assign6;

public class RabinKarp_Satvik { public final static int PRIME = 101;

public static void main(String[] args) {
    String str = "Hey I am Satvik MCA24078";
    String pattern = "MCA24078";
    int q = 101;
    System.out.println("Text: " + str);
    System.out.println("Pattern: " + pattern);
    search(pattern, str, q);
}

static void search(String pat, String txt, int q) {
    int M = pat.length();
    int N = txt.length();
    int p = 0; // hash for pattern
    int t = 0; // hash for text
    int h = 1;
    boolean flag = false;

    for (int i = 0; i < M - 1; i++)
        h = (h * PRIME) % q;

    for (int i = 0; i < M; i++) {
        p = (PRIME * p + pat.charAt(i)) % q;
        t = (PRIME * t + txt.charAt(i)) % q;
    }

    for (int i = 0; i <= N - M; i++) {
        if (p == t) {
            int j;
            for (j = 0; j < M; j++) {
                if (txt.charAt(i + j) != pat.charAt(j))
                    break;
            }
            if (j == M) {
                System.out.println("Pattern found at index " + i);
                flag = true;
            }
        }
        if (i < N - M) {
            t = (PRIME * (t - txt.charAt(i) * h) + txt.charAt(i + M)) % q;
            if (t < 0)
                t += q;
        }
    }
    if (!flag)
        System.out.println("Pattern not found");
}

} Output:

Positive input:

Text: Hey I am Satvik MCA24078 Pattern: MCA24078 Pattern found at index 18 Negative input (pattern = "MCA24079"):

Text: Hey I am Satvik MCA24078 Pattern: MCA24079 Pattern not found 23. Naïve String Matching (Same as Brute Force)

package Assign6;

public class NaiveStringMatching_Satvik { public static void main(String[] args) { String str = "Hey I am Satvik MCA24078"; String pattern = "MCA24073"; System.out.println("Text: " + str); System.out.println("Pattern: " + pattern); search(str, pattern); }

public static void search(String text, String pattern) {
    int n = text.length();
    int m = pattern.length();
    boolean flag = false;
    for (int i = 0; i <= n - m; i++) {
        int j;
        for (j = 0; j < m; j++) {
            if (text.charAt(i + j) != pattern.charAt(j))
                break;
        }
        if (j == m) {
            System.out.println("Pattern found at index " + i);
            flag = true;
        }
    }
    if (!flag)
        System.out.println("Pattern not found");
}

} Output:

Positive input (pattern = "Satvik"):

Text: Hey I am Satvik MCA24078 Pattern: Satvik Pattern found at index 9 Negative input:

Text: Hey I am Satvik MCA24078 Pattern: MCA24073 Pattern not found 24. Boyer Moore Algorithm

package Assign6;

public class BoyerMoore_Satvik { public static void main(String[] args) { String str = "Hey I am Satvik MCA24078"; String pattern = "MCA24078"; System.out.println("Text: " + str); System.out.println("Pattern: " + pattern); search(str.toCharArray(), pattern.toCharArray()); }

// Preprocessing for bad character heuristic
public static void badCharacter(char[] str, int size, int badchar[]) {
    for (int i = 0; i < 256; i++)
        badchar[i] = -1;

    for (int i = 0; i < size; i++)
        badchar[(int) str[i]] = i;
}

public static void search(char txt[], char pat[]) {
    int m = pat.length;
    int n = txt.length;
    boolean flag = false;

    int badchar[] = new int[256];
    badCharacter(pat, m, badchar);

    int s = 0;  // shift of the pattern with respect to text
    while (s <= (n - m)) {
        int j = m - 1;

        while (j >= 0 && pat[j] == txt[s + j])
            j--;

        if (j < 0) {
            System.out.println("Pattern occurs at index " + s);
            flag = true;

            s += (s + m < n) ? m - badchar[txt[s + m]] : 1;
        } else
            s += Math.max(1, j - badchar[txt[s + j]]);
    }

    if (!flag)
        System.out.println("Pattern not found");
}

} Output:

Positive input:

Text: Hey I am Satvik MCA24078 Pattern: MCA24078 Pattern occurs at index 16 Negative input (pattern = "MCA24079"):

Text: Hey I am Satvik MCA24078 Pattern: MCA24079 Pattern not found

Here’s a complete Java program implementing Floyd-Warshall algorithm (for all-pairs shortest path in a weighted graph) with a similar input/output pattern:

import java.util.Scanner; import java.util.Arrays;

public class FloydWarshall {

public static final int INF = 99999;

// Floyd-Warshall algorithm
public static void floydWarshall(int[][] graph, int V) {
    int[][] dist = new int[V][V];

    // Initialize the distance matrix same as input graph matrix
    for (int i = 0; i < V; i++) {
        dist[i] = Arrays.copyOf(graph[i], V);
    }

    // Add all vertices one by one as intermediate
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF &&
                    dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    printSolution(dist, V);
}

// Print the shortest distance matrix
public static void printSolution(int[][] dist, int V) {
    System.out.println("Shortest distances between every pair of vertices:");
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            if (dist[i][j] == INF)
                System.out.print("INF ");
            else
                System.out.print(dist[i][j] + "   ");
        }
        System.out.println();
    }
}

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

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

    int[][] graph = new int[V][V];

    System.out.println("Enter the adjacency matrix (use " + INF + " for no edge):");
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            graph[i][j] = sc.nextInt();
        }
    }

    System.out.println("\nInput Graph:");
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (graph[i][j] == INF)
                System.out.print("INF ");
            else
                System.out.print(graph[i][j] + "   ");
        }
        System.out.println();
    }

    floydWarshall(graph, V);

    sc.close();
}

}