1] Suppose you are working on a plagiarism detection tool for a university.

The tool needs to

check if certain phrases (patterns) appear in students' assignments (text). Design an
application to quickly and efficiently find all occurrences of a pattern in a given text
document.
import java.util.ArrayList;

import java.util.List;

public class Main {

public static int[] computeLPSArray(String pattern) {

int length = 0;

int i = 1;

int[] lps = new int[pattern.length()];

lps[0] = 0;

while (i < pattern.length()) {

if (pattern.charAt(i) == pattern.charAt(length)) {

length++;

lps[i] = length;

i++;

} else {

if (length != 0) {

length = lps[length - 1];

} else {

lps[i] = 0;

i++;

}
 return lps;

public static List<Integer> KMPSearch(String text, String pattern) {

int[] lps = computeLPSArray(pattern);

List<Integer> result = new ArrayList<>();

int i = 0;

int j = 0;

while (i < text.length()) {

if (pattern.charAt(j) == text.charAt(i)) {

i++;

j++;

if (j == pattern.length()) {

result.add(i - j);

j = lps[j - 1];

} else if (i < text.length() && pattern.charAt(j) != text.charAt(i)) {

if (j != 0) {

j = lps[j - 1];

} else {

i++;

return result;
 }

public static void main(String[] args) {

String text = "ababcabcabababd";

String pattern = "ababd";

List<Integer> occurrences = KMPSearch(text, pattern);

System.out.println("Pattern found at indices: " + occurrences);

Output:
2] Given a large dataset of customer records. Each record contains customer details such as
name, age, and purchase amount. Design an application using Quick Sort to sort these records
by purchase amount in descending order. Discuss the performance of your program with this
large dataset.

import java.util.Arrays;

class Customer {

String name;

int age;

double purchaseAmount;

Customer(String name, int age, double purchaseAmount) {

this.name = name;

this.age = age;

this.purchaseAmount = purchaseAmount;

public String toString() {

return "Customer{name='" + name + "', age=" + age + ", purchaseAmount=" + purchaseAmount + '}';

public class Main {

public static void quickSort(Customer[] customers, int low, int high) {

if (low < high) {

int pi = partition(customers, low, high);

quickSort(customers, low, pi - 1);

quickSort(customers, pi + 1, high);

}
}

private static int partition(Customer[] customers, int low, int high) {

double pivot = customers[high].purchaseAmount;

int i = (low - 1);

for (int j = low; j < high; j++) {

if (customers[j].purchaseAmount > pivot) {

i++;

Customer temp = customers[i];

customers[i] = customers[j];

customers[j] = temp;

Customer temp = customers[i + 1];

customers[i + 1] = customers[high];

customers[high] = temp;

return i + 1;

public static void main(String[] args) {

Customer[] customers = {

new Customer("Alice", 30, 250.5),

new Customer("Bob", 24, 150.75),

new Customer("Charlie", 28, 350.0),

new Customer("David", 22, 120.0),

new Customer("Eva", 35, 200.0)

};

System.out.println("Before sorting:");
 System.out.println(Arrays.toString(customers));

quickSort(customers, 0, customers.length - 1);

System.out.println("After sorting by purchase amount in descending order:");

System.out.println(Arrays.toString(customers));

Output:
3] Design and Implement an application that considers the problem of scheduling n jobs of
known durations t1, t2,..., tn for execution by a single processor. The jobs can be executed in
any order, one job at a time. Find and display the schedule that minimizes the total time spent
by all the jobs in the system by maximizing the profit.
import java.util.Arrays;

import java.util.Comparator;

class Job {

String jobId;

int duration;

int profit;

Job(String jobId, int duration, int profit) {

this.jobId = jobId;

this.duration = duration;

this.profit = profit;

@Override

public String toString() {

return "Job{jobId='" + jobId + "', duration=" + duration + ", profit=" + profit + '}';

public class JobScheduler {

public static void main(String[] args) {

Job[] jobs = {

new Job("Job1", 2, 100),

new Job("Job2", 1, 50),

new Job("Job3", 2, 20),

new Job("Job4", 1, 10),

new Job("Job5", 3, 150)

 };

System.out.println("Before scheduling:");

System.out.println(Arrays.toString(jobs));

Arrays.sort(jobs, Comparator.comparingInt(job -> job.duration));

System.out.println("After scheduling by shortest job first (SJF):");

System.out.println(Arrays.toString(jobs));

scheduleJobs(jobs);

public static void scheduleJobs(Job[] jobs) {

int n = jobs.length;

int[] waitingTime = new int[n];

int[] turnaroundTime = new int[n];

int totalWaitingTime = 0, totalTurnaroundTime = 0;

waitingTime[0] = 0;

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

waitingTime[i] = jobs[i - 1].duration + waitingTime[i - 1];

for (int i = 0; i < n; i++) {

turnaroundTime[i] = jobs[i].duration + waitingTime[i];

totalWaitingTime += waitingTime[i];

totalTurnaroundTime += turnaroundTime[i];

System.out.println("\nJob Schedule:");

for (int i = 0; i < n; i++) {

 System.out.println(jobs[i] + " | Waiting Time: " + waitingTime[i] + " | Turnaround Time: " +
turnaroundTime[i]);

System.out.println("\nAverage Waiting Time: " + (double) totalWaitingTime / n);

System.out.println("Average Turnaround Time: " + (double) totalTurnaroundTime / n);

int totalProfit = 0;

for (int i = 0; i < n; i++) {

totalProfit += jobs[i].profit;

System.out.println("Total Profit: " + totalProfit);

Output:
4] Construct a Optimal binary search tree for a given sorted array key [0.. n-1] of search keys
and an array freq[0.. n-1] of frequency counts, where freq[i] is the number of searches for
keys[i]. Design and implement Java Program to find the total cost of all the searches is as
small as possible.

public class OptimalBST {

public static void main(String[] args) {

int[] keys = {10, 12, 20};

int[] freq = {34, 8, 50};

int n = keys.length;

System.out.println("Minimum cost of Optimal BST is " + optimalBST(keys, freq, n));

public static int optimalBST(int[] keys, int[] freq, int n) {

int[][] cost = new int[n][n];

for (int i = 0; i < n; i++) {

cost[i][i] = freq[i];

int[][] sum = new int[n][n];

for (int i = 0; i < n; i++) {

sum[i][i] = freq[i];

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

sum[i][j] = sum[i][j - 1] + freq[j];

for (int length = 2; length <= n; length++) {

for (int i = 0; i < n - length + 1; i++) {

int j = i + length - 1;

cost[i][j] = Integer.MAX_VALUE;
 for (int r = i; r <= j; r++) {

int leftCost = (r > i) ? cost[i][r - 1] : 0;

int rightCost = (r < j) ? cost[r + 1][j] : 0;

int totalCost = leftCost + rightCost + sum[i][j];

if (totalCost < cost[i][j]) {

cost[i][j] = totalCost;

return cost[0][n - 1];

OUTPUT:
5. Design and Implement Java Program to find all Hamiltonian Cycles in a connected
undirected Graph G of n vertices using backtracking principle.

import java.util.ArrayList;

import java.util.List;

public class HamiltonianCycle {

private int[][] graph;

private int n; // Number of vertices

private List<List<Integer>> allCycles;

public HamiltonianCycle(int[][] graph) {

this.graph = graph;

this.n = graph.length;

this.allCycles = new ArrayList<>();

public void findAllHamiltonianCycles() {

boolean[] visited = new boolean[n];

ArrayList<Integer> path = new ArrayList<>();

path.add(0); // Start with the first vertex

visited[0] = true;

findAllHamiltonianCyclesUtil(0, visited, path);

private void findAllHamiltonianCyclesUtil(int vertex, boolean[] visited, List<Integer> path) {

if (path.size() == n) {

if (graph[vertex][path.get(0)] == 1) {

path.add(path.get(0)); // Add start vertex to complete the cycle

allCycles.add(new ArrayList<>(path)); // Store the cycle

 path.remove(path.size() - 1);

return;

for (int v = 0; v < n; v++) {

if (!visited[v] && graph[vertex][v] == 1) {

visited[v] = true;

path.add(v);

findAllHamiltonianCyclesUtil(v, visited, path);

visited[v] = false;

path.remove(path.size() - 1);

public void printAllCycles() {

if (allCycles.isEmpty()) {

System.out.println("No Hamiltonian cycles found.");

} else {

System.out.println("Hamiltonian Cycles:");

for (List<Integer> cycle : allCycles) {

System.out.println(cycle);

public static void main(String[] args) {

// Example graph

int[][] graph = {
 {0, 1, 1, 1, 1},

{1, 0, 1, 1, 0},

{1, 1, 0, 1, 1},

{1, 1, 1, 0, 1},

{1, 0, 1, 1, 0}

};

HamiltonianCycle hc = new HamiltonianCycle(graph);

hc.findAllHamiltonianCycles();

hc.printAllCycles();

OUTPUT: