# Lab 13: Final Review

*Due at 11:59pm on Friday, 5/3/2019.*

## 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 2-3 in lab13.py and lab13.scm and submit through OK.
- Question 4-7 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.

## Checkoff 09

### Q1: Exam Check-In

How do you plan on organizing your time and studying for the final exam during RRR week? What are your weakest topics, and how are you going to tackle them?

# Required Questions

## Trees

For a quick refresher on Trees, see Lab 07.

This question is to be done in

`lab13.py`

.

### Q2: 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 n branches
of each node with the smallest label.
>>> 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)])])
"""
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 09.

This question is to be done in

`lab13.scm`

.

### Q3: 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`

# Optional Questions

## Tree Recursion

For a quick refresher on tree recursion, see Discussion 03.

This question is to be done in

`lab13_extra.py`

.

### Q4: Num Splits

Given a list of numbers `s`

and a target difference `d`

, how many
different ways are there to split `s`

into two subsets such that the
sum of the first is within `d`

of the sum of the second? The number of
elements in each subset can differ.

You may assume that the elements in `s`

are distinct and that `d`

is always non-negative.

Note that the order of the elements within each subset does not matter, nor does
the order of the subsets themselves. For example, given the list `[1, 2, 3]`

,
you should not count `[1, 2], [3]`

and `[3], [1, 2]`

as distinct splits.

Hint: If the number you return is too large, you may be double-counting somewhere. If the result you return is off by some constant factor, it will likely be easiest to simply divide/subtract away that factor.

```
def num_splits(s, d):
"""Return the number of ways in which s can be partitioned into two
sublists that have sums within d of each other.
>>> num_splits([1, 5, 4], 0) # splits to [1, 4] and [5]
1
>>> num_splits([6, 1, 3], 1) # no split possible
0
>>> num_splits([-2, 1, 3], 2) # [-2, 3], [1] and [-2, 1, 3], []
2
>>> num_splits([1, 4, 6, 8, 2, 9, 5], 3)
12
"""
"*** YOUR CODE HERE ***"
def difference_so_far(s, difference):
if not s:
if abs(difference) <= d:
return 1
else:
return 0
element = s[0]
s = s[1:]
return difference_so_far(s, difference + element) + difference_so_far(s, difference - element)
return difference_so_far(s, 0)//2
```

Use Ok to test your code:

`python3 ok -q num_splits`

## Linked Lists

For a quick refresher on Linked Lists, see Lab 07.

This question is to be done in

`lab13_extra.py`

.

### Q5: Insert

Implement a function `insert`

that takes a `Link`

, a `value`

, and an
`index`

, and inserts the `value`

into the `Link`

at the given `index`

.
You can assume the linked list already has at least one element. Do not
return anything -- `insert`

should mutate the linked list.

Note: If the index is out of bounds, you can raise an`IndexError`

with:`raise IndexError`

```
def insert(link, value, index):
"""Insert a value into a Link at the given index.
>>> link = Link(1, Link(2, Link(3)))
>>> print(link)
<1 2 3>
>>> insert(link, 9001, 0)
>>> print(link)
<9001 1 2 3>
>>> insert(link, 100, 2)
>>> print(link)
<9001 1 100 2 3>
>>> insert(link, 4, 5)
IndexError
"""
"*** YOUR CODE HERE ***"
if index == 0:
link.rest = Link(link.first, link.rest)
link.first = value
elif link.rest is Link.empty:
raise IndexError
else:
insert(link.rest, value, index - 1)
# iterative solution
def insert(link, value, index):
while index > 0 and link.rest is not Link.empty:
link = link.rest
index -= 1
if index == 0:
link.rest = Link(link.first, link.rest)
link.first = value
else:
raise IndexError
```

Use Ok to test your code:

`python3 ok -q insert`

## More Scheme

For a quick refresher on Scheme, see Lab 09.

All remaining questions are to be done in

`lab13_extra.scm`

.

## Streams

For a quick refresher on streams, see Lab 11.

### Q6: Cycles

In Scheme, it's possible to have a stream with cycles. That is, a stream may contain itself as part of the stream definition.

```
scm> (define s (cons-stream 1 (cons-stream 2 s)))
scm> (car s)
1
scm> (car (cdr-stream (cdr-stream s)))
1
scm> (eq? (cdr-stream (cdr-stream s)) s)
#t
```

Implement `has-cycle?`

, which returns whether a stream contains a cycle. You
may assume that the input is either a stream of some unknown finite length, or
is one that contains a cycle. You should implement and use the `contains?`

procedure in your solution. We have provided a skeleton for `has-cycle?`

; your
solution must fit on the lines provided.

Hint:A stream has a cycle if you see the same pair object more than once. The built-in procedure`eq?`

may be used to check if two expressions evaluate to the same object in memory.`scm> (define lst1 '(1 2 3)) lst1 scm> (define lst2 lst1) lst2 scm> (define lst3 '(1 2 3)) lst3 scm> (eq? lst1 lst2) #t scm> (eq? lst1 lst3) #f`

```
(define (has-cycle? s)
(define (pair-tracker seen-so-far curr)
(define (pair-tracker seen-so-far curr) (cond (_________________ ____________)
(cond ((null? curr) #f) (_________________ ____________)
((contains? seen-so-far curr) #t) (else _________________________))
(else (pair-tracker (cons curr seen-so-far) (cdr-stream curr)))) )
______________________________
(pair-tracker nil s))
(define (contains? lst s)
'YOUR-CODE-HERE
(cond ((null? lst) #f)
((eq? s (car lst)) #t)
(else (contains? (cdr lst) s))))
```

Use Ok to test your code:

`python3 ok -q has-cycle`

## Macros

For a quick refresher on macros, see Discussion 10.

### Q7: Switch

Define the macro `switch`

, which takes in an expression `expr`

and a list of pairs, `cases`

, where the first element of the pair
is some *value* and the second element is a single expression. `switch`

will evaluate the expression contained in the list
of `cases`

that corresponds to the value that `expr`

evaluates to.

```
scm> (switch (+ 1 1) ((1 (print 'a))
(2 (print 'b))
(3 (print 'c))))
b
```

You may assume that the value `expr`

evaluates to is always the first element of one of the pairs in `cases`

. Additionally, it
is ok if your solution evaluates `expr`

multiple times.

```
(define-macro (switch expr cases)
'YOUR-CODE-HERE
(cons 'cond
(map (lambda (case) (cons `(equal? ,expr (quote ,(car case))) (cdr case)))
cases)))
```

Use Ok to test your code:

`python3 ok -q switch`