Experiments in Java : Experiments for Session A3: Analyzing Algorithms

Note that different computers run at very different speeds. Your instructor may suggest that you use larger or smaller values in these experiments. (On faster computers, you may find that the times for these values are too short to measure well; on slower computers, you may spend too much time waiting for results based on these values.)

Experiment A3.1: Wall-clock timing

Step 1. Create a new class, Analyzer, that includes a main method with the following lines.

    SimpleOutput out = new SimpleOutput();
    RecursiveExamples helper = new RecursiveExamples();
    long start_time; // The time the algorithm started
    long end_time;   // The time the algorithm ended
    int tmp;         // The result of some algorithms
    int n;           // The argument to some algorithms
    n = 15;
    start_time = System.currentTimeMillis();
    tmp = helper.fib(n);
    end_time = System.currentTimeMillis();
    out.println("Fibonacci of " + n + " is " + tmp);
    out.println("  That computation took " + (end_time-start_time) + 
                " milliseconds.");

Compile and execute Analyzer. Record the output. Execute it three more times, recording the output each time. Are your times all the same? After writing your answer, you may want read our notes on the subject.

Step 2. Compare your times with those of a few of your classmates. How much variation did you see? Why might you have seen such variation?

Step 3. Update the main method to time the twentieth Fibonacci number. Execute it four times, recording the output each time. How do these times relate to those in the previous step? Is that what you would expect?

Step 4. You may be wondering why we use tmp in the previous code. Let's try eliminating it. Update your main method with the following lines.

    start_time = System.currentTimeMillis();
    out.println("Fibonacci of " + n + " is " + helper.fib(n));
    end_time = System.currentTimeMillis();
    out.println("  That computation took " + (end_time-start_time) + " milliseconds.");

Recompile Analyzer. Execute it four times, recording the output each time. Are these times similar to those from the previous step? If not, why might they be different?

Step 5. Instead of rerunning Analyzer each time we want to compute the running time of Fibonacci on a different input, we might read in that input. First, we need to create a SimpleInput object.

    SimpleInput in = new SimpleInput();

    start_time = System.currentTimeMillis();
    out.print("Enter n: ");
    n = in.readInt();
    out.println("Fibonacci of " + n + " is " + helper.fib(n));
    end_time = System.currentTimeMillis();
    out.println("  That computation took " + (end_time-start_time) + " milliseconds.");

Step 6. Recompile Analyzer. Execute it four times, entering 15 each time. Record the output. Do the times vary more or less than in the previous steps? Why?

Step 7. Rather than executing Analyzer repeatedly, it might be better to use a loop to do the repetition. Replace the appropriate lines of the main method with

    int repetitions;  // The number of times to time
    int i;            // A counter
    out.print("Enter n: ");
    n = in.readInt();
    out.print("Enter the number of repetitions: ");
    repetitions = in.readInt();
    for (i = 0; i < repetitions; ++i) {
      start_time = System.currentTimeMillis();
      tmp = helper.fib(n);
      end_time = System.currentTimeMillis();
      out.println("Fibonacci of " + n + " is " + tmp);
      out.println("  That computation took " + (end_time-start_time) + " milliseconds.");
    } // for

Recompile and execute Analyzer, using an input of 15. Execute Analyzer. Record and explain the output.

Experiment A3.2: Comparing wall-clock times

Step 1. Using Analyzer, determine the wall clock time it takes to compute 2^N, for N equal to 0, 1, 2, 3, and 4, using the iterative exponentiation function provided by RecursiveExamples.

Step 2. Using Analyzer, determine the wall clock time it takes to compute 2^N, for N equal to 0, 1, 2, 3, and 4, using the recursive exponentiation function provided by RecursiveExamples.

Step 3. Based on those results, which do you expect to be the more efficient algorithm? Why?

Step 4. Using Analyzer, determine the wall clock time it takes to compute 2^N, for N equal to 10, 20, 30, 40, and 100, using the iterative exponentiation function provided by RecursiveExamples.

Step 5. Using Analyzer, determine the wall clock time it takes to compute 2^N, for N equal to 10, 20, 30, 40, and 100, using the recursive exponentiation function provided by RecursiveExamples.

Experiment A3.3: Counting steps

    MeasuredFibonacci fibhelper = new MeasuredFibonacci();
    out.print("Enter n: ");
    n = in.readInt();
    fibhelper.resetCounter();
    out.println("Fibonacci of " + n + " is " + 
                fibhelper.fib(n));
    out.println("  That computation took " + 
                fibhelper.getCounter() + " steps");

Compile and execute Analyzer. Record the output. Execute it three more times, recording the output each time. Are your outputs the same? Is this what you expected, based on your experience?

Step 2. Compare your times with those of a few of your classmates. How much variation did you see? Is this what you expected?

Step 3. Add a for loop that allows you to repeatedly test the number of steps.

    int steps;
    int i;
    fibhelper.resetCounter();
    for (i = 0; i < steps; ++i) {
      out.println("Fibonacci of " + n + " is " + 
                  fibhelper.fib(n));
      out.println("  That computation took " + 
                  fibhelper.getCounter() + " steps");
    } // for

Step 4. Determine the number of steps used in computing the Nth Fibonacci number, for each N from 1 to 10.

