Algorithm Lab Codes in Java

1. Sorting Algorithms - Merge Sort

class MergeSort {
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int L[] = new int[n1];
int R[] = new int[n2];
for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
void sort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l)/2;
sort(arr, l, m);
sort(arr, m+1, r);
merge(arr, l, m, r);
}
}
}

2. Searching Algorithms - Binary Search

class BinarySearch {
int binarySearch(int arr[], int x) {
int l = 0, r = arr.length - 1;
while (l <= r) {
int m = l + (r - l)/2;
if (arr[m] == x) return m;
if (arr[m] < x) l = m + 1;
else r = m - 1;
}
return -1;
}
}

3. Greedy Algorithms - Activity Selection

import java.util.*;
class ActivitySelection {
 Algorithm Lab Codes in Java

static class Activity {

int start, end;
Activity(int start, int end) { this.start = start; this.end = end; }
}
static void printMaxActivities(Activity arr[], int n) {
Arrays.sort(arr, Comparator.comparingInt(a -> a.end));
int i = 0;
System.out.println("(" + arr[i].start + ", " + arr[i].end + ")");
for (int j = 1; j < n; j++) {
if (arr[j].start >= arr[i].end) {
System.out.println("(" + arr[j].start + ", " + arr[j].end + ")");
i = j;
}
}
}
}

4. Dynamic Programming - 0/1 Knapsack Problem

class Knapsack {
int knapSack(int W, int wt[], int val[], int n) {
int dp[][] = new int[n+1][W+1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0)
dp[i][w] = 0;
else if (wt[i-1] <= w)
dp[i][w] = Math.max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w]);
else
dp[i][w] = dp[i-1][w];
}
}
return dp[n][W];
}
}

5. Divide and Conquer - Maximum Subarray (DC version)

class MaxSubArray {
int maxCrossingSum(int arr[], int l, int m, int h) {
int sum = 0, left_sum = Integer.MIN_VALUE;
for (int i = m; i >= l; i--) {
sum += arr[i];
if (sum > left_sum) left_sum = sum;
}
sum = 0;
int right_sum = Integer.MIN_VALUE;
for (int i = m + 1; i <= h; i++) {
sum += arr[i];
 Algorithm Lab Codes in Java

if (sum > right_sum) right_sum = sum;

}
return left_sum + right_sum;
}
int maxSubArraySum(int arr[], int l, int h) {
if (l == h) return arr[l];
int m = (l + h)/2;
return Math.max(Math.max(maxSubArraySum(arr, l, m),
maxSubArraySum(arr, m+1, h)),
maxCrossingSum(arr, l, m, h));
}
}

6. Backtracking - N-Queens Problem

class NQueens {
final int N = 8;
boolean isSafe(int board[][], int row, int col) {
for (int i = 0; i < col; i++)
if (board[row][i] == 1) return false;
for (int i=row, j=col; i>=0 && j>=0; i--, j--)
if (board[i][j] == 1) return false;
for (int i=row, j=col; j>=0 && i<N; i++, j--)
if (board[i][j] == 1) return false;
return true;
}
boolean solveNQUtil(int board[][], int col) {
if (col >= N) return true;
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQUtil(board, col + 1)) return true;
board[i][col] = 0;
}
}
return false;
}
void solveNQ() {
int board[][] = new int[N][N];
if (!solveNQUtil(board, 0)) {
System.out.print("Solution does not exist");
return;
}
printSolution(board);
}
void printSolution(int board[][]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
System.out.print(" " + board[i][j] + " ");
 Algorithm Lab Codes in Java

System.out.println();
}
}
}

7. Graph Algorithms - Dijkstra's Algorithm

import java.util.*;
class Dijkstra {
int V = 9;
int minDistance(int dist[], boolean sptSet[]) {
int min = Integer.MAX_VALUE, min_index = -1;
for (int v = 0; v < V; v++)
if (!sptSet[v] && dist[v] <= min) {
min = dist[v];
min_index = v;
}
return min_index;
}
void dijkstra(int graph[][], int src) {
int dist[] = new int[V];
Boolean sptSet[] = new Boolean[V];
for (int i = 0; i < V; i++) {
dist[i] = Integer.MAX_VALUE;
sptSet[i] = false;
}
dist[src] = 0;
for (int count = 0; count < V-1; count++) {
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v] != 0 &&
dist[u] != Integer.MAX_VALUE &&
dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
printSolution(dist);
}
void printSolution(int dist[]) {
System.out.println("Vertex Distance from Source");
for (int i = 0; i < V; i++)
System.out.println(i + " " + dist[i]);
}
}

8. Tree Algorithms - DFS on Tree

import java.util.*;
class DFS {
 Algorithm Lab Codes in Java

static void dfs(int v, boolean visited[], List<List<Integer>> adj) {

visited[v] = true;
System.out.print(v + " ");
for (int u : adj.get(v)) {
if (!visited[u])
dfs(u, visited, adj);
}
}
public static void main(String[] args) {
int V = 5;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++)
adj.add(new ArrayList<>());
adj.get(0).add(1);
adj.get(0).add(2);
adj.get(1).add(3);
adj.get(1).add(4);
boolean visited[] = new boolean[V];
dfs(0, visited, adj);
}
}

9. String Algorithms - KMP Pattern Matching

class KMP {
void computeLPSArray(String pat, int M, int lps[]) {
int len = 0;
lps[0] = 0;
int i = 1;
while (i < M) {
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++; }
}
}
}
void KMPSearch(String pat, String txt) {
int M = pat.length();
int N = txt.length();
int lps[] = new int[M];
computeLPSArray(pat, M, lps);
int i = 0, j = 0;
while (i < N) {
if (pat.charAt(j) == txt.charAt(i)) {
i++; j++;
 Algorithm Lab Codes in Java

}
if (j == M) {
System.out.println("Found pattern at index " + (i-j));
j = lps[j-1];
} else if (i < N && pat.charAt(j) != txt.charAt(i)) {
if (j != 0) j = lps[j-1];
else i++;
}
}
}
}