School of Computer Science and

Engineering
Design and Analysis of Algorithm
(R1UC404B)
Name: Ketan Dubey
Admission No.: 22SCSE1010483
Section: 03
Program: Btech CSE
Submitted to: Mr. Pravin Kumar, Mr. Ankur Gogoi
Sno. Experiment name Date signature
1 Write a program to sort given set of numbers in
ascending/descending order using Bubble sort and
also search a number using binary search.

2 Write a program to sort given set of numbers in

ascending/descending order using Insertion sort
and also search a number using linear search.

3 Write a program to sort given set of numbers in

ascending/descending order using Quick sort and
any other sorting algorithm. Also record the time
taken by these two programs and compare them.

4 Write a program to sort given set of numbers using

Heap sort.

5 Write a program to sort given set of numbers using

merge sort.

6 Write a program to sort given set of numbers

Counting Sort.

7 Write a program to implement Matrix Chain

Multiplication.

8 Write a program to implement Knapsack using

Greedy technique.

9 Write a program to implement Knapsack using

Dynamic programming.

10 Write a program to implement Dijkstra’s Algorithm.

11 Write a program to implement Bellman-Ford

Algorithm.

12 Write a program to implement n-Queen Problem

using backtracking.

13 Write a program to implement String Matching

using Rabin-Karp algorithm.

14 Obtain the Topological ordering of vertices in a

given digraph.

15 Write a program to implement Minimum Cost

spanning tree.

16 Write a program to implement Sum of subset

problem.

17 Write a program to implement Greedy algorithm

using Task Scheduling Problem

18 Write a program to implement Greedy algorithm

using Acitivity Selection Problem.

19 Compute the transitive closure of a given directed

graph using Warshall's algorithm. Write a program
to implement shortest path algorithm
20 Write a program to implement solve LCS problem.
Q1: Write a program to sort given set of numbers in ascending/descending order using
Bubble sort and also search a number using binary search.
Answer:
public class Q1_22SCSE1010483 {
public static void main(String[] args) {
int[] arr = {6, 7, 8, 9, 6, 6, 5, 3, 2};
int n = arr.length;

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

for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}

System.out.print("Sorted array: ");

for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
if (i < arr.length - 1) {
System.out.print(", ");
}
}
}
}

Q2: Write a program to sort given set of numbers in ascending/descending order using
Insertion sort and also search a number using linear search.
Answer:
import java.util.Scanner;

public class SortSearch {

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the number of elements: ");
int n = scanner.nextInt();
int[] arr = new int[n];
 System.out.println("Enter the elements:");
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}

System.out.print("Enter 1 for ascending order or 2 for descending order: ");

int choice = scanner.nextInt();

insertionSort(arr, choice);

System.out.println("Sorted array:");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();

System.out.print("Enter the element to search: ");

int searchElement = scanner.nextInt();

int index = linearSearch(arr, searchElement);

if (index == -1) {
System.out.println("Element not found in the array.");
} else {
System.out.println("Element found at index " + index);
}
}

public static void insertionSort(int[] arr, int choice) {

int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;

if (choice == 1) {
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
} else {
while (j >= 0 && arr[j] < key) {
arr[j + 1] = arr[j];
j--;
}
}
 arr[j + 1] = key;
}
}

public static int linearSearch(int[] arr, int searchElement) {

for (int i = 0; i < arr.length; i++) {
if (arr[i] == searchElement) {
return i;
}
}
return -1;
}
}

Q3: Write a program to sort given set of numbers in ascending/descending order

using Quick sort and any other sorting algorithm. Also record the time taken by
these two programs and compare them.
Answer:
import java.util.Random;
import java.util.Scanner;

public class SortComparison {

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the number of elements: ");
int n = scanner.nextInt();
int[] arr = new int[n];

Random random = new Random();

for (int i = 0; i < n; i++) {
arr[i] = random.nextInt(1000);
}

System.out.print("Enter 1 for ascending order or 2 for descending order: ");

int choice = scanner.nextInt();
 int[] quickSortArr = arr.clone();
long quickSortStartTime = System.nanoTime();
quickSort(quickSortArr, 0, quickSortArr.length - 1, choice);
long quickSortEndTime = System.nanoTime();
long quickSortDuration = quickSortEndTime - quickSortStartTime;

int[] mergeSortArr = arr.clone();

long mergeSortStartTime = System.nanoTime();
mergeSort(mergeSortArr, 0, mergeSortArr.length - 1, choice);
long mergeSortEndTime = System.nanoTime();
long mergeSortDuration = mergeSortEndTime - mergeSortStartTime;

System.out.println("Sorted array using Quick Sort:");

for (int i = 0; i < n; i++) {
System.out.print(quickSortArr[i] + " ");
}
System.out.println("\nTime taken by Quick Sort: " + quickSortDuration + "
nanoseconds");

System.out.println("\nSorted array using Merge Sort:");

for (int i = 0; i < n; i++) {
System.out.print(mergeSortArr[i] + " ");
}
System.out.println("\nTime taken by Merge Sort: " + mergeSortDuration + "
nanoseconds");

if (quickSortDuration < mergeSortDuration) {

System.out.println("\nQuick Sort is faster than Merge Sort.");
} else {
System.out.println("\nMerge Sort is faster than Quick Sort.");
}
}

public static void quickSort(int[] arr, int low, int high, int choice) {
if (low < high) {
int pivotIndex = partition(arr, low, high, choice);
quickSort(arr, low, pivotIndex - 1, choice);
quickSort(arr, pivotIndex + 1, high, choice);
}
}

private static int partition(int[] arr, int low, int high, int choice) {
int pivot = arr[high];
int i = low - 1;

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

 if (choice == 1) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
} else {
if (arr[j] > pivot) {
i++;
swap(arr, i, j);
}
}
}

swap(arr, i + 1, high);
return i + 1;
}

private static void swap(int[] arr, int i, int j) {

int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

public static void mergeSort(int[] arr, int left, int right, int choice) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid, choice);
mergeSort(arr, mid + 1, right, choice);
merge(arr, left, mid, right, choice);
}
}

private static void merge(int[] arr, int left, int mid, int right, int choice) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;

int[] L = new int[n1];

int[] R = new int[n2];

for (i = 0; i < n1; i++) {

L[i] = arr[left + i];
}
for (j = 0; j < n2; j++) {
R[j] = arr[mid + 1 + j];
 }

i = 0;
j = 0;
k = left;
while (i < n1 && j < n2) {
if (choice == 1) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
} else {
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++];
}
}
}

Q4: Write a program to sort given set of numbers using Heap sort.
Answer:
public class Q4_22SCSE1010483 {

public void sort(int arr[]) {

int n = arr.length;
 for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

for (int i = n - 1; i > 0; i--) {

int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;

heapify(arr, i, 0);
}
}

void heapify(int arr[], int n, int i) {

int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;

if (left < n && arr[left] > arr[largest])

largest = left;

if (right < n && arr[right] > arr[largest])

largest = right;

if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;

heapify(arr, n, largest);
}
}

static void printArray(int arr[]) {

int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}

public static void main(String args[]) {

int arr[] = { 12, 11, 13, 5, 6, 7 };
int n = arr.length;

Q4_22SCSE1010483ob = new Q4_22SCSE1010483();

ob.sort(arr);
 System.out.println("Sorted array is");
printArray(arr);
}
}

