# Lab 14: Final Review lab14.zip

Due by 11:59pm on Friday, December 6.

## Starter Files

Download lab14.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 lab14.py and lab14.scm and submit through OK.
• Questions 4-6 are considered extra practice. They can be found in the lab14extra.py and lab14extra.scm files. It is recommended that you complete them on your own time.

# Required Questions

## Trees

For a quick refresher on Trees, see Lab 05.

This question is to be done in `lab14.py`.

### Q1: Prune Min

Write a function that prunes a `Tree` `t` mutatively. `t` and its branches always have zero or two branches. For the trees with two branches, reduce the number of branches from two to one by keeping the branch that has the smaller label value. Do nothing with trees with zero branches.

Prune the tree from the bottom up. The result should be a linear tree.

``````def prune_min(t):
"""Prune the tree mutatively from the bottom up.

>>> t1 = Tree(6)
>>> prune_min(t1)
>>> t1
Tree(6)
>>> t2 = Tree(6, [Tree(3), Tree(4)])
>>> prune_min(t2)
>>> t2
Tree(6, [Tree(3)])
>>> t3 = Tree(6, [Tree(3, [Tree(1), Tree(2)]), Tree(5, [Tree(3), Tree(4)])])
>>> prune_min(t3)
>>> t3
Tree(6, [Tree(3, [Tree(1)])])
"""
if t.branches == []:
return
prune_min(t.branches)
prune_min(t.branches)
if (t.branches.label > t.branches.label):
t.branches.pop(0)
else:
t.branches.pop(1)``````

Use Ok to test your code:

``python3 ok -q prune_min``

## Scheme

For a quick refresher on Scheme, see Lab 9.

This question is to be done in `lab14.scm`.

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

## Streams

For a quick refresher on streams, see Discussion 11.

This question is to be done in `lab14_extra.scm`.

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

# Optional Questions

## Tree Recursion

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

This question is to be done in `lab14.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], ` and `, [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 
1
>>> num_splits([6, 1, 3], 1)  # no split possible
0
>>> num_splits([-2, 1, 3], 2) # [-2, 3],  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
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 `lab14_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``

## Macros

For a quick refresher on macros, see Discussion 11.

This question is to be done in `lab14_extra.scm`.

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