Scribd
Upload
61 views49 pages

Java Programs for Basic Algorithms

Uploaded by

A0554
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
61 views49 pages

Java Programs for Basic Algorithms

Uploaded by

A0554
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

1.

Program to implement Fibonacci series

import [Link].*;
class FibonacciExample1{
public static void main(String args[])
{
int n1=0,n2=1,n3,i,count=10;

for(i=0;i<count;++i)//loop starts from 2 because 0 and 1 are already


printed
{ [Link](n1+" ");
n3=n1+n2;

n1=n2;
n2=n3;
}

}}

OUTPUT:
[Link] to check whether a number is palindrome or not

import [Link].*;

import [Link].*;
class Palindrome{
public static void main(String args[]){
int n;
int rev=0;int rem;
Scanner sc=new Scanner([Link]);
n=[Link]();
int num=n;
while(n>0){
rem=n%10;
rev=rev*10+rem;
n=n/10;
}
if(rev==num){[Link]("Palindrome");}
else{
[Link]("Non Palindrome");
}
}
}

OUTPUT:
[Link] to print prime series

import [Link].*;
import [Link].*;
class Prime{
public static void main(String[] args){
int n;int count;
Scanner sc= new Scanner([Link]);
n=[Link]();
[Link](n);
for(int i=2;i<n;i++){
count=0;
for(int j=1;j<=i;j++){
if(i%j==0) count++;
}
if(count==2){ [Link](i+" ");}
}
}
}

OUTPUT:
[Link] to print pascal triangle:

public class Pascal


{
public static void main(String[] args)
{
int row=5, i, j, space, num;
for(i=0; i<row; i++)
{
for(space=row; space>i; space--)
{
[Link](" ");
}
num=1;
for(j=0; j<=i; j++)
{
[Link](num+ " ");
num = num*(i-j)/(j+1);
}
[Link]("\n");
}
}
}

OUTPUT:
[Link] to implement abstraction
import [Link].*;
abstract class Car{
abstract void accelerate();
}
//concrete class
class Suzuki extends Car{
void accelerate(){
[Link]("Suzuki::accelerate");

}
}
class abstraction{
public static void main(String args[]){
Car obj = new Suzuki(); //Car object =>contents of Suzuki
[Link](); //call the method
}
}

OUTPUT:
[Link] USING INTERFACE

import [Link].*;
interface Car{
void accelerate();
}
//concrete class
class Suzuki implements Car{
public void accelerate(){
[Link]("Suzuki::accelerate");

}
}
class abst{
public static void main(String args[]){
Suzuki obj = new Suzuki(); //Car object =>contents of
Suzuki
[Link](); //call the method
}
}

OUTPUT:
[Link] to implement inheritance

import [Link].*;
class Animal{
void eat(){[Link]("eating...");}
}
class cheetah extends Animal{
void run(){[Link]("running...");}
}
class inh{
public static void main(String args[]){
cheetah d=new cheetah();
[Link]();
[Link]();
}}

OUTPUT:
[Link] to implement method Polymorphism
a)Overloading:

class help{
static int multiply(int a,int b){
return a*b;
}
static double multiply(double a,double b){
return a*b;
}
static int multiply(int a,int b,int c){
return a*b*c;
}
}

class polymorphism{
public static void main(String[] args){
[Link]([Link](2,4));
[Link]([Link](5.5,6.6));
[Link]([Link](5,4,6));
}
}

OUTPUT:
b)overriding

class Parent{
void Print(){
[Link]("Parent");
}
}

