Lab 14: Final Review (Optional Lab)
Due at 11:59pm on Friday, 8/6/2019.
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.
- This lab is not worth any credit, and is just here for you to get practice. Feel free to attempt any questions you want for practice. The solutions have also been released for you to look at
Trees
For a quick refresher on Trees, see Lab 09.
This question is to be done in
lab14.py
.
Q1: 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 10.
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))
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
Tree Recursion
For a quick refresher on tree recursion, see Discussion 03.
This question is to be done in
lab14.py
.
Q3: 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
lab14.py
.
Q4: 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
Streams
For a quick refresher on streams, see Discussion 10.
Q5: 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