Due by 11:59pm on Thursday, July 13.

Starter Files

Download lab06.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the Ok autograder.

Most Questions Are Optional

There is only one required question on this lab, Q1: Pruning Leaves.

The rest of the questions in this assignment are not graded, but they are highly recommended to help you prepare for the upcoming exam. You will receive credit for this lab even if you do not complete the optional questions.

Required Questions

Trees

Q1: Pruning Leaves

Define a function prune_leaves that given a tree t and a tuple of values vals, produces a version of t with all its leaves that are in vals removed. Do not attempt to try to remove non-leaf nodes and do not remove leaves that do not match any of the items in vals. Return None if pruning the tree results in there being no nodes left in the tree.

def prune_leaves(t, vals):
    """Return a modified copy of t with all leaves that have a label
    that appears in vals removed.  Return None if the entire tree is
    pruned away.

    >>> t = tree(2)
    >>> print(prune_leaves(t, (1, 2)))
    None
    >>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
    >>> print_tree(numbers)
    1
      2
      3
        4
        5
      6
        7
    >>> print_tree(prune_leaves(numbers, (3, 4, 6, 7)))
    1
      2
      3
        5
      6
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q prune_leaves
Copy
✂️

Check Your Score Locally

You can locally check your score on each question of this assignment by running

python3 ok --score

This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

Submit

Make sure to submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. For a refresher on how to do this, refer to Lab 00.

Optional Questions

These questions are optional, but you must complete them in order to be checked off before the end of the lab period. They are also useful practice!

Control

Q2: Ordered Digits

Implement the function ordered_digits, which takes as input a positive integer and returns True if its digits, read left to right, are in non-decreasing order, and False otherwise. For example, the digits of 5, 11, 127, 1357 are ordered, but not those of 21 or 1375.

def ordered_digits(x):
    """Return True if the (base 10) digits of X>0 are in non-decreasing
    order, and False otherwise.

    >>> ordered_digits(5)
    True
    >>> ordered_digits(11)
    True
    >>> ordered_digits(127)
    True
    >>> ordered_digits(1357)
    True
    >>> ordered_digits(21)
    False
    >>> result = ordered_digits(1375) # Return, don't print
    >>> result
    False

    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q ordered_digits
Copy
✂️

Q3: K Runner

An increasing run of an integer is a sequence of consecutive digits in which each digit is larger than the last. For example, the number 123444345 has four increasing runs: 1234, 4, 4 and 345. Each run can be indexed from the end of the number, starting with index 0. In the example, the 0th run is 345, the first run is 4, the second run is 4 and the third run is 1234.

Implement get_k_run_starter, which takes in integers n and k and returns the 0th digit of the kth increasing run within n. The 0th digit is the leftmost number in the run. You may assume that there are at least k+1 increasing runs in n.

def get_k_run_starter(n, k):
    """Returns the 0th digit of the kth increasing run within n.
    >>> get_k_run_starter(123444345, 0) # example from description
    3
    >>> get_k_run_starter(123444345, 1)
    4
    >>> get_k_run_starter(123444345, 2)
    4
    >>> get_k_run_starter(123444345, 3)
    1
    >>> get_k_run_starter(123412341234, 1)
    1
    >>> get_k_run_starter(1234234534564567, 0)
    4
    >>> get_k_run_starter(1234234534564567, 1)
    3
    >>> get_k_run_starter(1234234534564567, 2)
    2
    """
    i = 0
    final = None
    while ____________________________:
        while ____________________________:
            ____________________________
        final = ____________________________
        i = ____________________________
        n = ____________________________
    return final

Use Ok to test your code:

python3 ok -q get_k_run_starter
Copy
✂️

Higher Order Functions

Q4: Make Repeater

Implement the function make_repeater so that make_repeater(func, n)(x) returns func(func(...func(x)...)), where func is applied n times. That is, make_repeater(func, n) returns another function that can then be applied to another argument. For example, make_repeater(square, 3)(42) evaluates to square(square(square(42))).

def make_repeater(func, n):
    """Returns the function that computes the nth application of func.

    >>> add_three = make_repeater(increment, 3)
    >>> add_three(5)
    8
    >>> make_repeater(triple, 5)(1) # 3 * 3 * 3 * 3 * 3 * 1
    243
    >>> make_repeater(square, 2)(5) # square(square(5))
    625
    >>> make_repeater(square, 4)(5) # square(square(square(square(5))))
    152587890625
    >>> make_repeater(square, 0)(5) # Yes, it makes sense to apply the function zero times!
    5
    """
    "*** YOUR CODE HERE ***"

