Lab 13: Final Review

Due at 11:59pm on Friday, 11/30/2018.

Lab Check-in 8 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 2-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.

Q1: Exam Check-In

Check in with an academic intern or TA about how you plan on preparing for the final exam.

  • What will you do differently that you didn't do for the midterms?
  • How will you organize all that time without any classes?
  • Do you have a list with all the resources you need to go through before test day (i.e., not just spamming practice exams but also Guerrilla worksheets, conceptual slides, etc)?
  • How will you make sure you don't get distracted when studying?
  • Other thoughts that come to mind?

    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_extra.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

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.

Q6: No Dots!

Implement the procedure nodots, which takes a nested list of numbers that may not be well-formed and returns a nested list with the same content and structure, but which does not have any dots when displayed. Lists are not well-formed if they do not properly terminate in a null list. In such cases, the list will print with a dot before the final item to indicate that its last two items are contained in a single pair. For example,

(cons 1 (cons 2 3))

would print as

(1 2 . 3)

for which nodots should substitute

(1 2 3)

You may find the built-in null? and pair? predicates useful.

(define (nodots s)
'YOUR-CODE-HERE
(define (dotted s) (and (pair? s) (not (or (pair? (cdr s)) (null? (cdr s)))))) (cond ((null? s) s) ((dotted s) (list (nodots (car s)) (cdr s))) ((pair? s) (cons (nodots (car s)) (nodots (cdr s)))) (else s)) ; Alternate solution (define (dotted s) (and (pair? s) (not (or (pair? (cdr s)) (null? (cdr s)))))) (define (car-number s) (not (pair? (car s)))) (cond ((null? s) s) ((and (dotted s) (car-number s)) (list (car s) (cdr s))) ((dotted s) (list (nodots (car s)) (cdr s))) ((and (pair? s) (car-number s) (cons (car s) (nodots (cdr s))))) ((pair? s) (cons (nodots (car s)) (nodots (cdr s))))) ; Alternate solution (cond ((null? s) nil) ((not (pair? s)) (list s)) ((pair? (car s)) (cons (nodots (car s)) (nodots (cdr s)))) (else (cons (car s) (nodots (cdr s)))) )
)

Use Ok to test your code:

python3 ok -q nodots

Streams

For a quick refresher on streams, see Discussion 10.

Q7: 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.

Q8: 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