EX NO: 02(a)

DATE: SEARCHING 1

AIM :

ALGORITHM :
Step 1: Start the program.
Step 2: Create a Scanner object to read input from the user.
Step 3: Read the size of the array (n) from the user.
Step 4: Create an integer array (a) of size n+1.
Step 5: Read the n+1 integers from the user and store them in the array.
Step 6: Read the value of k from the user.
Step 7: Traverse the array from start to end.
Step 8: If the current element of the array is equal to k, store its index in a variable c, print c
followed by a space, and increment the counter d by 1.
Step 9: After traversing the array, if d is still 0, print "-1 -1".
Step 10 : for (i = 0; i < n + 1; i++)
a[i] = sc.nextInt();
int k = sc.nextInt();
for (i = 0; i < n + 1; i++) {
if (a[i] == k) {
c = i;
PROGRAM :
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a[] = new int[n + 1];
int i, d = 0, c = 0;
for (i = 0; i < n + 1; i++)
a[i] = sc.nextInt();
int k = sc.nextInt();
for (i = 0; i < n + 1; i++) {
 if (a[i] == k) {
c = i;
System.out.print(c + " ");
d++;
}
}
if (d == 0)
System.out.println("-1 -1");
}
}
OUTPUT:
5
5 7 7 8 8 10
8
34

Class Performance
Record
Viva
Total

RESULT:
 EX NO : 02 (b)
DATE : SEARCHING 2

AIM:

ALGORITHM:
Step 1: Start
Step 2: Create a Scanner object to read input from the console
Step 3: Read an integer n from the console
Step 4: Create an integer array arr of size n
Step 5: For i from 0 to n-1, read each integer into the array arr from the console
Step 6: Initialize l to 0 and h to n-1
Step 7: While l <= h, do the following:
Step 7.1: If arr[l] <= arr[h], then print l and return from the program
Step 7.2: Set m to (l+h)/2
Step 7.3:Set next to (m+1)%n
Step 7.4:Set p to (m+n-1)%n
Step 7.5: If arr[m] <= arr[next] and arr[m] <= arr[p], then print m and
return from the program
Step 7.8: Else if arr[m] <= arr[h], then set h to m-1
Step 7.9: Else if arr[m] >= arr[l], then set l to m+1
Step 8: End
Step 9: while (1 <= h) {
if (arr[1] <= arr[h])
return l;
m = (1 + h) / 2;
next = (m + 1) % n;
p = (m + n - 1) % n;
if (arr[m] <= arr[next] && arr[m] <= arr[p])
return m;
else if (arr[m] <= arr[h])
h = m - 1;
else if (arr[m] >= arr[l])
l = m + 1;}
PROGRAM:
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt(); }
int l = 0, h = n - 1;
while (l <= h) {
if (arr[l] <= arr[h]) {
System.out.println(l);
return; }
int m = (l + h) / 2;
int next = (m + 1) % n;
int p = (m + n - 1) % n;
if (arr[m] <= arr[next] && arr[m] <= arr[p]) {
System.out.println(m);
return;
} else if (arr[m] <= arr[h]) {
h = m - 1;
} else if (arr[m] >= arr[l]) {
l = m + 1; } } }
}
OUTPUT: Class Performance
5 Record
8 9 10 2 5 6 Viva
3 Total

RESULT:
EX NO: 03 (a)
DIVIDE AND CONQUER 1
DATE:

AIM:

ALGORITHM:
Step 1: Read the size of first array (n1) from the user.
Step 2: Create an integer array arr1 of size n1.
Step 3: Read the elements of the array arr1 from the user.
Step 4: Read the size of second array (n2) from the user.
Step 5: Create an integer array arr2 of size n2.
Step 6: Read the elements of the array arr2 from the user.
Step 7: Read the position (pos) of the element to be searched from the user.
Step 8: Create an integer array newarr of size (n1 + n2).
Step 9: Copy the elements of arr1 and arr2 to newarr using System.arraycopy().
Step 10: Call the findElement() function and pass newarr and pos as arguments.
Step 11: Store the return value of the function in a variable named element.
Step 12: Print the value of element using System.out.println().
PROGRAM:
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n1 = sc.nextInt();
int[] arr1 = new int[n1];
for(int i=0; i<n1; i++)
arr1[i] = sc.nextInt();
int n2 = sc.nextInt();
int[] arr2 = new int[n2];
for(int i=0; i<n2; i++)
arr2[i] = sc.nextInt();
int pos = sc.nextInt();
int newarr[] = new int[n1+n2];
 System.arraycopy(arr1,0,newarr,0,n1);