class subclass1 extends Parent{

void Print(){
[Link]("subclass1");
}

class subclass2 extends Parent{

void Print(){
[Link]("subclass2");
}

public class overriding{


public static void main(String[] args){
Parent a;
a=new subclass1();
[Link]();
a=new subclass2();
[Link]();
}
}
OUTPUT:
[Link] to implement Encapsulation

class Person {
private String name;
private int age;

public String getName() { return name; }

public void setName(String name) { [Link] = name; }

public int getAge() { return age; }

public void setAge(int age) { [Link] = age; }


}

public class Encap {


public static void main(String[] args)
{
Person person = new Person();
[Link]("John");
[Link](30);

[Link]("Name: " + [Link]());


[Link]("Age: " + [Link]());
}
}

OUTPUT:
[Link] to implement static keyword

import [Link].*;

public class GFG {


static int a = 40;
int b = 50;

void simpleDisplay()
{ a=a+10;
[Link](a);
[Link](b);
}
static void staticDisplay()
{
[Link](a);
}
public static void main(String[] args)
{
GFG obj = new GFG();
[Link]();
staticDisplay();
}
}

OUTPUT:
[Link] to implement final keyword

class Bike{
final void run(){[Link]("running");}
}

class Honda extends Bike{


void run(){[Link]("running safely with 100kmph");}

public static void main(String args[]){


Honda honda= new Honda();
[Link]();
}
}

OUTPUT:
[Link] to implement abstract keyword

abstract class fg {
abstract void printInfo();
}

class employee extends fg {


void printInfo() {
String name = "aakanksha";
int age = 21;
float salary = 55552.2F;

[Link](name);
[Link](age);
[Link](salary);

class base {
public static void main(String args[]) {
fg s = new employee();
[Link]();
}
}

OUTPUT:
13. Write a program to implement Multi threading

class MultithreadingDemo extends Thread {


public void run()
{
try {
// Displaying the thread that is running
[Link](
"Thread " + [Link]().getId()
+ " is running");
}
catch (Exception e) {
// Throwing an exception
[Link]("Exception is caught");
}
}
}

// Main Class
public class Multithread {
public static void main(String[] args)
{
int n = 8; // Number of threads
for (int i = 0; i < n; i++) {
MultithreadingDemo object
= new MultithreadingDemo();
[Link]();
}
}
}
Output:
14. Write a program to implement String Reverse.

import [Link].*;
import [Link];

class StringReverse {
public static void main (String[] args) {

String str, nstr="";


char ch;
Scanner sc = new Scanner([Link]);
str = [Link]();

for (int i=0; i<[Link](); i++)


{
ch= [Link](i); //extracts each character
nstr= ch+nstr; //adds each character in front of the existing string
}
[Link]("Reversed word: "+ nstr);
}
}
OUTPUT:
[Link] a program to implement Binary Search:

import [Link].*;
class BinarySearch{

static void merge(int[] a , int l, int m, int h)


{
int i = l, j = m+1;
int k = 0;
int[] c = new int[10] ;
while(i<=m && j<= h)
{
if(a[i]>a[j])
{
c[k] = a[j];
k++;
j++;
}
else{
c[k] = a[i];
k++;
i++;
}
}
while(i<=m){
c[k] = a[i];
k++;
i++;

}
while(j<=h){
c[k] = a[j];
k++;
j++;

}
k = 0;
for(i = l; i<=h;i++)
{ a[i] = c[k]; k++;}
}
static void Merge_Sort(int[] a,int l, int h){
int mid = (l+h)/2;
if(l<h){
Merge_Sort(a,l,mid);
Merge_Sort(a,mid+1,h);
merge(a,l,mid ,h);
}
}

static int Bin_Search(int[] a, int key, int l, int h){

if(l<=h){
int mid = (l + h)/2;
if(a[mid]==key)
return mid + 1;
else if(a[mid]>key)
return Bin_Search(a,key,l, mid - 1);
else

return Bin_Search(a,key,mid+1, h);


}
else
return -1;
}
public static void main(String args[]){
Scanner sc = new Scanner([Link]);
int n,key ;
int a[] = new int[10];
[Link]("Enter the number of elements ");

n = [Link]();

for(int i = 0; i<n;i++){
a[i] = [Link]();
}
[Link]("Enter the key ");
key = [Link]();
Merge_Sort(a,0,n-1);
int pos =Bin_Search(a,key ,0,n-1);
if(pos == -1)
[Link]("Not found");
else
[Link](" the key is found at " + [Link](pos));

OUTPUT:
[Link] a program to implement Merge Sort:

import [Link].*;
class MergeSort{
static void merge(int[] a , int l, int m, int h)
{
int i = l, j = m+1;
int k = 0;
int[] c = new int[10] ;
while(i<=m && j<= h)
{
if(a[i]>a[j])
{
c[k] = a[j];
k++;
j++;
}
else{
c[k] = a[i];
k++;
i++;
}
}
while(i<=m){
c[k] = a[i];
k++;
i++;

}
while(j<=h){
c[k] = a[j];
k++;
j++;

}
k = 0;
for(i = l; i<=h;i++)
{ a[i] = c[k]; k++;}
}
static void Merge_Sort(int[] a,int l, int h){
int mid = (l+h)/2;
if(l<h){
Merge_Sort(a,l,mid);
Merge_Sort(a,mid+1,h);
merge(a,l,mid ,h);
}
}
public static void main(String args[]){
Scanner sc = new Scanner([Link]);
int n ;
int a[] = new int[10];
[Link]("Enter the number of elements ");

n = [Link]();

for(int i = 0; i<n;i++){
a[i] = [Link]();
}
Merge_Sort(a,0,n-1);
[Link]("The array after sorting ");
for(int i = 0; i<n;i++){
[Link](a[i]);
}
}
}
Output:
17. Write a program to implement n-Queen’s problem:

import [Link].*;
public class NQueenProblem{

Scanner sc=new Scanner([Link]);


int N=[Link]();
void printSol(int board[][]){
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(board[i][j]==1)
[Link](" "+'Q'+" ");
else [Link](" "+'-'+" ");

}
[Link]();
}
}

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


int i,j;
for(i=0;i<col;i++){
if(board[row][i]==1){
return false;
}
}

for(i=row,j=col;i>=0 && j>=0;i--,j--){


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

for(i=row,j=col;i<N && j>=0;i++,j--){


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

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

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

boolean solveNQ(){
int board[][]=new int[N][N];
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
board[i][j]=0;
}
}
if(solveNQUtil(board,0)==false){
[Link]("No solution");
return false;
}
printSol(board);
return true;
}
public static void main(String args[]){
NQueenProblem Queen=new NQueenProblem();
[Link]();
}
}

OUTPUT:
[Link] a program to implement SUBSET-SUM:

import [Link].*;
class sumOfSubsets {
static void sum(int ind,int s,int[] a,int n,int
target,List<Integer>subset){
if(ind==n ){
if(s==target)
[Link]("The subset is:"+subset);

return;
}
[Link](a[ind]);

s+=a[ind];
sum(ind+1,s,a,n,target,subset);
s-=a[ind];
[Link]([Link]()-1);
sum(ind+1,s,a,n,target,subset);

public static void main(String[] args) {


int n,target;
Scanner sc=new Scanner([Link]);
[Link]("Enter no. of elements in array");
n=[Link]();
[Link]("Enter target sum");
target=[Link]();
int[] a=new int[n];

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

[Link]("Enter array elements");


for(int i=0;i<n;i++){
a[i]=[Link]();
}

sum(0,0,a,n,target,subset);

}
}

OUTPUT:
19. Program implementing Optimal Binary Search tree:

import [Link].*;
import [Link].*;
import [Link].*;
class Main{
static int Find(int c[][],int[][] r , int i, int j){
int min = Integer.MAX_VALUE;
int m,l;
l=0;
for(m = r[i][j-1] ;m<=r[i+1][j] ;m++){
if(min>c[i][m-1] + c[m][j])
{ min = c[i][m-1] + c[m][j];
l = m;
}
}
return l;
}

public static void main(String args[]){


Scanner sc = new Scanner([Link]);
[Link]("Enter the number of nodes :");
int n = [Link]();
int[] p = new int[n+1];
int[] q = new int[n+1];
int[][] r = new int[n+1][n+1] ;
int[][] c = new int[n+1][n+1] ;
int[][] w = new int[n+1][n+1] ;
int mincost,i,j,m,k;
[Link]("Enter the success frequencies ");
for(i=1;i<=n;i++)
p[i] = [Link]();
[Link]("Enter the failure frequencies ");
for(i=0;i<=n;i++)
q[i] = [Link]();
for(i=0;i<=n-1;i++){
w[i][i]= q[i];
r[i][i] = 0;
31

c[i][i] = 0;
w[i][i+1] = w[i][i]+p[i+1]+q[i+1];
c[i][i+1] = w[i][i+1];
r[i][i+1] = i+1;
}
w[n][n] =q[n];c[n][n] =0; r[n][n] =0;
for(m=2;m<=n;m++){
for(i=0;i<=n-m;i++){j
= i+m;
w[i][j] = w[i][j-1]+p[j] + q[j];k
= Find(c,r,i,j);
c[i][j] = w[i][j] + c[i][k-1]+c[k][j];
r[i][j] = k;
}
}
[Link]("the min cost is : " + c[0][n]);
}
}
Output:

20. Write a program to implement 0/1 Knapsack problem by


32

using Dynamic Programming:

import [Link].*;
public class main
{
public static void main(String[] args)
{Scanner sc=new Scanner([Link]);
[Link]("Enter no of instances");
int n=[Link]();
int[] p=new int[n+1];
int[] wt=new int[n+1];
int[] x=new int[n+1];
[Link]("enter capacity");

int m =[Link]();
int i,w,j;
p[0]=0;
wt[0]=0;
[Link]("Enter profits");
for(i=1;i<=n;i++){
p[i]=[Link]();
}
[Link]("Enter weights");
for(i=1;i<=n;i++){
wt[i]=[Link]();
}
int[][] k=new int[n+1][m+1];
for(i=0;i<=n;i++){
for(w=0;w<=m;w++){
if(i==0 || w==0){
k[i][w]=0;
}
else if(wt[i]<=w){
if(p[i]+k[i-1][w-wt[i]] >= k[i-1][w]){
k[i][w]=p[i]+k[i-1][w-wt[i]];
}
else{
k[i][w]=k[i-1][w];
33

}
}
else{
k[i][w]=k[i-1][w];
}
}
}
[Link]("Maxprofit:"+k[n][m]);
i=n;
j=m;
while(i>0 && j>0)
{if(k[i][j]==k[i-1][j]){
x[i]=0;
i--;
}
else{
x[i]=1;
j=j-wt[i];
i--;
}
}
for(i=1;i<=n;i++){
[Link](x[i]+" ");
}
}
}

Output:
34

21. Write a program to implement Greedy Knapsack problem:

import [Link].*;
import [Link].*;

class knapsack{
public static void main(String[] args){
int i,j;
float t,profit=0;
Scanner sc=new Scanner([Link]);
[Link]("enter the number:");
int n=[Link]();
float[] p=new float[n];
float[] w=new float[n];
float[] temp=new float[n];
float[] x=new float[n];
[Link]("enter the weights:");
for(i=0;i<n;i++){
w[i]=[Link]();
}
[Link]("Enter the profits:");
for(i=0;i<n;i++){
p[i]=[Link]();
}
for(i=0;i<n;i++){
temp[i]=(float)p[i]/w[i];
}
for(i=0;i<n;i++){
for(j=0;j<n-i-1;j++){
if(temp[j]<temp[j+1]){

t=temp[j];
temp[j]=temp[j+1];
temp[j+1]=t;
35

t=w[j];
w[j]=w[j+1];
w[j+1]=t;

t=p[j];
p[j]=p[j+1];
p[j+1]=t;
}
}
}
for(i=0;i<n;i++){
[Link](p[i]+" ");
}
[Link]();
for(i=0;i<n;i++){
[Link](w[i]+" ");
}
[Link]();
for(i=0;i<n;i++){
[Link](temp[i]+" ");
}
[Link]();
[Link]("Enter the capacity:");
int c=[Link]();
for(i=0;i<n;i++){
if(w[i]<=c){
x[i]=1;
c-=w[i];
profit+=p[i];
}
else{
break;
}
36

}
if(i<=n){
x[i]=c/w[i];
profit+=p[i]*(x[i]);
}

for(i=0;i<n;i++){
[Link](x[i]+" ");
}
[Link](profit);

OUTPUT:
37

22. Write a program to implement Prim’s minimum cost


spanning tree by using Greedy Method:

import [Link].*;
[Link].*;
import [Link].*;
class Prims{
int V;
int mincost;
int graph[][] = new int[100][100] ;

int[][] tree=new int[99][2];


void getgraph(){
Scanner sc = new Scanner([Link]);
[Link]("Enter the value of n :”);
V = [Link]();
[Link]("Enter the cost matrix“);
int i,j;

for(i = 0;i<V;i++){
for(j = 0;j<V;j++)
{
graph[i][j] = [Link]();
if(graph[i][j] ==0)
graph[i][j] =Integer.MAX_VALUE;
}

void findMST(){
getgraph();
int i,j,k,l;
int min,m,minval,mindex;
38

int[] near = new int[V];


min=Integer.MAX_VALUE;
k=0;l=0;
for(i=0;i<V;i++){
for(j=0;j<V;j++){
if(graph[i][j]<min)
{

min=graph[i][j];
k = i;
l =j;

}
}
}

tree[0][0]= k;
tree[0][1] = l;

mincost = 0;
mincost+=graph[k][l];
for(i=0;i<V;i++){
if(graph[i][l]<graph[i][k])
near[i] = l;

else near[i] = k;
}
near[k] = near[l] = -1;

mindex = 0
for(i=1;i<V-1;i++)
{
minval = Integer.MAX_VALUE;
for(j=0;j<V;j++){
if(near[j]!=-1 &&
graph[j][near[j]]<minval)
39

{minval =graph[j][near[j]] ;
mindex = j;
}
}

tree[i][0] = mindex;
tree[i][1]=near[mindex];
mincost+= graph[mindex][near[mindex]];
near[mindex] = -1;
for(m=0;m<V;m++){
if(near[m]!=-1 &&
graph[m][near[m]]>graph[m][mindex])
near[m] = mindex;
}
}
for(i=0;i<V-1;i++){
for(j=0;j<2;j++){
[Link](tree[i][j]+ " " );
}
[Link]();
}
[Link]("Mincost:"+mincost);
}
}
class Main{
public static void main(String args[]){
Prims g = new Prims();
[Link]();
}
}
40

Output:
41

23. Write a program to implement Kruskal’s minimum cost


spanning tree by using Greedy Method:

import [Link].*;
import [Link].*;
import [Link].*;
class Kruskals{
int V;
int mincost;
int graph[][] = new int[100][100] ;

int[][] tree = new int[99][2];


void getgraph(){
Scanner sc = new Scanner([Link]);

[Link]("Enter the number of nodes ");


V = [Link]();
[Link]("Enter the cost matrix ");int
i,j;

for(i = 0;i<V;i++){
for(j = 0;
j<V;j++){
graph[i][j]= [Link]();
if(graph[i][j] ==0)
graph[i][j] =Integer.MAX_VALUE;
}

int find(int i,int[] parent){


if(parent[i]==-1)
return -1;
while(parent[i]!=-1){
i=parent[i];}
return i;
42

void FindMST(){
getgraph();
int i,j,k,l,min,m,minval,mindex;

int[] initial=new int[V*V];


int[] fin=new int[V*V];
int[] cost=new int[V*V];

k=0;
for(i=0;i<V;i++){
for(j=0;j<V;j++){
cost[k]=graph[i][j];
initial[k]=i;
fin[k]=j;
k++;
}
}

for(i=0;i<(V*V)-1;i++){
for(j=0;j<(V*V)-i-1;j++){
if(cost[j]>cost[j+1]){
int temp=cost[j];
cost[j]=cost[j+1];
cost[j+1]=temp;
temp=initial[j];
initial[j]=initial[j+1];
initial[j+1]=temp;
temp=fin[j];
fin[j]=fin[j+1];
43

fin[j+1]=temp;

}
}
}

[Link]();

int[] parent=new int[V*V];


for(i=0;i<V*V;i++) parent[i]=-1;
int mincost=0;

int ptr=0;
i=0;
while(i<V-1){
k=initial[ptr];
l=fin[ptr];
/ [Link](k+" "+l);
int p1=find(k,parent);
int p2=find(l,parent);
/ [Link]("p1:"+p1+" p2:"+p2);
if((p1!=p2 && p1!=l && p2!=k) || (p1==-1 && p2==-1)){
mincost+=cost[ptr];
tree[i][0]=initial[ptr];
tree[i][1]=fin[ptr];
parent[k]=l;
i++;
}
ptr++;
}

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

for(j=0;j<2;j++){
[Link](tree[i][j]+ " " );
}
[Link]();
}
[Link]("Mincost:"+mincost);
}
}
class Main{
public static void main(String args[]){
Kruskals g = new Kruskals();
[Link]();
}
}
OUTPUT:
45

24. Write a program to implement Job sequencing with


deadlines by using Greedy Method:
import [Link].*;
import [Link].*;
class jobScheduling{
public static void main(String args[]){
int i,j,t,k,r,q,profit=0;
Scanner sc=new Scanner([Link]);
[Link]("enter the number:");
int n=[Link]();
int[] d=new int[n+1];
int[] p=new int[n+1];
int[] J=new int[n+1];
int[] t1=new int[n+1];

d[0]=0;
J[0]=0;
p[0]=0;
J[1]=1;
[Link]("enter the deadlines:");
for(i=1;i<n+1;i++){
d[i]=[Link]();
}
[Link]("Enter the profits:");
for(i=1;i<n+1;i++){
p[i]=[Link]();
}
for(i=0;i<n+1;i++){
t1[i]=p[i];
}
for(i=1;i<n+1;i++){
for(j=1;j<n-i;j++){
if(p[j]<p[j+1]){
t=d[j];
d[j]=d[j+1];
d[j+1]=t;

t=p[j];
p[j]=p[j+1];
p[j+1]=t;
46

}
}
}
for(i=0;i<n+1;i++){
[Link](d[i]+" ");
}
[Link]();
for(i=0;i<n+1;i++){
[Link](p[i]+" ");
}
[Link]();
k=1;
for(i=2;i<n;i++){
r=k;
while((d[J[r]]>d[i]) && (d[J[r]]!=r)){
r=r-1;
}
if((d[J[r]]<=d[i]) && (d[i]>r)){
for(q=k;q>r+1;q--){
J[q+1]=J[q];
}
J[r+1]=i;
k++;

}
[Link]();
for(i=0;i<=n;i++){
[Link](J[i]+" ");
}
[Link]();
for(i=0;i<n;i++){
if(J[i]!=0){

[Link](J[i]+" ");
profit+=t1[J[i]];
}
}
[Link](profit);
47

}
}Output:

25. Write a program to implement Single source shortest


path problem by using Greedy Method:

import
[Link].*;
import
[Link].*;class
Main{
public static void main(String args[]){
int n , v,u,i,j;

int min;
Scanner sc = new Scanner([Link]);
[Link]("Enter the value of n :");
n = [Link]();
int[][] cost = new int[n][n];
int[] dist = new int[n+1];
int[] prev=new int[n];
boolean[] visited = new boolean[n];
[Link]("Enter the adjacency matrix :");
for (i=0;i<n;i++){
for(j=0;j<n;j++){
cost[i][j]=[Link]();
48

if(cost[i][j]==0)
cost[i][j] = Integer.MAX_VALUE;
}
}
[Link]("Enter v");
v = [Link]();
for(i=0;i<n;i++){
visited[i] =false;
dist[i]=cost[v][i];
prev[i]=-1;
}
visited[v]=true;
dist[v] = 0;
dist[n]=integer.MAX_VALUE;
for(i=0;i<n-1;i++){
min = n;
for(j=0;j<n ;j++)
{
if(visited[j]==false){
if(dist[j]<=dist[min])
{
min = j;

}
}
}

visited[min]=true;
for(u=0;u<n;u++)
{
if(visited[u]==false){

if(dist[min]!= Integer.MAX_VALUE&&cost[min][u]!= Integer.MAX_VALUE


&&dist[u]>dist[min]+cost[min][u]){
dist[u]=dist[min]+cost[min][u];
prev[u]=min;
}
49

}
}
}

for(i=0;i<n;i++){
[Link]("Distance from source to "+i+":"+dist[i]);
List<Integer>path=new ArrayList<>();
int cur=i;
while(cur!=-1){
[Link](0,cur);
cur=prev[cur];
}
[Link](0,v);
[Link]("shortest path from "+v+" to "+i+":"+path);
}

}
}
Output:

Common questions

Powered by AI

The static keyword in Java allows fields and methods to belong to the class rather than to any specific instance. This provides advantages such as memory efficiency (since static fields are shared across all instances) and easy access from static contexts without needing an instance . However, it poses challenges such as lack of flexibility since static methods cannot be overridden, potential difficulties in unit testing due to their global state nature, and the risk of memory leaks if used improperly .

The `merge` function in Merge Sort is crucial as it combines two sorted subarrays into one sorted array, thereby maintaining the sorted order . It ensures correctness by comparing elements from each subarray (left and right) and arranging them into a new array in descending order before writing the results back to the original array. This merging process, called after dividing the array, is what ultimately results in a well-sorted array upon completion of all recursive `Merge_Sort` calls .

Abstract classes in Java provide a base for subclasses to implement specific methods while maintaining a shared contract through abstract methods, which must be overridden in the subclasses . Interfaces, on the other hand, define a contract where implementing classes must provide concrete implementations of all methods declared in the interface. The key difference is that abstract classes can have method implementations and state (fields), whereas interfaces cannot; interfaces only allow method declarations and static constants .

The Fibonacci series program demonstrates control structures in Java through the use of a for loop to iterate over the sequence count. The loop manages the calculation of the next Fibonacci number by updating variables n1, n2, and n3 on each iteration . This process highlights the use of looping and basic arithmetic operations in managing a sequence of outputs efficiently. Conditionals are implicit as the loop executes up to a predefined count, emphasizing the use of control structures in repetitive tasks.

Method overloading occurs when multiple methods in the same class have the same name but different parameter lists. It allows for methods to handle different types of inputs . Method overriding, in contrast, involves redefining a method's behavior in a subclass that is already defined in its parent class, allowing for runtime polymorphism . Overloading is used to create multiple methods to perform similar functions based on varied data inputs, whereas overriding allows for extending or modifying parent class method behavior in derived classes.

Prim's and Kruskal's algorithms differ primarily in their approach to constructing a minimum spanning tree. Prim's algorithm grows the spanning tree from an initial node, adding the smallest edge from the tree to a vertex outside of it considering weights directly related to the tree . Kruskal's, on the other hand, sorts all edges first by weight and adds them incrementally to an initially empty spanning tree ensuring no cycles form within the tree . This means Prim's is typically better suited to dense graphs while Kruskal's is effective for sparse graphs due to its edge-centric strategy. Both algorithms use a greedy approach but handle graph components individually.

Encapsulation in Java is achieved by wrapping data (variables) and methods in a single unit (class) and restricting access to the data by using access modifiers like private, while providing public getter and setter methods for accessing or modifying them . The practical benefits include improved modularity and maintainability, prevention of unauthorized access to data, and enhanced security by hiding the internal state of the object from the outside world .

The Palindrome checker uses a while loop to reverse the digits of the input number by successively extracting and appending the last digit (using modulus and integer division). Conditionals are employed to compare the reversed number against the original input, determining and printing whether it is a palindrome or not. This method relies on basic control flow constructs to iterate and evaluate conditions for determining palindrome status .

Inheritance and polymorphism together enhance code reuse and flexibility by allowing a subclass to inherit fields and methods from a parent class, thereby promoting code reuse . Polymorphism allows objects to be treated as instances of their parent class through method overriding or interface implementation, enabling flexible and dynamic method call decisions at runtime. This combination allows for extending base class functionality with subclass-specific implementations, thus promoting a modular design and allowing easy maintenance and expansion of the codebase .

The recursion method is effective in solving the n-Queens problem because it simplifies the process of exploring each possible configuration of queens on the board, allowing for a straightforward backtracking approach to explore and eliminate invalid positions by employing a recursive function to build solutions incrementally . However, its limitations include potentially high computational cost for large n due to its recursive nature and the exponential growth of possible solutions, leading to increased time and space complexity as n increases .

You might also like