EX NO : 01

DATE : GCD AND LCM

AIM :
To write a Java program to find the GCD and LCM of two given numbers

ALGORITHM:
Step 1: Start.
Step 2: Declare variables x, y, gcd = 1, and lcm.
Step 3: Read two numbers x and y.
Step 4: Repeat the loop from I = 1 to I ≤ x and I ≤ y.
Step 5: Check if x and y are divisible by i.
Step 6: If both are divisible, store I as gcd.
Step 7: Continue the loop until the condition ends.
Step 8: Print the value of gcd.
Step 9: Calculate lcm = (x × y) / gcd.
Step 10: Print the value of lcm.
Step 11: Stop.

1
PROGRAM:

//[Link]
import [Link];
public class gcd
{
public static void main(String[] args)
{
int x , y , gcd = 1,lcm;
Scanner sc=new Scanner([Link]);
[Link]("Enter X value:");
x=[Link]();
[Link]("Enter Y value:");
y=[Link]();
for(int i = 1; i <= x && i <= y; i++)
{
if(x%i==0 && y%i==0)
gcd = i;
}
[Link]("GCD :"+ gcd);
lcm=(x*y)/gcd;
[Link]("LCM :"+ lcm);
}
}

2
OUTPUT:

RESULT:
Thus the given program is Executed Successfully and Output is verified.

3
EX NO : 02
DATE : FIBONACCI SERIES

AIM:
To write a Java program to generate Fibonacci series using recursion.

ALGORITHM:

Step 1: Start the program.

Step 2: Define a recursive function fiboRecur(n).
Step 3: If n = 0, return 0.
Step 4: If n = 1 or n = 2, return 1.
Step 5: Otherwise return fiboRecur(n-1) + fiboRecur(n-2).
Step 6: In the main method, read the value N.
Step 7: Use a loop from I = 0 to N-1.
Step 8: Call the recursive function and print Fibonacci numbers.
Step 9: Stop the program.

4
PROGRAM:

//[Link]
import [Link];
public class fibo{
public static int fibbo(int n)
{
if(n == 0)
{
return 0;
}
if(n == 1 || n == 2)
{
return 1;
}
return fibbo(n-2) + fibbo(n-1);
}
public static void main(String args[])
{
Scanner s=new Scanner([Link]);
[Link]("Enter Any Number: ");
int n=[Link]();
[Link]("Fibonacci Series: ");
for(int i = 0; i < n; i++)
{
[Link](fibbo(i) +" ");
}
}
}

5
OUTPUT:

RESULT:
Thus the given program is Executed Successfully and Output is verified.

6
EX NO : 03
DATE : SELECTION SORT

AIM:
To write a Java program to sort a set of numbers using Selection Sort.

ALGORITHM:

Step 1: Start the program.

Step 2: Read the number of elements n.
Step 3: Read n elements into an array.
Step 4: Use a loop from I = 0 to n-1.
Step 5: Compare element arr[i] with remaining elements.
Step 6: If a smaller element is found, swap the elements.
Step 7: Repeat the process until the array is sorted.
Step 8: Display the sorted array.
Step 9: Stop the program.

7
PROGRAM:

//[Link]
import [Link];
public class SSort
{
public static void selectionSort(int[] arr,int n){
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
if (arr[i] > arr[j])
{
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
}
}
public static void main(String a[])
{
Scanner sc=new Scanner([Link]);
[Link]("Enter the number of elements you want to store: ");
int n=[Link]();
int[] array = new int[n];
[Link]("Enter the elements of the array: ");
for(int i=0; i<n; i++)
{
array[i]=[Link]();
}
[Link]("Before Selection Sort");

8
for(int i=0; i<n; i++) {
[Link](array[i]+" ");
}
[Link]();
selectionSort(array,n);
[Link]("After Selection Sort");
for(int i=0; i<n; i++)
{
[Link](array[i]+" ");
}
}
}

9
OUTPUT:

RESULT:
Thus the given program is Executed Successfully and Output is verified.

10
EX NO : 04
DATE : BUBBLE SORT

AIM:
To write a Java program to sort a set of numbers using Bubble Sort.

ALGORITHM:

Step 1: Start the program.

Step 2: Read the number of elements n.
Step 3: Read the array elements.
Step 4: Use outer loop from I = 0 to n-1.
Step 5: Use inner loop to compare adjacent elements.
Step 6: If arr[j-1] > arr[j], swap the elements.
Step 7: Continue until all elements are sorted.
Step 8: Display the sorted array.
Step 9: Stop the program.

11
PROGRAM:

//[Link]
import [Link];
public class BSort {
public static void bubbleSort(int[] arr,int n){
for (int i = 0; i < n - 1; i++)
{
for(int j=1; j < (n-i); j++){
if(arr[j-1] > arr[j]){
int temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
}
public static void main(String a[])
{
Scanner sc=new Scanner([Link]);
[Link]("Enter the number of elements you want to store: ");
int n=[Link]();
int[] array = new int[n];
[Link]("Enter the elements of the array: ");
for(int i=0; i<n; i++)
{
array[i]=[Link]();
}
[Link]("Before Bubble Sort");
for(int i=0; i<n; i++) {
[Link](array[i]+" ");
}

12
[Link]();
bubbleSort(array,n);
[Link]("After Bubble Sort");
for(int i=0; i<n; i++) {
[Link](array[i]+" ");
}
}
}

13
OUTPUT:

RESULT:
Thus the given program is Executed Successfully and Output is verified.

14
EX NO : 05
DATE : LINEAR SEARCH

AIM:
To write a Java program to search an element using Linear Search.

ALGORITHM:

Step 1: Start the program.

Step 2: Read the number of elements n.
Step 3: Read array elements.
Step 4: Read the element to be searched key.
Step 5: Compare key with each element in the array.
Step 6: If element matches, return its position.
Step 7: If the loop ends without finding the element, return -1.
Step 8: Display the result.
Step 9: Stop the program.

15
PROGRAM:

//[Link]
import [Link];
public class LinearSearch
{
public static int linearSearch(int[] arr, int key,int n)
{
for(int i=0;i<n;i++)
{
if(arr[i] == key)
{
return i;
}
}
return -1;
}
public static void main(String a[])
{
int n;
Scanner sc=new Scanner([Link]);
[Link]("Enter the number of elements you want to store: ");
n=[Link]();
int[] array = new int[n];
[Link]("Enter the elements of the array: ");
for(int i=0; i<n; i++)
{
array[i]=[Link]();
}
[Link]("Enter the element to search: ");
int key =[Link]();
int index= linearSearch(array, key,n);

16
if (index>=0)
[Link](key+" is found at location: "+(index+1));
else
[Link](key+" is not found ");
}
}

17
OUTPUT:

RESULT:
Thus the given program is Executed Successfully and Output is verified.

18
EX NO : 06
DATE : BINARY SEARCH

AIM:
To write a Java program to search an element using Binary Search.

ALGORITHM:

Step 1: Start the program.

Step 2: Read the number of elements n.
Step 3: Read sorted array elements.
Step 4: Read the element to search key.
Step 5: Set first = 0 and last = n-1.
Step 6: Find mid = (first + last) / 2.
Step 7: If arr[mid] = key, element is found.
Step 8: If arr[mid] < key, search in right half.
Step 9: If arr[mid] > key, search in left half.
Step 10: Repeat until element is found or search ends.
Step 11: Stop the program.

19
PROGRAM:

//[Link]
import [Link];
class BinarySearch
{
public static void binarySearch(int arr[], int first, int last, int key)
{
int mid = (first + last)/2;
while( first <= last )
{
if ( arr[mid] < key )
{
first = mid + 1;
}
else if ( arr[mid] == key )
{
[Link]("Element is found at location: " + (mid+1));
break;
}
else
{
last = mid - 1;
}
mid = (first + last)/2;
}
if ( first > last )
{
[Link]("Element is not found!");
}
}
public static void main(String args[]){

20
Scanner sc=new Scanner([Link]);
[Link]("Enter the number of elements you want to store: ");
int n=[Link]();
int[] array = new int[n];
[Link]("Enter the elements of the array: ");
for(int i=0; i<n; i++)
{
array[i]=[Link]();
}
[Link]("Enter the element to search: ");
int key =[Link]();
binarySearch(array,0,n-1,key);
}
}

21
OUTPUT:

RESULT:
Thus the given program is Executed Successfully and Output is verified.

22
EX NO : 07
DATE : STACK OPERATIONS USING ARRAY

AIM:
To write a Java program to perform stack operations using arrays.

ALGORITHM:

Step 1: Start the program.

Step 2: Declare stack array and initialize top = -1.
Step 3: Display menu (Push, Pop, Display, Exit).
Step 4: Read the user choice.
Step 5: If choice is Push, insert element into stack.
Step 6: If choice is Pop, remove top element from stack.
Step 7: If choice is Display, print stack elements.
Step 8: Repeat until Exit is selected.
Step 9: Stop the program.

23
PROGRAM:

//[Link]
import [Link];
public class stackoper
{
int max=5;
int s[]=new int[max];
int top=-1;
void push(int ele)
{
if(top>=max-1)
[Link]("stack overflow");
else
s[++top]=ele;
}
int pop()
{
int z=0;
if(top==-1)
[Link]("stack underflow");
else
z=s[top--];
return z;
}
void display()
{
if(top==-1)
[Link]("stack empty");
else
{
for(int i=top;i>-1;i--)

24
[Link](s[i]+" ");
}}
public static void main(String args[])
{
int q=1;
stackoper m = new stackoper();
[Link]("program to perform stack operations");
Scanner sc=new Scanner([Link]);
while(q!=0)
{
[Link]("1. Push [Link] 3. Display [Link]");
[Link]("Enter your choice");
int ch=[Link]();
switch(ch)
{
case 1:
[Link]("enter the element to be pushed");
int ele=[Link]();
[Link](ele);
break;
case 2:
int popele;
popele=[Link]();
[Link]("the poped element is");
[Link](popele+" ");
break;
case 3:
[Link]("elements in the stack are");
[Link]();
break;
case 4:
q=0; } }}}

25
OUTPUT:

RESULT:
Thus the given program is Executed Successfully and Output is verified.

26
EX NO : 08
DATE : BINOMIAL COEFFICIENT

AIM:
To write a Java program to find Binomial Coefficient using recursion.

ALGORITHM:

Step 1: Start the program.

Step 2: Read values n and k.
Step 3: If k > n, return 0.
Step 4: If k = 0 or k = n, return 1.
Step 5: Otherwise return C(n-1, k-1) + C(n-1, k).
Step 6: Print the binomial coefficient values.
Step 7: Stop the program.

27
PROGRAM:

//[Link]
import [Link];
class BCE {
static int binomialCoeff(int n, int k)
{
if (k > n)
return 0;
if (k == 0 || k == n)
return 1;
return binomialCoeff(n - 1, k - 1)
+ binomialCoeff(n - 1, k);
}
public static void main(String[] args)
{
int n,k ;
Scanner sc=new Scanner([Link]);
[Link]("Enter n value ");
n=[Link]();
[Link]("Enter k value ");
k=[Link]();
[Link]("BinomialCoeff of C(%d, %d) is\n",n,k);
for(int i = 0; i <= n; i++)
{
for (int j=0; j<=i && j<=k;j++)
[Link](binomialCoeff(i, j)+” “);
[Link]();
}
}
}

28
OUTPUT:

RESULT:
Thus the given program is Executed Successfully and Output is verified.

29
EX NO : 09
DATE : WARSHALL ALGORITHM

AIM:
To write a Java program to find transitive closure of a graph using Warshall’s algorithm.

ALGORITHM:

Step 1: Start the program.

Step 2: Read number of nodes n.
Step 3: Read adjacency matrix of graph.
Step 4: Use three nested loops for k, I, and j.
Step 5: If path exists from I to k and k to j, set p[i][j] = 1.
Step 6: Repeat until all nodes are checked.
Step 7: Display the transitive closure matrix.
Step 8: Stop the program.

30
PROGRAM:

//[Link]
import [Link];
class Warshall
{
public static void Trans_Clos(int p[][],int n)
{
int i,j,k;
for(k=1;k<=n;k++)
{
for(j=1;j<=n;j++)
{
for(i=1;i<=n;i++)
{
if((p[i][j]==0) && (p[i][k]==1) && (p[k][j]==1))
{ p[i][j]=1;}
}
}
}
}
public static void main(String args[])
{
int i,j,n;
Scanner sc=new Scanner([Link]);
[Link]("Enter the number of nodes: ");
n=[Link]();
int[][] array = new int[10][10];
[Link]("Enter the adjacency matrix: ");
for(i=1; i<=n; i++)
{
for(j=1;j<=n;j++)

31
{
array[i][j]=[Link]();
}
}
Trans_Clos(array,n);
[Link]("Transitive Closure : ");
for(i=1; i<=n; i++)
{
for(j=1;j<=n;j++)
{
[Link](" %d \t",array[i][j]);
}
[Link]("\n");
}
}
}

32
OUTPUT:

RESULT:
Thus the given program is Executed Successfully and Output is verified.

33
EX NO : 10
DATE : FLOYD’S ALGORITHM

AIM:
To find the shortest path between all pairs of vertices in a weighted graph using Floyd’s Algorithm.

ALGORITHM:

Step 1: Start the program.

Step 2: Read the number of vertices n.
Step 3: Read the adjacency (cost) matrix of the graph.
Step 4: Initialize the distance matrix with the given cost matrix.
Step 5: Set k = 1.
Step 6: For i = 1 to n and j = 1 to n, check if dist[i][k] + dist[k][j] < dist[i][j].
Step 7: If the condition is true, update dist[i][j] = dist[i][k] + dist[k][j].
Step 8: Increment k and repeat the process until k ≤ n.
Step 9: Display the shortest distance matrix.
Step 10: Stop the program.

34
PROGRAM:

//[Link]
import [Link];
public class Floyds {
static final int INF = 9999;
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
[Link]("Enter number of vertices: ");
int n = [Link]();
int graph[][] = new int[n][n];
[Link]("Enter the adjacency matrix:");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = [Link]();
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][k] + graph[k][j] < graph[i][j]) {
graph[i][j] = graph[i][k] + graph[k][j];
}}}}
[Link]("Shortest Distance Matrix:");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
[Link](graph[i][j] + " ");
}
[Link]();
}
}
}

