Experiments for Session A3: Analyzing Algorithms

Name: ________________
ID:_______________

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

Required file:

• `RecursiveExamples.java`

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();
```

Then we add a line to read in the input. Here is one way to do it.

```    start_time = System.currentTimeMillis();
out.print("Enter n: ");
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: ");
out.print("Enter the number of repetitions: ");
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

Required file:

• `RecursiveExamples.java` (preferably as modified in the lab on recursion).

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

```N  Time
-  ----
1
2
3
4
```

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

```N  Time
-  ----
1
2
3
4
```

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 2N, for N equal to 10, 20, 30, 40, and 100, using the iterative exponentiation function provided by `RecursiveExamples`.

```N   Time(R) Time(I)
--- ------- -------
10
20
30
40
100
```

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

```N   Time
--- ----
10
20
30
40
100
```

Step 6. Do these new results change your opinion? Why or why not?

Experiment A3.3: Counting steps

Required file:

• `MeasuredFibonacci.java`

Step 1. Update the `main` method of `Analyzer` with the following lines:

```    MeasuredFibonacci fibhelper = new MeasuredFibonacci();
out.print("Enter n: ");
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
```

Recompile and execute `Analyzer`. Record and explain the output.

When you are done, read the notes on the subject.

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

```N       Nth Fib   Steps
--      -------   -----
1
2
3
4
5
6
7
8
9
10
```
What do you observe about these numbers?

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.

```N       Nth Fib   Steps
--      -------   -----
1
2
3
4
5
6
7
8
9
10
```

What do you observe about these numbers?

Experiment A3.4: Comparing steps

Required file:

• `MeasuredExponentiation.java`

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: ");
out.println("Enter n: ");

// 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 2N, for N equal to 0, 1, 2, 3, and 4, using the iterative and recursive exponentiation functions.

```N  Time(R) Time(I)
-  ------- -------
1
2
3
4
```

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 2N, for N equal to 10, 20, 30, 40, and 100, using the iterative and recursive exponentiation functions provided by `MeasuredExponentiation`.

```N   Time
--- ----
10
20
30
40
100
```

Step 4. Do these new results change your opinion? Why or why not?

Experiment A3.5: Binary search

Required files:

• `IntSeq.java`

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? ");
// 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?

After recording your answer, you may with to look at the notes on this problem.

Experiment A3.6: Finding the smallest element

Required files:

• `Counter.java`
• `IntSeq.java`
• `IntSeqTester.java`

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.

```10:

20:

100:

1000:

```
After recording your results, you may want to look at the notes on this step.

Experiment A3.7: Finding smaller elements

Required files:

• `IntSeq.java`
• `IntSeqTester.java`

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 `Counter`s 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 3. Use your modified `IntSeqTester` to fill in the following table.

```Steps to find the smallest five elements in a list of size N, using
the selection strategy and the better insertion strategy.

N          steps               steps
(selection)         (insertion)

500

1000

2000

```

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

```Steps to find the smallest seven elements in a list of size N, using
the selection strategy and the better insertion strategy.

N          steps               steps
(selection)         (insertion)

500

1000

2000

```

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

```Steps to find the smallest K elements in a list of size N, using
the selection strategy and the better insertion strategy.

K    N          steps               steps
(selection)         (insertion)

5   500

10  1000

15  2000

```

Step 8.

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.

```Steps to find the smallest K elements in a list of size N, using
the selection strategy and the better insertion strategy.

K    N          steps               steps
(selection)         (insertion)

25   250

50   500

100 1000

200 2000
```

Step 9.

Do those number match those theorized in the discussion? Why or why not?

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