# Lab 13: Final Review

*Due at 11:59pm on Friday, 08/03/2018.*

*Lab Check-in 7 questions here.*

## Starter Files

Download lab13.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the Ok autograder.

## Submission

By the end of this lab, you should have submitted the lab with
`python3 ok --submit`

. You may submit more than once before the
deadline; only the final submission will be graded.
Check that you have successfully submitted your code on
okpy.org.

- To receive credit for this lab, you must complete Questions 1-3 in lab13.py and lab13.scm and submit through OK.
- Question 4-8 are considered
**extra practice**. They can be found in the lab13_extra.py and lab13_extra.scm files. It is recommended that you complete them on your own time.

# Required Questions

## Mutable Functions

For a quick refresher on mutable functions, see Discussion 9.

This question is to be done in

`lab13.py`

.

### Q1: Efficient Count Change

Recall the `count_change`

function from earlier in the semester that takes in
some `amount`

and returns the number of ways to make change for `amount`

using
coins with denominations that are powers of two. We can simplify this problem
by introducing an additional parameter, `coins`

, a tuple of coin values with
which to count change:

```
def count_change(amount, coins=(50, 25, 10, 5, 1)):
"""
>>> count_change(7, (1, 2, 4, 8))
6
"""
if amount == 0:
return 1
elif amount < 0 or len(coins) == 0:
return 0
return count_change(amount, coins[1:]) + count_change(amount - coins[0], coins)
```

This function is quite slow on larger inputs, since it repeats the same
computation many times. For example, to find `count_change(7, (1, 2, 4, 8))`

,
we make recursive calls to `count_change(7, (2, 4, 8))`

and ```
count_change(6,
(1, 2, 4, 8))
```

. Both these calls make recursive calls to ```
count_change(6, (2,
4, 8))
```

, which will get computed twice! Draw out the recursive call tree to
convice yourself of this repeated call with the same arguments.

To speed things up, complete the implementation below for `make_count_change`

,
which returns a function that is equivalent to `count_change`

but is more
efficient. This more efficient version should only perform any computation it
has not seen before, i.e. for arguments that have never been passed in
previously. If it is called with a pair of arguments previously seen, then it
should just return the previously computed value. Once you are done, compare
the two versions on a large number such as 500 to make sure that your code is
faster than the original version.

```
def make_count_change():
"""Return a function to efficiently count the number of ways to make
change.
>>> cc = make_count_change()
>>> cc(500, (50, 25, 10, 5, 1))
59576
"""
computed = {}
def count_change(amount, coins=(50, 25, 10, 5, 1)):
if _________________________:
if amount == 0: return 1
elif _________________________:
elif amount < 0 or len(coins) == 0: return 0
elif (amount, coins) in computed:
return ____________________
return computed[(amount, coins)] else:
count = _____________________________ + _____________________________
count = count_change(amount, coins[1:]) + count_change(amount - coins[0], coins) ___________________________
computed[(amount, coins)] = count return count
return count_change
```

Use Ok to test your code:

`python3 ok -q make_count_change`

## Streams

For a quick refresher on streams, see Discussion 10.

This question is to be done in

`lab13.scm`

.

### Q2: Run-Length Encoding

Run-length encoding is a very simple data compression technique,
whereby runs of data are compressed and stored as a single value. A
*run* is defined to be a contiguous sequence of the same number. For
example, in the (finite) sequence

`1, 1, 1, 1, 1, 6, 6, 6, 6, 2, 5, 5, 5`

there are four runs: one each of 1, 6, 2, and 5. We can represent the same sequence as a sequence of two-element lists:

`(1 5), (6 4), (2 1), (5 3)`

Notice that the first element of each list is the number in a run, and the second element is the number of of times that number appears in the run.

We will extend this idea to streams. Write a function called `rle`

that takes
in a stream of data, and returns a corresponding stream of two-element lists,
which represents the run-length encoded version of the stream. You do not have
to consider compressing infinite runs.