For an extra challenge, try defining make_repeater using composer and your accumulate function in a single one-line return statement.

def composer(func1, func2):
    """Returns a function f, such that f(x) = func1(func2(x))."""
    def f(x):
        return func1(func2(x))
    return f

Use Ok to test your code:

python3 ok -q make_repeater
Copy
✂️

Q5: Apply Twice

Using make_repeater define a function apply_twice that takes a function of one argument as an argument and returns a function that applies the original function twice. For example, if inc is a function that returns 1 more than its argument, then apply_twice(inc) should be a function that returns two more:

def apply_twice(func):
    """Returns a function that applies func twice.

    func -- a function that takes one argument

    >>> apply_twice(square)(2)
    16
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q apply_twice
Copy
✂️

Q6: It's Always a Good Prime

Implement div_by_primes_under, which takes in an integer n and returns an n-divisibility checker. An n-divisibility-checker is a function that takes in an integer k and returns whether k is divisible by any integers between 2 and n, inclusive. Equivalently, it returns whether k is divisible by any primes less than or equal to n.

Review the Disc 01 is_prime problem for a reminder about prime numbers.

You can also choose to do the no lambda version, which is the same problem, just with defining functions with def instead of lambda.

Hint: If struggling, here is a partially filled out line for after the if statement:

checker = (lambda f, i: lambda x: __________)(checker, i)

def div_by_primes_under(n):
    """
    >>> div_by_primes_under(10)(11)
    False
    >>> div_by_primes_under(10)(121)
    False
    >>> div_by_primes_under(10)(12)
    True
    >>> div_by_primes_under(5)(1)
    False
    """
    checker = lambda x: False
    i = ____________________________
    while ____________________________:
        if not checker(i):
            checker = ____________________________
        i = ____________________________
    return ____________________________

def div_by_primes_under_no_lambda(n):
    """
    >>> div_by_primes_under_no_lambda(10)(11)
    False
    >>> div_by_primes_under_no_lambda(10)(121)
    False
    >>> div_by_primes_under_no_lambda(10)(12)
    True
    >>> div_by_primes_under_no_lambda(5)(1)
    False
    """
    def checker(x):
        return False
    i = ____________________________
    while ____________________________:
        if not checker(i):
            def outer(____________________________):
                def inner(____________________________):
                    return ____________________________
                return ____________________________
            checker = ____________________________
        i = ____________________________
    return ____________________________

Use Ok to test your code:

python3 ok -q div_by_primes_under
python3 ok -q div_by_primes_under_no_lambda
Copy
✂️

Environment Diagrams

Q7: Doge

Draw the environment diagram for the following code.

wow = 6

def much(wow):
    if much == wow:
        such = lambda wow: 5
        def wow():
            return such
        return wow
    such = lambda wow: 4
    return wow()

wow = much(much(much))(wow)

You can check out what happens when you run the code block using Python Tutor. Please ignore the “ambiguous parent frame” message on step 18. The parent is in fact f1.

Q8: YY Diagram

Draw the environment diagram that results from executing the code below.

Tip: Using the + operator with two strings results in the second string being appended to the first. For example "C" + "S" concatenates the two strings into one string "CS".

y = "y"
h = y
def y(y):
    h = "h"
    if y == h:
        return y + "i"
    y = lambda y: y(h)
    return lambda h: y(h)
y = y(y)(y)

You can check out what happens when you run the code block using Python Tutor.

Q9: Environment Diagrams - Challenge

These questions were originally developed by Albert Wu and are included here for extra practice. We recommend checking your work in PythonTutor after filling in the diagrams for the code below.

Challenge 1

Draw the environment diagram that results from executing the code below.

Guiding Notes: Pay special attention to the names of the frames!

Multiple assignments in a single line: We will first evaluate the expressions on the right of the assignment, and then assign those values to the expressions on the left of the assignment. For example, if we had x, y = a, b, the process of evaluating this would be to first evaluate a and b, and then assign the value of a to x, and the value of b to y.

def funny(joke):
    hoax = joke + 1
    return funny(hoax)

def sad(joke):
    hoax = joke - 1
    return hoax + hoax

funny, sad = sad, funny
result = funny(sad(1))

Challenge 2

Draw the environment diagram that results from executing the code below.

def double(x):
    return double(x + x)

first = double

def double(y):
    return y + y

result = first(10)

Recursion and Tree Recursion

Q10: Subsequences

A subsequence of a sequence S is a subset of elements from S, in the same order they appear in S. Consider the list [1, 2, 3]. Here are a few of it's subsequences [], [1, 3], [2], and [1, 2, 3].

Write a function that takes in a list and returns all possible subsequences of that list. The subsequences should be returned as a list of lists, where each nested list is a subsequence of the original input.

In order to accomplish this, you might first want to write a function insert_into_all that takes an item and a list of lists, adds the item to the beginning of each nested list, and returns the resulting list.

def insert_into_all(item, nested_list):
    """Return a new list consisting of all the lists in nested_list,
    but with item added to the front of each. You can assume that
     nested_list is a list of lists.

    >>> nl = [[], [1, 2], [3]]
    >>> insert_into_all(0, nl)
    [[0], [0, 1, 2], [0, 3]]
    """
    "*** YOUR CODE HERE ***"

def subseqs(s):
    """Return a nested list (a list of lists) of all subsequences of S.
    The subsequences can appear in any order. You can assume S is a list.

    >>> seqs = subseqs([1, 2, 3])
    >>> sorted(seqs)
    [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
    >>> subseqs([])
    [[]]
    """
    if ________________:
        ________________
    else:
        ________________
        ________________

Use Ok to test your code:

python3 ok -q subseqs
Copy
✂️

Q11: Non-Decreasing Subsequences

Just like the last question, we want to write a function that takes a list and returns a list of lists, where each individual list is a subsequence of the original input.

This time we have another condition: we only want the subsequences for which consecutive elements are nondecreasing. For example, [1, 3, 2] is a subsequence of [1, 3, 2, 4], but since 2 < 3, this subsequence would not be included in our result.

You may assume that the list passed in as s contains only nonnegative elements.

Fill in the blanks to complete the implementation of the non_decrease_subseqs function. You may assume that the input list contains no negative elements.

You may use the provided helper function insert_into_all, which takes in an item and a list of lists and inserts the item to the front of each list.

def non_decrease_subseqs(s):
    """Assuming that S is a list, return a nested list of all subsequences
    of S (a list of lists) for which the elements of the subsequence
    are strictly nondecreasing. The subsequences can appear in any order.

    >>> seqs = non_decrease_subseqs([1, 3, 2])
    >>> sorted(seqs)
    [[], [1], [1, 2], [1, 3], [2], [3]]
    >>> non_decrease_subseqs([])
    [[]]
    >>> seqs2 = non_decrease_subseqs([1, 1, 2])
    >>> sorted(seqs2)
    [[], [1], [1], [1, 1], [1, 1, 2], [1, 2], [1, 2], [2]]
    """
    def subseq_helper(s, prev):
        if not s:
            return ____________________
        elif s[0] < prev:
            return ____________________
        else:
            a = ______________________
            b = ______________________
            return insert_into_all(________, ______________) + ________________
    return subseq_helper(____, ____)

Use Ok to test your code:

python3 ok -q non_decrease_subseqs
Copy
✂️

Q12: Number of Trees

A full binary tree is a tree where each node has either 2 branches or 0 branches, but never 1 branch.

Write a function which returns the number of unique full binary tree structures that have exactly n leaves. See the doctests for visualizations of the possible full binary tree sturctures that have 1, 2, and 3 leaves.

Hint: A full binary tree can be constructed by connecting two smaller full binary trees to a root node. If the two smaller full binary trees have a and b leaves, the new full binary tree will have a + b leaves. For example, as shown in the first diagram below, a full binary tree with 4 leaves can be constructed by connecting a full binary tree that has three leaves (yellow) with a full binary tree that has one leaf (orange). A full binary tree with 4 leaves can also be constructed by connecting two full binary trees with 2 leaves each (second diagram)

For those interested in combinatorics, this problem does have a closed form solution):

def num_trees(n):
    """Returns the number of unique full binary trees with exactly n leaves. E.g.,

    1   2        3       3    ...
    *   *        *       *
       / \      / \     / \
      *   *    *   *   *   *
              / \         / \
             *   *       *   *

    >>> num_trees(1)
    1
    >>> num_trees(2)
    1
    >>> num_trees(3)
    2
    >>> num_trees(8)
    429

    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q num_trees
Copy
✂️

Lists

Q13: Remove Odd Indices

Complete the recursive function remove_odd_indices, which takes in a list lst and a boolean odd, and returns a new list with elements removed at certain indices. If odd is True, then the function should remove elements at odd indices; otherwise if odd is False, then the function should remove even indexed items.

Note: Remember that lists are zero-indexed; thus, the first element is at index 0, the second element is at index 1, etc. Also remember that you can put not in front of a boolean in order to get its opposite value.

Important: Use recursion; the tests will fail if you use any loops (for, while).

def remove_odd_indices(lst, odd):
    """Remove elements of lst that have odd indices. Use recursion!

    >>> s = [1, 2, 3, 4]
    >>> t = remove_odd_indices(s, True)
    >>> s
    [1, 2, 3, 4]
    >>> t
    [1, 3]
    >>> l = [5, 6, 7, 8]
    >>> m = remove_odd_indices(l, False)
    >>> m
    [6, 8]
    >>> remove_odd_indices([9, 8, 7, 6, 5, 4, 3], False)
    [8, 6, 4]
    >>> remove_odd_indices([2], False)
    []
    >>> # Do not use while/for loops!
    >>> from construct_check import check
    >>> # ban iteration
    >>> check(HW_SOURCE_FILE, 'remove_odd_indices',
    ...       ['While', 'For'])
    True
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q remove_odd_indices
Copy
✂️

Q14: Subset Sum (from Su15 MT 1)

Implement the subset_sum(target, lst) function: given a target integer target and a list of integers lst, return True if it is possible to add together any of the integers in lst to get the target. For example, subset_sum(10, [-1, 5, 4, 6]) will return True (either -1 + 5 + 6 = 10 or 4 + 6 = 10), while subset_sum(4, [5, -2, 12]) will return False.

Note: an integer may appear multiple times in lst (for example, [2, 4, 2, 3]). An integer in lst can only be used once (for example, subset_sum(4, [2, 3]) is False because we can only use the 2 once).

def subset_sum(target, lst):
    """Returns True if it is possible to add some of the integers in lst
    to get target.

    >>> subset_sum(10, [-1, 5, 4, 6])
    True
    >>> subset_sum(4, [5, -2, 12])
    False
    >>> subset_sum(-3, [5, -2, 2, -2, 1])
    True
    >>> subset_sum(0, [-1, -3, 15])     # Sum up none of the numbers to get 0
    True
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q subset_sum
Copy
✂️

Mutability

Q15: Shuffle

Define a function shuffle that takes a sequence with an even number of elements (cards) and creates a new list that interleaves the elements of the first half with the elements of the second half.

To interleave two sequences s0 and s1 is to create a new sequence such that the new sequence contains (in this order) the first element of s0, the first element of s1, the second element of s0, the second element of s1, and so on.

Note: If you're running into an issue where the special heart / diamond / spades / clubs symbols are erroring in the doctests, feel free to copy paste the below doctests into your file as these don't use the special characters and should not give an "illegal multibyte sequence" error.

def card(n):
    """Return the playing card numeral as a string for a positive n <= 13."""
    assert type(n) == int and n > 0 and n <= 13, "Bad card n"
    specials = {1: 'A', 11: 'J', 12: 'Q', 13: 'K'}
    return specials.get(n, str(n))

def shuffle(cards):
    """Return a shuffled list that interleaves the two halves of cards.

    >>> shuffle(range(6))
    [0, 3, 1, 4, 2, 5]
    >>> suits = ['H', 'D', 'S', 'C']
    >>> cards = [card(n) + suit for n in range(1,14) for suit in suits]
    >>> cards[:12]
    ['AH', 'AD', 'AS', 'AC', '2H', '2D', '2S', '2C', '3H', '3D', '3S', '3C']
    >>> cards[26:30]
    ['7S', '7C', '8H', '8D']
    >>> shuffle(cards)[:12]
    ['AH', '7S', 'AD', '7C', 'AS', '8H', 'AC', '8D', '2H', '8S', '2D', '8C']
    >>> shuffle(shuffle(cards))[:12]
    ['AH', '4D', '7S', '10C', 'AD', '4S', '7C', 'JH', 'AS', '4C', '8H', 'JD']
    >>> cards[:12]  # Should not be changed
    ['AH', 'AD', 'AS', 'AC', '2H', '2D', '2S', '2C', '3H', '3D', '3S', '3C']
    """
    assert len(cards) % 2 == 0, 'len(cards) must be even'
    half = _______________
    shuffled = []
    for i in _____________:
        _________________
        _________________
    return shuffled

Use Ok to test your code:

python3 ok -q shuffle
Copy
✂️

Q16: Trade

In the integer market, each participant has a list of positive integers to trade. When two participants meet, they trade the smallest non-empty prefix of their list of integers. A prefix is a slice that starts at index 0.

Write a function trade that exchanges the first m elements of list first with the first n elements of list second, such that the sums of those elements are equal, and the sum is as small as possible. If no such prefix exists, return the string 'No deal!' and do not change either list. Otherwise change both lists and return 'Deal!'. A partial implementation is provided.

Hint: You can mutate a slice of a list using slice assignment. To do so, specify a slice of the list [i:j] on the left-hand side of an assignment statement and another list on the right-hand side of the assignment statement. The operation will replace the entire given slice of the list from i inclusive to j exclusive with the elements from the given list. The slice and the given list need not be the same length.

>>> a = [1, 2, 3, 4, 5, 6]
>>> b = a
>>> a[2:5] = [10, 11, 12, 13]
>>> a
[1, 2, 10, 11, 12, 13, 6]
>>> b
[1, 2, 10, 11, 12, 13, 6]

Additionally, recall that the starting and ending indices for a slice can be left out and Python will use a default value. lst[i:] is the same as lst[i:len(lst)], and lst[:j] is the same as lst[0:j].

def trade(first, second):
    """Exchange the smallest prefixes of first and second that have equal sum.

    >>> a = [1, 1, 3, 2, 1, 1, 4]
    >>> b = [4, 3, 2, 7]
    >>> trade(a, b) # Trades 1+1+3+2=7 for 4+3=7
    'Deal!'
    >>> a
    [4, 3, 1, 1, 4]
    >>> b
    [1, 1, 3, 2, 2, 7]
    >>> c = [3, 3, 2, 4, 1]
    >>> trade(b, c)
    'No deal!'
    >>> b
    [1, 1, 3, 2, 2, 7]
    >>> c
    [3, 3, 2, 4, 1]
    >>> trade(a, c)
    'Deal!'
    >>> a
    [3, 3, 2, 1, 4]
    >>> b
    [1, 1, 3, 2, 2, 7]
    >>> c
    [4, 3, 1, 4, 1]
    >>> d = [1, 1]
    >>> e = [2]
    >>> trade(d, e)
    'Deal!'
    >>> d
    [2]
    >>> e
    [1, 1]
    """
    m, n = 1, 1

    equal_prefix = lambda: ______________________
    while _______________________________:
        if __________________:
            m += 1
        else:
            n += 1

    if equal_prefix():
        first[:m], second[:n] = second[:n], first[:m]
        return 'Deal!'
    else:
        return 'No deal!'

Use Ok to test your code:

python3 ok -q trade
Copy
✂️

Data Abstraction

Acknowledgements. This interval arithmetic example is based on a classic problem from Structure and Interpretation of Computer Programs, Section 2.1.4.

Introduction. Alyssa P. Hacker is designing a system to help people solve engineering problems. One feature she wants to provide in her system is the ability to manipulate inexact quantities (such as measurements from physical devices) with known precision, so that when computations are done with such approximate quantities the results will be numbers of known precision. For example, if a measured quantity x lies between two numbers a and b, Alyssa would like her system to use this range in computations involving x.

Alyssa's idea is to implement interval arithmetic as a set of arithmetic operations for combining "intervals" (objects that represent the range of possible values of an inexact quantity). The result of adding, subtracting, multiplying, or dividing two intervals is also an interval, one that represents the range of the result.

Alyssa suggests the existence of an abstraction called an "interval" that has two endpoints: a lower bound and an upper bound. She also presumes that, given the endpoints of an interval, she can create the interval using data abstraction. Using this constructor and the appropriate selectors, she defines the following operations:

def str_interval(x):
    """Return a string representation of interval x."""
    return '{0} to {1}'.format(lower_bound(x), upper_bound(x))

def add_interval(x, y):
    """Return an interval that contains the sum of any value in interval x and
    any value in interval y."""
    lower = lower_bound(x) + lower_bound(y)
    upper = upper_bound(x) + upper_bound(y)
    return interval(lower, upper)

Q17: Interval Abstraction

Alyssa's program is incomplete because she has not specified the implementation of the interval abstraction. She has implemented the constructor for you; fill in the implementation of the selectors.

def interval(a, b):
    """Construct an interval from a to b."""
    assert a <= b, 'Lower bound cannot be greater than upper bound'
    return [a, b]

def lower_bound(x):
    """Return the lower bound of interval x."""
    "*** YOUR CODE HERE ***"

def upper_bound(x):
    """Return the upper bound of interval x."""
    "*** YOUR CODE HERE ***"

Use Ok to unlock and test your code:

python3 ok -q interval -u
python3 ok -q interval
Copy
✂️

Q18: Interval Arithmetic

After implementing the abstraction, Alyssa decided to implement a few interval arithmetic functions.

This is her current implementation for interval multiplication. Unfortunately there are some data abstraction violations, so your task is to fix this code before someone sets it on fire.

def mul_interval(x, y):
    """Return the interval that contains the product of any value in x and any
    value in y."""
    p1 = x[0] * y[0]
    p2 = x[0] * y[1]
    p3 = x[1] * y[0]
    p4 = x[1] * y[1]
    return [min(p1, p2, p3, p4), max(p1, p2, p3, p4)]

Use Ok to unlock and test your code:

python3 ok -q mul_interval -u
python3 ok -q mul_interval
Copy
✂️

Interval Subtraction

Using a similar approach as mul_interval and add_interval, define a subtraction function for intervals. If you find yourself repeating code, see if you can reuse functions that have already been implemented.

def sub_interval(x, y):
    """Return the interval that contains the difference between any value in x
    and any value in y."""
    "*** YOUR CODE HERE ***"

Use Ok to unlock and test your code:

python3 ok -q sub_interval -u
python3 ok -q sub_interval
Copy
✂️

Interval Division

Alyssa implements division below by multiplying by the reciprocal of y. A systems programmer looks over Alyssa's shoulder and comments that it is not clear what it means to divide by an interval that spans zero. Add an assert statement to Alyssa's code to ensure that no such interval is used as a divisor:

def div_interval(x, y):
    """Return the interval that contains the quotient of any value in x divided by
    any value in y. Division is implemented as the multiplication of x by the
    reciprocal of y."""
    "*** YOUR CODE HERE ***"
    reciprocal_y = interval(1/upper_bound(y), 1/lower_bound(y))
    return mul_interval(x, reciprocal_y)

Use Ok to unlock and test your code:

python3 ok -q div_interval -u
python3 ok -q div_interval
Copy
✂️

Q19: Par Diff

After considerable work, Alyssa P. Hacker delivers her finished system. Several years later, after she has forgotten all about it, she gets a frenzied call from an irate user, Lem E. Tweakit. It seems that Lem has noticed that the formula for parallel resistors can be written in two algebraically equivalent ways:

par1(r1, r2) = (r1 * r2) / (r1 + r2)

or

par2(r1, r2) = 1 / (1/r1 + 1/r2)

He has written the following two programs, each of which computes the parallel_resistors formula differently:

def par1(r1, r2):
    return div_interval(mul_interval(r1, r2), add_interval(r1, r2))

def par2(r1, r2):
    one = interval(1, 1)
    rep_r1 = div_interval(one, r1)
    rep_r2 = div_interval(one, r2)
    return div_interval(one, add_interval(rep_r1, rep_r2))

Lem points out that Alyssa's program gives different answers for the two ways of computing. Find two intervals r1 and r2 that demonstrate the difference in behavior between par1 and par2 when passed into each of the two functions.

Demonstrate that Lem is right. Investigate the behavior of the system on a variety of arithmetic expressions. Make some intervals r1 and r2, and show that par1 and par2 can give different results.

def check_par():
    """Return two intervals that give different results for parallel resistors.

    >>> r1, r2 = check_par()
    >>> x = par1(r1, r2)
    >>> y = par2(r1, r2)
    >>> lower_bound(x) != lower_bound(y) or upper_bound(x) != upper_bound(y)
    True
    """
    r1 = interval(1, 1) # Replace this line!
    r2 = interval(1, 1) # Replace this line!
    return r1, r2

Use Ok to test your code:

python3 ok -q check_par
Copy
✂️

Trees

Q20: Preorder

Define the function preorder, which takes in a tree as an argument and returns a list of all the entries in the tree in the order that print_tree would print them.

The following diagram shows the order that the nodes would get printed, with the arrows representing function calls.

Note: This ordering of the nodes in a tree is called a preorder traversal.

def preorder(t):
    """Return a list of the entries in this tree in the order that they
    would be visited by a preorder traversal (see problem description).

    >>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
    >>> preorder(numbers)
    [1, 2, 3, 4, 5, 6, 7]
    >>> preorder(tree(2, [tree(4, [tree(6)])]))
    [2, 4, 6]
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q preorder
Copy
✂️

Iterators and Generators

Q21: Repeated

Implement repeated, which takes in an iterator t and returns the first value in t that appears k times in a row.

Note: You can assume that the iterator t will have a value that appears at least k times in a row. If you are receiving a StopIteration, your repeated function is likely not identifying the correct value.

Your implementation should iterate through the items in a way such that if the same iterator is passed into repeated twice, it should continue in the second call at the point it left off in the first. An example of this behavior is in the doctests.

def repeated(t, k):
    """Return the first value in iterator T that appears K times in a row.
    Iterate through the items such that if the same iterator is passed into
    the function twice, it continues in the second call at the point it left
    off in the first.

    >>> s = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> repeated(s, 2)
    9
    >>> s2 = iter([10, 9, 10, 9, 9, 10, 8, 8, 8, 7])
    >>> repeated(s2, 3)
    8
    >>> s = iter([3, 2, 2, 2, 1, 2, 1, 4, 4, 5, 5, 5])
    >>> repeated(s, 3)
    2
    >>> repeated(s, 3)
    5
    >>> s2 = iter([4, 1, 6, 6, 7, 7, 8, 8, 2, 2, 2, 5])
    >>> repeated(s2, 3)
    2
    """
    assert k > 1
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q repeated
Copy
✂️

Q22: Hailstone

Write a generator function that outputs the hailstone sequence starting at number n.

Here's a quick reminder of how the hailstone sequence is defined:

1. Pick a positive integer n as the start.
2. If n is even, divide it by 2.
3. If n is odd, multiply it by 3 and add 1.
4. Continue this process until n is 1.

As an extra challenge, try writing a solution using recursion. Since hailstone returns a generator, you can yield from a call to hailstone!

def hailstone(n):
    """Yields the elements of the hailstone sequence starting at n.

    >>> for num in hailstone(10):
    ...     print(num)
    10
    5
    16
    8
    4
    2
    1
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q hailstone
Copy
✂️

Efficiency

Q23: Efficiency Practice

Choose the term that fills in the blank for the functions defined below: <function> runs in ____ time in the length of its input.

• Constant
• Logarithmic
• Linear
• Quadratic
• Exponential
• None of these

Assume that len runs in constant time and all runs in linear time in the length of its input. Selecting an element of a list by its index requires constant time. Constructing a range requires constant time.

def count_partitions(n, m):
    """Counts the number of partitions of a positive integer n, 
    using parts up to size m."""
    if n == 0:
        return 1
    elif n < 0:
        return 0
    elif m == 0:
        return 0
    else:
        with_m = count_partitions(n-m, m)
        without_m = count_partitions(n, m-1)
        return with_m + without_m

def is_palindrome(s):
    """Return whether a list of numbers s is a palindrome."""
    return all([s[i] == s[len(s) - i - 1] for i in range(len(s))])

def binary_search(lst, n):
    """Takes in a sorted list lst and returns the index where integer n
    is contained in lst. Returns -1 if n does not exist in lst."""
    low = 0
    high = len(lst)
    while low <= high:
        middle = (low + high) // 2
        if lst[middle] == n:
            return middle
        elif n < lst[middle]:
            high = middle - 1
        else:
            low = middle + 1
    return -1

The is_palindrome question was reformatted from question 6(d) on fall 2019's final.

Use Ok to test your understanding:

python3 ok -q efficiency_practice -u
Copy
✂️