Assignment 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();
}
}
- 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");
}
}
}
- 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");
}
}
}
- 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");
}
}
}
- 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();
}
}
- 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();
}
}
- 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();
}
}
- 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();
}
}
- 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);
}
}
- 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
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
- 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();
}
}