```
scm> (define s (cons-stream 1 (cons-stream 1 (cons-stream 2 nil))))
s
scm> (define encoding (rle s))
encoding
scm> (car encoding) ; Run of number 1 of length 2
(1 2)
scm> (car (cdr-stream encoding)) ; Run of number 2 of length 1
(2 1)
scm> (stream-to-list (rle (list-to-stream '(1 1 2 2 2 3)))) ; See functions in lab13.scm
((1 2) (2 3) (3 1))
```

```
(define (rle s)
'YOUR-CODE-HERE
(define (track-run elem st len)
(cond ((null? st) (cons-stream (list elem len) nil))
((= elem (car st)) (track-run elem (cdr-stream st) (+ len 1)))
(else (cons-stream (list elem len) (rle st))))
)
(if (null? s)
nil
(track-run (car s) (cdr-stream s) 1)))
```

Use Ok to test your code:

`python3 ok -q rle`

## Tail Recursion

For a quick refresher on tail recursion, see Discussion 10.

This question is to be done in

`lab13.scm`

.

### Q3: Replicate

Write a tail-recursive function that returns a list with `x`

repeated `n`

times.

```
scm> (tail-replicate 3 10)
(3 3 3 3 3 3 3 3 3 3)
scm> (tail-replicate 5 0)
()
scm> (tail-replicate 100 5)
(100 100 100 100 100)
```

```
(define (tail-replicate x n)
'YOUR-CODE-HERE
(define (helper n so-far)
(if (= n 0) so-far
(helper (- n 1) (cons x so-far))))
(helper n '()))
```

Use Ok to test your code:

`python3 ok -q tail-replicate`

# Optional Questions

## Trees

For a quick refresher on trees, see Lab 9.

This question is to be done in

`lab13_extra.py`

.

### Q4: Prune Small

Complete the function `prune_small`

that takes in a `Tree`

`t`

and a
number `n`

and prunes `t`

mutatively. If `t`

or any of its branches
has more than `n`

branches, the `n`

branches with the smallest labels
should be kept and any other branches should be *pruned*, or removed,
from the tree.

```
def prune_small(t, n):
"""Prune the tree mutatively, keeping only the smallest
n branches of every tree node.
>>> t1 = Tree(6)
>>> prune_small(t1, 2)
>>> t1
Tree(6)
>>> t2 = Tree(6, [Tree(3), Tree(4)])
>>> prune_small(t2, 1)
>>> t2
Tree(6, [Tree(3)])
>>> t3 = Tree(6, [Tree(1), Tree(3, [Tree(1), Tree(2), Tree(3)]), Tree(5, [Tree(3), Tree(4)])])
>>> prune_small(t3, 2)
>>> t3
Tree(6, [Tree(1), Tree(3, [Tree(1), Tree(2)])])
"""
if t.is_leaf():
____________
return while ___________________________:
while len(t.branches) > n: largest = max(_______________, key=____________________)
largest = max(t.branches, key=lambda x: x.label) _________________________
t.branches.remove(largest) for __ in _____________:
for b in t.branches: ___________________
prune_small(b, n)
```

Use Ok to test your code:

`python3 ok -q prune_small`

## Scheme

For a quick refresher on Scheme, see Lab 07.

These questions are to be done in

`lab13_extra.scm`

.

### Q5: Compose All

Implement `compose-all`

, which takes a list of one-argument functions and
returns a one-argument function that applies each function in that list in turn
to its argument. For example, if `func`

is the result of calling `compose-all`

on a list of functions `(f g h)`

, then `(func x)`

should be equivalent to the
result of calling `(h (g (f x)))`

.

```
scm> (define (square x) (* x x))
square
scm> (define (add-one x) (+ x 1))
add-one
scm> (define (double x) (* x 2))
double
scm> (define composed (compose-all (list double square add-one)))
composed
scm> (composed 1)
5
scm> (composed 2)
17
```

```
(define (compose-all funcs)
'YOUR-CODE-HERE
(lambda (x)
(if (null? funcs)
x
((compose-all (cdr funcs)) ((car funcs) x)))))
```

