# Lab 13: Final Review lab13.zip

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))
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
"""
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``

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.

<1 2 3>
<9001 1 2 3>
<9001 1 100 2 3>
IndexError
"""
if index == 0:
raise IndexError
else:

# iterative solution
index -= 1
if index == 0:
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``