CSC 207  Grinnell College  Spring, 2012 
Algorithms and ObjectOriented Design  
Load into Eclipse the java programs in the following directory:
cd ~walker/public_html/courses/207.sp12/labs/analysis
TestAnalysis.java is the main program that calls the other pieces (Loop1.java ... Loop8.java). TestAnalysis.java allows you to conduct experiments for the subsequent exercises.
The program uses commandline input.
To supply this information, select the "Run as Configurations..." option. Once the window comes up, be sure you have selcted TestAnalysis, and select the "Arguments" tab.
For example, to run the code for Exercise 1 with n=15, you would type
1 15in the arguments window, and then click "Run".
Note: In this lab, a variable NUMBER_REPETITIONS is specified to repeat a segment of code NUMBER_REPETITIONS^{2} times. This allows reasonable timings to be compared within the accuracy of the clock.
package analysis;
public class Loop1 {
public static int run(int n) {
int sum = 0;
for (int i=0 ; i < n ; i+=2)
sum++;
return sum;
}
}
Loop1
?package analysis;
public class Loop2 {
public static int run(int n) {
int sum = 0;
for (int i=0 ; i < n ; i++)
for (int j=0 ; j < n ; j++)
sum++;
return sum;
}
}
Loop2
?package analysis;
public class Loop3 {
public static int run(int n) {
int sum = 0;
for (int i=0 ; i < n ; i++)
sum++;
for (int j=0 ; j < n ; j++)
sum++;
return sum;
}
}
Loop3
?package analysis;
public class Loop4 {
public static int run(int n) {
int sum = 0;
for (int i=0 ; i < n ; i++)
for (int j=0 ; j < n * n ; j++)
sum++;
return sum;
}
}
Loop4
?package analysis;
public class Loop5 {
public static int run(int n) {
int sum = 0;
for (int i=0 ; i < n ; i++)
for (int j=0 ; j < i ; j++)
sum++;
return sum;
}
}
Loop5
?package analysis;
public class Loop6 {
public static int run(int n) {
int sum = 0;
for (int i=0 ; i < n ; i++)
for (int j=0 ; j < n * n ; j++)
for (int k=0 ; k < j ; k++)
sum++;
return sum;
}
}
Loop6
is still possible,
using the same formula as used in Exercise 5.b. Hazard a guess as
to the formula and predict the result for Loop6
?
package analysis;
public class Loop7 {
public static int run(int n) {
int sum = 0;
for (int i=1 ; i < n ; i = i * 2 )
sum++;
return sum;
}
}
Loop7
?package analysis;
public class Loop8 {
public static int run(int n) {
int sum = 0;
for (int i=1 ; i <= n ; i++)
for (int j=1 ; j <= i * i ; j++)
if ( j % i == 0)
for (int k=0; k < j ; k++ )
sum++;
return sum;
}
}
Loop8
?
IfIn this exercise, you will perform an analysis similar to Figure 5.13 (p. 189) in the book forF(N) is a tight answer for the running time, then the computed values converge to a positive constant. IfF(N) is an overestimate, the values converge to zero.
Loop6
. An OpenOffice
spreadsheet analysis.ods has been created
for you that will simply your bookkeeping and analysis process.
Loop6
and place these values (in increasing
order) and the results of running the procedure for those N
in the table.
Say we have an N×N matrix such that values are increasing from left to right in every row, and values are also increasing from top to bottom in every column. The following is an example:
1  2  4  6 
3  5  7  9 
4  8  11  13 
7  9  12  14 
This document is available on the World Wide Web as
http://www.walker.cs.grinnell.edu/courses/207.sp012/labs/labanalysis.shtml
Adapted from Mark Allen Weiss, Data Structures and Problem Solving Using Java, 3/e Exercises 5.15, 5.16, and 5.21 created 7 January 2009 by Jerod Weinman updated 23 February 2010 by Jerod Weinman revised 2728 February 2012 by Henry M. Walker 

For more information, please contact Henry M. Walker at walker@cs.grinnell.edu. 