35
OUTPUT:

RESULT:
Thus the given program is Executed Successfully and Output is verified.

36
EX NO : 11
DATE : KNAPSACK PROBLRM

AIM:
To write a Java program to solve Knapsack problem using Dynamic Programming.

ALGORITHM:

Step 1: Start the program.

Step 2: Read number of items n.
Step 3: Read weights and values of items.
Step 4: Read maximum capacity W.
Step 5: Create table K[n+1][W+1].
Step 6: If I = 0 or w = 0, set value 0.
Step 7: If weight of item ≤ capacity, take maximum of including or excluding item.
Step 8: Otherwise copy value from previous row.
Step 9: Repeat until table is filled.
Step 10: Display maximum profit.
Step 11: Stop the program.

37
PROGRAM:

//[Link]
import [Link];
public class knapsack
{
static int max(int a, int b)
{
return (a > b)? a : b;
}
static int knapSack(int W, int wt[], int val[], int n)
{
int i, w;
int [][]K = new int[n+1][W+1];
int []item = new int[n];
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i==0 || w==0)
K[i][w] = 0;
else if (wt[i-1] <= w)
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
else
K[i][w] = K[i-1][w];
}
}
[Link]("KnapSack Problem Dynamic Programming ");
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{

38
[Link](" %d \t",K[i][w]);}
[Link]("\n");}
return K[n][W];
}
public static void main(String args[])
{
Scanner sc = new Scanner([Link]);
[Link]("Enter the number of items: ");
int n = [Link]();
[Link]("Enter the items weights: ");
int []wt = new int[n];
for(int i=0; i<n; i++)
wt[i] = [Link]();
[Link]("Enter the items values: ");
int []val = new int[n];
for(int i=0; i<n; i++)
val[i] = [Link]();
[Link]("Enter the maximum capacity: ");
int W = [Link]();
[Link]("The max value in knapsack is: " + knapSack(W, wt, val, n));
}
}

