Oct:31(Fri)

CS 163-01 Lab/Homework #_

Consider the following six program fragments:

1.     sum = 0;
       for ( i = 0; i < n; i++ )
           for ( j = 0; j < 100; j++ )
               sum++;
   

2.     sum = 0;
       for ( i = 0; i < n; i++ )
           for ( j = 0; j < n; j++ )
               sum++;
   

3.     sum = 0;
       for ( i = 0; i < n; i++ )
           for ( j = 0; j < n * n; j++ )
               sum++;
   

4.     sum = 0;
       for ( i = 0; i < n; i++ )
           for ( j = 0; j < i; j++ )
               sum++;
   

5.     sum = 0;
       for ( i = 0; i < n; i++ )
           for ( j = 0; j < i * i; j++ )
               for ( k = 0; k < j; k++ )
                   sum++;
   

6.     sum = 0;
       for ( i = 1; i < n; i++ )
           for ( j = 1; j < i * i; j++ )
               if ( j % i == 0 )
                   for ( k = 0; k < j; k++ )
                       sum++;
   

1. Give static analyses of the running times for each of these program fragments (in terms of n).
   Treat each of these program fragments separately.
2. Flesh out each of these six program fragments to make six complete Java programs.
   In each program, take a value for n as a command-line argument (rem. in Eclipse use Run...), and output the final value of sum.
3. Using script to record what you're doing, use time to time executions of each of your six programs here giving a range of values for n as follows:
   0. As indicated in lectures, what you need to type to time each execution is as follows:

          time java program_name value_for_n
      

      And among the three times reported by time, the one that is best for our purposes here is the one labeled "user".
   1. For the range of values for n, try powers of ten — 1,10,100,1000,10000,... — until the time of execution is over a minute.
      • Use control-C to interrupt an execution that takes more than 2 minutes.
   2. If a program's execution times jump too much using the powers of 10 for values for n (e.g. from 0.003s for n := 10, to 17s. for n := 100, to over 2 minutes requiring control-C for n := 1000), then do the following: by trial and error (and inference/interpolation), find a value for n that is a multiple of 8 and that yields a time between 30 seconds and 2 minutes, and then use the values n/8, n/4, n/2, and n.
   3. For each of your six programs here, make a table showing the values used for n, the ratio r_n between successive values used for n, the execution times, the ratios between successive execution times, and the integer powers of r_n — i.e.  values of the form (r_n)k — that are closest to the ratios between times.
      Do not include data from cases when you use control-C to interrupt execution.
      In cases when you have to use values {n/8, n/4, n/2, n}, use only the data for these values; i.e. in such cases, don't bother including data for other values that are powers of 10.
      Here's a sample table:

          values ratios
           used  of n-s           ratios       values (r_n)k
          for n   r_n     times  of times closest to ratios of times
          -----  ------ -------- -------- --------------------------
           100    N.A.    0.01s.   N.A.           N.A.
           200     2      0.13s.  13.00         16 == 24
           400     2      0.99s.   7.61          8 == 2³
           800     2      7.59s.   7.67          8 == 2³
          1600     2     61.34s.   8.08          8 == 2³
      

4. Compare your static analyses from part (a) with the actual performances that you determine in part (c).

[Acknowledgement: this exercise is derived from Mark Allen Weiss.]