---------------------------------------------------------------------------------------------------------------------------
  														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;
			}
		}
	}
}