Step 5. Update MeasuredFibonacci so that it only counts the number of times the base case (N is 1 or 2) is used. Determine the number of steps used in computing the Nth Fibonacci number, for each N from 1 to 10.

Experiment A3.4: Comparing steps

Step 1. Create a new class, ExpMeasurer with a main method with the following lines.

    // Prepare for reading input and writing output.
    SimpleInput in = new SimpleInput();
    SimpleOutput out = new SimpleOutput();
    // Build something that can measure steps for exponentiation.
    MeasuredExponentiation measurer = new MeasuredExponentiation()
    // The values we will use.
    int n;
    double x;

    // Get the values to use in computations.
    out.println("This program computes x^n in two ways and reports on " +
                "the number of steps in each computation.");
    out.println("Enter x: ");
    x = in.readDouble();
    out.println("Enter n: ");
    n = in.readInt();

    // Compute the exponent recursively, counting steps.
    measurer.resetCounter();
    out.println("Recursively: " + 
                x + "^" + n + " = " + measurer.recExp(x,n));
    out.println("  " + measurer.getCounter() + " steps");
    measurer.resetCounter();

    // Compute the exponent iteratively, counting steps.
    out.println("Iteratively: " + 
                x + "^" + n + " = " + measurer.itExp(x,n));
    out.println("  " + measurer.getCounter() + " steps");

Using ExpMeasurer, determine the number of steps it takes to compute 2^N, for N equal to 0, 1, 2, 3, and 4, using the iterative and recursive exponentiation functions.

Step 2. Based on those results, which do you expect to be the more efficient algorithm? Why?

Step 3. Using Analyzer, determine the number of steps it takes to compute 2^N, for N equal to 10, 20, 30, 40, and 100, using the iterative and recursive exponentiation functions provided by MeasuredExponentiation.

Experiment A3.5: Binary search

Step 1. Create a new class, SearchTester, with a main method that contains the following lines.

    // Prepare for reading input and generating output.
    SimpleInput in = new SimpleInput();
    SimpleOutput out = new SimpleOutput();
    // Prepare our sequence. 
    IntSeq seq = new IntSeq();
    // The value we're looking for
    int val;
    // The position of that value
    int pos;

    // Fill the sequence with the even numbers from 2 to 32.
    seq.fill(0,15,2,2);
    // Read a value and determine its position.
    out.print("Search for what value? ");
    val = in.readInt();
    // Search for the value, counting the steps.
    seq.resetSteps();
    pos = seq.binarySearch(val, evens);
    if (pos == -1) {
      out.println(val + " is not in the first sixteen even numbers");
    } // invalid position
    else {
      out.println(val + " falls at position " + pos);
    } // valid position
    out.println("Searching took " + seq.getSteps() + " steps");

Compile and execute SearchTester. How many steps does it take to determine whether 16 is in the array? 12? 1? 15? 0? Can you explain why?

Experiment A3.6: Finding the smallest element

Step 1. In the past, we've used internal fields to count the number of steps an algorithm takes. This introduces some overhead when we don't care about the number of steps. A more object-oriented solution would be to provide a separate Counter object that can be used for counting. Read the code for that class and explain what it does.

Step 2. Build a new version of the smallest method from IntSeq that takes a Counter as a parameter and uses that counter to count the steps it executes. Recompile IntSeq and correct any errors. Summarize your changes.

Step 3. Extend IntSeqTester so that it uses a Counter to count the steps in IntSeq's smallest method. Recompile IntSeqTester and correct any errors. Summarize your changes.

Step 4. Execute IntSeqTester and record the number of steps required to find the smallest element in lists of size 10, 20, 100, and 1000.

Experiment A3.7: Finding smaller elements

Step 1. Make copies of IntSeq.java and IntSeqTester.java. Compile them and execute IntSeqTester. Find the five smallest elements in a list of size 50. Record the results.

Step 2. Update IntSeq so that fiveSmallest, newFiveSmallest, and any methods they use take Counters as parameters and count their steps. Update IntSeqTester to call those methods with a Counter and print out the number of steps executed. Recompile both files and correct any errors. Summarize your changes.

Step 4. Update IntSeq and IntSeqTester to look for the seven smallest elements, rather than the five smallest elements. Fill in the table.

Step 5. Add kSmallest and newKSmallest methods to IntSeq. These will behave like fiveSmallest and newFiveSmallest so that they take k (the number of small elements to find) as a parameter. Recompile IntSeq and correct any errors. Summarize your changes.

Step 6. Update IntSeqTester so that it reads in the number of elements to find in the cases in which we want K small elements. Recompile IntSeqTester and correct any errors. Summarize your changes.

Step 7. Using your augmented IntSeqTester, record the number of steps for each of the following

Step 2. Repeat step 7 for the following table. In these cases you are selecting the top 10 percent of the list, while in step 7 you selected the top 1 percent.

Step 10. What do you conclude about the advantages of one strategy over the other?

[Front Door] [Introduction] [Code]

Source text last modified Mon Oct 25 22:16:59 1999.

This page generated on Tue Oct 26 15:37:47 1999 by Siteweaver.

Contact our webmaster at rebelsky@math.grin.edu