39
OUTPUT:

RESULT:
Thus the given program is Executed Successfully and Output is verified.

40
EX NO : 12
DATE : PRIM’S ALGORITHM

AIM:
To write a Java program to find Minimum Spanning Tree using Prim’s algorithm.

ALGORITHM:

Step 1: Start the program.

Step 2: Read number of vertices n.
Step 3: Read weighted adjacency matrix.
Step 4: Choose source vertex.
Step 5: Mark source vertex as visited.
Step 6: Find minimum weight edge connecting visited and unvisited vertex.
Step 7: Add edge to spanning tree.
Step 8: Mark new vertex as visited.
Step 9: Repeat until n-1 edges are selected.
Step 10: Display the edges and total cost.
Step 11: Stop the program.

41
PROGRAM:

//[Link]
import [Link];
public class prim
{
public static void main(String[] args)
{
int w[][]=new int[10][10];
int n,i,j,s,k=0;
int min;
int sum=0;
int u=0,v=0;
int flag=0;
int sol[]=new int[10];
[Link]("Enter the number of vertices");
Scanner sc=new Scanner([Link]);
n=[Link]();
for(i=1;i<=n;i++)
sol[i]=0;
[Link]("Enter the weighted graph");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
w[i][j]=[Link]();
[Link]("Enter the source vertex");
s=[Link]();
sol[s]=1;
k=1;
while (k<=n-1)
{
min=99;
for(i=1;i<=n;i++)

42
for(j=1;j<=n;j++)
if(sol[i]==1&&sol[j]==0)
if(i!=j&&min>w[i][j])
{
min=w[i][j];
u=i;
v=j;
}
sol[v]=1;
sum=sum+min;
k++;
[Link](u+"->"+v+"="+min);
}
for(i=1;i<=n;i++)
if(sol[i]==0)
flag=1;
if(flag==1)
[Link]("No spanning tree");
else
[Link]("The cost of minimum spanning tree is"+sum);
}
}

43
OUTPUT:

RESULT:
Thus the given program is Executed Successfully and Output is verified.

44
EX NO : 13
DATE : KRUSKAL’S ALGORITHM

AIM:
To write a Java program to find the Minimum Cost Spanning Tree of a connected undirected graph
using Kruskal’s algorithm.

ALGORITHM:

Step 1: Start the program.

