View difference between Paste ID: igqTjW7P and JcEQr5By

 ---------------------------------------------------------------------------------------------------------------------------
   														Program 1 A
 ---------------------------------------------------------------------------------------------------------------------------
 
 package Students;
 import java.util.*;
 public class Student
 {
 	String usn;
 	String name;
 	String branch;
 	long phone;
 	void getDetails()
 	{
 		Scanner in=new Scanner(System.in);
 		System.out.println("Enter the Student USN");
 		usn=in.nextLine();
 		System.out.println("Enter the Student Name");
 		name=in.nextLine();
 		System.out.println("Enter the Student Branch");
 		branch=in.nextLine();
 		System.out.println("Enter the Student phone");
 		phone=in.nextLong();
 }
 void putDetails()
 {
 System.out.println("\n\t USN:"+ usn + "\n \t Name:"+ name +"\n \t Branch:"+ branch + "\n \t Phone:"+phone );
 		System.out.println("\n");
 }
 public static void main(String args[])
 {
 		int i,n;
 		System.out.println("Enter the number of students");
 		Scanner in=new Scanner (System.in);
 		n=in.nextInt();
 		Student a[]=new Student[n];
 		for(i=0;i<n;i++)
 			a[i]=new Student(); //allocate memory for N objects
 		for(i=0;i<n;i++)
 		{
 			System.out.println("\nEnter details of Student" +(i+1));
 			a[i].getDetails();
 		}
 		for(i=0;i<n;i++)
 		{
 			System.out.println("\nThe details of  Student" +(i+1));
 			a[i].putDetails();
 		}
 }
 }
 
 ----------------------------------------------------------------------------------------------------------------------------
    															Program 1 B
 ----------------------------------------------------------------------------------------------------------------------------
 
 package Students;
 import java.util.*;
 class StackMethods
 {
 int top;
 int size;
 int[] stack ;
 public StackMethods(int arraySize)
 {
         size=arraySize;
         stack= new int[size];
         top=-1;
 }
 public void push(int value)
 {
 	 if(top==size-1)
 {
 	 System.out.println("Stack is full, can't push a value");
 }
 	else
 	{
 	top=top+1;
 	stack[top]=value;
 	}
     }
     public int pop()
 {
 	int t=0;
 	if(top==-1)
 	{
 		System.out.println("Can't pop...stack is empty");
 return -1;
 	}
 	else
 	{
 		t=top--;
 return stack[t];
 	}
     }
 public void display()
 {
 	     for(int i=top;i>=0;i--)
 	{
 		 System.out.print(stack[i]+" ");
 	}
 	System.out.println("\n");
 }
 }
  public class Stack1
 {
 public static void main(String[] args)
 {
         Scanner in = new Scanner(System.in);
   System.out.println("Stack operations\n");
 System.out.println("Enter Size of Stack ");
 int n = in.nextInt();
 int choice ;
 /* Creating object of class arrayStack */
   StackMethods stk = new StackMethods(n);
 /* Perform Stack Operations */
 do{
 	System.out.println("\nStack Operations");
 System.out.println("1. push");
 	System.out.println("2. pop");
 	System.out.println("3. display");
 System.out.println("Enter the choice");
 	 int ch = in.nextInt();
  switch (ch)
 	 {
 		case 1 : System.out.println("Enter element to push");
 			stk.push( in.nextInt() );
 			break;
 		case 2 :int s=stk.pop();
 			if (s!=-1)
 System.out.println("Popped Element = " + s);
 			break;
 case 3 :stk.display();
 		 	break;
 	  }
   System.out.println("Do you want to continue press 0/1");
 	  choice=in.nextInt();
 	}
            while(choice==1);
          }
      }
 
 ----------------------------------------------------------------------------------------------------------------------------
    															Program 2 A
 ----------------------------------------------------------------------------------------------------------------------------
 
 package Students;
 import java.util.Scanner;
  class Staff
 {
 	int staffID;
 	String sname;
 	long  phone;
 	float salary;
 	void getSdetails()
 	{
 		Scanner in=new Scanner(System.in);
 		System.out.println("Enter the Staff ID");
 		staffID=in.nextInt();
 		System.out.println("Enter the Staff Name");
 		sname=in.next();
 		System.out.println("Enter the Staff Phone no");
 		phone=in.nextLong();
 		System.out.println("Enter the Staff Salary");
 		salary=in.nextFloat();
 	}
 	void putSdetails()
 	{
 	System.out.println("staff ID=" +staffID);
 System.out.println("staff Name=" +sname);
 System.out.println("staff phone no=" +phone);
 System.out.println("staff Salary=" +salary);
 System.out.println("\n");
 	}
    }
 class Teaching extends Staff
 {
 	String domain;
 	String publication;
 
 void getTdetails()
 	{
 		Scanner in=new Scanner(System.in);
 		System.out.println("Enter the Domain");
 		domain=in.nextLine();
 		System.out.println("Enter the Publication");
 		publication=in.nextLine();
 	}
 	void putTdetails()
 	{
 		System.out.println("Domain ="+domain);
 		System.out.println("Publication ="+publication);
 		 System.out.println("\n");
 	}
 }
 class Technical extends Staff
 {
 	String skills;
 	void getT1details()
 	{
 		Scanner in=new Scanner(System.in);
 		System.out.println("Enter the Skills");
 		skills=in.nextLine();
 	}
 	void putT1details()
 	{
 		System.out.println("Skills ="+skills);
 		 System.out.println("\n");
 	}
 }
 class Contract extends Staff
 {
 	String period;
 void getCdetails()
 	{
 		Scanner in=new Scanner(System.in);
 		System.out.println("Enter the Period");
 		period=in.nextLine();
 	}
 	void putCdetails()
 	{
 		System.out.println("period ="+period);
 		 System.out.println("\n");
 	}
 }
 class Inheritance
 {
 public static void main(String args[])
 {
 		int i,n;
 		System.out.println("Enter the number of staff");
 		Scanner in=new Scanner(System.in);
 		n=in.nextInt();
 		Staff sf[]=new Staff[n];
 		Teaching t[]=new Teaching[n];
 		Technical t1[]=new Technical[n];
 		Contract c[]=new Contract[n];
 		for(i=0;i<n;i++)
 		{
 			sf[i]=new Staff(); //allocate memory for staff object
 			t[i]=new Teaching();//allocate memory for Teaching object
 			t1[i]=new Technical();//allocate memory for Technical object
 			c[i]=new Contract();//allocate memory for Contract object
 		}
 		for(i=0;i<n;i++)             //Read the details of Staff & its subclasses
 		{
 			System.out.println("Enter the details of staff"+(i+1));
 			sf[i].getSdetails();
 			t[i].getTdetails();
 			t1[i].getT1details();
 			c[i].getCdetails();
 		}
 		System.out.println("...............");
 		for(i=0;i<n;i++)             //Display the details of Staff & its subclasses
 		{
 			System.out.println("The Details of staff"+(i+1));
 			sf[i].putSdetails();
 			t[i].putTdetails();
 			t1[i].putT1details();
 			c[i].putCdetails();
 			System.out.println("...............");
 		}
 }
 }
 
 ----------------------------------------------------------------------------------------------------------------------------
    															Program 2 B
 ----------------------------------------------------------------------------------------------------------------------------
 
 package staff;
 import java.util.Scanner;
 import java.util.StringTokenizer;
 
 public class Customer
 {
 	public String readCustomer()
 	{
 		Scanner scanner = new Scanner(System.in);
 		System.out.println("Enter name and DOB in <name,dd/mm/yyyy> format");
 		String str = scanner.next();
 		if(!str.startsWith("<") ||!str.endsWith(">"))
 		{
 			System.out.println("Please enter it in proper format");
 			System.exit(0);
 		}
 		return str;
 	}
 	public void displayCustomer(String data)
 {
 		String st = data.substring(0, data.length());
 		StringTokenizer token = new StringTokenizer(st, "<,/>");
 		String finalString =null;
 		while(token.hasMoreTokens())
 {
 			if(finalString == null)
 			{
 				finalString = token.nextToken();
 			}
 			else
 			{
 				finalString =finalString+","+token.nextToken();
 			}
 		}
 		System.out.println("The Resultant String is:" +"<" +finalString+">");
 	}
 	public static void main(String args[])
 	{
 		Customerc = new Customer();
 		String data=c.readCustomer();
 		c.displayCustomer(data);
 	}
 }
 
 ----------------------------------------------------------------------------------------------------------------------------
    															Program 3 A
 ----------------------------------------------------------------------------------------------------------------------------
 
 package Exception;
 import java.util.Random;
 import java.util.Scanner;
 
 public class Test
 {
 	public static void main(String[] args)
 {
 		int a,b,d;
 		Scanner in=new Scanner(System.in);
 		System.out.println("Enter the value of a");
 		 a=in.nextInt();
 		System.out.println("Enter the value of b");
 	            b=in.nextInt();
 		try
 {
 		     d=a/b;
 		     System.out.println("\nThe Result of "+a+"/"+b+ " is:"+d);
 		   }
 		catch(ArithmeticException ae)
 {
 			System.out.println("division by zero");
 		}
 	}
 }
 
 ----------------------------------------------------------------------------------------------------------------------------
    															Program 3 B
 ----------------------------------------------------------------------------------------------------------------------------
 
 package Exception;
 import java.util.Random;
 import java.util.Scanner;
 
 public class Mythread
 {
 	public static void main(String[] args) throws InterruptedException
 	{
 		Runnable r1 = new Runnable1();
 		Thread t1 = new Thread(r1);
 		t1.start();
 		Thread.sleep(5000);
 
 		Runnable r2 = new Runnable2();
 		Thread t2 = new Thread(r2);
 		t2.start();
 		Thread.sleep(5000);
 
 		Runnable r3=new Runnable3();
 		Thread t3 = new Thread(r3);
 		t3.start();
 	}
 }
 class Runnable1 implements Runnable
 {
 	public void run()
 {
 		Scanner in=new Scanner(System.in);
 		System.out.println("Enter number to find square");
 		int a=in.nextInt();
 int b=a*a;
 System.out.println("The square of number is:"+b);
 	}
 }
 class Runnable2 implements Runnable
 {
 	public void run()
 {
 		Scanner in=new Scanner(System.in);
 		System.out.println("Enter number to find cube");
 		int c=in.nextInt();
 		int d=c*c*c;
 		System.out.println("The cube of number is:"+d);
 	}
 }
 class Runnable3 implements Runnable
 {
 	int n,i;
 	public void run()
 	{
 		Scanner in=new Scanner(System.in);
 		Random rand=new Random();
 		n=rand.nextInt(50);
 		System.out.println("\nEnter the number of elements");
 		n=in.nextInt();
 		int arr[]=new int[n];
 		for(i=0;i<n;i++)
 		arr[i]=rand.nextInt(50);
 		System.out.println("\nthe random elements are ");
 		for(i=0;i<n;i++)
 		System.out.println(arr[i]+" ");
 	}
 }
 
 ----------------------------------------------------------------------------------------------------------------------------
    															Program 4
 ----------------------------------------------------------------------------------------------------------------------------
 
 package sort;
 import java.util.Random;
 import java.util.Scanner;
 
 public class QuickSort
 {
 	static int max=50000;
 	public static int partition(int a[],int low,int high)
 	{
 	int i,j,temp,key;
 	key=a[low];
 	i=low;
 	j=high+1;
 	while(i<=j)
 	{
 		do
 			i++;
 		while (key>=a[i]&& i<=high);
 		do
 			j--;
 		while(key<a[j]);
 		if(i<j)
 		{
 		temp=a[i];
 		a[i]=a[j];
 		a[j]=temp;
 		}
 	}
 	temp=a[low];
 	a[low]=a[j];
 	a[j]=temp;
 	return j;
 }
 public static void qs (int a[],int low, int high)
 {
 	int mid;
 	if(low<high)
 	{
 		mid=partition(a,low,high);
 		qs(a,low,mid-1);
 		qs(a,mid+1,high);
 	}
 }
 public static void main(String args[])
 {
 	int n,i;
 	Scanner in=new Scanner(System.in);
 	Random rand=new Random();
 	System.out.println("Quicksort Test");
 	/* Accept no.of Elements */
 	System.out.println("\nEnter the number of elements");
 	n=in.nextInt();
 	/* create array of n elements */
 	int arr[]=new int[max];
 	try{
 	/* Generate Random Numbers */
 	for(i=0;i<n;i++)
 	arr[i]=rand.nextInt(100);
 	/* Print random numbers */
 	System.out.println("\nthe random elements are ");
 	for(i=0;i<n;i++)
 	System.out.println(arr[i]+" ");
 	long start_time=System.nanoTime();
 	/*call method Quick Sort*/
 	qs(arr,0,n-1);
 	long end_time=System.nanoTime();
 	/* Print Sorted Array */
 	System.out.println("\nThe Elements After sorting");
 	for(i=0;i<n;i++)
 	System.out.println(arr[i]+" ");
 	long t=end_time - start_time;
 	System.out.println(“Time taken for execution is:”+t+” nanoseconds);
 	}
 	catch(ArrayIndexOutOfBoundsException ae)
 	{
 		System.out.println("Array Index reached maximum ");
 	}
 	}
 }
 
 
 ----------------------------------------------------------------------------------------------------------------------------
    															Program 5
 ----------------------------------------------------------------------------------------------------------------------------
 
 package sort1;
 import java.util.Random;
 import java.util.Scanner;
 
 public class MergeSort
 {
 static int max=50000;
 public static void mergesort(int a[],int low,int high)
 {
         int mid;
         if(high>low)
         {
                mid=(low+high)/2;
                mergesort(a,low,mid);
                mergesort(a,mid+1,high);
                merge(a,low,mid,high);
          }
   }
  public static void merge(int a[],int low,int mid,int high)
  {
           int k=low,j=mid+1,i=low;
           int c[]=new int[1000];
           while((i<=mid)&&(j<=high))
           {
                if(a[i]<=a[j])
                {
                       c[k]=a[i];
                       i=i+1;
                 }
                else
                 {
                        c[k]=a[j];
                        j=j+1;
                  }
              k=k+1;
  }
 while(i<=mid)
 {
       c[k]=a[i];
       k=k+1;
       i=i+1;
  }
 while(j<=high)
  {
      c[k]=a[j];
      k=k+1;
      j=j+1;
 }
 for(i=low;i<=high;i++)
 a[i]=c[i];
 }
 public static void main(String args[] )
 {
 	int n,i;
 	Scanner in=new Scanner(System.in);
 	Random rand=new Random();
 	System.out.println("MergeSort Test");
 	/* Accept no.of Elements */
 	System.out.println("\nEnter the number of elements");
 	n=in.nextInt();
 	/* create array of n elements */
 	int arr[]=new int[max];
 	try{
 	/* Generate Random Numbers */
 	for(i=0;i<n;i++)
 	arr[i]=rand.nextInt(100);
 	/* Print random numbers */
 	System.out.println("\nthe random elements are ");
 	for(i=0;i<n;i++)
 	System.out.println(arr[i]+" ");
 long start_time=System.nanoTime();
 	/*call method merge Sort*/
 	mergesort(arr,0,n-1);
 long end_time=System.nanoTime();
 	/* Print Sorted Array */
 	System.out.println("\nThe Elements After sorting");
 	for(i=0;i<n;i++)
 	System.out.println(arr[i]+" ");
 long t=end_time - start_time;
 	System.out.println(“Time taken for execution is:”+t+” nanoseconds);
 	}
 	catch(ArrayIndexOutOfBoundsException ae)
 	{
 		System.out.println("Array Index reached maximum ");
 	}
 	}
 }
 
 ----------------------------------------------------------------------------------------------------------------------------
    															Program 6 A
 ----------------------------------------------------------------------------------------------------------------------------
 
 package knapsack;
 import java.util.Scanner;
 public class Knapsack1
 {
 private static int w[]=new int[10];
 private static int b[]=new int[10];
 private static int v[][]=new int[10][10];
 private static int value[]=new int[10];
 static int max(int a,int b)
 {
 return(a>b)?a:b;
 	}
 	static int knap(int i,int j)
 	{
 		if(i==0 || j==0)
 			v[i][j]=0;
 		elseif(j<w[i])
 			v[i][j]=knap(i-1,j);
 		else
 			v[i][j]=max(knap(i-1,j), value[i]+knap(i-1,j-w[i]));
 		returnv[i][j];
 	}
 	static void optimal(int i,int j)
 	{
 		if(i>=1 || j>=1)
 			if(v[i][j]!=v[i-1][j])
 			{
 				System.out.println("Item:"+i);
 				b[i]=1;
 				j=j-w[i];
 				optimal(i-1,j);
 			}
 			else
 				optimal(i-1,j);
 	}
 	public static void main(String[] args)
 {
 		int profit, w1,n,i,j;
 		Scanner sc=new Scanner(System.in);
 		System.out.println("enter the number of items:");
 		n=sc.nextInt();
 		System.out.println("enter the capacity of the knapsack:");
 		w1=sc.nextInt();
 		System.out.println("enter the values:");
 		for(i=1;i<=n;i++)
 		value[i]=sc.nextInt();
 		System.out.println("enter the weights:");
 		for(i=1;i<=n;i++)
 		w[i]=sc.nextInt();
 		profit=knap(n,w1);
 		System.out.println("profit: "+profit);
 		System.out.println("\noptimal subset is:\n");
 		optimal(n,w1);
 		System.out.println("the solution vector is:");
 		for(i=1;i<=n;i++)
 		System.out.println(b[i]);
 	   }
 }
 
 ----------------------------------------------------------------------------------------------------------------------------
    															Program 6 B
 ----------------------------------------------------------------------------------------------------------------------------
 
 package knapsack;
 import java.util.Scanner;
 public class Knapsack2
 {
 public static void knapsack(int n, int item[],float weight[], float profit[], float capacity)
 {
 		float tp = 0,u;
 		int i;
 		u =  capacity;
 		float x[]=new float[20];
 		for (i = 0; i < n; i++)
 		x[i] = (float) 0.0;
 for (i = 0; i < n; i++)
  {
       if (weight[i] > u)
          break;
       else {
          x[i] = (float) 1.0;
          tp = tp + profit[i];
          u = (int) (u - weight[i]);
       }
    }
 
    if (i < n)
       x[i] = u / weight[i];
    tp = tp + (x[i] * profit[i]);
    System.out.println("\nThe result vector is:- ");
    for (i = 0; i < n; i++)
       System.out.println("\tItem "+item[i]+":" +x[i]);
    System.out.println("\nMaximum profit is:- " +tp);
 }
 public static void main(String[] args)
 {
    float weight[]=new float[20];
    float profit[]=new float[20];
    float capacity;
    int num, i, j;
    float ratio[]=new float[20], temp;
    int item[]=new int[10];
    Scanner in=new Scanner(System.in);
    System.out.println("\nEnter the no. of objects:- ");
    num=in.nextInt();
    System.out.println("\nEnter the the items, weights and profits of each object:- ");
    for (i = 0; i < num; i++)
   {
         item[i]=in.nextInt();
        weight[i]=in.nextFloat();
        profit[i]=in.nextFloat();
    }
    System.out.println("\nEnter the capacityacity of knapsack:- ");
    capacity=in.nextFloat();
    for (i = 0; i < num; i++)
    {
       ratio[i] = profit[i] / weight[i];
    }
    for (i = 0; i < num; i++)
   {
        for (j = i + 1; j < num; j++)
       {
          if (ratio[i] < ratio[j])
         {
             temp = ratio[j];
             ratio[j] = ratio[i];
             ratio[i] = temp;
 
             temp = weight[j];
             weight[j] = weight[i];
             weight[i] = temp;
 
             temp = profit[j];
             profit[j] = profit[i];
             profit[i] = temp;
 
 	temp=item[j];
 	item[j]=item[i];
 	item[i]=(int)temp;
          }
       }
    }
    knapsack(num, item,weight, profit, capacity);
 }
 }
 
 ----------------------------------------------------------------------------------------------------------------------------
    															Program 7
 ----------------------------------------------------------------------------------------------------------------------------
 
 package shortestpath;
 import java.util.Scanner;
 public class Dijkstra
 {
 	public static int findmin()
 	{
 		int i,n,min=0;
 		int d[]=new int[20];
 		int s[]=new int[20];
 		Scanner in=new Scanner(System.in);
 		n=in.nextInt();
 		for(i=1;i<=n;i++)
 		{
 			if(s[i]==0)
 			{
 				min=i;
 				break;
 			 }
 		}
 		 for(i=1;i<=n;i++)
 		 {
 			if(d[i]<d[min] && s[i]==0)
 			 min=i;
 		}
 		return min;
 	}
 public void dijkstra(int v,int w[][],int s[],int d[],int n)
 	{
 		int i,w1,u,k,j;
 		int p[]=new int[20];
 		for(i=1;i<=n;i++)
 		{
 			s[i]=0;
 			d[i]=999;
 	p[i]=0;
 		}
 	d[v]=0;
 		for(k=1;k<=n;k++)
 		{
 	  u=findmin();
 	  s[u]=1;
 			for(w1=1;w1<=n;w1++)
 			{
 				if(w[u][w1]!=999 && s[w1]==0)
 				{
 					if(d[w1]>d[u]+w[u][w1])
 					{
 						d[w1]=d[u]+w[u][w1];
 						p[w1]=u;
 					}
 				}
 			}
 		}
 		System.out.println("shortest path costs\n");
 		for(i=1;i<=n;i++)
 		{
 		if(d[i]==999)
 		System.out.println("sorry!  no path for source" + v + "to" + i + "vertex");
 		else
 		System.out.println("path cost from" +v+ "to" +i+ "is:" +d[i]+"\n");
 		}
 		System.out.println("shortest group of paths are\n");
 		for(i=1;i<=n;i++)
 		{
 			if(i!=v && d[i]!=999)
 			{
 				System.out.print(i);
 				 j=p[i];
 				while(p[j]!=0)
 				{
 					System.out.println("<----"+ j +" ");
 					j=p[j];
 				}
 				System.out.println("<----"+ v +"\n");
 			}
 		}
 	}
 	public static void main(String args[])
 	{
 		 int i,j,n,v;
 		int d[]=new int[20];
 		int s[]=new int[20];
 		int w[][]=new int[50][50];
 		Dijikstra d1 = new Dijikstra();
 		Scanner in=new Scanner(System.in);
 		System.out.println("enter the number of vertices\n");
 		n=in.nextInt();
 		System.out.println("enter the cost of vertices\n");
 		for(i=1;i<=n;i++)
 		for(j=1;j<=n;j++)
 		{
 			w[i][j]=in.nextInt();
 		}
 		System.out.println("enter the source vertex\n");
 		v=in.nextInt();
 	      /* call Dijkstra method */
 		d1.dijkstra(v,w,s,d,n);
 	 }
 }
 -------------------------------------------------------------------------------------------------
 PROG 8
 --------------------------------------------------------------------------------------------------
 import java.util.*;
 public class Kruskal
 {
 	static int parent[]=new int[10];
 	static int cost[][]=new int[10][10];
 	public static void main(String args[])
 	{
 		Scanner sn=new Scanner(System.in);
 		System.out.print("Enter the no. of vertices : ");
 		int n=sn.nextInt();
 		System.out.println("Enter the cost matrix : ");
 		for(int i=1;i<=n;i++)
 			for(int j=1;j<=n;j++)
 				cost[i][j]=sn.nextInt();
 		kruskal(n);
 	}
 	public static void kruskal(int n)
 	{
 		int c=1,sum=0;
 		while(c<n)
 		{
 			int u=0,v=0,i=0,j=0;
 			int min=999;
 			for(i=1;i<=n;i++)
 				for(j=1;j<=n;j++)
 					if(cost[i][j]<min&&i!=j)
 					{
 						min=cost[i][j];
 						u=i;
 						v=j;
 					}
 			i=find(u);
 			j=find(v);
 			if(i!=j)
 			{
 				union(i,j);
 				sum+=cost[u][v];
 				System.out.println("(" + u + "," + v + ")" + "=" + cost[u][v]);
 				c++;
 			}
 			cost[u][v]=cost[v][u]=999;
 		}
 		System.out.println("Minimum Cost: "+sum);
 	}
 	static int find(int p)
 	{
 		while(parent[p]!=0)
 			p=parent[p];
 		return p;
 	}
 	static void union(int i,int j)
 	{
 		if(i<j)
 			parent[i]=j;
 		else
 			parent[j]=i;
 	}
 }
 -------------------------------------------------------------------------------------------------
 PROG 9
 --------------------------------------------------------------------------------------------------
 import java.util.*;
 public class Prims
 {
 	public static void main(String args[])
 	{
 		int cost[][]=new int[10][10];
 		int vis[]=new int[10];
 		Scanner sn=new Scanner(System.in);
 		System.out.print("Enter the no. of vertices : ");
 		int n=sn.nextInt();
 		for(int i=1;i<=n;i++)
 			vis[i]=0;
 		System.out.println("Enter the cost matrix : ");
 		for(int i=1;i<=n;i++)
 			for(int j=1;j<=n;j++)
 				cost[i][j]=sn.nextInt();
 		System.out.print("Enter the source vertex : ");
 		int source=sn.nextInt();
 		vis[source]=1;
 		int c=1,sum=0;
 		while(c<n)
 		{
 			int min=999;
 			int u=0,v=0;
 			for(int i=1;i<=n;i++)
 				for(int j=1;j<=n;j++)
 					if(vis[i]==1&&vis[j]==0)
 						if(i!=j&&cost[i][j]<min)
 						{
 							min=cost[i][j];
 							u=i;
 							v=j;
 						}
 			vis[v]=1;
 			c++;
 			sum+=min;
 			System.out.println(u + "->" + v + "=" + min);
 		}
 		for(int i=1;i<=n;i++)
 			if(vis[i]==0)
 			{
 				System.out.println("No Spanning tree!!");
 				System.exit(0);
 			}
 		System.out.println("The cost of minimum spanning tree is" + sum);
 	}
 }
 -------------------------------------------------------------------------------------------------
 PROG 10 A
 ----------------------------------------------------------------------------------------------------
 import java.util.*;
 public class Floyd
 {
 	static int cost[][]=new int[10][10];
 	public static void main(String args[])
 	{
 		Scanner sn=new Scanner(System.in);
 		System.out.print("Enter the no. of vertices : ");
 		int n=sn.nextInt();
 		System.out.println("Enter the cost matrix : ");
 		for(int i=1;i<=n;i++)
 			for(int j=1;j<=n;j++)
 				cost[i][j]=sn.nextInt();
 		floyd(n);
 		System.out.println("The distance matrix : ");
 		for(int i=1;i<=n;i++)
 		{
 			for(int j=1;j<=n;j++)
 				System.out.print(cost[i][j]+" ");
 			System.out.println();
 		}
 	}
 	public static void floyd(int n)
 	{
 		for(int k=1;k<=n;k++)
 			for(int i=1;i<=n;i++)
 				for(int j=1;j<=n;j++)
 					if(cost[i][j]>(cost[i][k]+cost[k][j]))
 						cost[i][j]=cost[i][k]+cost[k][j];
 	}
 }
 ------------------------------------------------------------------------------------------------
 PROG 10 B
 -------------------------------------------------------------------------------------------------
 import java.util.*;
 public class tsp
 {
 	final static int MAX=100;
 	public static void main(String args[])
 	{
 		int cost[][]=new int[MAX][MAX];
 		int tour[]=new int[MAX];
 		Scanner sn=new Scanner(System.in);
 		System.out.print("Enter the no. of vertices : ");
 		int n=sn.nextInt();
 		System.out.println("Enter the cost matrix : ");
 		for(int i=1;i<=n;i++)
 			for(int j=1;j<=n;j++)
 				cost[i][j]=sn.nextInt();
 		for(int i=1;i<=n;i++)
 			tour[i]=i;
 		int min_cost=tsp_dp(cost,tour,1,n);
 		System.out.println("Minimunm cost : "+min_cost+"\n\nTour : ");
 		for(int i=1;i<=n+1;i++)
 			System.out.print(tour[i]+" ");
 	}
 	public static int tsp_dp(int cost[][],int tour[],int start,int n)
 	{
 		int temp[]=new int[MAX];
 		int mintour[]=new int[MAX];
 		int mincost,ccost;
 		if(start==n-1)
 			return(cost[tour[n-1]][tour[n]]+cost[tour[n]][1]);
 		mincost=999;
 		for(int i=start+1;i<=n;i++)
 		{
 			for(int j=1;j<=n;j++)
 				temp[j]=tour[j];
 			temp[start+1]=tour[i];
 			temp[i]=tour[start+1];
 			if(cost[tour[start]][tour[i]]+(ccost=tsp_dp(cost,temp,start+1,n))<mincost)
 			{
 				mincost=ccost+cost[tour[start]][tour[i]];
 				for(int k=1;k<=n;k++)
 					mintour[k]=temp[k];
 			}
 		}
 		int i;
 		for(i=1;i<=n;i++)
 			tour[i]=mintour[i];
 		tour[i]=start;
 		return mincost;
 	}
 }
 ------------------------------------------------------------------------------------------------
 PROG 11
 --------------------------------------------------------------------------------------------------
 import java.util.*;
 public class subset
 {
 	public static void main(String args[])
 	{
 		int a[]=new int[10];
 		int x[]=new int[10];
 		int flag=0;
 		Scanner s=new Scanner(System.in);
 		System.out.print("Enter the number of elements in the set : ");
 		int n=s.nextInt();
 		System.out.println("Enter the elements : ");
 		for(int i=1;i<=n;i++)
 				a[i]=s.nextInt();
 		System.out.print("Enter the desired sum : ");
 		int dsum=s.nextInt();
 		for(int i=1;i<Math.pow(2,n);i++)
 		{
 			subset(i,n,x);
 			int sum=0;
 			for(int j=1;j<=n;j++)
 				if(x[j]==1)
 					sum+=a[j];
 			if(sum==dsum)
 			{
 				flag=1;
 				System.out.print("Subset : {");
 				for(int j=1;j<=n;j++)
 					if(x[j]==1)
 						System.out.print(a[j]+",");
 				System.out.println("} = "+sum);
 			}
 		}
 		if(flag==0)
 			System.out.println("No such subset found!!");
 	}
 	public static void subset(int num,int n,int x[])
 	{
 		for(int i=1;i<=n;i++)
 			x[i]=0;
 		for(int i=n;num!=0;i--)
 		{
 			x[i]=num%2;
 			num/=2;
 		}
 	}
 }
 -------------------------------------------------------------------------------------------------
 PROG 12
 ------------------------------------------------------------------------------------------------
 import java.util.*;
 public class Hamiltonian
 {
 	static int x[]=new int[10];
 	public static void main(String args[])
 	{
 		int adj[][]=new int[10][10];
 		Scanner sn=new Scanner(System.in);
 		System.out.print("Enter the no. of vertices : ");
 		int n=sn.nextInt();
 		System.out.println("Enter the 0/1 Adjacency matrix : ");
 		for(int i=1;i<=n;i++)
 			for(int j=1;j<=n;j++)
 			{
 				adj[i][j]=sn.nextInt();
 				x[i]=0;
 			}
 		x[1]=1;
 		System.out.println("Hamiltonian Cycles : ");
 		hamiltonian(adj,n,2);
 	}
 	static void hamiltonian(int adj[][],int n,int k)
 	{
 		while(true)
 		{
 			nextval(adj,n,k);
 			if(x[k]==0)
 				return;
 			if(k==n)
 			{
 				for(int i=1;i<=n;i++)
 				System.out.print(x[i]+" -> ");
 				System.out.println(x[1]);
 			}
 			else
 				hamiltonian(adj,n,k+1);
 		}
 	}
 	static void nextval(int adj[][],int n,int k)
 	{
 		int i;
 		while(true)
 		{
 			x[k]=(x[k]+1)%(n+1);
 			if(x[k]==0)
 				return;
 			if(adj[x[k-1]][x[k]]==1)
 			{
 				for(i=1;i<k;i++)
 					if(x[i]==x[k])
 						break;
 				if(i==k)
 					if((k<n)||((k==n)&&(adj[x[n]][x[1]]==1)))
 						return;
 			}
 		}
 	}
 }