System.arraycopy(arr2,0,newarr,n1,n2);
int element = findElement(newarr,pos);
System.out.println(element);
}
public static int findElement(int[] arr, int pos) {
int left = 0;
int right = arr.length-1;
while(left <= right) {
int mid = left + (right-left)/2;
if(mid == pos-1)
return arr[mid];
else if(mid < pos-1)
left = mid+1;
else
right = mid-1;
}
return -1;
}}
OUTPUT:
5
23769
4
1 4 8 10
Class Performance
5
Record
6
Viva
Total

RESULT:
EX NO: 03 (b)
DIVIDE AND CONQUER 2
DATE:

AIM:

ALGORITHM:
Step 1: Define a class Pair to hold the minimum and maximum values
Step 2: Define a function findMinMax to take the array, left and right indices as input
Step 3: Check if left equals right. If yes, return a Pair object with arr[left] as min and max
Step 4: Check if right equals left+1. If yes, compare arr[left] and arr[right], and return a Pair
object with the minimum and maximum values
Step 5: Find the mid index as left + (right-left)/2
Step 6: Recursively call findMinMax on the left half of the array from left to mid and store the
returned Pair object as leftResult
Step 7: Recursively call findMinMax on the right half of the array from mid+1 to right and store
the returned Pair object as rightResult
Step 8: Find the minimum and maximum values from leftResult and rightResult
Step 9: Return a Pair object with the minimum and maximum values found in step 8.
PROGRAM:
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++)
arr[i] = sc.nextInt();
Pair result = findMinMax(arr, 0, n-1);
System.out.println("Minimum element: " + result.min);
System.out.println("Maximum element: " + result.max);
}
static class Pair {
int min;
int max;
 public Pair(in t min, int max) {
this.min = min;
this.max = max;
}
}
public static Pair findMinMax(int[] arr, int left, int right) {
if(left == right) {
return new Pair(arr[left], arr[right]);
}
if(right == left+1) {
if(arr[left] < arr[right]) {
return new Pair(arr[left], arr[right]);
} else {
return new Pair(arr[right], arr[left]);
}
}
int mid = left + (right-left)/2;
Pair leftResult = findMinMax(arr, left, mid);
Pair rightResult = findMinMax(arr, mid+1, right);
int min = Math.min(leftResult.min, rightResult.min);
int max = Math.max(leftResult.max, rightResult.max);
return new Pair(min, max);
}
}
OUTPUT:
Class Performance
5
4 8 1 21 7 Record

Minimum Element: 1 Viva

Maximum Element: 21 Total

RESULT:
EX NO: 04(a)
QUICK SORT
DATE:

AIM:

ALGORITHM:
Step 1 − Choose the highest index value has pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is new pivot
Step 9− Make the right-most index value pivot
Step 10 − partition the array using pivot value
Step 11− quicksort left partition recursively
Step 12 − quicksort right partition recursively
PROGRAM:
import java.io.*;
class QuickSort {
static void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static int partition(int[] arr, int low, int high){
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);}
 }
swap(arr, i + 1, high);
return (i + 1);
}
static void quickSort(int[] arr, int low, int high){
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high); }
}
public static void printArr(int[] arr){
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" "); }
}
public static void main(String[] args){
int[] arr = { 10, 7, 8, 9, 1, 5 };
int N = arr.length;
quickSort(arr, 0, N - 1);
System.out.println("Sorted array:");
printArr(arr);
}
}
OUTPUT:
Sorted Array: 1 5 7 8 9 10

Class Performance
Record

Viva
Total
RESULT:
 EX NO: 03(b)
LARGEST SUM CONTINGUOUS SUBARRAY
DATE :

AIM:

ALGORITHM:
Step 1: Initialize two variables, max_so_far and max_ending_here, to the smallest possible integer
and 0, respectively.
Step 2: Traverse the array from left to right.
Step 3: Add each element to max_ending_here.
Step 4: If max_ending_here is greater than max_so_far, update max_so_far with max_ending_here.
Step 5: If max_ending_here becomes negative, set it to 0.
Step 6: Continue traversing the array until all elements have been processed.
Step 7: Return max_so_far as the result.
Step 8: Initialize:
max_so_far = INT_MIN
max_ending_here = 0
Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
(c) if(max_ending_here < 0)
max_ending_here = 0
return max_so_far
PROGRAM:
import java.io.*;
import java.util.*;
class Kadane {
public static void main(String[] args){
int[] a = { -2, -3, 4, -1, -2, 1, 5, -3 };
System.out.println("Maximum contiguous sum is "+ maxSubArraySum(a));
}
static int maxSubArraySum(int a[]){
 int size = a.length;
int max_so_far = Integer.MIN_VALUE, max_ending_here = 0;
for (int i = 0; i < size; i++) {
max_ending_here = max_ending_here + a[i];
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
if (max_ending_here < 0)
max_ending_here = 0;
}
return max_so_far;
}
}
OUTPUT:
Maximum contiguous sum is 7

Class Performance
Record
Viva
Total

RESULT:

EX NO : 05(a)
FLOYD WARSHALL ALGORITHM
DATE:

AIM:

ALGORITHM:
Step 1: Initialize the solution matrix same as the input graph matrix as a first step.
Step 2: Then update the solution matrix by considering all vertices as an intermediate vertex.
Step 3: The idea is to one by one pick all vertices and updates all shortest paths which include the
picked vertex as an intermediate vertex in the shortest path.
Step 4: When we pick vertex number k as an intermediate vertex, we already have considered
vertices {0, 1, 2, .. k-1} as intermediate vertices.
Step 5: For every pair (i, j) of the source and destination vertices respectively, there are two
possible cases.
Step 6: void floydwarshall(){
int cost [N][N]; int i, j, k;
for(i=0; i<N; i++)
for(j=0; j<N; j++)
cost [i][j]= cost Mat [i] [i];
for(k=0; k<N; k++){
for(i=0; i<N; i++)
for(j=0; j<N; j++)
if(cost [i][j]> cost [i] [k] + cost [k][j];
cost [i][j]=cost [i] [k]+'cost [k] [i]: } }
PROGRAM:
import java.io.*;
import java.lang.*;
import java.util.*;
class AllPairShortestPath {
final static int INF = 99999, V = 4;
void floydWarshall(int dist[][]){

int i, j, k;
for (k = 0; k < V; k++) { for (i = 0; i < V; i++) { for (j = 0; j < V; j++) {
if (dist[i][k] + dist[k][j]< dist[i][j])
 dist[i][j] = dist[i][k] + dist[k][j]; } } }
printSolution(dist);
}
void printSolution(int dist[][]){
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){
int graph[][] = { { 0, 5, INF, 10 },{ INF, 0, 3, INF },{ INF, INF, 0, 1 },{ INF, INF, INF, 0 }
};
AllPairShortestPath a = new AllPairShortestPath();
a.floydWarshall(graph);}
}
OUTPUT:
0 5 8 9
INF 0 3 4
INF INF 0 1
Class Performance
INF INF INF 0
Record
Viva
Total

RESULT:
EX NO: 06(a)
MAXIMUM FLOW PROBLEM
DATE:

AIM:

ALGORITHM:
Step 1: Initialize flow in all edges to 0.
Step 2: While there exists an augmenting path P from source 's' to sink 't' in the residual graph:
a) Use BFS to find path P with available capacity > 0.
b) Find the minimum residual capacity (bottleneck capacity) along path P; call it pathFlow.
c) For each edge (u, v) in P:
i) Subtract pathFlow from residual capacity of edge (u, v)
ii) Add pathFlow to residual capacity of reverse edge (v, u)
d) Add pathFlow to the overall maxFlow.
Step 3: return maxFlow
PROGRAM :
import java.util.*;
public class MaxFlow {
static final int V = 6;
int fordFulkerson(int[][] graph, int s, int t) {
int u, v;
int[][] rGraph = new int[V][V];
for (u = 0; u < V; u++)
for (v = 0; v < V; v++)
rGraph[u][v] = graph[u][v];
int[] parent = new int[V];
int maxFlow = 0;
while (bfs(rGraph, s, t, parent)) {
int pathFlow = Integer.MAX_VALUE;
for (v = t; v != s; v = parent[v]) {
u = parent[v];
pathFlow = Math.min(pathFlow, rGraph[u][v]); }
for (v = t; v != s; v = parent[v]) {
 u = parent[v];
rGraph[u][v] -= pathFlow;
rGraph[v][u] += pathFlow; }
maxFlow += pathFlow; }
return maxFlow; }
boolean bfs(int[][] rGraph, int s, int t, int[] parent) {
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
queue.add(s);
visited[s] = true;
parent[s] = -1;
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v = 0; v < V; v++) {
if (!visited[v] && rGraph[u][v] > 0) {
queue.add(v);
parent[v] = u;
visited[v] = true;}}}
return visited[t]; }
public static void main(String[] args) {
MaxFlow m = new MaxFlow();
int[][] graph = new int[][]{
{0, 16, 13, 0, 0, 0},
{0, 0, 10, 12, 0, 0},
{0, 0, 0, 0, 0, 0} };
System.out.println("The maximum possible flow is: " +m.fordFulkerson(graph, 0, 5)) }}
OUTPUT :
Class Performance
The maximum possible flow is: 23
Record
Viva
Total

RESULT :
EX NO: 06(b)
DIJKSTRA’S ALGORITHM
DATE:
AIM:

ALGORITHM:
Step 1: Create a set 'visited' to store visited vertices.
Step 2: Create an array 'dist[]' and initialize all distances as infinity.
Step 3: Set dist[source] = 0.
Step 4: Create a priority queue and insert source vertex with distance 0.
Step 5: While the priority queue is not empty:
a) Extract vertex u with minimum distance.
b) If u is already visited, skip.
c) Mark u as visited.
d) For each neighbor v of u:
i) If dist[u] + weight(u, v) < dist[v], then
ii) Update dist[v]
iii) Add v to the priority queue
Step 6: Return dist[] array containing shortest distances from source.
PROGRAM :
import java.util.*;
class Dijkstra {
static class Edge {
int dest, weight;
Edge(int dest, int weight) {
this.dest = dest;
this.weight = weight; }}
static class Node implements Comparable<Node> {
int vertex, distance;
Node(int vertex, int distance) {
this.vertex = vertex;
this.distance = distance; }
public int compareTo(Node other) {
return this.distance - other.distance; }}
static void dijkstra(List<List<Edge>> graph, int source) {
 int V = graph.size();
int[] dist = new int[V];
boolean[] visited = new boolean[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[source] = 0;
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(source, 0));
for (Edge edge : graph.get(u)) {
int v = edge.dest;
int weight = edge.weight;
if (!visited[v] && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.add(new Node(v, dist[v])); }}}
System.out.println("Vertex\tDistance from Source " + source);
for (int i = 0; i < V; i++) {
System.out.println(i + "\t\t" + dist[i]); }}
public static void main(String[] args) {
List<List<Edge>> graph = new ArrayList<>();
graph.add(new ArrayList<>());
graph.get(0).add(new Edge(1, 10));
graph.get(0).add(new Edge(4, 5));
graph.get(1).add(new Edge(2, 1));
graph.get(1).add(new Edge(4, 2));
graph.get(2).add(new Edge(3, 4));
dijkstra(graph, 0); }}
OUTPUT : Class Performance
0 0 Record
1 8
Viva
2 9
Total
RESULT :
EX NO: 07(a)
PRIM’S ALGORITHM
DATE:
AIM:

