- Assigned
- Wednesday, Nov 14, 2018
- Due
- Lab writeups are due at 10:30pm on the day of the next class meeting. For example, a Wednesday lab is due at 10:30pm on Friday. Each lab writeup will be announced at the end of class on a lab day.
- Summary
- In this laboratory, you will explore the running time for a few algorithm variants.

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

b. Review the file to see what procedures are included. You may find it easiest to look at the list provided by the (define …) menu.

`reverse`

procedure.a. Add counters for `list-append`

, `list-reverse-1`

, the kernel of
`list-reverse-2`

and any other things you think will be useful to count
as we analyze the various versions of `list-reverse`

. For example,

```
(define list-append-counter (counter-new "list-append"))
```

b. Add a line of code to each of those procedures so that it increments the appropriate counter. For example,

```
(define list-append
(lambda (front back)
(counter-increment! list-append-counter)
...))
```

c. Find out how many times `list-append`

is called in reversing a list of seven elements by entering the following commands in the interactions pane.

```
> (counter-reset! list-append-counter)
> (list-reverse-1 (iota 7))
> (counter-print list-append-counter)
```

d. Did you get the same answer as in self-check 3(c)? If not, why do you think you got a different result?

e. Find out how many times `kernel`

is called in reversing a list of
seven elements.

f. Did you get the same answer as in self-check 3(e)? If not, what difference do you see?

What if we also care about calls to `car`

, `cdr`

, and such? We’ll need
to create our own versions of those procedures, along with counters. As
a start, we might write:

```
(define car-counter (counter-new "car"))
(define cdr-counter (counter-new "cdr"))
(define cons-counter (counter-new "cons"))
(define null?-counter (counter-new "null?"))
(define list-counters (list car-counter cdr-counter cons-counter null?-counter))
(define $car
(lambda (lst)
(counter-increment! car-counter)
(car lst)))
(define $cdr
(lambda (lst)
(counter-increment! cdr-counter)
(cdr lst)))
(define $cons
(lambda (val lst)
(counter-increment! cons-counter)
(cons val lst)))
(define $null?
(lambda (val)
(counter-increment! null?-counter)
(null? val)))
```

We then have to update all of our calls to `car`

to use `$car`

instead. For example, here’s an updated definition of `list-reverse-1`

.

```
(define list-reverse-1
(lambda (lst)
(if ($null? lst)
null
(list-append (list-reverse-1 ($cdr lst)) (list ($car lst))))))
```

Unfortunately, we can’t quite do that for `list`

, because `list`

takes
a variable number of parameters. So, we might rewrite the `list-reverse-1`

procedure to more explicitly use `cons`

.

```
(define list-reverse-1
(lambda (lst)
(if ($null? lst)
null
(list-append (list-reverse-1 ($cdr lst))
($cons ($car lst) null)))))
```

a. Update the definition of `list-append`

so that it uses `$car`

,
`$cons`

, `$cdr`

, and `$null?`

.

b. Find out how many procedure calls are done for each procedure
in reversing a list of length seven, using `list-reverse-1`

, with the
following.

```
> (for-each counter-reset! list-counters)
> (list-reverse-1 (iota 7))
> (for-each counter-print list-counters)
```

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

?

c. Update `list-reverse-2`

and find out how many procedure calls
(including calls to `kernel`

) are made when we use that procedure to
reverse a list of length seven.

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

?

a. Fill in the following chart to the best of your ability. Note that
the total function calls should include calls to `car`

, `cdr`

, and the
rest.

List Length | rev1: Calls to `list-append` |
rev1: Total function calls | rev2: Calls to `kernel` |
rev2: Total function calls |
---|---|---|---|---|

2 | ||||

4 | ||||

8 | ||||

16 |

```
; rev-1 rev-1 rev-2 rev-2
; length l-a total kernel total
; 2
; 4
; 8
; 16
```

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

c. Check your results experimentally.

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

Here is a third version of `alphabetically-first`

, which should already
be in your definitions.

```
(define alphabetically-first-3
(lambda (strings)
(let kernel ([first-so-far (car strings)]
[remaining (cdr strings)])
(if (null? remaining)
first-so-far
(kernel (first-of-two first-so-far (car remaining))
(cdr remaining))))))
```

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 alphabetically first to alphabetically last.

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 alphabetically last to alphabetically first. (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.

e. Check your answer experimentally.

Consider `alphabetically-first-4`

, a variant of an efficient version of `alphabetically-first`

that has additional error checking added.

```
(define alphabetically-first-4
(lambda (strings)
(when (not (all-string? strings))
(error "alphabetically-first: expects a list of strings; received" strings))
(if (null? (cdr strings))
(car strings)
(first-of-two (car strings)
(alphabetically-first-4 (cdr strings))))))
```

a. Predict the number of calls to `alphabetically-first-4`

in finding
the alphabetically first in a list of eight strings.

b. Check your hypothesis.

c. Predict the number of calls to `all-string?`

in finding the
alphabetically first in a list of eight strings.

d. Check your hypothesis.

Rewrite `alphabetically-first-4`

so that it continues to check
preconditions, but precondition checking does not exact such a heavy
penalty.

Consider the problem of extracting successors of a particular element in a list of elements.

```
> (successors 'a (list 'b 'a 'c 'd 'a 'b 'd 'a 'b))
'(c b b)
```

There are a variety of approaches that students tend to use.

a. Some use direct recursion.

```
(define successors-1
(lambda (val lst)
(cond
[(or (null? lst) (null? (cdr lst)))
null]
[(equal? val (car lst))
(cons (car (cdr lst)) (successors-1 val (cdr lst)))]
[else
(successors-1 val (cdr lst))])))
```

b. Some make a list of pairs of element and successor, filter the list for those whose first element matches, and then take the cadr of the matching elements

```
(define successors-2
(lambda (val lst)
(let* ([pairs (map make-pair lst (append (cdr lst) (list "<end>")))]
[matches (filter (o (l-s equal? val) car) pairs)]
[result (map (o car cdr) matches)])
result)))
(define make-pair
(lambda (a b)
(cons a (cons b null))))
```

c. Some make a list of pairs of element and position, filter the list for those whose element matches, extract the indices, increment the indices, and then use list-ref to find the elements.

```
(define successors-3
(lambda (val lst)
(let* ([pairs (map make-pair lst (iota (length lst)))]
[matches (filter (o (l-s equal? val) car) pairs)]
[indices (map (o car cdr) matches)]
[result (map (o (l-s my-list-ref lst) increment) indices)])
result)))
(define my-list-ref
(lambda (lst index)
(if (zero? index)
(car lst)
(my-list-ref (cdr lst) (decrement index)))))
```

Determine experimentally how many calls to the core list procedures each
of these procedure does. You need only count the explicit calls to
`car`

, `cdr`

, and `cons`

, in each of the above.