SHARE
TWEET

Untitled

a guest Oct 23rd, 2019 97 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /** COMP2009-ACE WEEK 3+4 - LAB - FORMATIVE EXERRCISE
  2.     Title:  Analysis of Algorithms
  3.     Author: Andrew Parkes
  4.    
  5.     This exercise is formative, so feel free to work together, but recommend to try it yourself first.
  6. */
  7. import java.util.Random;
  8. import java.lang.Math;
  9.  
  10. public class Main {
  11.    
  12.     /// used for counting primitive operations
  13.     static int c;
  14.     static Random rnd;
  15.  
  16.     /* Main method:  runs the experiments and prints results.
  17.    
  18.         You can (and should) change this as needed.
  19.        
  20.         E.g. You should change the maxN and maxRuns to values of your choice.
  21.         You may well also want to do more than just report the n,c from each run.
  22.         e.g. to collect and print more 'statistics' such as worst, best, average at each value of n.
  23.     */
  24.     public static void main(String[] a){
  25.        
  26.         int maxN = 10;   // CHANGE AS NEEDED
  27.         int numRuns = 5;  // CHANGE AS NEEDED
  28.        
  29.         rnd = new Random();
  30.  
  31.         for (int n = 1 ; n <= maxN ; n+=1 ) {
  32.             int[] A = new int[n];
  33.             double worst_case=0.0,best_case=Integer.MAX_VALUE,sum=0.0;
  34.             for (int run = 0 ; run < numRuns ; run++ ) {
  35.                 // initialise A with randomised values
  36.                 randInit(A);
  37.                 // reset the counter, c, run f, and report the count
  38.                 c=0;
  39.                 int out = p(A);
  40.                 //System.out.println(n + " " + c);
  41.                 // KEEP EXTRA STATISTICS AS NEEDED
  42.                 if (c>worst_case) worst_case=c;
  43.                 if (c<best_case) best_case=c;
  44.                 sum+=c;
  45.                
  46.             }
  47.             System.out.println(n+" "+worst_case+" "+best_case+" "+sum/numRuns);
  48.         }
  49.         // PROCESS/PRINT EXTRA STATISTICS AS NEEDED
  50.     }
  51.    
  52.     /*  This is the function 'p' that needs to be analysed.
  53.         It works on an integer array, 'A' with n elements.
  54.         You can think of it as a piece of 'legacy code' you are given and it is suspected to
  55.         be causing trouble, such as making the application program to be going slow.
  56.         You need to analyse its scaling behaviour and make other comments.
  57.         The "c += " fragments have been added to help, but are not intnded as part of the "p()" methof itself.  However, they are part of the annotated code and do run.
  58.        
  59.         Note in particular if the increment is in the body of the loop then it will run each time the body runs, and so you should not then directly include terms to account for the "Number of passes". Hence, it is a bit differnt from the lectures.
  60.  
  61.         NOTE: Do _NOT_ take this as an example of how to write good code!
  62.         Parts of it may be deliberately poor to illustrate useful points.
  63.  
  64.         DO NOT CHANGE THIS FUNCTION EXCEPT THE increments to the counter on the r.h.s. !!!
  65.        
  66.        
  67.     // My own counting solution
  68.         */
  69.     // static int p(int[] A) {
  70.     //  int n = A.length;                       c += 3; // 1. obtain A from address space, 2. obtain length of A, 3. assigning length of A to n
  71.     //     int[] B = new int[n];                c += 3; // 1. get value of n, instantiate a new integer array with the size equal to the value of n, 3. assign it to integer array B
  72.      
  73.     //  int sum = 0;                            c += 1; // 1. assignment of value
  74.     //  int max = 0;                            c += 1; // 1. assignment of value
  75.     //     for (int p=0; p < n; p++) {          c += 2*n; // 1. for loop 2. check for condition 3. run n times
  76.     //      int k = A[p];                       c += 3*n; // 1. get value for p, 2. index array A with p, 3. assign to int k, n = run n times
  77.     //      sum += k;                           c += 3*n; // 1. get value of k, 2. + value of k to value of sum, 3. assign total value to var sum, n = run n times
  78.     //      B[p] = sum;                         c += 4*n; // 1. get value of sum, 2. get value of p, 3. index array B[] with value of p, 4. assign to B[p], n = run n times
  79.     //      int m = 0;                          c += 1*n; // 1. initialize and assign m to 0
  80.     //      int s;                              c += 1*n; // 1. initialize var s
  81.     //      s = ( n%2 == 0 ? sum : k );         c += 0 ;
  82.     //      while ( s >= 2 ) {                  c += 0 ;
  83.     //          s /= 2;                         c += 0 ;
  84.     //          m++;                            c += 0 ;
  85.     //      }
  86.  
  87.     //      if ( m > max ) {                    c += 0 ;
  88.     //              max = m;                    c += 0 ;
  89.     //          }
  90.     //      }
  91.     //                                      c += 0; // for 'anything else'
  92.     //  A = B;                              c += 0;
  93.     //                                      c += 0; // for the 'return'
  94.     //  return max;
  95.     // }
  96.  
  97.     // TSN's primitive counting solution
  98.     // static int p(int[] A) {
  99.     //  int n = A.length;                       c += 2;
  100.     //     int[] B = new int[n];                c += (100+2)*n;
  101.     //  // new is expensive (lots of operations)
  102.  
  103.     //  int sum = 0;                            c += 1;
  104.     //  int max = 0;                            c += 1;
  105.     //     for (int p=0; p < n; p++) {          c += (n+1);
  106.     //      int k = A[p];                       c += 3*n;
  107.     //      sum += k;                           c += 2*n;
  108.     //      B[p] = sum;                         c += 3*n;
  109.     //      int m = 0;                          c += n;
  110.     //      int s;                              c += n;
  111.     //      s = ( n%2 == 0 ? sum : k );         c += 4*n ;
  112.     //      while ( s >= 2 ) {                  c += 2*n ;
  113.     //          s /= 2;                         c += 2*n*(Math.log((double) s) / Math.log((double) 2)) ;
  114.     //          m++;                            c += 2*n*(Math.log((double) s) / Math.log((double) 2)) ;
  115.     //      }
  116.  
  117.     //      if ( m > max ) {                    c += 2*n ;
  118.     //              max = m;                    c += n ;
  119.     //          }
  120.     //      }
  121.     //                                      c += 2*n; // for 'anything else'
  122.     //  A = B;                              c += 1;
  123.     //                                      c += 1; // for the 'return'
  124.     //  return max;
  125.     // }
  126.  
  127.         // log and n not needed as the code already loops this function for you,
  128.         // you dont have to account for the loops in calculating the operations
  129.         static int p(int[] A) {
  130.             int n = A.length;                       c += 2;
  131.             int[] B = new int[n];                   c += (100+2)*n;
  132.             // new is expensive (lots of operations)
  133.    
  134.             int sum = 0;                            c += 1;
  135.             int max = 0;                            c += 1;
  136.             for (int p=0; p < n; p++) {             c += (n+1);
  137.                 int k = A[p];                       c += 3;
  138.                 sum += k;                           c += 2;
  139.                 B[p] = sum;                         c += 3;
  140.                 int m = 0;                          c += 1;
  141.                 int s;                              c += 1;
  142.                 s = ( n%2 == 0 ? sum : k );         c += 4 ;
  143.                 while ( s >= 2 ) {                  c += 2 ;
  144.                     s /= 2;                         c += 2;
  145.                     m++;                            c += 2;
  146.                 }
  147.    
  148.                 if ( m > max ) {                    c += 2 ;
  149.                         max = m;                    c += n ;
  150.                     }
  151.                 }
  152.                                                 c += 2; // for 'anything else'
  153.             A = B;                              c += 1;
  154.                                                 c += 1; // for the 'return'
  155.             return max;
  156.         }
  157.    
  158.        
  159.     /* Used to initialise the array A.
  160.        You are expected to first do experiments using version exactly as below.
  161.     */
  162.     static void randInit(int[] A) {
  163.             int n = A.length;
  164.             for (int i = 0 ; i < n ; i++ ) {
  165.                 A[i] = 10*n + rnd.nextInt( n );
  166.             }
  167.         }
  168.        
  169.        
  170.     /* OPTIONAL: use these other versions in order to initialise the array, and get graphs that are more interesting.
  171.    
  172.        Used to initialise the array A.
  173.        You are expected to first do experiments using version exactly as below.
  174.     */
  175.     static void randInit_v2(int[] A) {
  176.             int n = A.length;
  177.             if (n%3 == 0) {
  178.                 for (int i = 0 ; i < n ; i++ ) {
  179.                     A[i] = 10*n + rnd.nextInt( n );
  180.                 }
  181.             }
  182.         }
  183.        
  184.    
  185.     /* Used to initialise the array A.
  186.        You are expected to report results using version exactly as below.
  187.        DO NOT CHANGE THIS FUNCTION!!!
  188.        (Unless you know what you are doing, e.g. for some "side experiments"
  189.         used to help you understand.)
  190.     */
  191.     static void randInit_v3(int[] A) {
  192.             int n = A.length;
  193.            
  194.             if (n%3 == 0) {
  195.                 for (int i = 0 ; i < n ; i++ ) {
  196.                     A[i] = 10*n + rnd.nextInt( n );
  197.                 }
  198.             }
  199.             else {
  200.                 for (int i = 0 ; i < n ; i++ ) {
  201.                     A[i] = 10 + rnd.nextInt(  Math.min( n, 100)   );
  202.                 }
  203.             }
  204.         }
  205.        
  206. }
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