ALGORITHM:
Step 1: Determine an arbitrary vertex as the starting vertex of the MST.
Step 2: Follow steps 3 to 5 till there are vertices that are not included in the MST (known as fringe vertex).
Step 3: Find edges connecting any tree vertex with the fringe vertices.
Step 4: Find the minimum among these edges.
Step 5: Add the chosen edge to the MST if it does not form any cycle. Step 6: Return the MST and exit.
Step 6 : prim(graph): mst = empty set
startVertex = first vertex in graph
mst.add(startVertex)
edges = edges connected to startVertex
while mst has fewer vertices than graph:
minEdge, minWeight = findMinEdge(edges)
mst.add(minEdge)
for edge in edges connected to minEdge:
if edge is not in mst:
edges.add(edge)
edges.remove(minEdge)
return mst as an array
PROGRAM :
import java.util.*;
class PrimMST {
private static final int V = 5;
int minKey(int key[], Boolean mstSet[]) {
int min = Integer.MAX_VALUE, min_index = -1;
for (int v = 0; v < V; v++)
if (!mstSet[v] && key[v] < min) {
min = key[v];
min_index = v; }
return min_index }
void printMST(int parent[], int graph[][]) {
 System.out.println("Edge \tWeight");
for (int i = 1; i < V; i++)
System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]) }
void primMST(int graph[][]) {
int parent[] = new int[V];
int key[] = new int[V];
Boolean mstSet[] = new Boolean[V];
for (int i = 0; i < V; i++) {
key[i] = Integer.MAX_VALUE;
mstSet[i] = false; }
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++)
if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v]; }}
printMST(parent, graph); }
public static void main(String[] args) {
int graph[][] = {{ 0, 2, 0, 6, 0 },{ 2, 0, 3, 8, 5 },{ 0, 3, 0, 0, 7 },{ 6, 8, 0, 0, 9 },{ 0, 5, 7, 9, 0 }};
PrimMST mst = new PrimMST();
mst.primMST(graph); }}
OUTPUT :
Class Performance
Edge Weight
Record
0-1 2
Viva
1-2 3
Total
0-3 6
1-4 5
RESULT :
EX NO: 07(b)
KRUSKAL’S ALGORITHM
DATE:
AIM:

ALGORITHM:
Step 1: Create a forest F in such a way that every vertex of the graph is a separate tree.
Step 2: Create a set E that contains all the edges of the graph.
Step 3: Repeat Steps 4 and 5 while E is NOT EMPTY and F is not spanning
Step 4: Remove an edge from E with minimum weight
Step 5: If the edge obtained in Step 4 connects two different trees, then add it to the forest F(for combining two trees into
one tree) else discard the edge

Step 6: KRUSKAL(G): A = ∅

For each vertex v ∈ G.V:

MAKE-SET(v)For each edge (u, v)∈ G.E ordered by increasing order by weight(u,v):
if FIND-SET(u) ≠ FIND-SET(v):
A = A ∪ {(u, v)}
UNION(u, v)
return A
PROGRAM :
import java.util.Arrays;
public class Main {
static int find(int[] parent, int node) {
if (parent[node] != node)
parent[node] = find(parent, parent[node]);
return parent[node];
}
static void union(int[] parent, int[] rank, int u, int v) {
u = find(parent, u);
v = find(parent, v);
if (rank[u] < rank[v]) parent[u] = v;
else if (rank[u] > rank[v]) parent[v] = u;
else { parent[v] = u; rank[u]++; }
}
static void kruskal(int[][] edges, int n) {
Arrays.sort(edges, (a, b) -> a[2] - b[2]);
 int[] parent = new int[n];
int[] rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
int cost = 0;
System.out.println("Edge \tWeight");
for (int[] edge : edges) {
int u = find(parent, edge[0]);
int v = find(parent, edge[1]);
if (u != v) {
union(parent, rank, u, v);
cost += edge[2];
System.out.println(edge[0] + " - " + edge[1] + "\t" + edge[2]);
}
}
System.out.println("Total MST cost: " + cost);
}
public static void main(String[] args) {
int[][] edges = { {0, 1, 10},{0, 2, 6},{0, 3, 5},{1, 3, 15},{2, 3, 4}};
kruskal(edges, 4);
}
}
OUTPUT :
Edge Weight
2-3 4 Class Performance

0-3 5 Record

0-1 10 Viva

Total MST cost: 19 Total

RESULT :
EX NO: 08(a)
N-Queen PROBLEM
DATE:
AIM:

ALGORITHM:

Step 1: Start from the leftmost column (col = 0).

Step 2: If all queens are placed (col >= N), print the board and return true.
Step 3: For each row in the current column:

3.1 If placing a queen at [row][col] is safe:

3.1.1 Place the queen.

3.1.2 Recur for next column.

3.1.3 If recursion returns true, return true.

3.1.4 Else, backtrack (remove queen).

Step 4: If no row works, return false to backtrack.

PROGRAM :

import java.util.*;

public class NQueens {

static int N;

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;

return true; }

static boolean solve(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 (solve(board, col + 1)) return true;

board[i][col] = 0; }}

return false; }

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

