Due by 11:59pm on Wednesday, February 25

Instructions

Download hw04.zip. Inside the archive, you will find a file called hw04.py, along with a copy of the ok autograder.

Submission: When you are done, submit the assignment to Gradescope. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on Gradescope. See Lab 0 for more instructions on submitting assignments.

Using Ok: If you have any questions about using Ok, please refer to this guide.

Readings: You might find the following references useful:

• Section 2.4

Grading: Homework is graded based on correctness. Each incorrect problem will decrease the total score by one point. This homework is out of 6 points.

Required Questions

Q1: Smoothing

The idea of smoothing a function is a concept used in signal processing among other things. If f is a one-argument function and dx is some small number, then the smoothed version of f is the function whose value at a point x is the average of f(x - dx), f(x), and f(x + dx). Write a function smooth that takes as input a function f and a value to use for dx and returns a function that computes the smoothed version of f. Do not use any def statements inside of smooth; use lambda expressions instead.

def smooth(f, dx):
    """Returns the smoothed version of f, g where

    g(x) = (f(x - dx) + f(x) + f(x + dx)) / 3

    >>> square = lambda x: x ** 2
    >>> round(smooth(square, 1)(0), 3)
    0.667
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q smooth
Copy
✂️

It is sometimes valuable to repeatedly smooth a function (that is, smooth the smoothed function, and so on) to obtain the n-fold smoothed function. Show how to generate the n-fold smoothed function, n_fold_smooth, of any given function using your smooth function and repeated function:

def repeated(f, n):
    """Returns a single-argument function that takes a value, x, and applies
    the single-argument function F to x N times.
    >>> repeated(lambda x: x*x, 3)(2)
    256
    """
    def h(x):
        for k in range(n):
            x = f(x)
        return x
    return h

As with smooth, use lambda expressions rather than def statements in the body of n_fold_smooth.

def n_fold_smooth(f, dx, n):
    """Returns the n-fold smoothed version of f

    >>> square = lambda x: x ** 2
    >>> round(n_fold_smooth(square, 1, 3)(0), 3)
    2.0
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q n_fold_smooth
Copy
✂️

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

Note: 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].

Important: The starter code has already implemented the part of the function that performs the swap using slice assignment. Your task is only to figure out the correct prefix lengths to swap.

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  # a's prefix [1,1,3,2] is replaced with b's prefix [4,3]
    [4, 3, 1, 1, 4]
    >>> b  # b's prefix [4,3] is replaced with a's prefix [1,1,3,2]
    [1, 1, 3, 2, 2, 7]
    >>> c = [3, 3, 2, 4, 1]
    >>> trade(b, c)  # No prefixes with equal sum
    'No deal!'
    >>> b  # b remains unchanged
    [1, 1, 3, 2, 2, 7]
    >>> c  # c remains unchanged
    [3, 3, 2, 4, 1]
    >>> trade(a, c)  # Trades 4+3+1=8 for 3+3+2=8
    '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)  # Trades 1+1=2 for 2=2
    '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
✂️

Q3: Filter

Write a function filter that takes in a list lst and condition, a one-argument function that returns either True or False, and mutates lst so that it only contains elements satisfying condition.

Hint: Avoid mutating the list as you are iterating through it as this may cause issues with iterating through all the elements.

def filter(condition, lst):
    """Filters lst with condition using mutation.
    >>> original_list = [5, -1, 2, 0]
    >>> filter(lambda x: x % 2 == 0, original_list)
    >>> original_list
    [2, 0]
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q filter
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 Assignment

Submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions.