The TAO of Java

Laboratory: Algorithm Analysis

Summary: In this laboratory, you will have an opportunity to analyze some standard algorithms theoretically and experimentally.

Contents:

• Exercises
  • Exercise 0: Preparation
  • Exercise 1: Predicting Running Times
  • Exercise 2: Code Reading
  • Exercise 3: Code Reading, Revisited
  • Exercise 4: Experimental Analysis of exptFor
  • Exercise 5: Experimental Analysis of exptWhile
  • Exercise 6: Experimental Analysis of BigDecimal.pow
  • Exercise 7: Experimental Analysis of sequentialSearch
  • Exercise 8: Experimental Analysis of binarySearch

Required Code Files:

• Analyst.java
• AnalyzeExpt.java
• AnalyzeSearch.java
• Mathematician.java
• Searcher.java

Exercises

Exercise 0: Preparation

In this laboratory, you will use a package entitled username.analysis.

a. In a terminal window, type

/home/rebelsky/bin/tao analysis

You should see messages about files being copied to a temporary directory.

b. Start Eclipse.

c. In Eclipse, build a project named Temp from /home/username/CSC152/Temp.

d. In the Temp project, you should see a package named username.analysis. Drag that package to your Code project.

e. Delete the Temp project.

You can now work with the new package.

Exercise 1: Predicting Running Times

Make sure to do this exercise with at least one colleague!

If you look at Mathematician.java, you will see that it contains two central methods:

• exptFor
• exptWhile

You will also find that Searcher.java, contains two central methods:

• sequentialSearch
• binarySearch

Look at the methods, and, for each, consider which function best models the running time of that function. It is likely that you will find that some are O(log₂n), some are O(n), some are O(n²), and perhaps that some are best modeled by some other function.

Exercise 2: Code Reading

If you look again at Mathematician.java, you will see that it contains a field, a, of type Analyst. What does the purpose of this field seem to be?

You may also want to look at AnalyzeExpt to see how (or if) the field is used.

Exercise 3: Code Reading, Revisited

In AnalyzeExpt there are a set of nested loops. The innermost loop reads as follows

        for (int rep = 0; rep < REPETITIONS; rep++) {
          BigDecimal result = emily.exptFor(x,n);
        } // for

What seems to be the purpose of that inner loop. Note that you may want to look to see how REPETITIONS is used elsewhere.

Exercise 4: Experimental Analysis of exptFor

a. Compile and run AnalyzeExpt.

b. Sketch graphs of the results. (You should have two graphs, one for steps and one for time.)

c. Determine whether exptFor behaves as you expected.

d. Do you see differences between the count of steps and the count of time? If so, what accounts for those differences?

Exercise 5: Experimental Analysis of exptWhile

a. Modify the main method of TestExpt so that it tests exptWhile rather than exptFor.

b. Compile and run TestExpt.

c. Sketch graphs of the results. (You should have two graphs, one for steps and one for time.)

d. Determine whether exptWhile behaves as you expected.

Exercise 6: Experimental Analysis of BigDecimal.pow

As you may have noted, the BigDecimal package includes a pow method. Although you cannot determine the number of steps the method uses, you can check its running time. Do so.

Is the method better than or worse than exptWhile?

Exercise 7: Experimental Analysis of sequentialSearch

a. Modify the main method of AnalyzeSearch so that it tests sequentialSearch. Note that you'll need to create an array in which to search and to search for a variety of values. I'd recommend that you also try a variety of array sizes. You may find the randomArray method useful.

b. Compile and run AnalyzeSearch.

c. Sketch graphs of the results. (You should have two graphs, one for steps and one for time.)

d. Determine whether sequentialSearch behaves as you expected.

Exercise 8: Experimental Analysis of binarySearch

a. Modify the main method of AnalyzeSearch so that it tests binarySearch. Note that the arrays you create must be sorted in increasing order. You may find it useful to build a variant of randomArray for this purpose.

b. Compile and run AnalyzeSearch.

c. Sketch graphs of the results. (You should have two graphs, one for steps and one for time.)

d. Determine whether analyzeSearch behaves as you expected.

History

Wednesday, 16 March 2005 [Samuel A. Rebelsky]

• Created.

Monday, 31 October 2005 [Samuel A. Rebelsky]

• Updated code (significantly) and some of the questions.

Monday, 3 April 2006 [Samuel A. Rebelsky]

• Moved from Espresso to TAO.
• Began a new rewrite.

Wednesday, 5 April 2006 [Samuel A. Rebelsky]

• Moved code from one file to separate files.
• Rewrote to accomodate those changes.
• Rewrote code reading questions from scratch.
• Added question on BigDecimal.pow