# Laboratory: Analyzing Procedures

Summary: In this laboratory, you will explore the running time for a few algorithm variants.

## Preparation

a. Make a copy of `analysis-lab.scm`, which contains most of the procedures you will need for this lab.

b. Review the file to see what procedure are included. (You may find it easiest to look at the list provided by the Index button.

## Exercises

### Exercise 1: Manual Analysis

a. Add the following line to the beginning of `list-append` (immediately after the line containing the `lambda`).

```(write (list 'list-append front back)) (newline)
```

b. Determine how many times `list-append` is called when reversing a list of length seven using `list-reverse-1`.

c. Add the following line to the kernel of `list-reverse-2` (again, immediately after the line containing the `lambda`).

```(write (list 'kernel remaining reversed)) (newline)
```

d. Determine how many times the kernel is called when reversing a list of length seven using `list-reverse-2`.

e. Comment out the lines that you just added by prefixing them with a semicolon.

### Exercise 2: Automatic Analysis

a. Replace the `define` for `list-reverse-1` with `define\$`, as in the following.

```(define\$ list-reverse-1
(lambda (lst)
...))
```

b. Find out how many times `list-append` is called in reversing a list of seven elements by entering the following command in the interactions pane.

````>` `(analyze (list-reverse-1 (list 1 2 3 4 5 6 7)) list-append)`
```

c. Did you get the same answer as in the previous exercise? If not, why do you think you got a different result?

d. One potential issue is that we haven't told the analyst to include the recursive calls in `list-append`. We can do so by replacing `define` with `define\$` in the definition of `list-append`.

e. Once again, find out how many times `list-append` is called in reversing a list of seven elements by entering the following command in the interactions pane.

````>` `(analyze (list-reverse-1 (list 1 2 3 4 5 6 7)) list-append)`
```

f. Did you get the same answer as in exercise 1? If not, what difference do you see?

g. Replace the `define` in `list-reverse-2` with `define\$`.

h. Find out how many times `kernel` is called in reversing a list of seven elements by entering the following command in the interactions pane.

````>` `(analyze (list-reverse-2 (list 1 2 3 4 5 6 7)) kernel)`
```

i. Did you get the same answer as in exercise 1? If not, what difference do you see?

In the previous exercise, you considered only a single procedure in each case (`list-append` for `list-reverse-1`, `list-reverse-2-kernel` for `list-reverse-2`). Suppose we incorporate all of the other procedures. What effect does it have?

a. Find out how many total procedure calls are done in reversing a list of length seven, using `list-reverse-1`, with the following.

````>` `(analyze (list-reverse-1 (list 1 2 3 4 5 6 7)))`
```

b. How does that number of calls seem to relate to the number of calls to `list-append`?

c. Are there any procedures you're surprised to see?

d. Find out how many total procedure calls are done in reversing a list of length seven, using `list-reverse-2`, by entering the following command.

````>` `(analyze (list-reverse-2 (list 1 2 3 4 5 6 7)))`
```

e. How does that number of calls seem to relate to the number of calls to `kernel`?

f. Are there any procedures you're surprised to see?

### Exercise 4: Predicting Calls

a. Fill in the following chart to the best of your ability.

List Length rev1: Calls to `list-append` rev1: Total calls rev2: Calls to `kernel` rev2: Total calls
2
4
8
16

b. Predict what the entries will be for a list size of 32.

d. Write a formula for the columns, to the best of your ability.

### Exercise 5: The Brightest Color, Revisited

Here is a third version of `rgb-brightest`, which should already be in your program.

```(define rgb-brightest-3
(lambda (colors)
(let kernel ((brightest-so-far (car colors))
(remaining-colors (cdr colors)))
(if (null? remaining-colors)
brightest-so-far
(kernel (rgb-brighter brightest-so-far (car remaining-colors))
(cdr remaining-colors))))))
```

a. Find out how many steps this procedure takes on lists of length 2, 4, 8, and 16 in which the elements are arranged from lightest to darkest. (You may want to review the reading to see how we built lists of colors arranged from lightest to darkest.)

b. Find out how many steps this procedure takes on lists of length 2, 4, 8, and 16 in which the elements are arranged from darkest to lightest. (You can reverse the lists from the previous step to create these lists.)

c. Find out how many steps this procedure takes on lists of length 2, 4, 8, and 16 in which the elements are in no particular order.

d. Predict the number of steps this procedure will take on each kind of list, where the length is 32.

## For Those with Extra Time

### Extra 1: The Effects of Preconditions

Consider `rgb-brightest-4`, a variant of an efficient version of `rgb-brightest` that has additional error checking added.

```(define rgb-brightest-4
(lambda (colors)
(when (not (all-rgb? colors))
(error "rgb-brightest: expects a list of colors; received" colors))
(if (null? (cdr colors))
(car colors)
(rgb-brighter (car colors)
(rgb-brightest-4 (cdr colors))))))
```

a. Predict the number of calls to `rgb-brightest-4` in finding the brightest in a list of eight colors.

c. Predict the number of calls to `all-rgb?` in finding the brightest in a list of eight colors.

Rewrite `rgb-brightest-4` so that it continues to check preconditions, but precondition checking does not exact such a heavy penalty.
This work is licensed under a Creative Commons Attribution-NonCommercial 2.5 License. To view a copy of this license, visit `http://creativecommons.org/licenses/by-nc/2.5/` or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.