Q5: Write a program to sort given set of numbers using merge sort.
Answer:
public class Q5_22SCSE1010483 {

public void sort(int arr[], int left, int right) {

if (left < right) {
int mid = (left + right) / 2;

sort(arr, left, mid);

sort(arr, mid + 1, right);

merge(arr, left, mid, right);

}
}

void merge(int arr[], int left, int mid, int right) {

int n1 = mid - left + 1;
int n2 = right - mid;

int leftArray[] = new int[n1];

int rightArray[] = new int[n2];

for (int i = 0; i < n1; ++i)

leftArray[i] = arr[left + i];
for (int j = 0; j < n2; ++j)
rightArray[j] = arr[mid + 1 + j];

int i = 0, j = 0;

int k = left;
while (i < n1 && j < n2) {
if (leftArray[i] <= rightArray[j]) {
arr[k] = leftArray[i];
i++;
} else {
arr[k] = rightArray[j];
 j++;
}
k++;
}

while (i < n1) {

arr[k] = leftArray[i];
i++;
k++;
}

while (j < n2) {

arr[k] = rightArray[j];
j++;
k++;
}
}

static void printArray(int arr[]) {

int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}

public static void main(String args[]) {

int arr[] = { 12, 11, 13, 5, 6, 7 };

System.out.println("Given Array");
printArray(arr);

Q5_22SCSE1010483 ob = new Q5_22SCSE1010483();

ob.sort(arr, 0, arr.length - 1);

System.out.println("\nSorted array");
printArray(arr);
}
}

Q6: Write a program to sort given set of numbers Counting Sort.

Answer:
public class Q6_22SCSE1010483 {
public static void sort(int[] arr) {
int n = arr.length;

int max = findMax(arr);

int[] count = new int[max + 1];

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

count[arr[i]]++;
}

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

count[i] += count[i - 1];
}

int[] output = new int[n];

for (int i = n - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}

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

arr[i] = output[i];
}
}

private static int findMax(int[] arr) {

int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}

public static void printArray(int[] arr) {

for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}

public static void main(String[] args) {

int arr[] = { 4, 2, 2, 8, 3, 3, 1 };
 System.out.println("Given Array:");
printArray(arr);

sort(arr);

System.out.println("Sorted Array:");
printArray(arr);
}
}

Q7: Write a program to implement Matrix Chain Multiplication.