Step 2: Read the number of vertices n.
Step 3: Read the weighted adjacency matrix of the graph.
Step 4: Initialize parent array for union-find operation.
Step 5: Find the minimum edge in the graph.
Step 6: Check whether the selected edge forms a cycle using find() function.
Step 7: If it does not form a cycle, include the edge in the spanning tree.
Step 8: Perform union of the vertices.
Step 9: Repeat until n-1 edges are selected.
Step 10: Display the edges and total cost of the Minimum Spanning Tree.
Step 11: Stop the program

45
PROGRAM:

//[Link]
import [Link];
public class Kruskal
{
int parent[]=new int[10];
int find(int m)
{
int p=m;
while(parent[p]!=0)
p=parent[p];
return p;
}
void union(int i,int j)
{
if(i<j)
parent[i]=j;
else
parent[j]=i;
}
void krkl(int[][]a, int n)
{
int u=0,v=0,min,k=0,i,j,sum=0;
while(k<n-1)
{
min=99;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(a[i][j]<min&&i!=j)
{
min=a[i][j];

46
u=i;
v=j;
}
i=find(u);
j=find(v);
if(i!=j)
{
union(i,j);
[Link]("("+u+","+v+")"+"="+a[u][v]);
sum=sum+a[u][v];
k++;
}
a[u][v]=a[v][u]=99;
}
[Link]("The cost of minimum spanning tree = "+sum);
}
public static void main(String[] args)
{
int a[][]=new int[10][10];
int i,j;
[Link]("Enter the number of vertices of the graph");
Scanner sc=new Scanner([Link]);
int n;
n=[Link]();
[Link]("Enter the wieghted matrix");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=[Link]();
Kruskal k=new Kruskal();
[Link](a,n);
}
}.

47
OUTPUT:

RESULT:
Thus the given program is Executed Successfully and Output is verified.

48
EX NO : 14
DATE : TOPOLOGICAL ORDERING

AIM:
To write a Java program to obtain the topological ordering of vertices in a given directed graph.

ALGORITHM:

Step 1: Start the program.

Step 2: Read the number of nodes n.
Step 3: Read the adjacency matrix of the graph.
Step 4: Compute the indegree of each vertex.
Step 5: Push all vertices with indegree 0 into a stack.
Step 6: Remove a vertex from the stack and add it to the result list.
Step 7: Reduce the indegree of adjacent vertices.
Step 8: If indegree becomes 0, push it into the stack.
Step 9: Repeat until the stack becomes empty.
Step 10: Display the topological order.
Step 11: Stop the program.

49
PROGRAM:

//[Link]
import [Link];
class Tsort
{
public static void findindegree(int a[][],int indegree[],int n)
{
int i,j,sum;
for(j=1;j<=n;j++)
{
sum=0;
for(i=1;i<=n;i++)
{
sum=sum+a[i][j];
}
indegree[j]=sum;
}
}
public static void topological(int p[][],int n)
{
int[] t = new int[10];
int[] indegree = new int[10];
int[] s = new int[10];
int k,top,i,u,v;
k=1;
top=-1;
findindegree(p,indegree,n);
for(i=1;i<=n;i++)
{
if(indegree[i]==0)
{

50
s[++top]=i;
}}
while(top!=-1)
{
u=s[top--];
t[k++]=u;
for(v=1;v<=n;v++)
{
if(p[u][v]==1)
{
indegree[v]--;
if(indegree[v]==0)
{
s[++top]=v;
}}}}
[Link]("Topological sequence is");
for(i=1;i<=n;i++)
[Link]("%d \t",t[i]);
}
public static void main(String args[])
{
int[][] array = new int[10][10];
int i,j,n;
Scanner sc=new Scanner([Link]);
[Link]("Enter the number of nodes: ");
n=[Link]();
[Link]("Enter the adjacency matrix: ");
for(i=1; i<=n; i++)
{
for(j=1;j<=n;j++)
{
array[i][j]=[Link]();

51
}
}
[Link]("\nThe adjacency matirx is:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
[Link]("%d \t",array[i][j]);
}
[Link]("\n");
}
topological(array,n);
}
}

52
OUTPUT:

RESULT:
Thus the given program is Executed Successfully and Output is verified.

53
EX NO : 15
DATE : BREADTH FIRST SEARCH

AIM:
To write a Java program to print all nodes reachable from a given starting node using BFS.

ALGORITHM:

Step 1: Start the program.

Step 2: Read the number of nodes n.
Step 3: Read the adjacency matrix of the graph.
Step 4: Initialize the visited array.
Step 5: Read the source node.
Step 6: Insert the source node into the queue.
Step 7: Remove a node from the queue.
Step 8: Visit all adjacent unvisited nodes and insert them into the queue.
Step 9: Mark them as visited.
Step 10: Repeat until the queue becomes empty.
Step 11: Display reachable nodes.
Step 12: Stop the program.

54
PROGRAM:

