SHARE
TWEET

Untitled

a guest May 22nd, 2019 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ---------------------------------------------------------------------------------------------------------------------------                                                                                                                                      
  2.                                                         Program 1 A
  3. ---------------------------------------------------------------------------------------------------------------------------
  4.  
  5. package Students;
  6. import java.util.*;
  7. public class Student
  8. {
  9.     String usn;
  10.     String name;
  11.     String branch;
  12.     long phone;
  13.     void getDetails()
  14.     {
  15.         Scanner in=new Scanner(System.in);     
  16.         System.out.println("Enter the Student USN");
  17.         usn=in.nextLine();
  18.         System.out.println("Enter the Student Name");
  19.         name=in.nextLine();
  20.         System.out.println("Enter the Student Branch");
  21.         branch=in.nextLine();
  22.         System.out.println("Enter the Student phone");
  23.         phone=in.nextLong();
  24. }
  25. void putDetails()
  26. {
  27. System.out.println("\n\t USN:"+ usn + "\n \t Name:"+ name +"\n \t Branch:"+ branch + "\n \t Phone:"+phone );
  28.         System.out.println("\n");
  29. }
  30. public static void main(String args[])
  31. {
  32.         int i,n;
  33.         System.out.println("Enter the number of students");
  34.         Scanner in=new Scanner (System.in);
  35.         n=in.nextInt();
  36.         Student a[]=new Student[n];
  37.         for(i=0;i<n;i++)
  38.             a[i]=new Student(); //allocate memory for N objects
  39.         for(i=0;i<n;i++)
  40.         {
  41.             System.out.println("\nEnter details of Student" +(i+1));
  42.             a[i].getDetails();
  43.         }
  44.         for(i=0;i<n;i++)
  45.         {
  46.             System.out.println("\nThe details of  Student" +(i+1));
  47.             a[i].putDetails();
  48.         }
  49. }
  50. }
  51.  
  52. ----------------------------------------------------------------------------------------------------------------------------                                                                                                                                 
  53.                                                             Program 1 B
  54. ----------------------------------------------------------------------------------------------------------------------------
  55.  
  56. package Students;
  57. import java.util.*;
  58. class StackMethods
  59. {
  60. int top;
  61. int size;
  62. int[] stack ;
  63. public StackMethods(int arraySize)
  64. {
  65.         size=arraySize;
  66.         stack= new int[size];
  67.         top=-1;
  68. }
  69. public void push(int value)
  70. {
  71.      if(top==size-1)
  72. {
  73.      System.out.println("Stack is full, can't push a value");
  74. }
  75.     else
  76.     {
  77.     top=top+1;
  78.     stack[top]=value;
  79.     }
  80.     }
  81.     public int pop()
  82. {
  83.     int t=0;
  84.     if(top==-1)
  85.     {
  86.         System.out.println("Can't pop...stack is empty");
  87. return -1;
  88.     }
  89.     else
  90.     {
  91.         t=top--;
  92. return stack[t];
  93.     }
  94.     }
  95. public void display()
  96. {  
  97.          for(int i=top;i>=0;i--)
  98.     {
  99.          System.out.print(stack[i]+" ");
  100.     }
  101.     System.out.println("\n");
  102. }
  103. }
  104.  public class Stack1
  105. {
  106. public static void main(String[] args)
  107. {
  108.         Scanner in = new Scanner(System.in);        
  109.   System.out.println("Stack operations\n");
  110. System.out.println("Enter Size of Stack ");
  111. int n = in.nextInt();
  112. int choice ;
  113. /* Creating object of class arrayStack */
  114.   StackMethods stk = new StackMethods(n);
  115. /* Perform Stack Operations */
  116. do{
  117.     System.out.println("\nStack Operations");
  118. System.out.println("1. push");
  119.     System.out.println("2. pop");
  120.     System.out.println("3. display");
  121. System.out.println("Enter the choice");
  122.      int ch = in.nextInt();
  123.  switch (ch)
  124.      {
  125.         case 1 : System.out.println("Enter element to push");
  126.             stk.push( in.nextInt() );
  127.             break;                        
  128.         case 2 :int s=stk.pop();
  129.             if (s!=-1)
  130. System.out.println("Popped Element = " + s);
  131.             break;                        
  132. case 3 :stk.display();
  133.             break;                        
  134.       }
  135.   System.out.println("Do you want to continue press 0/1");
  136.       choice=in.nextInt();
  137.     }          
  138.            while(choice==1);
  139.          }
  140.      }
  141.  
  142. ----------------------------------------------------------------------------------------------------------------------------                                                                                                                                 
  143.                                                             Program 2 A
  144. ----------------------------------------------------------------------------------------------------------------------------
  145.  
  146. package Students;
  147. import java.util.Scanner;
  148.  class Staff
  149. {
  150.     int staffID;
  151.     String sname;
  152.     long  phone;
  153.     float salary;  
  154.     void getSdetails()
  155.     {
  156.         Scanner in=new Scanner(System.in);
  157.         System.out.println("Enter the Staff ID");
  158.         staffID=in.nextInt();
  159.         System.out.println("Enter the Staff Name");
  160.         sname=in.next();
  161.         System.out.println("Enter the Staff Phone no");
  162.         phone=in.nextLong();
  163.         System.out.println("Enter the Staff Salary");
  164.         salary=in.nextFloat();
  165.     }  
  166.     void putSdetails()
  167.     {
  168.     System.out.println("staff ID=" +staffID);
  169. System.out.println("staff Name=" +sname);
  170. System.out.println("staff phone no=" +phone);
  171. System.out.println("staff Salary=" +salary);
  172. System.out.println("\n");
  173.     }
  174.    }
  175. class Teaching extends Staff
  176. {
  177.     String domain;
  178.     String publication;
  179.    
  180. void getTdetails()
  181.     {
  182.         Scanner in=new Scanner(System.in);
  183.         System.out.println("Enter the Domain");
  184.         domain=in.nextLine();
  185.         System.out.println("Enter the Publication");
  186.         publication=in.nextLine();
  187.     }
  188.     void putTdetails()
  189.     {
  190.         System.out.println("Domain ="+domain);
  191.         System.out.println("Publication ="+publication);
  192.          System.out.println("\n");
  193.     }
  194. }
  195. class Technical extends Staff
  196. {
  197.     String skills;
  198.     void getT1details()
  199.     {
  200.         Scanner in=new Scanner(System.in);
  201.         System.out.println("Enter the Skills");
  202.         skills=in.nextLine();
  203.     }
  204.     void putT1details()
  205.     {
  206.         System.out.println("Skills ="+skills);
  207.          System.out.println("\n");
  208.     }
  209. }
  210. class Contract extends Staff
  211. {
  212.     String period;
  213. void getCdetails()
  214.     {
  215.         Scanner in=new Scanner(System.in);
  216.         System.out.println("Enter the Period");
  217.         period=in.nextLine();
  218.     }
  219.     void putCdetails()
  220.     {
  221.         System.out.println("period ="+period);
  222.          System.out.println("\n");
  223.     }
  224. }
  225. class Inheritance
  226. {
  227. public static void main(String args[])
  228. {
  229.         int i,n;
  230.         System.out.println("Enter the number of staff");
  231.         Scanner in=new Scanner(System.in);
  232.         n=in.nextInt();
  233.         Staff sf[]=new Staff[n];
  234.         Teaching t[]=new Teaching[n];
  235.         Technical t1[]=new Technical[n];
  236.         Contract c[]=new Contract[n];
  237.         for(i=0;i<n;i++)
  238.         {
  239.             sf[i]=new Staff(); //allocate memory for staff object
  240.             t[i]=new Teaching();//allocate memory for Teaching object
  241.             t1[i]=new Technical();//allocate memory for Technical object
  242.             c[i]=new Contract();//allocate memory for Contract object
  243.         }
  244.         for(i=0;i<n;i++)             //Read the details of Staff & its subclasses
  245.         {
  246.             System.out.println("Enter the details of staff"+(i+1));
  247.             sf[i].getSdetails();
  248.             t[i].getTdetails();
  249.             t1[i].getT1details();
  250.             c[i].getCdetails();    
  251.         }
  252.         System.out.println("...............");
  253.         for(i=0;i<n;i++)             //Display the details of Staff & its subclasses
  254.         {
  255.             System.out.println("The Details of staff"+(i+1));
  256.             sf[i].putSdetails();
  257.             t[i].putTdetails();
  258.             t1[i].putT1details();
  259.             c[i].putCdetails();
  260.             System.out.println("...............");         
  261.         }  
  262. }
  263. }
  264.  
  265. ----------------------------------------------------------------------------------------------------------------------------                                                                                                                                 
  266.                                                             Program 2 B
  267. ----------------------------------------------------------------------------------------------------------------------------
  268.  
  269. package staff;
  270. import java.util.Scanner;
  271. import java.util.StringTokenizer;
  272.  
  273. public class Customer
  274. {
  275.     public String readCustomer()
  276.     {
  277.         Scanner scanner = new Scanner(System.in);
  278.         System.out.println("Enter name and DOB in <name,dd/mm/yyyy> format");
  279.         String str = scanner.next();       
  280.         if(!str.startsWith("<") ||!str.endsWith(">"))
  281.         {
  282.             System.out.println("Please enter it in proper format");
  283.             System.exit(0);
  284.         }
  285.         return str;
  286.     }
  287.     public void displayCustomer(String data)
  288. {
  289.         String st = data.substring(0, data.length());
  290.         StringTokenizer token = new StringTokenizer(st, "<,/>");
  291.         String finalString =null;
  292.         while(token.hasMoreTokens())
  293. {
  294.             if(finalString == null)
  295.             {
  296.                 finalString = token.nextToken();
  297.             }
  298.             else
  299.             {
  300.                 finalString =finalString+","+token.nextToken();
  301.             }
  302.         }
  303.         System.out.println("The Resultant String is:" +"<" +finalString+">");
  304.     }
  305.     public static void main(String args[])
  306.     {
  307.         Customerc = new Customer();
  308.         String data=c.readCustomer();
  309.         c.displayCustomer(data);
  310.     }
  311. }
  312.  
  313. ----------------------------------------------------------------------------------------------------------------------------                                                                                                                                 
  314.                                                             Program 3 A
  315. ----------------------------------------------------------------------------------------------------------------------------
  316.  
  317. package Exception;
  318. import java.util.Random;
  319. import java.util.Scanner;
  320.  
  321. public class Test
  322. {
  323.     public static void main(String[] args)
  324. {
  325.         int a,b,d;
  326.         Scanner in=new Scanner(System.in);
  327.         System.out.println("Enter the value of a");
  328.          a=in.nextInt();
  329.         System.out.println("Enter the value of b");
  330.                 b=in.nextInt();
  331.         try
  332. {
  333.              d=a/b;
  334.              System.out.println("\nThe Result of "+a+"/"+b+ " is:"+d);
  335.            }
  336.         catch(ArithmeticException ae)
  337. {
  338.             System.out.println("division by zero");
  339.         }
  340.     }
  341. }
  342.  
  343. ----------------------------------------------------------------------------------------------------------------------------                                                                                                                                 
  344.                                                             Program 3 B
  345. ----------------------------------------------------------------------------------------------------------------------------
  346.  
  347. package Exception;
  348. import java.util.Random;
  349. import java.util.Scanner;
  350.  
  351. public class Mythread
  352. {
  353.     public static void main(String[] args) throws InterruptedException
  354.     {
  355.         Runnable r1 = new Runnable1();
  356.         Thread t1 = new Thread(r1);
  357.         t1.start();
  358.         Thread.sleep(5000);
  359.  
  360.         Runnable r2 = new Runnable2();
  361.         Thread t2 = new Thread(r2);
  362.         t2.start();
  363.         Thread.sleep(5000);
  364.  
  365.         Runnable r3=new Runnable3();
  366.         Thread t3 = new Thread(r3);
  367.         t3.start();
  368.     }
  369. }
  370. class Runnable1 implements Runnable
  371. {
  372.     public void run()
  373. {
  374.         Scanner in=new Scanner(System.in);
  375.         System.out.println("Enter number to find square");
  376.         int a=in.nextInt();
  377. int b=a*a;
  378. System.out.println("The square of number is:"+b);  
  379.     }  
  380. }
  381. class Runnable2 implements Runnable
  382. {
  383.     public void run()
  384. {
  385.         Scanner in=new Scanner(System.in);
  386.         System.out.println("Enter number to find cube");
  387.         int c=in.nextInt();
  388.         int d=c*c*c;
  389.         System.out.println("The cube of number is:"+d);
  390.     }    
  391. }
  392. class Runnable3 implements Runnable
  393. {
  394.     int n,i;
  395.     public void run()
  396.     {
  397.         Scanner in=new Scanner(System.in);
  398.         Random rand=new Random();
  399.         n=rand.nextInt(50);
  400.         System.out.println("\nEnter the number of elements");
  401.         n=in.nextInt();
  402.         int arr[]=new int[n];
  403.         for(i=0;i<n;i++)
  404.         arr[i]=rand.nextInt(50);
  405.         System.out.println("\nthe random elements are ");
  406.         for(i=0;i<n;i++)
  407.         System.out.println(arr[i]+" ");
  408.     }
  409. }
  410.  
  411. ----------------------------------------------------------------------------------------------------------------------------                                                                                                                                 
  412.                                                             Program 4
  413. ----------------------------------------------------------------------------------------------------------------------------
  414.  
  415. package sort;
  416. import java.util.Random;
  417. import java.util.Scanner;
  418.  
  419. public class QuickSort
  420. {
  421.     static int max=50000;
  422.     public static int partition(int a[],int low,int high)
  423.     {  
  424.     int i,j,temp,key;
  425.     key=a[low];
  426.     i=low;
  427.     j=high+1;
  428.     while(i<=j)
  429.     {
  430.         do
  431.             i++;
  432.         while (key>=a[i]&& i<=high);
  433.         do
  434.             j--;
  435.         while(key<a[j]);
  436.         if(i<j)
  437.         {
  438.         temp=a[i];
  439.         a[i]=a[j];
  440.         a[j]=temp;
  441.         }
  442.     }
  443.     temp=a[low];
  444.     a[low]=a[j];
  445.     a[j]=temp;
  446.     return j;
  447. }
  448. public static void qs (int a[],int low, int high)
  449. {
  450.     int mid;
  451.     if(low<high)
  452.     {
  453.         mid=partition(a,low,high);
  454.         qs(a,low,mid-1);
  455.         qs(a,mid+1,high);
  456.     }
  457. }
  458. public static void main(String args[])
  459. {
  460.     int n,i;
  461.     Scanner in=new Scanner(System.in); 
  462.     Random rand=new Random();
  463.     System.out.println("Quicksort Test");
  464.     /* Accept no.of Elements */
  465.     System.out.println("\nEnter the number of elements");
  466.     n=in.nextInt();
  467.     /* create array of n elements */
  468.     int arr[]=new int[max];
  469.     try{
  470.     /* Generate Random Numbers */
  471.     for(i=0;i<n;i++)
  472.     arr[i]=rand.nextInt(100);
  473.     /* Print random numbers */
  474.     System.out.println("\nthe random elements are ");
  475.     for(i=0;i<n;i++)
  476.     System.out.println(arr[i]+" ");
  477.     long start_time=System.nanoTime();
  478.     /*call method Quick Sort*/
  479.     qs(arr,0,n-1);
  480.     long end_time=System.nanoTime();
  481.     /* Print Sorted Array */
  482.     System.out.println("\nThe Elements After sorting");
  483.     for(i=0;i<n;i++)
  484.     System.out.println(arr[i]+" ");
  485.     long t=end_time - start_time;
  486.     System.out.println(“Time taken for execution is:”+t+” nanoseconds);
  487.     }
  488.     catch(ArrayIndexOutOfBoundsException ae)
  489.     {
  490.         System.out.println("Array Index reached maximum ");
  491.     }
  492.     }
  493. }
  494.  
  495.  
  496. ----------------------------------------------------------------------------------------------------------------------------                                                                                                                                 
  497.                                                             Program 5
  498. ----------------------------------------------------------------------------------------------------------------------------
  499.  
  500. package sort1;
  501. import java.util.Random;
  502. import java.util.Scanner;
  503.  
  504. public class MergeSort
  505. {
  506. static int max=50000;
  507. public static void mergesort(int a[],int low,int high)
  508. {
  509.         int mid;
  510.         if(high>low)
  511.         {
  512.                mid=(low+high)/2;
  513.                mergesort(a,low,mid);
  514.                mergesort(a,mid+1,high);
  515.                merge(a,low,mid,high);
  516.          }
  517.   }
  518.  public static void merge(int a[],int low,int mid,int high)
  519.  { 
  520.           int k=low,j=mid+1,i=low;
  521.           int c[]=new int[1000];
  522.           while((i<=mid)&&(j<=high))
  523.           {
  524.                if(a[i]<=a[j])
  525.                {
  526.                       c[k]=a[i];
  527.                       i=i+1;
  528.                 }
  529.                else
  530.                 {
  531.                        c[k]=a[j];
  532.                        j=j+1;
  533.                  }
  534.              k=k+1;
  535.  }
  536. while(i<=mid)
  537. {
  538.       c[k]=a[i];
  539.       k=k+1;
  540.       i=i+1;
  541.  }
  542. while(j<=high)
  543.  {
  544.      c[k]=a[j];
  545.      k=k+1;
  546.      j=j+1;
  547. }
  548. for(i=low;i<=high;i++)
  549. a[i]=c[i];
  550. }
  551. public static void main(String args[] )
  552. {
  553.     int n,i;
  554.     Scanner in=new Scanner(System.in);
  555.     Random rand=new Random();
  556.     System.out.println("MergeSort Test");
  557.     /* Accept no.of Elements */
  558.     System.out.println("\nEnter the number of elements");
  559.     n=in.nextInt();
  560.     /* create array of n elements */
  561.     int arr[]=new int[max];
  562.     try{
  563.     /* Generate Random Numbers */
  564.     for(i=0;i<n;i++)
  565.     arr[i]=rand.nextInt(100);
  566.     /* Print random numbers */
  567.     System.out.println("\nthe random elements are ");
  568.     for(i=0;i<n;i++)
  569.     System.out.println(arr[i]+" ");
  570. long start_time=System.nanoTime();
  571.     /*call method merge Sort*/
  572.     mergesort(arr,0,n-1);
  573. long end_time=System.nanoTime();
  574.     /* Print Sorted Array */
  575.     System.out.println("\nThe Elements After sorting");
  576.     for(i=0;i<n;i++)
  577.     System.out.println(arr[i]+" ");
  578. long t=end_time - start_time;
  579.     System.out.println(“Time taken for execution is:”+t+” nanoseconds);
  580.     }
  581.     catch(ArrayIndexOutOfBoundsException ae)
  582.     {
  583.         System.out.println("Array Index reached maximum ");
  584.     }
  585.     }
  586. }
  587.  
  588. ----------------------------------------------------------------------------------------------------------------------------                                                                                                                                 
  589.                                                             Program 6 A
  590. ----------------------------------------------------------------------------------------------------------------------------
  591.  
  592. package knapsack;
  593. import java.util.Scanner;
  594. public class Knapsack1
  595. {
  596. private static int w[]=new int[10];
  597. private static int b[]=new int[10];
  598. private static int v[][]=new int[10][10];
  599. private static int value[]=new int[10];
  600. static int max(int a,int b)
  601. {
  602. return(a>b)?a:b;
  603.     }
  604.     static int knap(int i,int j)
  605.     {
  606.         if(i==0 || j==0)
  607.             v[i][j]=0;
  608.         elseif(j<w[i])
  609.             v[i][j]=knap(i-1,j);
  610.         else
  611.             v[i][j]=max(knap(i-1,j), value[i]+knap(i-1,j-w[i]));
  612.         returnv[i][j];
  613.     }
  614.     static void optimal(int i,int j)
  615.     {
  616.         if(i>=1 || j>=1)
  617.             if(v[i][j]!=v[i-1][j])
  618.             {
  619.                 System.out.println("Item:"+i);
  620.                 b[i]=1;
  621.                 j=j-w[i];
  622.                 optimal(i-1,j);
  623.             }
  624.             else
  625.                 optimal(i-1,j);
  626.     }
  627.     public static void main(String[] args)
  628. {
  629.         int profit, w1,n,i,j;
  630.         Scanner sc=new Scanner(System.in);
  631.         System.out.println("enter the number of items:");
  632.         n=sc.nextInt();
  633.         System.out.println("enter the capacity of the knapsack:");
  634.         w1=sc.nextInt();
  635.         System.out.println("enter the values:");
  636.         for(i=1;i<=n;i++)
  637.         value[i]=sc.nextInt();
  638.         System.out.println("enter the weights:");
  639.         for(i=1;i<=n;i++)
  640.         w[i]=sc.nextInt();
  641.         profit=knap(n,w1);
  642.         System.out.println("profit: "+profit);
  643.         System.out.println("\noptimal subset is:\n");
  644.         optimal(n,w1);
  645.         System.out.println("the solution vector is:");
  646.         for(i=1;i<=n;i++)
  647.         System.out.println(b[i]);
  648.        }
  649. }
  650.  
  651. ----------------------------------------------------------------------------------------------------------------------------                                                                                                                                 
  652.                                                             Program 6 B
  653. ----------------------------------------------------------------------------------------------------------------------------
  654.  
  655. package knapsack;
  656. import java.util.Scanner;
  657. public class Knapsack2
  658. {
  659. public static void knapsack(int n, int item[],float weight[], float profit[], float capacity)
  660. {
  661.         float tp = 0,u;
  662.         int i;
  663.         u =  capacity;
  664.         float x[]=new float[20];
  665.         for (i = 0; i < n; i++)
  666.         x[i] = (float) 0.0;
  667. for (i = 0; i < n; i++)
  668.  {
  669.       if (weight[i] > u)
  670.          break;
  671.       else {
  672.          x[i] = (float) 1.0;
  673.          tp = tp + profit[i];
  674.          u = (int) (u - weight[i]);
  675.       }
  676.    }
  677.  
  678.    if (i < n)
  679.       x[i] = u / weight[i];
  680.    tp = tp + (x[i] * profit[i]);
  681.    System.out.println("\nThe result vector is:- ");
  682.    for (i = 0; i < n; i++)
  683.       System.out.println("\tItem "+item[i]+":" +x[i]);
  684.    System.out.println("\nMaximum profit is:- " +tp);
  685. }
  686. public static void main(String[] args)
  687. {  
  688.    float weight[]=new float[20];
  689.    float profit[]=new float[20];
  690.    float capacity;
  691.    int num, i, j;
  692.    float ratio[]=new float[20], temp;
  693.    int item[]=new int[10];
  694.    Scanner in=new Scanner(System.in);  
  695.    System.out.println("\nEnter the no. of objects:- ");
  696.    num=in.nextInt();
  697.    System.out.println("\nEnter the the items, weights and profits of each object:- ");
  698.    for (i = 0; i < num; i++)
  699.   {
  700.         item[i]=in.nextInt();
  701.        weight[i]=in.nextFloat();
  702.        profit[i]=in.nextFloat();
  703.    }
  704.    System.out.println("\nEnter the capacityacity of knapsack:- ");
  705.    capacity=in.nextFloat();
  706.    for (i = 0; i < num; i++)
  707.    {
  708.       ratio[i] = profit[i] / weight[i];
  709.    }
  710.    for (i = 0; i < num; i++)
  711.   {
  712.        for (j = i + 1; j < num; j++)
  713.       {
  714.          if (ratio[i] < ratio[j])
  715.         {
  716.             temp = ratio[j];
  717.             ratio[j] = ratio[i];
  718.             ratio[i] = temp;
  719.  
  720.             temp = weight[j];
  721.             weight[j] = weight[i];
  722.             weight[i] = temp;
  723.  
  724.             temp = profit[j];
  725.             profit[j] = profit[i];
  726.             profit[i] = temp;
  727.  
  728.     temp=item[j];
  729.     item[j]=item[i];
  730.     item[i]=(int)temp;
  731.          }
  732.       }
  733.    }
  734.    knapsack(num, item,weight, profit, capacity);
  735. }
  736. }
  737.  
  738. ----------------------------------------------------------------------------------------------------------------------------                                                                                                                                 
  739.                                                             Program 7
  740. ----------------------------------------------------------------------------------------------------------------------------
  741.  
  742. package shortestpath;
  743. import java.util.Scanner;
  744. public class Dijkstra
  745. {
  746.     public static int findmin()
  747.     {
  748.         int i,n,min=0;
  749.         int d[]=new int[20];
  750.         int s[]=new int[20];
  751.         Scanner in=new Scanner(System.in);
  752.         n=in.nextInt();
  753.         for(i=1;i<=n;i++)
  754.         {
  755.             if(s[i]==0)
  756.             {
  757.                 min=i;
  758.                 break;
  759.              }
  760.         }
  761.          for(i=1;i<=n;i++)
  762.          {
  763.             if(d[i]<d[min] && s[i]==0)
  764.              min=i;
  765.         }
  766.         return min;
  767.     }
  768. public void dijkstra(int v,int w[][],int s[],int d[],int n)
  769.     {
  770.         int i,w1,u,k,j;
  771.         int p[]=new int[20];
  772.         for(i=1;i<=n;i++)
  773.         {
  774.             s[i]=0;
  775.             d[i]=999;
  776.     p[i]=0;
  777.         }
  778.     d[v]=0;
  779.         for(k=1;k<=n;k++)
  780.         {
  781.       u=findmin();
  782.       s[u]=1;
  783.             for(w1=1;w1<=n;w1++)
  784.             {
  785.                 if(w[u][w1]!=999 && s[w1]==0)
  786.                 {
  787.                     if(d[w1]>d[u]+w[u][w1])
  788.                     {
  789.                         d[w1]=d[u]+w[u][w1];
  790.                         p[w1]=u;
  791.                     }
  792.                 }
  793.             }
  794.         }
  795.         System.out.println("shortest path costs\n");
  796.         for(i=1;i<=n;i++)
  797.         {
  798.         if(d[i]==999)
  799.         System.out.println("sorry!  no path for source" + v + "to" + i + "vertex");
  800.         else
  801.         System.out.println("path cost from" +v+ "to" +i+ "is:" +d[i]+"\n");
  802.         }
  803.         System.out.println("shortest group of paths are\n");
  804.         for(i=1;i<=n;i++)
  805.         {
  806.             if(i!=v && d[i]!=999)
  807.             {
  808.                 System.out.print(i);
  809.                  j=p[i];
  810.                 while(p[j]!=0)
  811.                 {
  812.                     System.out.println("<----"+ j +" ");
  813.                     j=p[j];
  814.                 }
  815.                 System.out.println("<----"+ v +"\n");
  816.             }
  817.         }
  818.     }
  819.     public static void main(String args[])
  820.     {
  821.          int i,j,n,v;
  822.         int d[]=new int[20];
  823.         int s[]=new int[20];
  824.         int w[][]=new int[50][50];
  825.         Dijikstra d1 = new Dijikstra();
  826.         Scanner in=new Scanner(System.in);
  827.         System.out.println("enter the number of vertices\n");
  828.         n=in.nextInt();
  829.         System.out.println("enter the cost of vertices\n");
  830.         for(i=1;i<=n;i++)
  831.         for(j=1;j<=n;j++)
  832.         {
  833.             w[i][j]=in.nextInt();
  834.         }
  835.         System.out.println("enter the source vertex\n");
  836.         v=in.nextInt();
  837.           /* call Dijkstra method */
  838.         d1.dijkstra(v,w,s,d,n);
  839.      }
  840. }
  841. -------------------------------------------------------------------------------------------------
  842. PROG 8
  843. --------------------------------------------------------------------------------------------------
  844. import java.util.*;
  845. public class Kruskal
  846. {
  847.     static int parent[]=new int[10];
  848.     static int cost[][]=new int[10][10];
  849.     public static void main(String args[])
  850.     {
  851.         Scanner sn=new Scanner(System.in);
  852.         System.out.print("Enter the no. of vertices : ");
  853.         int n=sn.nextInt();
  854.         System.out.println("Enter the cost matrix : ");
  855.         for(int i=1;i<=n;i++)
  856.             for(int j=1;j<=n;j++)
  857.                 cost[i][j]=sn.nextInt();
  858.         kruskal(n);
  859.     }
  860.     public static void kruskal(int n)
  861.     {
  862.         int c=1,sum=0;
  863.         while(c<n)
  864.         {
  865.             int u=0,v=0,i=0,j=0;
  866.             int min=999;
  867.             for(i=1;i<=n;i++)
  868.                 for(j=1;j<=n;j++)
  869.                     if(cost[i][j]<min&&i!=j)
  870.                     {
  871.                         min=cost[i][j];
  872.                         u=i;
  873.                         v=j;
  874.                     }
  875.             i=find(u);
  876.             j=find(v);
  877.             if(i!=j)
  878.             {
  879.                 union(i,j);
  880.                 sum+=cost[u][v];
  881.                 System.out.println("(" + u + "," + v + ")" + "=" + cost[u][v]);
  882.                 c++;
  883.             }
  884.             cost[u][v]=cost[v][u]=999;
  885.         }
  886.         System.out.println("Minimum Cost: "+sum);
  887.     }
  888.     static int find(int p)
  889.     {
  890.         while(parent[p]!=0)
  891.             p=parent[p];
  892.         return p;
  893.     }
  894.     static void union(int i,int j)
  895.     {
  896.         if(i<j)
  897.             parent[i]=j;
  898.         else
  899.             parent[j]=i;
  900.     }
  901. }
  902. -------------------------------------------------------------------------------------------------
  903. PROG 9
  904. --------------------------------------------------------------------------------------------------
  905. import java.util.*;
  906. public class Prims
  907. {
  908.     public static void main(String args[])
  909.     {
  910.         int cost[][]=new int[10][10];
  911.         int vis[]=new int[10];
  912.         Scanner sn=new Scanner(System.in);
  913.         System.out.print("Enter the no. of vertices : ");
  914.         int n=sn.nextInt();
  915.         for(int i=1;i<=n;i++)
  916.             vis[i]=0;
  917.         System.out.println("Enter the cost matrix : ");
  918.         for(int i=1;i<=n;i++)
  919.             for(int j=1;j<=n;j++)
  920.                 cost[i][j]=sn.nextInt();
  921.         System.out.print("Enter the source vertex : ");
  922.         int source=sn.nextInt();
  923.         vis[source]=1;
  924.         int c=1,sum=0;
  925.         while(c<n)
  926.         {
  927.             int min=999;
  928.             int u=0,v=0;
  929.             for(int i=1;i<=n;i++)
  930.                 for(int j=1;j<=n;j++)
  931.                     if(vis[i]==1&&vis[j]==0)
  932.                         if(i!=j&&cost[i][j]<min)
  933.                         {
  934.                             min=cost[i][j];
  935.                             u=i;
  936.                             v=j;
  937.                         }
  938.             vis[v]=1;
  939.             c++;
  940.             sum+=min;
  941.             System.out.println(u + "->" + v + "=" + min);
  942.         }
  943.         for(int i=1;i<=n;i++)
  944.             if(vis[i]==0)
  945.             {
  946.                 System.out.println("No Spanning tree!!");
  947.                 System.exit(0);
  948.             }
  949.         System.out.println("The cost of minimum spanning tree is" + sum);
  950.     }
  951. }
  952. -------------------------------------------------------------------------------------------------
  953. PROG 10 A
  954. ----------------------------------------------------------------------------------------------------
  955. import java.util.*;
  956. public class Floyd
  957. {
  958.     static int cost[][]=new int[10][10];
  959.     public static void main(String args[])
  960.     {
  961.         Scanner sn=new Scanner(System.in);
  962.         System.out.print("Enter the no. of vertices : ");
  963.         int n=sn.nextInt();
  964.         System.out.println("Enter the cost matrix : ");
  965.         for(int i=1;i<=n;i++)
  966.             for(int j=1;j<=n;j++)
  967.                 cost[i][j]=sn.nextInt();
  968.         floyd(n);
  969.         System.out.println("The distance matrix : ");
  970.         for(int i=1;i<=n;i++)
  971.         {
  972.             for(int j=1;j<=n;j++)
  973.                 System.out.print(cost[i][j]+" ");
  974.             System.out.println();
  975.         }
  976.     }
  977.     public static void floyd(int n)
  978.     {
  979.         for(int k=1;k<=n;k++)
  980.             for(int i=1;i<=n;i++)
  981.                 for(int j=1;j<=n;j++)
  982.                     if(cost[i][j]>(cost[i][k]+cost[k][j]))
  983.                         cost[i][j]=cost[i][k]+cost[k][j];
  984.     }
  985. }
  986. ------------------------------------------------------------------------------------------------
  987. PROG 10 B
  988. -------------------------------------------------------------------------------------------------
  989. import java.util.*;
  990. public class tsp
  991. {
  992.     final static int MAX=100;
  993.     public static void main(String args[])
  994.     {
  995.         int cost[][]=new int[MAX][MAX];
  996.         int tour[]=new int[MAX];
  997.         Scanner sn=new Scanner(System.in);
  998.         System.out.print("Enter the no. of vertices : ");
  999.         int n=sn.nextInt();
  1000.         System.out.println("Enter the cost matrix : ");
  1001.         for(int i=1;i<=n;i++)
  1002.             for(int j=1;j<=n;j++)
  1003.                 cost[i][j]=sn.nextInt();
  1004.         for(int i=1;i<=n;i++)
  1005.             tour[i]=i;
  1006.         int min_cost=tsp_dp(cost,tour,1,n);
  1007.         System.out.println("Minimunm cost : "+min_cost+"\n\nTour : ");
  1008.         for(int i=1;i<=n+1;i++)
  1009.             System.out.print(tour[i]+" ");
  1010.     }
  1011.     public static int tsp_dp(int cost[][],int tour[],int start,int n)
  1012.     {
  1013.         int temp[]=new int[MAX];
  1014.         int mintour[]=new int[MAX];
  1015.         int mincost,ccost;
  1016.         if(start==n-1)
  1017.             return(cost[tour[n-1]][tour[n]]+cost[tour[n]][1]);
  1018.         mincost=999;
  1019.         for(int i=start+1;i<=n;i++)
  1020.         {
  1021.             for(int j=1;j<=n;j++)
  1022.                 temp[j]=tour[j];
  1023.             temp[start+1]=tour[i];
  1024.             temp[i]=tour[start+1];
  1025.             if(cost[tour[start]][tour[i]]+(ccost=tsp_dp(cost,temp,start+1,n))<mincost)
  1026.             {
  1027.                 mincost=ccost+cost[tour[start]][tour[i]];
  1028.                 for(int k=1;k<=n;k++)
  1029.                     mintour[k]=temp[k];
  1030.             }
  1031.         }
  1032.         int i;
  1033.         for(i=1;i<=n;i++)
  1034.             tour[i]=mintour[i];
  1035.         tour[i]=start;
  1036.         return mincost;
  1037.     }
  1038. }
  1039. ------------------------------------------------------------------------------------------------
  1040. PROG 11
  1041. --------------------------------------------------------------------------------------------------
  1042. import java.util.*;
  1043. public class subset
  1044. {
  1045.     public static void main(String args[])
  1046.     {
  1047.         int a[]=new int[10];
  1048.         int x[]=new int[10];
  1049.         int flag=0;
  1050.         Scanner s=new Scanner(System.in);
  1051.         System.out.print("Enter the number of elements in the set : ");
  1052.         int n=s.nextInt();
  1053.         System.out.println("Enter the elements : ");
  1054.         for(int i=1;i<=n;i++)
  1055.                 a[i]=s.nextInt();
  1056.         System.out.print("Enter the desired sum : ");
  1057.         int dsum=s.nextInt();
  1058.         for(int i=1;i<Math.pow(2,n);i++)
  1059.         {
  1060.             subset(i,n,x);
  1061.             int sum=0;
  1062.             for(int j=1;j<=n;j++)
  1063.                 if(x[j]==1)
  1064.                     sum+=a[j];
  1065.             if(sum==dsum)
  1066.             {
  1067.                 flag=1;
  1068.                 System.out.print("Subset : {");
  1069.                 for(int j=1;j<=n;j++)
  1070.                     if(x[j]==1)
  1071.                         System.out.print(a[j]+",");
  1072.                 System.out.println("} = "+sum);
  1073.             }
  1074.         }
  1075.         if(flag==0)
  1076.             System.out.println("No such subset found!!");
  1077.     }
  1078.     public static void subset(int num,int n,int x[])
  1079.     {
  1080.         for(int i=1;i<=n;i++)
  1081.             x[i]=0;
  1082.         for(int i=n;num!=0;i--)
  1083.         {
  1084.             x[i]=num%2;
  1085.             num/=2;
  1086.         }
  1087.     }
  1088. }
  1089. -------------------------------------------------------------------------------------------------
  1090. PROG 12
  1091. ------------------------------------------------------------------------------------------------
  1092. import java.util.*;
  1093. public class Hamiltonian
  1094. {
  1095.     static int x[]=new int[10];
  1096.     public static void main(String args[])
  1097.     {
  1098.         int adj[][]=new int[10][10];
  1099.         Scanner sn=new Scanner(System.in);
  1100.         System.out.print("Enter the no. of vertices : ");
  1101.         int n=sn.nextInt();
  1102.         System.out.println("Enter the 0/1 Adjacency matrix : ");
  1103.         for(int i=1;i<=n;i++)
  1104.             for(int j=1;j<=n;j++)
  1105.             {
  1106.                 adj[i][j]=sn.nextInt();
  1107.                 x[i]=0;
  1108.             }
  1109.         x[1]=1;
  1110.         System.out.println("Hamiltonian Cycles : ");
  1111.         hamiltonian(adj,n,2);
  1112.     }
  1113.     static void hamiltonian(int adj[][],int n,int k)
  1114.     {
  1115.         while(true)
  1116.         {
  1117.             nextval(adj,n,k);
  1118.             if(x[k]==0)
  1119.                 return;
  1120.             if(k==n)
  1121.             {
  1122.                 for(int i=1;i<=n;i++)
  1123.                 System.out.print(x[i]+" -> ");
  1124.                 System.out.println(x[1]);
  1125.             }
  1126.             else
  1127.                 hamiltonian(adj,n,k+1);
  1128.         }
  1129.     }
  1130.     static void nextval(int adj[][],int n,int k)
  1131.     {
  1132.         int i;
  1133.         while(true)
  1134.         {
  1135.             x[k]=(x[k]+1)%(n+1);
  1136.             if(x[k]==0)
  1137.                 return;
  1138.             if(adj[x[k-1]][x[k]]==1)
  1139.             {
  1140.                 for(i=1;i<k;i++)
  1141.                     if(x[i]==x[k])
  1142.                         break;
  1143.                 if(i==k)
  1144.                     if((k<n)||((k==n)&&(adj[x[n]][x[1]]==1)))
  1145.                         return;
  1146.             }
  1147.         }
  1148.     }
  1149. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top