for (int[] row : board) {

for (int cell : row)

System.out.print(cell == 1 ? " Q " : " . ");

System.out.println();}}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

System.out.print("Enter n: ");

N = sc.nextInt();

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

if (solve(board, 0)) print(board);

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

OUTPUT :

. Q . . Class Performance

. . . Q Record
Viva
Q . . .
Total
. . Q .

RESULT :
EX NO: 08(b)
SUBSET SUM PROBLEM
DATE:
AIM:

ALGORITHM:
Step 1: Create a 2D boolean array dp[n+1][sum+1]
Step 2: Initialize dp[0][0] = true (empty subset sums to 0)
Step 3: For i from 1 to n:
For j from 0 to sum:
If j < arr[i-1]:
dp[i][j] = dp[i-1][j]
Else:
dp[i][j] = dp[i-1][j] || dp[i-1][j - arr[i-1]]
Step 4: Return dp[n][sum]
PROGRAM :
public class SubsetSum {

// Function to check if subset sum is possible

static boolean isSubsetSum(int[] arr, int n, int sum) {
boolean[][] dp = new boolean[n + 1][sum + 1];

// Base case: sum 0 is always possible (with empty subset)

for (int i = 0; i <= n; i++)
dp[i][0] = true;

// Fill the subset table

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
if (arr[i - 1] > j)
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - arr[i - 1]];
}
 }

return dp[n][sum];
}

public static void main(String[] args) {

int[] arr = {3, 34, 4, 12, 5, 2};
int sum = 9;
int n = arr.length;

if (isSubsetSum(arr, n, sum))
System.out.println("Found a subset with given sum");
else
System.out.println("No subset with given sum");
}
}
OUTPUT :
Found a subset with given sum

Class Performance
Record
Viva
Total

RESULT :
EX NO: 09
JOB - ASSIGNMENT PROBLEM
DATE:
AIM:

ALGORITHM:
Step 1: Initialize minimum cost to infinity.
Step 2: Start assigning jobs to workers one by one.
Step 3: For each worker, try every unassigned job:
3.1 Add job to current assignment
3.2 Calculate current cost
3.3 If cost is already more than min cost → prune (skip)
3.4 If all workers are assigned → update min cost if lower
3.5 Else → recurse to next worker
Step 4: Backtrack to explore other job combinations
Step 5: Repeat until all possibilities are checked
Step 6: Return the minimum cost found
PROGRAM :
import java.util.*;
public class Main {
static final int N = 4;
static class Node {
int worker, job, cost, pathCost;
boolean[] assigned;
Node parent;
Node(int worker, int job, boolean[] assigned, Node parent, int[][] costMatrix) {
this.worker = worker;
this.job = job;
this.parent = parent;
this.assigned = assigned.clone();
if (job != -1) this.assigned[job] = true;
pathCost = (parent != null ? parent.pathCost : 0) + (worker != -1 && job != -1 ? costMatrix[worker]
[job] : 0);
cost = pathCost + estimate(costMatrix, worker + 1, this.assigned); }
int estimate(int[][] costMatrix, int nextWorker, boolean[] assigned) {
 int cost = 0;
for (int i = nextWorker; i < N; i++) {
int min = Integer.MAX_VALUE;
for (int j = 0; j < N; j++)
if (!assigned[j]) min = Math.min(min, costMatrix[i][j]);
cost += min; }
return cost; }}
static void printPath(Node node) {
if (node == null || node.worker == -1) return;
printPath(node.parent);
System.out.println("Worker " + (char)('A' + node.worker) + " → Job " + node.job); }
static int findMinCost(int[][] costMatrix) {
PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.cost));
pq.add(new Node(-1, -1, new boolean[N], null, costMatrix));
int nextWorker = curr.worker + 1;
for (int j = 0; j < N; j++)
if (!curr.assigned[j])
pq.add(new Node(nextWorker, j, curr.assigned, curr, costMatrix)); }
return -1; }
public static void main(String[] args) {
int[][] cost = {{9, 2, 7, 8},{6, 4, 3, 7},{5, 8, 1, 8},{7, 6, 9, 4}};
System.out.println("Minimum Cost: " + findMinCost(cost)); }}
OUTPUT :
Worker A → Job 1 Class Performance
Worker B → Job 2 Record
Worker C → Job 0 Viva
Worker D → Job 3
Total
Minimum Cost: 13