//[Link]
import [Link];
class bfs
{
public static void BFS(int a[][],int source,int visited[],int n)
{
int[] queue = new int[10];
int f,r,u,v;
f=0;
r=-1;
queue[++r]=source;
while(f<=r)
{
u=queue[f++];
for(v=1;v<=n;v++)
{
if(a[u][v]==1 && visited[v]==0)
{
queue[++r]=v;
visited[v]=1;
}}
}}
public static void main(String args[])
{
int[][] array = new int[10][10];
int n,i,j,source;
int[] visited = new int[10];
Scanner sc=new Scanner([Link]);
[Link]("Enter the number of nodes: ");
n=[Link]();

55
[Link]("Enter the adjacency matrix: ");
for(i=1; i<=n; i++)
{
for(j=1;j<=n;j++)
{
array[i][j]=[Link]();
}
}
for(i=1;i<=n;i++)
visited[i]=0;
[Link]("Enter source node: ");
source=[Link]();
visited[source]=1;
[Link]("\nThe adjacency matirx is:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
[Link]("%d \t",array[i][j]);
}
[Link]("\n");
}
BFS(array,source,visited,n);
for(i=1;i<=n;i++)
{
if(visited[i]!=0)
[Link]("Node %d is reachable \n ",i);
else
[Link]("Node %d is not reachable \n ",i);
}
}
}

56
OUTPUT:

RESULT:
Thus the given program is Executed Successfully and Output is verified.

57
EX NO : 16
DATE : DEPTH FIRST SEARCH

AIM:
To write a Java program to check whether a given graph is connected using DFS.

ALGORITHM:

Step 1: Start the program.

Step 2: Read the number of nodes n.
Step 3: Read the adjacency matrix.
Step 4: Initialize visited array.
Step 5: Read the source node.
Step 6: Mark the source node as visited.
Step 7: For every adjacent node, if not visited, call DFS recursively.
Step 8: Continue until all reachable nodes are visited.
Step 9: Check if any node remains unvisited.
Step 10: If yes, graph is not connected; otherwise graph is connected.
Step 11: Stop the program.

58
PROGRAM:

//[Link]
import [Link];
class dfs
{
public static void DFS(int a[][],int source,int visited[],int n)
{
int v; visited[source]=1;
for(v=1;v<=n;v++)
{
if(a[source][v]==1 && visited[v]==0)
DFS(a,v,visited,n);
}
}
public static void main(String args[])
{
int[][] array = new int[10][10];
int n,i,j,source,f=0;
int[] visited = new int[10];
Scanner sc=new Scanner([Link]);
[Link]("Enter the number of nodes: ");
n=[Link]();
[Link]("Enter the adjacency matrix: ");
for(i=1; i<=n; i++)
{
for(j=1;j<=n;j++)
{
array[i][j]=[Link]();
}
}
for(i=1;i<=n;i++)

59
visited[i]=0;
[Link]("Enter source node: ");
source=[Link]();
visited[source]=1;
[Link]("\nThe adjacency matirx is:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
[Link]("%d \t",array[i][j]);
}
[Link]("\n");
}
DFS(array,source,visited,n);
for(i=1;i<=n;i++)
{
if(visited[i]==0)
{
[Link]("Graph is not connected \n ");
f=1;
break;
}
}
if (f==0)
[Link]("Graph is connected \n ");
}
}

60
OUTPUT:

RESULT:
Thus the given program is Executed Successfully and Output is verified.

61
EX NO : 17
DATE : QUICK SORT

AIM:
To write a Java program to sort a set of integers using Quick Sort and compute time complexity.

ALGORITHM:

Step 1: Start the program.

Step 2: Read the number of elements n.
Step 3: Generate random elements.
Step 4: Choose the first element as pivot.
Step 5: Partition the array into two parts based on pivot.
Step 6: Recursively apply quick sort to left and right subarrays.
Step 7: Repeat until the array is sorted.
Step 8: Display sorted elements.
Step 9: Display the time taken for sorting.
Step 10: Stop the program.

62
PROGRAM:

//[Link]
import [Link];
import [Link];
public class Qsort
{
public static void main(String[] args)
{
int a[]= new int[100000];
Scanner in = new Scanner([Link]);
long start, end;
[Link]("QUICK SORT PROGRAM");
[Link]("Enter the number of elements to be sorted");
int n = [Link]();
Random rand= new Random();
for(int i=0;i<n;i++)
a[i]=[Link](100);
[Link]("Array elements to be sorted are");
for(int i=0; i<n; i++)
[Link](a[i]+" ");
a[n]=999;
start=[Link]();
quicksort(a,0,n-1);
end=[Link]();
[Link]("\nThe sorted elements are");
for(int i=0; i<n; i++)
[Link](a[i]+" ");
[Link]("\nThe time taken to sort is "+(end-start)+"ns");
}
static void quicksort(int a[],int p, int q)
{

63
int j;
if(p < q)
{
j=partition(a,p,q);
quicksort(a,p,j-1);
quicksort(a,j+1,q);
}}
static int partition(int a[],int m, int p)
{
int v, i, j;
v=a[m];
i=m;
j=p;
while(i <= j)
{
while(a[i] <= v)
i++;
while(a[j] > v)
j--;
if(i < j)
interchange(a,i,j);
}
a[m] = a[j];
a[j] = v;
return j;
}
static void interchange(int a[], int i, int j) {
int p;
p = a[i];
a[i] = a[j];
a[j] = p;
}}

