Espresso: A Concentrated Introduction to 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: Wall Time
  • Exercise 4: Experimental Analysis of exptFor
  • Exercise 5: Experimental Analysis of exptWhile
  • Exercise 6: Experimental Analysis of sequentialSearch
  • Exercise 7: Experimental Analysis of binarySearch

Required Code Files:

• Computer.java

Exercises

Exercise 0: Preparation

a. Create a package named username.analysis.

b. Make a copy of Computer.java.

c. Update that file to use your package name.

Exercise 1: Predicting Running Times

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

If you look at Computer.java, you will see that it contains four central methods:

• exptFor
• exptWhile
• sequentialSearch
• binarySearch

Look at the methods, and, for each, 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 Computer.java, you will see that it also contains a few bookkeeping methods, particularly reset, step, and steps.

Explain the purpose of those methods. You may also want to look at the main method to see how they are used.

Exercise 3: Wall Time

If you look at the main method, you'll see the lines

  alpha = System.currentTimeMillis();
  ...
  omega = System.currentTimeMillis();

Explain the purpose of those lines.

Exercise 4: Experimental Analysis of exptFor

a. Compile and run Computer.

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

c. Determine whether exptFor behaves as you expected.

Exercise 5: Experimental Analysis of exptWhile

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

b. Compile and run Computer.

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

d. Determine whether exptFor behaves as you expected.

Exercise 6: Experimental Analysis of sequentialSearch

a. Modify the main method of Computer 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 Computer.

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

d. Determine whether exptFor behaves as you expected.

Exercise 7: Experimental Analysis of binarySearch

a. Modify the main method of Computer 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 Computer.

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

d. Determine whether exptFor 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.