RESULT :
EX NO: 10(a)
TRAVELLING SALESMAN PROBLEM
DATE:
AIM:

ALGORITHM:
Step 1: Start from a random city.
Step 2: From the current city, choose the nearest unvisited city and move to that city.
Step 3: Mark the chosen city as visited.
Step 4: Repeat step 2 and 3 until all cities are visited.
Step 5: Once all cities are visited, return to the starting city.
Step 6: If size of S is 2, then S must be {1, i}, C(S, i) = dist(1, i) Else if size of S is greater than 2. C(S, i) =
min { C(S-{i}, j) + dis(j, i)} where j belongs to S, j != i and j != 1.
PROGRAM:
import java.io.*;
import java.util.*;

public class TSE {

static int n = 4;
static int MAX = 1000000;

// Distance matrix (1-indexed)

static int[][] dist = {
{ 0, 0, 0, 0, 0 },
{ 0, 0, 10, 15, 20 },
{ 0, 10, 0, 25, 25 },
{ 0, 15, 25, 0, 30 },
{ 0, 20, 25, 30, 0 },
};
static int[][] memo = new int[n + 1][1 << (n + 1)];
static int fun(int i, int mask) {
if (mask == ((1 << i) | 3))
return dist[1][i];
if (memo[i][mask] != 0)
return memo[i][mask];
 int res = MAX;
for (int j = 1; j <= n; j++) {
if ((mask & (1 << j)) != 0 && j != i && j != 1) {
res = Math.min(res, fun(j, mask & (~(1 << i))) + dist[j][i]);
}
}
return memo[i][mask] = res;
}
public static void main(String[] args) {
int ans = MAX;
for (int i = 1; i <= n; i++) {
ans = Math.min(ans, fun(i, (1 << (n + 1)) - 1) + dist[i][1]);
}
System.out.println("The cost of most efficient tour = " + ans);
}
}

OUTPUT :
The cost of most efficient tour = 80

Class Performance
Record
Viva
Total

RESULT :
EX NO: 10(b)
HAMILTON PATH
DATE:
AIM:

ALGORITHM:
Step 1: Initialize an empty path array and mark all vertices as unvisited.
Step 2: Choose a starting vertex and add it to the path array.
Step 2.1: If the path array contains all vertices, return true and print the path.
Step 2.2: Else, consider all the vertices adjacent to the last vertex added to the path array.
Step 3: For each adjacent vertex, check if it is not already in the path array.
Step 4: If the vertex is not in the path array, add it to the path array and mark it as visited.
Step 5: Recursively check if adding the vertex to the path leads to a solution.
Step 5.1: If the recursive call returns true, return true and print the path.
Step 5.2: Else, remove the vertex from the path array and mark it as unvisited.
Step 6: If no adjacent vertex leads to a solution, return false.
PROGRAM :
import java.util.*;
public class HamiltonianPath {
private static boolean[] visited;
private static int n;
private static boolean foundPath;
public static boolean isHamiltonianPathPresent(int[][] edges, int vertices) {
n = vertices;
visited = new boolean[n + 1];
foundPath = false;
visited[1] = true;
dfs(1, 1, edges);
visited[1] = false;
return foundPath;
}
private static void dfs(int node, int count, int[][] edges) {
if (count == n) {
foundPath = true;
 return; }
for (int[] edge : edges) {
if (edge[0] == node && !visited[edge[1]]) {
visited[edge[1]] = true;
dfs(edge[1], count + 1, edges);
visited[edge[1]] = false;
}}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the number of vertices: ");
int n = sc.nextInt();
System.out.println("Enter the number of edges: ");
int m = sc.nextInt();
int[][] edges = new int[m][2];
System.out.println("Enter the edges: ");
for (int i = 0; i < m; i++) {
edges[i][0] = sc.nextInt();
edges[i][1] = sc.nextInt();}
if (isHamiltonianPathPresent(edges, n)) {
System.out.println("Hamiltonian Path is Present"); } else {
System.out.println("Hamiltonian Path is Not Present");}}}
OUTPUT :
Enter the number of vertices: Class Performance
4 Record
Enter the number of edges: Viva
3 Total
Enter the edges:
12
23
31
Hamilton Path is present
RESULT :