64
OUTPUT:

RESULT:
Thus the given program is Executed Successfully and Output is verified.

65
EX NO : 18
DATE : MERGE SORT

AIM:
To write a Java program to sort a set of integers using Merge Sort and compute time complexity.

ALGORITHM:

Step 1: Start the program.

Step 2: Read the number of elements n.
Step 3: Generate random elements.
Step 4: Divide the array into two halves.
Step 5: Recursively sort the left half.
Step 6: Recursively sort the right half.
Step 7: Merge the two sorted halves.
Step 8: Repeat until the whole array is sorted.
Step 9: Display sorted elements and time taken.
Step 10: Stop the program.

66
PROGRAM:

//[Link]
import [Link];
import [Link];
public class Msort
{
public static void main(String[] args)
{
int a[]= new int[100000];
Scanner in = new Scanner([Link]);
long start, end;
[Link]("MERGE SORT PROGRAM");
[Link]("Enter the number of elements to be sorted");
int n = [Link]();
Random rand= new Random();
for(int i=0;i<n;i++)
a[i]=[Link](100);
[Link]("Array elements to be sorted are");
for(int i=0; i<n; i++)
[Link](a[i]+" ");
start=[Link]();
mergesort(a,0,n-1);
end=[Link]();
[Link]("\nThe sorted elements are");
for(int i=0; i<n; i++)
[Link](a[i]+" ");
[Link]("\nThe time taken to sort is "+(end-start)+"ns");
}
static void mergesort(int a[], int low, int high)
{
int mid;
if(low < high)
67
{
mid = (low+high)/2;
mergesort(a, low, mid);
mergesort(a, mid+1, high);
merge(a, low, mid, high);
}}
static void merge(int a[], int low, int mid, int high)
{
int i, j, h, k, b[]= new int[100000];
h=low; i=low; j=mid+1;
while((h<=mid) && (j<=high))
{
if(a[h] < a[j])
{
b[i]=a[h];
h=h+1;
}
else
{
b[i] = a[j];
j=j+1;
}
i = i+1;
}
if(h > mid)
{
for(k=j; k<=high; k++)
{
b[i]=a[k];
i= i+1;
}
}

68
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i= i+1;
}}
for(k=low; k<= high; k++)
a[k] = b[k];
}
}

69
OUTPUT:

RESULT:
Thus the given program is Executed Successfully and Output is verified.

70
EX NO : 19
DATE : SUBSET SUM PROBLEM

AIM:
To write a Java program to find a subset of a given set whose sum equals a given value.

ALGORITHM:

Step 1: Start the program.

Step 2: Read number of elements n.
Step 3: Read the elements of the set.
Step 4: Read the target sum d.
Step 5: Generate all possible subsets using binary representation.
Step 6: Calculate the sum of elements in each subset.
Step 7: Compare subset sum with target sum d.
Step 8: If equal, display the subset.
Step 9: If no subset is found, display solution does not exist.
Step 10: Stop the program.

71
PROGRAM:

//[Link]
import [Link];
import static [Link];
public class subset
{
void subset(int num,int n, int x[])
{
int i;
for(i=1;i<=n;i++)
x[i]=0;
for(i=n;num!=0;i--)
{
x[i]=num%2;
num=num/2;
}}
public static void main(String[] args)
{
int a[]=new int[10];
int x[]=new int[10];
int n,d,sum,present=0;
int j;
[Link]("enter the number of elements of set");
Scanner sc=new Scanner([Link]);
n=[Link]();
[Link]("enter the elements of set");
for(int i=1;i<=n;i++)
a[i]=[Link]();
[Link]("enter the positive integer sum");
d=[Link]();
if(d>0)
{
72
for(int i=1;i<=[Link](2,n)-1;i++)
{
subset s=new subset();
[Link](i,n,x);
sum=0;
for(j=1;j<=n;j++)
if(x[j]==1)
sum=sum+a[j];
if(d==sum)
{
[Link]("Subset={ ");
present=1;
for(j=1;j<=n;j++)
if(x[j]==1)
[Link](a[j]+" ");
[Link]("}="+d);
[Link]();
}
}
}
if(present==0)
[Link]("Solution does not exists");
}
}

