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:

Required Code Files:

## 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(log2n), some are O(n), some are O(n2), 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`

This page was generated by Siteweaver on Wed Apr 5 10:58:47 2006.
The source to the page was last modified on Wed Apr 5 10:58:45 2006.
This page may be found at `http://www.cs.grinnell.edu/~rebelsky/TAO/Labs/analysis.html`.

You may wish to validate this page's HTML ; ; Check with Bobby

Samuel A. Rebelsky
rebelsky@grinnell.edu