• API
• FAQ
• Tools
• Archive
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"
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.

Top