Record Book Format:

Left Side Right Side

Sample Input Question
Aim
Sample Output Algorithm
Program
Result

1. Segmented Sieve Algorithm

Problem Statement:
Write a Java program to find all prime numbers within a given range using the segmented sieve
technique.

Aim:
To develop a Java program that finds all prime numbers within a given range using the segmented
sieve algorithm.

Algorithm:

1. Start the program.

2. Read two integers, low and high, as the range.

3. Generate all primes up to √high using a simple sieve.

4. Create a boolean array for the range [low, high].

5. Mark non-primes in the range using previously found primes.

6. Print all remaining unmarked numbers.

7. End the program.

Program Code:
import [Link].*;

public class SegmentedSieve {

static List<Integer> simpleSieve(int limit) {
boolean[] mark = new boolean[limit + 1];
[Link](mark, true);
List<Integer> primes = new ArrayList<>();
for (int p = 2; p * p <= limit; p++) {
if (mark[p]) {
for (int i = p * p; i <= limit; i += p)
mark[i] = false;
}
}
for (int i = 2; i <= limit; i++)
if (mark[i]) [Link](i);
return primes;
 }

static void segmentedSieve(int low, int high) {

int limit = (int)[Link](high);
List<Integer> primes = simpleSieve(limit);
boolean[] mark = new boolean[high - low + 1];
[Link](mark, true);

for (int p : primes) {

int start = [Link](p * p, (low + p - 1) / p * p);
for (int j = start; j <= high; j += p)
mark[j - low] = false;
}

for (int i = low; i <= high; i++)

if (mark[i - low]) [Link](i + " ");
}

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);
[Link]("Enter lower bound: ");
int low = [Link]();
[Link]("Enter upper bound: ");
int high = [Link]();
[Link]("Prime numbers in range:");
segmentedSieve(low, high);
}
}

Sample Input:
Enter lower bound: 10
Enter upper bound: 30

Sample Output:
Prime numbers in range:
11 13 17 19 23 29

Result:
The program successfully finds all prime numbers in the given range using the segmented sieve
algorithm.

2. Convert Integer to Roman Numeral

Problem Statement:
Write a Java program to convert a given integer into its Roman numeral equivalent.

Aim:
To develop a Java program that converts an integer into its Roman numeral equivalent.

Algorithm:
 1. Start the program.

2. Read an integer input.

3. Create arrays for Roman numerals and their integer values.

4. Subtract and append symbols until the number becomes zero.

5. Print the final Roman numeral string.

6. End the program.

Program Code:
import [Link].*;

public class IntegerToRoman {

public static String intToRoman(int num) {
int[] val = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
String[] syms =
{"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
StringBuilder roman = new StringBuilder();
for (int i = 0; i < [Link]; i++) {
while (num >= val[i]) {
num -= val[i];
[Link](syms[i]);
}
}
return [Link]();
}

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);
[Link]("Enter a number: ");
int n = [Link]();
[Link]("Roman numeral: " + intToRoman(n));
}
}

Sample Input:
Enter a number: 3549

Sample Output:
Roman numeral: MMMDXLIX

Result:
The program successfully converts an integer into its Roman numeral equivalent.

3. Binary Search in 2D Matrix

Problem Statement:
Write a Java program to search for a target element in a sorted 2D matrix using binary search.
Aim:
To develop a Java program to perform binary search in a sorted 2D matrix.

Algorithm:

1. Start the program.

2. Flatten the 2D matrix logically.

3. Use binary search between 0 and (rows × cols − 1).

4. Compare the middle element with the target.

5. Return true if found; otherwise false.

6. End the program.

Program Code:
public class Search2DMatrix {
public static boolean searchMatrix(int[][] matrix, int target) {
int rows = [Link], cols = matrix[0].length;
int left = 0, right = rows * cols - 1;
while (left <= right) {
int mid = (left + right) / 2;
int midVal = matrix[mid / cols][mid % cols];
if (midVal == target) return true;
else if (midVal < target) left = mid + 1;
else right = mid - 1;
}
return false;
}

public static void main(String[] args) {

int[][] matrix = {
{1, 3, 5, 7},
{10, 11, 16, 20},
{23, 30, 34, 60}
};
int target = 16;
[Link](searchMatrix(matrix, target) ? "Element found" :
"Element not found");
}
}

Sample Output:
Element found

Result:
The program successfully searches for a target element in a sorted 2D matrix.
4. Search in Rotated Sorted Array
Problem Statement:
Write a Java program to find a target element in a rotated sorted array using modified binary search.