Answer:
public class Q7_22SCSE1010483 {
static int matrixChainOrder(int p[], int n) {
int m[][] = new int[n][n];
int i, j, k, L, q;
for (i = 1; i < n; i++)
m[i][i] = 0;

for (L = 2; L < n; L++) {

for (i = 1; i < n - L + 1; i++) {
j = i + L - 1;
if (j == n) continue;
m[i][j] = Integer.MAX_VALUE;
for (k = i; k <= j - 1; k++) {
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[] = new int[]{1, 2, 3, 4};
int size = arr.length;
System.out.println("Minimum number of multiplications is " +
matrixChainOrder(arr, size));
}
}
Q8: Write a program to implement Knapsack using Greedy technique.
Answer:
import java.util.Arrays;
import java.util.Comparator;

class Item {
int value, weight;

public Item(int value, int weight) {

this.value = value;
this.weight = weight;
}
}

public class Q8_22SCSE1010483 {

private static double getMaxValue(Item[] items, int capacity) {

Arrays.sort(items, new Comparator<Item>() {
@Override
public int compare(Item o1, Item o2) {
double r1 = (double) o1.value / o1.weight;
double r2 = (double) o2.value / o2.weight;
return Double.compare(r2, r1);
}
});

double totalValue = 0.0;

for (Item item : items) {

int curWeight = item.weight;
int curValue = item.value;

if (capacity - curWeight >= 0) {

capacity -= curWeight;
totalValue += curValue;
} else {
double fraction = ((double) capacity / curWeight);
totalValue += (curValue * fraction);
capacity = (int) (capacity - (curWeight * fraction));
break;
}
}

return totalValue;
 }

public static void main(String[] args) {

Item[] items = {
new Item(60, 10),
new Item(100, 20),
new Item(120, 30)
};
int capacity = 50;

double maxValue = getMaxValue(items, capacity);

System.out.println("Maximum value in Knapsack = " + maxValue);
}
}

Q9: Write a program to implement Knapsack using Dynamic programming.

Answer:
public class Q9_22SCSE1010483 {

public static int knapSack(int capacity, int weights[], int values[], int n) {
int i, w;
int K[][] = new int[n + 1][capacity + 1];

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

for (w = 0; w <= capacity; w++) {
if (i == 0 || w == 0)
K[i][w] = 0;
else if (weights[i - 1] <= w)
K[i][w] = Math.max(values[i - 1] + K[i - 1][w - weights[i - 1]], K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}

return K[n][capacity];
}

public static void main(String args[]) {

int values[] = new int[] { 60, 100, 120 };
int weights[] = new int[] { 10, 20, 30 };
int capacity = 50;
int n = values.length;
 System.out.println("Maximum value in Knapsack = " + knapSack(capacity, weights,
values, n));
}
}

Q10: Write a program to implement Dijkstra’s Algorithm.

Answer:
import java.util.*;

class Q10_22SCSE1010483 {

static class Graph {

private int V;
private LinkedList<Edge>[] adj;

static class Edge {

int target;
int weight;

Edge(int target, int weight) {

this.target = target;
this.weight = weight;
}
}

Graph(int V) {
this.V = V;
adj = new LinkedList[V];
for (int i = 0; i < V; i++) {
adj[i] = new LinkedList<>();
}
}

void addEdge(int src, int dest, int weight) {

adj[src].add(new Edge(dest, weight));
adj[dest].add(new Edge(src, weight)); // For undirected graph
}

void dijkstra(int src) {

PriorityQueue<Node> pq = new PriorityQueue<>(V, Comparator.comparingInt(node -
> node.distance));
int[] dist = new int[V];

Arrays.fill(dist, Integer.MAX_VALUE);
 dist[src] = 0;
pq.add(new Node(src, 0));

while (!pq.isEmpty()) {
Node node = pq.poll();
int u = node.vertex;

for (Edge edge : adj[u]) {

int v = edge.target;
int weight = edge.weight;

if (dist[u] + weight < dist[v]) {

dist[v] = dist[u] + weight;
pq.add(new Node(v, dist[v]));
}
}
}

printSolution(dist);
}

void printSolution(int[] dist) {

System.out.println("Vertex \t\t Distance from Source");
for (int i = 0; i < dist.length; i++)
System.out.println(i + " \t\t " + dist[i]);
}

static class Node {

int vertex;
int distance;

Node(int vertex, int distance) {

this.vertex = vertex;
this.distance = distance;
}
}
}

public static void main(String[] args) {

int V = 9;
Graph g = new Graph(V);

g.addEdge(0, 1, 4);
g.addEdge(0, 7, 8);
g.addEdge(1, 2, 8);
 g.addEdge(1, 7, 11);
g.addEdge(2, 3, 7);
g.addEdge(2, 8, 2);
g.addEdge(2, 5, 4);
g.addEdge(3, 4, 9);
g.addEdge(3, 5, 14);
g.addEdge(4, 5, 10);
g.addEdge(5, 6, 2);
g.addEdge(6, 7, 1);
g.addEdge(6, 8, 6);
g.addEdge(7, 8, 7);

g.dijkstra(0);
}
}

Q.11 Write a program to implement Bellman-Ford Algorithm.

Ans=

import java.util.ArrayList;

import java.util.List;

public class BellmanFord {

private int V;

private List<List<Edge>> adj;

private static class Edge {

int src, dest, weight;

Edge(int src, int dest, int weight) {

this.src = src;

this.dest = dest;

this.weight = weight;

}
BellmanFord(int V) {

this.V = V;

adj = new ArrayList<>(V);

for (int i = 0; i < V; ++i)

adj.add(new ArrayList<>());

void addEdge(int u, int v, int w) {

adj.get(u).add(new Edge(u, v, w));

int[] BellmanFord(int src) {

int[] dist = new int[V];

for (int i = 0; i < V; ++i)

dist[i] = Integer.MAX_VALUE;

dist[src] = 0;

for (int i = 1; i <= V - 1; ++i) {

for (int u = 0; u < V; ++u) {

for (Edge e : adj.get(u)) {

int v = e.dest, weight = e.weight;

dist[v] = Math.min(dist[v], dist[u] + weight);

for (int u = 0; u < V; ++u) {

for (Edge e : adj.get(u)) {

int v = e.dest, weight = e.weight;

if (dist[v] > dist[u] + weight) {

System.out.println("Graph contains negative weight cycle");

return null;

return dist;

}
 public static void main(String[] args) {

int V = 5;

BellmanFord graph = new BellmanFord(V);

graph.addEdge(0, 1, -1);

graph.addEdge(0, 2, 4);

graph.addEdge(1, 2, 3);

graph.addEdge(2, 1, 1);

graph.addEdge(1, 3, 2);

graph.addEdge(2, 3, 2);

graph.addEdge(3, 4, -2);

int[] dist = graph.BellmanFord(0);

if (dist == null) {

} else {

System.out.println("Vertex \tDistance from Source 0");

for (int i = 0; i < V; ++i)

System.out.println(i + "\t" + dist[i]);

Output:

Q.12 Write a program to implement n-Queen Problem using backtracking.

Ans=

public class NQueens {

final int N;

public NQueens(int n) {
 this.N = n;

boolean isSafe(int board[][], int row, int col) {

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

if (board[i][col] == 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 >= 0 && j < N; i--, j++) {

if (board[i][j] == 1) {

return false;

return true;

boolean solveNQueens(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 (solveNQueens(board, col + 1)) {

return true;

board[i][col] = 0;

return false;
 }

void printSolution(int board[][]) {

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

for (int j = 0; j < N; j++) {

System.out.print(" " + board[i][j] + " ");

System.out.println();

public static void main(String[] args) {

int N = 4;

int board[][] = new int[N][N];

NQueens queens = new NQueens(N);

if (queens.solveNQueens(board, 0)) {

System.out.println("Solution found:");

queens.printSolution(board);

} else {

System.out.println("No solution exists");

Output:

Q.13 Write a program to implement String Matching using Rabin-Karp algorithm

Ans=

public class RabinKarp {

final int d = 256;

int hash(String str, int n) {

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

hash = (hash * d + str.charAt(i)) % q;

return hash;

int dthPower(int x, int d) {

int result = 1;

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

result = (result * x) % q;

return result;

void search(String pat, String txt) {

int M = pat.length();

int N = txt.length();

int p = 0;

int t = 0;

int h = 1;

if (M > N) {

System.out.println("Pattern not found");

return;

h = dthPower(d, M - 1);

p = hash(pat, M);

t = hash(txt, M);

for (int i = 0; i <= N - M; i++) {

if (p == t) {

boolean found = true;

for (int j = 0; j < M; j++) {

if (pat.charAt(j) != txt.charAt(i + j)) {

found = false;

break;

}
 }

if (found) {

System.out.println("Pattern found at index " + i);

if (i < N - M) {

t = (d * (t - txt.charAt(i) * h) + txt.charAt(i + M)) % q;

if (t < 0) {

t = (t + q);

public static void main(String[] args) {

String txt = " KETAN ";

String pat = "AN";

RabinKarp rk = new RabinKarp();

rk.search(pat, txt);

Output:

Q.14 Obtain the Topological ordering of vertices in a given digraph.

Ans=

import java.util.*;

public class TopologicalSort {

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

public TopologicalSort(int v) {

V = v;

adj = new ArrayList<>(v);

for (int i = 0; i < v; ++i)

adj.add(new ArrayList<>());

void addEdge(int u, int v) {

adj.get(u).add(v);

A recursive function used by topologicalSort

void topologicalSortUtil(int v, boolean visited[], Stack<Integer> stack) {

visited[v] = true;

Integer i;

for (i : adj.get(v)) {

if (!visited[i])

topologicalSortUtil(i, visited, stack);

stack.push(v);

List<Integer> topologicalSort() {

Stack<Integer> stack = new Stack<>();

boolean visited[] = new boolean[V];

for (int i = 0; i < V; i++)

visited[i] = false;

for (int i = 0; i < V; i++)

if (!visited[i])

topologicalSortUtil(i, visited, stack);

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

while (!stack.isEmpty())

order.add(stack.pop());
 return order;

public static void main(String args[]) {

TopologicalSort g = new TopologicalSort(6);

g.addEdge(5, 2);

g.addEdge(5, 0);

g.addEdge(4, 0);

g.addEdge(4, 1);

g.addEdge(2, 3);

g.addEdge(3, 1);

System.out.println("Topological Ordering of Vertices:");

List<Integer> order = g.topologicalSort();

for (int i : order)

System.out.print(i + " ");

Output:

Q.15 Write a program to implement Minimum Cost spanning tree.

Ans:

import java.util.ArrayList;

import java.util.Comparator;

import java.util.List;

public class KetanMST {

static class Edge {

int src, dest, weight;

Edge(int src, int dest, int weight) {

 this.src = src;

this.dest = dest;

this.weight = weight;

static class UnionFind {

int[] parent, rank;

UnionFind(int n) {

parent = new int[n];

rank = new int[n];

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

parent[i] = i;

int find(int x) {

if (parent[x] != x)

parent[x] = find(parent[x]);

return parent[x];

void union(int x, int y) {

int rootX = find(x);

int rootY = find(y);

if (rank[rootX] < rank[rootY])

parent[rootX] = rootY;

else if (rank[rootX] > rank[rootY])

parent[rootY] = rootX;

else {

parent[rootY] = rootX;

rank[rootX]++;

public static int KetanMST(List<Edge> edges, int V) {

edges.sort(Comparator.comparingInt(e -> e.weight));

 UnionFind uf = new UnionFind(V);

int mstCost = 0;

int edgesIncluded = 0;

for (Edge edge : edges) {

int x = uf.find(edge.src);

int y = uf.find(edge.dest);

if (x != y) {

uf.union(x, y);

mstCost += edge.weight;

edgesIncluded++;

if (edgesIncluded == V - 1)

return mstCost;

return -1; // No MST possible if graph is disconnected

public static void main(String[] args) {

List<Edge> edges = new ArrayList<>();

edges.add(new Edge(0, 1, -1));

edges.add(new Edge(0, 2, 4));

edges.add(new Edge(1, 2, 3));

edges.add(new Edge(2, 1, 1));

edges.add(new Edge(1, 3, 2));

edges.add(new Edge(2, 3, 2));

edges.add(new Edge(3, 4, -2));

int V = 5;

int mstCost = KetanMST(edges, V);

System.out.println("Minimum Cost Spanning Tree Cost: " + mstCost);

Output:
Q.16 Write a program to implement Sum of subset problem.

Ans:

Class KetanSubsetSum {

static boolean is KetanSubsetSum(int arr[], int n, int sum) {

if (sum == 0) return true;

if (n == 0) return false;

return isKetanSubsetSum(arr, n - 1, sum) || isKetanSubsetSum(arr, n - 1, sum - arr[n - 1]);

public static void main(String[] args) {

int arr[] = {3, 34, 4, 12, 5, 2};

int sum = 9;

if (isKetanSubsetSum(arr, arr.length, sum))

System.out.println("Found a subset with given sum");

else

System.out.println("No subset with given sum");

Output:

Q.17 Write a program to implement Greedy algorithm using Task Scheduling Problem.

Ans:

import java.util.ArrayList;

import java.util.Collections;

import java.util.Comparator;

import java.util.List;

public class GreedyTaskScheduling {

static class Task {

int startTime;

int endTime;

Task(int startTime, int endTime) {

 this.startTime = startTime;

this.endTime = endTime;

public static int findMaxTasks(List<Task> tasks) {

Collections.sort(tasks, Comparator.comparingInt(t -> t.endTime));

int lastEndTime = 0;

int count = 0;

for (Task task : tasks) {

if (task.startTime > lastEndTime) {

lastEndTime = task.endTime;

count++;

return count;

public static void main(String[] args) {

List<Task> tasks = new ArrayList<>();

tasks.add(new Task(1, 2));

tasks.add(new Task(3, 4));

tasks.add(new Task(0, 6));

tasks.add(new Task(5, 7));

tasks.add(new Task(8, 9));

int maxTasks = findMaxTasks(tasks);

System.out.println("Maximum number of tasks that can be scheduled: " + maxTasks);

Output:

Q.18 Write a program to implement Greedy algorithm using Acitivity Selection Problem.

Ans:

import java.util.ArrayList;
import java.util.Collections;

import java.util.Comparator;

import java.util.List;

public class ActivitySelection {

static class Activity {

int start;

int finish;

Activity(int start, int finish) {

this.start = start;

this.finish = finish;

public static List<Activity> selectActivities(List<Activity> activities) {

Collections.sort(activities, Comparator.comparingInt(a -> a.finish));

List<Activity> selectedActivities = new ArrayList<>();

int currentEndTime = 0;

for (Activity activity : activities) {

if (activity.start >= currentEndTime) {

selectedActivities.add(activity);

currentEndTime = activity.finish;

return selectedActivities;

public static void main(String[] args) {

List<Activity> activities = new ArrayList<>();

activities.add(new Activity(1, 2));

activities.add(new Activity(3, 4));

activities.add(new Activity(0, 6));

activities.add(new Activity(5, 7));

activities.add(new Activity(8, 9));

 List<Activity> selectedActivities = selectActivities(activities);

System.out.println("Selected activities:");

for (Activity activity : selectedActivities) {

System.out.println("Start: " + activity.start + ", Finish: " + activity.finish);

Output:

Q.19 Compute the transitive closure of a given directed graph using Warshall's algorithm. Write a program to
implement shortest path algorithm.

Ans:

public class WarshallTransitiveClosure {

public static void transitiveClosure(int[][] graph, int V) {

for (int k = 0; k < V; k++) {

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

for (int j = 0; j < V; j++) {

graph[i][j] = graph[i][j] | (graph[i][k] & graph[k][j]);

public static void printTransitiveClosure(int[][] graph, int V) {

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

for (int j = 0; j < V; j++) {

System.out.print(graph[i][j] + " ");

System.out.println();

}
 }

public static void main(String[] args) {

int V = 4; // Number of vertices

int[][] graph = {

{1, 0, 0, 1},

{0, 1, 0, 1},

{0, 0, 1, 0},

{0, 0, 0, 1}

};

transitiveClosure(graph, V);

System.out.println("Transitive Closure Matrix:");

printTransitiveClosure(graph, V);

Output:

Q.20 Write a program to implement solve LCS problem.

Ans:

public class LCS {

public static int lcs(String str1, String str2) {

int m = str1.length();

int n = str2.length();

int[][] dp = new int[m + 1][n + 1];

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

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

if (i == 0 || j == 0) {

dp[i][j] = 0;

} else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {

dp[i][j] = 1 + dp[i - 1][j - 1];

} else {
 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

return dp[m][n];

public static void main(String[] args) {

String str1 = " NEEDOFCARD";

String str2 = " NEED";

int lcsLength = lcs(str1, str2);

System.out.println("Length of LCS: " + lcsLength);

Output: