Lab 14 - Final Review (Optional Lab)

Instructions: https://inst.eecs.berkeley.edu/~cs61a/su19/lab/lab14/

Solutions:

• Python: https://github.com/tomthestrom/cs61a/blob/master/lab/lab14/lab14.py

• Scheme: https://github.com/tomthestrom/cs61a/blob/master/lab/lab14/lab14.scm

Trees - 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 ___________________________:
        largest = max(_______________, key=____________________)
        _________________________
    for __ in _____________:
        ___________________

Q1: Solution

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 len(t.branches) > n:
        largest = max(t.branches, key=lambda x: x.label)
        t.branches.remove(largest)
    for b in t.branches:
        prune_small(b, n)

Scheme - 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

Q2: Solution

(define (compose-all funcs)
    (lambda (x) (if (null? funcs)
                    x
                    (
                     (compose-all (cdr funcs))
                     ((car funcs) x)
                     )
                )
      )
)

Linked Lists - 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

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 ***"

Q4: Solution

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:
        old_first = link.first
        link.first = value

        new_link = Link(old_first)
        new_link.rest = link.rest

        link.rest = new_link

    i = 1 
    
    while i <= index: 
        if link.rest is Link.empty:
            raise IndexError

        if i == index:
            new_link = Link(value)
            new_link.rest = link.rest
            link.rest = new_link
            break

        i += 1
        link = link.rest

Streams - 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)
    (cond (_________________ ____________)
          (_________________ ____________)
          (else _________________________))
    )
  ______________________________
)

(define (contains? lst s)
  'YOUR-CODE-HERE
)

Q5: Solution

(define (contains? lst s)
    (cond
        ((null? lst) #f)
        ((eq? (car lst) s) #t)
        (else (contains? (cdr lst) s))
        )
    )


(define (has-cycle? s)
  (define (pair-tracker seen-so-far curr)
    (cond ((null? curr) #f)
          ((contains? seen-so-far curr) #t)
          ;we basically create a list of pointers
          (else (pair-tracker (append seen-so-far (list curr)) (cdr-stream curr)))
    ))
  (pair-tracker (list s)  (cdr-stream s))
)