Aim:
To develop a Java program that finds an element in a rotated sorted array.

Algorithm:

1. Start the program.

2. Use binary search logic to find sorted half.

3. Check if the target lies in that half.

4. Adjust search space accordingly.

5. Print index if found.

6. End the program.

Program Code:
public class SearchRotatedArray {
public static int search(int[] nums, int target) {
int left = 0, right = [Link] - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) return mid;
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid])
right = mid - 1;
else
left = mid + 1;
} else {
if (nums[mid] < target && target <= nums[right])
left = mid + 1;
else
right = mid - 1;
}
}
return -1;
}

public static void main(String[] args) {

int[] nums = {4,5,6,7,0,1,2};
int target = 0;
int result = search(nums, target);
if (result != -1)
[Link]("Element found at index: " + result);
else
[Link]("Element not found");
}
}
Sample Output:
Element found at index: 4

Result:
The program successfully finds an element in a rotated sorted array.

5. Merge Overlapping Intervals (Greedy)

Problem Statement:
Write a Java program to merge all overlapping intervals using a greedy approach.

Aim:
To develop a Java program that merges overlapping intervals using a greedy strategy.

Algorithm:

1. Start the program.

2. Read all intervals and store them in an array.

3. Sort intervals by their starting time.

4. Compare current interval with the previous one:

 If overlapping, merge them.

 Otherwise, add to the result list.

5. Display merged intervals.

6. End the program.

Program Code:
import [Link].*;

public class MergeIntervals {

public static int[][] merge(int[][] intervals) {
[Link](intervals, (a, b) -> [Link](a[0], b[0]));
List<int[]> merged = new ArrayList<>();
for (int[] interval : intervals) {
if ([Link]() || [Link]([Link]() - 1)[1] <
interval[0]) {
[Link](interval);
} else {
[Link]([Link]() - 1)[1] =
[Link]([Link]([Link]() - 1)[1], interval[1]);
}
}
return [Link](new int[[Link]()][]);
}

public static void main(String[] args) {

int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};
int[][] merged = merge(intervals);
 [Link]("Merged Intervals:");
for (int[] i : merged)
[Link]("[" + i[0] + "," + i[1] + "]");
}
}

Sample Output:
Merged Intervals:
[1,6]
[8,10]
[15,18]

Result:
The program successfully merges all overlapping intervals using a greedy approach.

6. Matrix Chain Multiplication (Dynamic

Programming)
Problem Statement:
Write a Java program to find the minimum number of scalar multiplications needed to multiply a
chain of matrices.

Aim:
To develop a Java program that implements matrix chain multiplication using dynamic programming.

Algorithm:

1. Start the program.

2. Input dimensions of matrices.

3. Use DP to find the optimal parenthesization minimizing multiplications.

4. Display the minimum number of multiplications.

5. End the program.

Program Code:
public class MatrixChainMultiplication {
static int matrixChainOrder(int p[], int n) {
int[][] m = new int[n][n];
for (int L = 2; L < n; L++) {
for (int i = 1; i < n - L + 1; i++) {
int j = i + L - 1;
m[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
if (q < m[i][j]) m[i][j] = q;
}
}
}
 return m[1][n - 1];
}

public static void main(String[] args) {

int arr[] = {1, 2, 3, 4};
int n = [Link];
[Link]("Minimum number of multiplications: " +
matrixChainOrder(arr, n));
}
}

Sample Output:
Minimum number of multiplications: 18

Result:
The program successfully calculates the minimum number of scalar multiplications required for
matrix chain multiplication.

7. Wildcard Pattern Matching (Dynamic

Programming)
Problem Statement:
Write a Java program to check if a given string matches a pattern containing wildcards ‘?’ and ‘*’.

Aim:
To develop a Java program that performs wildcard pattern matching using dynamic programming.

Algorithm:

1. Start the program.

2. Define a DP table where dp[i][j] = true if first i characters of string match first j characters of
pattern.

3. Handle wildcards ‘*’ (matches any sequence) and ‘?’ (matches one character).

4. Fill DP table accordingly.

5. Print whether the string matches the pattern.

6. End the program.