73
OUTPUT:

RESULT:
Thus the given program is Executed Successfully and Output is verified.

74
EX NO : 20
DATE : TRAVELLING SALESMAN PROBLEM

AIM:
To write a Java program to find the minimum cost path for travelling through all cities.

ALGORITHM:

Step 1: Start the program.

Step 2: Read the number of cities n.
Step 3: Read the cost matrix.
Step 4: Initialize the tour array.
Step 5: Use recursion to generate possible tours.
Step 6: Compute cost for each tour.
Step 7: Select the minimum cost tour.
Step 8: Display optimal tour path.
Step 9: Display minimum cost.
Step 10: Stop the program.

75
PROGRAM:

//[Link]
import [Link];
public class TSP
{
public static void main(String[] args)
{
Scanner in = new Scanner([Link]);
int c[][]=new int[10][10], tour[]=new int[10];
int i, j,cost;
[Link]("Enter No. of Cities: ");
int n = [Link]();
if(n==1)
{
[Link]("Path is not possible");
[Link](0);
}
[Link]("Enter the Cost Matrix");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
c[i][j] = [Link]();
for(i=1;i<=n;i++)
tour[i]=i;
cost = tspdp(c, tour, 1, n);
[Link]("\tThe Optimal Tour is = ");
for(i=1;i<=n;i++)
[Link](tour[i]+"->");
[Link]("1");
[Link]("\tMinimum Cost = "+cost);
}
static int tspdp(int c[][], int tour[], int start, int n)
{
76
int mintour[]=new int[10], temp[]=new int[10], mincost=999,ccost, i, j, k;
if(start == n-1)
{
return (c[tour[n-1]][tour[n]] + c[tour[n]][1]);
}
for(i=start+1; i<=n; i++)
{
for(j=1; j<=n; j++)
temp[j] = tour[j];
temp[start+1] = tour[i];
temp[i] = tour[start+1];
if((c[tour[start]][tour[i]]+(ccost=tspdp(c,temp,start+1,n)))<mincost)
{
mincost = c[tour[start]][tour[i]] + ccost;
for(k=1; k<=n; k++)
mintour[k] = temp[k];
}
}
for(i=1; i<=n; i++)
tour[i] = mintour[i];
return mincost;
}
}

77
OUTPUT:

RESULT:
Thus the given program is Executed Successfully and Output is verified.

78
EX NO : 01
DATE : HAMILTONIAN CYCLE

AIM:
To write a Java program to find all Hamiltonian cycles in a connected undirected graph.

ALGORITHM:

Step 1: Start the program.

Step 2: Read number of vertices n.
Step 3: Read number of edges.
Step 4: Create adjacency matrix of graph.
Step 5: Initialize path array.
Step 6: Fix the first vertex.
Step 7: Use backtracking to assign next vertices.
Step 8: Check whether vertex is valid and not repeated.
Step 9: If all vertices are included and last vertex connects to first, print cycle.
Step 10: Continue searching for other cycles.
Step 11: Stop the program.

79
PROGRAM:

//[Link]
import [Link];
public class Hcycle
{
static int x[] = new int[10];
public static void main(String[] args)
{
Scanner sc = new Scanner([Link]);
int i,j,x1, x2, edges, n;
int g[][] = new int[10][10];
[Link]("Enter No. of Vertices: ");
n = [Link]();
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
g[i][j] = 0;
x[i]=0;
}}
[Link]("Enter No. of Edges: ");
edges = [Link]();
for(i=1;i<=edges;i++)
{
[Link]("Enter the Edge"+i+": ");
x1 = [Link]();
x2 = [Link]();
g[x1][x2] = 1;
g[x2][x1] = 1;
}
x[1] = 1;

80
[Link]("\nHamiltonian Cycle");
hcycle(g,n,2);
}
public static void nextvalue(int g[][],int n,int k)
{
int j;
while(true)
{
x[k] = (x[k] + 1) % (n+1);
if(x[k] == 0)
return;
if(g[x[k-1]][x[k]] == 1)
{
for(j=1;j<=k-1;j++)
{
if(x[j] == x[k] )
break;
}
if(j == k)
{
if((k<n) || ((k==n) && (g[x[n]][x[1]] == 1)))
return;
}}}}
public static void hcycle(int g[][],int n, int k)
{
int i;
while(true)
{
nextvalue(g,n,k);
if(x[k]== 0)
return;
if(k==n)

81
{
for(i=1;i<=n;i++)
[Link](x[i]+"-->");
[Link](x[1]+"\n");
}
else
hcycle(g,n,k+1);
}
}
}

82
OUTPUT:

RESULT:
Thus the given program is Executed Successfully and Output is verified.

83