//program 1 

    package selectionsort;
    import java.util.Scanner;
    import java.util.Random;

    public class SelectionSort {
    public static void sort(int[] a) {
    int min, temp;
    for (int i = 0; i < a.length; i++) {
    min = i;
    for (int j = i + 1; j < a.length; j++) {
    if (a[j] < a[min]) // Corrected the missing closing parenthesis
    min = j;
    }
    temp = a[i];
    a[i] = a[min];
    a[min] = temp;
    }
    }

    public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    System.out.println("Enter size of array");
    int n = scan.nextInt();
    int a[] = new int[n];
    System.out.println("The random elements of array");
    Random random = new Random();
    for (int i = 0; i < n; i++) {
    a[i] = Math.abs(random.nextInt(1000));
    System.out.print(a[i] + " ");}
    long startTime = System.nanoTime();
    sort(a);
    long endTime = System.nanoTime();
    long runTime = endTime - startTime;
    // Print runtime in nanoseconds
    System.out.println("\nSelection Sort runtime: ");
    System.out.print(runTime + " nanoseconds");
    System.out.print("\nSorted Array: ");
    for (int i = 0; i < n; i++) {
    System.out.print(a[i] + " ");
    }
    }
    }

    
    

        //program 2

    package quick;
    import java.util.Random;
    import java.util.Scanner;
    public class Quick {
    public static void sort(int[] a) {
    long startTime =System.nanoTime();
    quicksort(a, 0, a.length-1);
    long stopTime =System.nanoTime();
    long elapsedTime= stopTime-startTime;
    System.out.println("\nTime taken");
    System.out.println(elapsedTime);
    }

    public static void quicksort(int a[],int low, int high) {
    int j;
    if(low <= high)
    {
    j=part(a,low,high);
    quicksort(a,low,j-1);
    quicksort(a,j+1,high);
    }
    }

    public static int part(int a[],int low, int high)
    {
    int i, j, pivot;
    pivot=a[low];
    i=low+1;
    j=high;while(true)
    {
    while(i < high && pivot > a[i])
    i++;
    while(a[j] > pivot)
    j--;
    if (i < j)
    {
    int temp=a[i];
    a[i]=a[j];
    a[j]=temp;
    }
    else
    {
    int temp = a[low];
    a[low]=a[j];
    a[j]=temp;
    return j;
    }
    }
    }

    public static void main(String[] args) {
    Scanner scan =new Scanner(System.in);
    System.out.println("enter size of the array");
    int n = scan.nextInt();
    int a[]=new int[n];
    System.out.println(" the random elements of the array");
    Random random = new Random();
    for(int i=0;i < n;i++)
    {
    a[i]=Math.abs(random.nextInt(100));
    }
    for(int i=0;i < n;i++)
    {System.out.print(a[i] +" ");
    }
    sort(a);
    System.out.println("Sorted array");
    for(int i=0;i < n;i++){
    System.out.print(a[i] +" ");
    }
    }
    }

    
    

        //program 3

    package mergesort;
    import java.util.Random;
    import java.util.Scanner;
    public class Mergesort {
    public static void sort(int[] a)
    {
    long startTime =System.nanoTime();
    merge(a,0,a.length-1);
    long stopTime =System.nanoTime();
    long elapsedTime= stopTime-startTime;
    System.out.println("\nTime taken");
    System.out.println(elapsedTime);
    }

    public static void merge(int a[],int low, int high)
    {
    int mid ;
    if(low < high)
    {
    mid=(low+high)/2;
    merge(a,low,mid);
    merge(a,mid+1,high);
    simplemerge(a,low,mid,high);
    }
    }

    public static void simplemerge(int a[],int low,int mid,int high)
    {
    int i = low;int j= mid+1; int k=low;
    int c[] =new int[high+high];
    while(i <= mid && j <= high)
    {
    if (a[i] < a[j])
    c[k++] = a[i++];
    else
    c[k++] = a[j++];
    }
    while(j <= high)
    c[k++] = a[j++];
    while(i <= mid)
    c[k++] = a[i++];
    for (i=low; i <= high; i++)
    a[i] = c[i];
    }

    public static void main(String[] args) {
    // TODO code application logic here
    Scanner scan =new Scanner(System.in);
    System.out.println("enter size of the array");
    int n =scan.nextInt();
    int a[]=new int[n];
    System.out.println("the random elements of the array");
    Random random = new Random();
    for(int i=0;i < n;i++)
    {
    a[i]=Math.abs(random.nextInt(5000));
    }
    for(int i=0;i < n;i++)
    {
    System.out.print(a[i] +" ");
    }
    sort(a);
    System.out.println("Sorted array");
    for(int i=0;i < n;i++)
    System.out.print(a[i]+" ");
    }
    }


    
    

        //program 4

    //4.a.
    package greedyknapsack;
    import java.util.Scanner;
    public class Greedyknapsack{
    static void knapsack (int n,float weight[],float profit[],float capacity)
    {
    float x[]= new float [20],tp=0;
    int i,j,u;
    c= (int) capacity;
    for (i=0;ic )
    break;
    else
    {
    x[i]=(float) 1.0;
    tp = tp + profit[i];
    c=(int)(c-weight[i]);
    }
    }
    if(i < n)
    x[i]= c/weight[i];
    tp=tp+(x[i] * profit[i]);System.out.println("the result vector");
    for (i=0;i < n;i++)
    System.out.println( + x[i]);
    System.out.println("the total profit is");
    System.out.println( + 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;
    System.out.println("\nenter the no of objects");
    Scanner s = new Scanner(System.in);
    num =s.nextInt();
    System.out.println("\n enter weights and profit of each object");
    for(i=0;i < num;i++)
    {
    weight[i]=s.nextInt();
    profit[i]= s.nextInt();
    }
    System.out.println("\ncapacity of knapsack");
    capacity=s.nextInt();
    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;
    }
    }
    }
    knapsack(num,weight,profit,capacity);
    }
    }

    //4.b.
    import java.util.*;
    public class Dijkstra
    {
    public int distance[] = new int[10];
    public int cost[][] = new int[10][10];

    public void calc(int n,int s)
    {
    int flag[] = new int[n+1];
    int i,minpos=1,k,c,minimum;
    for(i=1; i<=n; i++)
    {
    flag[i]=0;
    this.distance[i] = this.cost[s][i];
    }
    c = 2;
    while(c<=n)
    {
    minimum=99;
    for(k=1; k<=n; k++)
    {
    if(this.distance[k] < minimum && flag[k]!=1)
    {
    minimum = this.distance[i];
    minpos = k;
    }
    }
    flag[minpos] = 1;
    c++;
    for(k=1;k<=n;k++)
    {if(this.distance[minpos]+this.cost[minpos][k] < this.distance[k]&&flag[k]!=1 )
    this.distance[k]=this.distance[minpos]+this.cost[minpos][k];
    }
    }
    }

    public static void main(String args[])
    {
    int nodes,source,i,j;
    Scanner in = new Scanner(System.in);
    System.out.println("Enter the Number of Nodes \n");
    nodes = in.nextInt();
    Dijkstra d = new Dijkstra();
    System.out.println("Enter the Cost Matrix Weights: \n");
    for(i=1;i<=nodes;i++)
    for(j=1;j<=nodes;j++)
    {
    d.cost[i][j]=in.nextInt();
    if(d.cost[i][j]==0)
    d.cost[i][j]=999;
    }
    System.out.println("Enter the Source Vertex :\n");
    source=in.nextInt()
    d.calc(nodes,source);
    System.out.println("The Shortest Path from Source \t"+source+"\t to all other vertices are:\n");
    for(i=1;i<=nodes;i++)
    if(i!=source)
    System.out.println("source:"+d.distance[i]+"\t");:"+source+"\tdestination:"+i+"\tMinCost is: :"+d.distance[i]+"\t");
    }
    }

    //4.c.
    package kruskals;
    import java.util.*;
    public class Kruskals {
    public int parent[] = new int[15];
    public int cost[][] = new int[10][10];
    public int mincost;

    public void calc(int n)
    {
    int flag[] = new int[n+1];
    int i,j,min=999,num_edges=1,a=1,b=1,minpos_i=1,minpos_j=1;
    parent[minpos_i]= 0;parent[minpos_j]= 0;
    while(num_edges < n)
    {
    for(i=1 , min=999; i<=n; i++)
    for(j=1 ; j<=n; j++)
    if(this.cost[i][j] < min)
    {
    min = this. cost[i][j];
    a = minpos_i = i;
    b = minpos_j = j;
    }
    while(parent[minpos_i]!=0)
    minpos_i=parent[minpos_i];
    while(parent[minpos_j]!=0)
    minpos_j=parent[minpos_j];
    if(minpos_i!= minpos_j)
    {
    System.out.println("\t from Vertex \t"+a+"\t to Vertex \t"+b+"-mincost:"+min+"\n");
    this.mincost=this.mincost+min;
    num_edges=num_edges+1;
    this.parent[minpos_j]=minpos_i;
    }
    this.cost[a][b]=this.cost[b][a]=999;
    }
    System.out .println("MINIMUM COST SPANNING TREE (MCST)="+mincost);
    }

    public static void main(String[] args) {
    int nodes,i,j;
    Scanner in = new Scanner(System.in);
    System.out.println("Enter the Number of Nodes \n");
    nodes = in.nextInt ();
    Kruskals k = new Kruskals();
    System.out.println ("Enter the Cost Matrix Weights : \n");
    for(i=1; i<=nodes; i++)
    for(j=1; j<=nodes; j++)
    {
    k.cost[i][j] = in.nextInt();
    if(k.cost[i][j] == 0)
    k.cost[i][j] = 999;
    }
    k.calc(nodes);
    }
    }

    //4.d.
    package prim;
    import java.util.Scanner;
    public class Prim {
    public int isVisited[] = new int[15];
    public int cost[][] = new int[10][10];
    public int mincost;

    public void calc(int n) {
    int num_edges = 1, a = 1, b = 1, minpos_i = 1, minpos_j = 1;
    while (num_edges < n) {
    int i, j, min = 999;
    for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
    if (this.cost[i][j] < min) {
    if (this.isVisited[i] != 0) {
    min = this.cost[i][j];
    a = minpos_i = i;
    b = minpos_j = j;
    }
    }
    }
    }
    if (this.isVisited[minpos_i] == 0 || this.isVisited[minpos_j] == 0) {
    System.out.println("\t from Vertex \t" + a + "\t to Vertex \t" + b + "-mincost:" +min + " \n");
    this.mincost = this.mincost + min;num_edges = num_edges + 1;
    this.isVisited[b] = 1;
    }
    this.cost[a][b] = this.cost[b][a] = 999;
    }
    System.out.println("MINIMUM COST SPANNING TREE (MCST) = " + mincost);
    }

    public static void main(String args[]) {
    int nodes, i, j;
    Scanner in = new Scanner(System.in);
    System.out.println("Enter the Number of Nodes: ");
    nodes = in.nextInt();
    Prim p = new Prim();
    System.out.println("Enter the Cost Matrix Weights: ");
    for (i = 1; i <= nodes; i++) {
    for (j = 1; j <= nodes; j++) {
    p.cost[i][j] = in.nextInt();
    if (p.cost[i][j] == 0) {
    p.cost[i][j] = 999;
    }
    }
    }
    p.isVisited[1] = 1; // Initialization
    p.calc(nodes);
    }
    }


    
    

        //program 5

    package subset;
    public class Subset {
    static int count,d =9;
    static int a[]= new int[10];
    static int w[]= {1,2,5,6,8};

    public static void main(String[] args) {
    int sum = 0,i,n;
    n = 5;
    System.out.print("\n the set for sum is S=❴ ");
    for(i=0; i < n-1; i++)
    System.out.print(w[i]+",");
    System.out.println(w[i]+ "❵" );
    System.out.println("d=" +d);
    for(i=0; i < n; i++)
    sum += w[i];
    if (sum < d)
    {
    System.out.println("there is no solution");
    }
    System.out.println("The solution is ");
    count=0;
    sumsubset(0,0,sum);
    }

    public static void sumsubset(int sum,int index,int remainingsum)
    {
    int i;
    a[index]=1;
    if (sum+w[index]== d){
    System.out.println("\n solution ="+(++count));
    for(i=0;i<=index;i++)
    {
    if (a[i]== 1)
    System.out.print(" "+w[i]);
    }
    }
    else if (sum + w[index] + w[index+1] <= d )
    sumsubset(sum + w[index],index+1,remainingsum-w[index] );
    if( (sum + remainingsum - w[index] >= d) && (sum+w[index+1]) <= d)
    {
    a[index] =0;
    sumsubset(sum,(index+1),remainingsum- w[index]);
    }
    }
    }

    
    

        //program 6

    package hamiltonian;
    import java.util.*;
    public class Hamiltonian {
    static int MAX = 25;
    static int vertex[]=new int [MAX];

    public static void main(String[] args) {
    int i,j,v1,v2,Edges,n;
    int G[][] =new int[MAX][MAX];
    System.out.println("\n Program for hamiltonian cycle");
    System.out.println("Enter number of vertices of graph");
    Scanner in = new Scanner(System.in);
    n= in.nextInt();
    for(i=1;i<=n;i++)
    {
    for(j=1;j<=n ;j++)
    {
    G[i][j] =0;
    vertex[i]=0;
    }
    }
    System.out.println("enter the total no of edges");
    Edges= in.nextInt();
    for(i=1;i<=Edges;i++)
    {
    System.out.println("enter the edge ");
    v1=in.nextInt();
    v2=in.nextInt();
    G[v1][v2]= 1;
    G[v2][v1]= 1;
    }
    vertex[1]=1;System.out.println("Hamiltonian cycle");
    H_cycle(G,n,2);
    }

    public static void Nextvertex(int G[][],int n,int k)
    {
    int j;
    while(true)
    {
    vertex[k]= (vertex[k] +1)%(n+1);
    if(vertex[k]==0)
    return;
    if(G[vertex[k-1]][vertex[k]]!=0)
    {
    for(j=1;j<=k-1;j++)//every adjacent vertex
    {
    if(vertex[j] == vertex[k])// not a distinct vertex
    break;
    }
    if(j==k)// obtain a distinct vertex
    {
    if ((k < n) || (k == n) && (G[vertex[n]][vertex[1]] !=0))
    return;//return a distinct vertex
    }
    }
    }
    }

    public static void H_cycle(int G[][],int n ,int k)
    {
    int i;
    while(true)
    {
    Nextvertex(G,n,k);
    if (vertex[k]==0)
    return;if(k==n)
    {
    System.out.print("\n");
    for(i=1;i<=n;i++)
    System.out.print(vertex[i]+"->");
    System.out.print(""+vertex[1]);
    }
    else
    H_cycle(G,n,k+1);
    }
    }
    }
    
    

        //program 7

    //7.a.
    package floyd;
    import java.util.*;
    public class Floyd {
    public static void main(String[] args) {
    int wt[][]=new int[10][10];
    int n,i,j;
    System.out.print("\n Create a graph using adjacency matrix");
    System.out.print("\n Enter no of vertices");
    Scanner in= new Scanner(System.in);
    n=in.nextInt();
    System.out.print("Enter elements enter 999 as infinity value");
    for(i=1;i<=n; i++)
    {
    for(j=1;j<= n;j++)
    {
    System.out.print("\nwt["+i+"]["+j+"]");
    wt[i][j]=in.nextInt();
    }
    }
    System.out.print("\n\t Computing ALl pairs shortest path..\n");
    Floyd_shortest_path(wt,n);
    }

    public static void Floyd_shortest_path(int wt[][],int n)
    {
    int d[][]=new int[10][10];
    int i,j,k;
    for(i=1;i<= n;i++){
    for(j=1;j<= n;j++)
    {
    d[i][j]= wt[i][j];
    }
    }
    for(k=1;k<= n;k++)
    {
    for(i=1;i<= n;i++)
    {
    for(j=1;j<= n;j++)
    {
    d[i][j] = min(d[i][j],(d[i][k]+d[k][j]));
    }
    }
    }
    for(k=0;k<= n;k++)
    {
    System.out.print("d("+k+")\n");
    for(i=1;i<= n;i++)
    {
    for(j=1;j<= n;j++)
    {
    System.out.print(" "+d[i][j]);
    }
    System.out.print("\n");
    }
    }
    }

    public static int min(int a,int b)
    {
    if(a < b)
    return a;
    elsereturn b;
    }
    }

    //7.b.
    package tsp;
    import java.util.*;
    public class TSP{
    static int cost =0;

    public static void main(String[] args)
    {
    int a[][]=new int[10][10];
    int visited[]=new int[10];
    int i,j,n;
    System.out.print("\n Enter no of cities \n");
    Scanner in= new Scanner(System.in);
    n= in.nextInt();
    //create(a,visited,n);
    System.out.println("Enter cost matrix");
    for(i=0;i < n;i++)
    {
    for(j=0;j < n;j++)
    {
    a[i][j]=in.nextInt();
    }
    visited[i]=0;
    }
    System.out.println("The Path is");
    mincost(a,n,0,visited);
    display();
    }

    public static void mincost(int a[][],int n,int city,int visited[])
    {
    int i,cityno;
    visited[city]=1;
    System.out.print((city+1)+"->");
    cityno=least(a,visited,n,city);
    if(cityno==999){
    cityno=0;
    System.out.print(""+(cityno+1));
    cost+=a[city][cityno];
    return;
    }
    mincost(a,n,cityno,visited);
    }

    public static int least(int a[][],int visited[],int n,int c)
    {
    int i,minnode=999,min=999,newmin=0;
    for(i=0;i <= n;i++)
    {
    if ( (a[c][i]!=0) && (visited[i]==0) )
    if(a[c][i] < min)
    { min=a[i][0]+a[c][i];
    newmin = a[c][i];
    minnode=i;
    }
    }
    if (min!=999)
    cost+=newmin;
    return minnode;
    }

    public static void display()
    {
    System.out.println("\n Total cost of tour "+cost);
    }
    }

    //7.c.
    package knapsack;
    import java.util.Scanner;
    public class Knapsack {
    static int max(int a,int b)
    {
    return (a>b)?a:b;
    }

    public static void main(String[] args) {
    int n,i,j,cap;
    int[] p =new int[20];
    int[] w= new int [20];
    int[][] v =new int[10][10];
    System.out.println("enter no of items\n");
    Scanner s=new Scanner(System.in);
    n =s.nextInt();
    for(i=1;i <= n;i++)
    {
    System.out.println("\n enter weights and profit of each object");
    w[i]=s.nextInt();
    p[i]= s.nextInt();
    }
    System.out.println("\ncapacity of knapsack");
    cap=s.nextInt();
    for(i=0;i <= n;i++)
    v[i][0]=0;
    for(i=1;i <= n;i++) // to find the maximum values of item to be placed
    for(j=1;j <= cap;j++)
    {
    if(w[i] > j)
    v[i][j]=v[i-1][j];
    elsev[i][j] = max(v[i-1][j],v[i-1][j-w[i]]+p[i]);
    }
    System.out.println("\n the table is\n");
    for(i=0;i <= n;i++)
    {
    for(j=0;j <= cap;j++)
    {
    System.out.print(v[i][j]+" ");
    }
    System.out.println("\n");
    }
    System.out.println("the maximum profit is\n"+v[n][cap]);
    System.out.println("optimal subset ❴");
    // to find the items placed in the knapsack
    j=cap;
    for(i=n; i>=1; i--)
    if( v[i][j] != v[i-1][j]) // if values not of v[i][j] and v[i-1][j] are not same then pick that
    item i
    {
    System.out.println("item\t"+i);
    j=j-w[i];
    // reduce the capacity of the knapsack after picking item i
    }
    System.out.println("\t ❵");
    }
    }