Program Code:
public class WildcardMatching {
static boolean isMatch(String s, String p) {
int m = [Link](), n = [Link]();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;

for (int j = 1; j <= n; j++)

if ([Link](j - 1) == '*')
 dp[0][j] = dp[0][j - 1];

for (int i = 1; i <= m; i++) {

for (int j = 1; j <= n; j++) {
if ([Link](j - 1) == '*')
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
else if ([Link](j - 1) == '?' || [Link](j - 1) ==
[Link](i - 1))
dp[i][j] = dp[i - 1][j - 1];
}
}
return dp[m][n];
}

public static void main(String[] args) {

String str = "baaabab";
String pattern = "ba*a?";
[Link](isMatch(str, pattern) ? "Match Found" : "No
Match");
}
}

Sample Output:
Match Found

Result:
The program correctly matches strings against patterns with wildcards using dynamic programming.

8. Counting Set Bits

Problem Statement:
Write a Java program to count the number of set bits (1s) in the binary representation of a given
integer.

Aim:
To develop a Java program that counts the number of set bits in a binary number.

Algorithm:

1. Start the program.

2. Read an integer input.

3. Initialize count = 0.

4. While number > 0:

 Increment count if (n & 1) == 1.

 Right shift n by 1.

5. Print the count.

 6. End the program.

Program Code:
import [Link].*;

public class CountSetBits {

public static int countBits(int n) {
int count = 0;
while (n > 0) {
count += n & 1;
n >>= 1;
}
return count;
}

public static void main(String[] args) {

Scanner sc = new Scanner([Link]);
[Link]("Enter a number: ");
int n = [Link]();
[Link]("Number of set bits: " + countBits(n));
}
}

Sample Input:
Enter a number: 13

Sample Output:
Number of set bits: 3

Result:
The program successfully counts the number of set bits in the given integer.

9. N-Queens Problem (Backtracking)

Problem Statement:
Write a Java program to place N queens on an N×N chessboard so that no two queens attack each
other.

Aim:
To develop a Java program that solves the N-Queens problem using backtracking.

Algorithm:

1. Start the program.

2. Place queens row by row.

3. For each column, check if it is safe to place the queen.

4. If safe, place and recurse to the next row.

 5. Backtrack if no valid position is found.

6. Print all valid board configurations.

7. End the program.

Program Code:
public class NQueens {
static int N = 4;

static void printSolution(int board[][]) {

for (int[] row : board) {
for (int val : row)
[Link]((val == 1 ? "Q " : ". "));
[Link]();
}
[Link]();
}

static 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; i < N && j >= 0; i++, j--)

if (board[i][j] == 1) return false;

return true;
}

static boolean solveNQUtil(int board[][], int col) {

if (col >= N) {
printSolution(board);
return true;
}
boolean res = false;
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
res = solveNQUtil(board, col + 1) || res;
board[i][col] = 0;
}
}
return res;
}

public static void main(String[] args) {

int board[][] = new int[N][N];
solveNQUtil(board, 0);
}
}
Sample Output:
Q . . .
. . Q .
. Q . .
. . . Q

Q . . .
. . . Q
. Q . .
. . Q .

Result:
The program successfully places N queens on the chessboard such that no two queens attack each
other.

10. Detect Cycle in Graph (DFS)

Problem Statement:
Write a Java program to detect the presence of a cycle in a graph using Depth First Search (DFS).

Aim:
To develop a Java program that detects cycles in a directed graph using DFS.

Algorithm:

1. Start the program.

2. Represent the graph using adjacency lists.

3. Perform DFS traversal.

4. Track visited nodes and recursion stack.

5. If a node is visited again in the current recursion path, a cycle exists.

6. End the program.

Program Code:
import [Link].*;

public class DetectCycleGraph {

private final int V;
private final List<List<Integer>> adj;

public DetectCycleGraph(int V) {
this.V = V;
adj = new ArrayList<>();
for (int i = 0; i < V; i++)
[Link](new ArrayList<>());
}

void addEdge(int u, int v) {

 [Link](u).add(v);
}

boolean isCyclicUtil(int v, boolean[] visited, boolean[] recStack) {

if (recStack[v]) return true;
if (visited[v]) return false;

visited[v] = true;
recStack[v] = true;

for (int neighbor : [Link](v))

if (isCyclicUtil(neighbor, visited, recStack))
return true;

recStack[v] = false;
return false;
}

boolean isCyclic() {
boolean[] visited = new boolean[V];
boolean[] recStack = new boolean[V];
for (int node = 0; node < V; node++)
if (isCyclicUtil(node, visited, recStack))
return true;
return false;
}

public static void main(String[] args) {

DetectCycleGraph g = new DetectCycleGraph(4);
[Link](0, 1);
[Link](1, 2);
[Link](2, 0);
[Link](2, 3);

if ([Link]())
[Link]("Cycle detected in the graph");
else
[Link]("No cycle detected");
}
}

Sample Output:
Cycle detected in the graph

Result:
The program successfully detects the presence of a cycle in a directed graph using DFS.