Use Ok to test your code:

`python3 ok -q compose-all`

### Q6: Deep Map

Write the function `deep-map`

, which takes a function `fn`

and a nested list
`s`

. A nested list is a list where each element is either a number or a list
(e.g. `(1 (2) 3)`

where `1`

, `(2)`

, and `3`

are the elements). It returns a list
with identical structure to `s`

, but replacing each non-list element by the
result of applying `fn`

on it, even for elements within sub-lists. For example:

```
scm> (define (double x) (* 2 x))
double
scm> (deep-map double '(2 (3 4)))
(4 (6 8))
```

Assume that the input has no dotted (malformed) lists.

Hint: You can use the function`list?`

, which checks if a value is a list.

```
(define (deep-map fn s)
'YOUR-CODE-HERE
(cond ((null? s) s)
((list? (car s)) (cons (deep-map fn (car s))
(deep-map fn (cdr s))))
(else (cons (fn (car s))
(deep-map fn (cdr s))))))
```

Use Ok to test your code:

`python3 ok -q deep-map`

### Q7: Tally

Implement `tally`

, which takes a list of `names`

and returns a
list of pairs, one pair for each unique name in `names`

. Each pair should
contain a name and the number of times that the name appeared in `names`

. Each
name should appear only once in the output, and the names should be ordered by
when they first appear in `names`

.

Hint: Use the`eq?`

procedure to test if two names are the same.

```
scm> (tally '(james jen jemin john))
((james . 1) (jen . 1) (jemin . 1) (john . 1))
scm> (tally '(billy billy bob billy bob billy bob))
((billy . 4) (bob . 3))
scm> (tally '())
()
```

```
(define (tally names)
'YOUR-CODE-HERE
(map (lambda (name) (cons name (count name names))) (unique names)))
```

Hint: If you find the procedure getting too complicated, you may want to try implementing the`count`

and`unique`

helper procedures to use in your solution. You may also want to use`map`

and`filter`

in your solution.

```
; Implementing and using these helper procedures is optional. You are allowed
; to delete them.
(define (unique s)
'YOUR-CODE-HERE
(if (null? s) nil
(cons (car s)
(unique (filter (lambda (x) (not (eq? (car s) x))) (cdr s))))))
(define (count name s)
'YOUR-CODE-HERE
(if (null? s) 0
(+ (if (eq? name (car s)) 1 0)
(count name (cdr s)))))
```

Use Ok to test your code:

`python3 ok -q tally`

## More Tail Recursion

This question is to be done in

`lab13_extra.scm`

.

### Q8: Insert

Write a tail-recursive function that inserts a number `n`

into a non-empty
sorted list of numbers, `s`

.

Hint:Use the built-in Scheme function`append`

to concatenate two lists together.`scm> (append '(1 2) '(3 4)) (1 2 3 4) scm> (append '(2 4 6) '()) (2 4 6) scm> (append '() '(5 3 1)) (5 3 1)`

```
scm> (insert 1 '(2))
(1 2)
scm> (insert 5 '(2 4 6 8))
(2 4 5 6 8)
scm> (insert 1000 '(1 2 3 4 5 6))
(1 2 3 4 5 6 1000)
```

```
(define (insert n s)
'YOUR-CODE-HERE
(define (insert-help s so-far)
(cond ((null? s) (append so-far (cons n s)))
((< n (car s)) (append so-far (cons n s)))
(else (insert-help (cdr s) (append so-far (list (car s)))))))
(insert-help s nil))
```

Use Ok to test your code:

`python3 ok -q insert`

The Ok tests for this problem don't check whether your solution is tail-recursive! In order to check your understanding, you can run some manual tests with large input such as the following to ensure that your function use a constant number of frames:

`scm> (define big-list (tail-replicate 3 1000)) big-list scm> (define result (insert 4 big-list)) result scm> (define expected (append big-list (list 4))) expected scm> (equal? result expected) True`