Homework 2

Due by 11:59pm on Tuesday, 9/5

Instructions

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

Submission: When you are done, submit with python3 ok --submit. 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 okpy.org. 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:

The construct_check module is used in this assignment, which defines a function check. For example, a call such as

check("foo.py", "func1", ["While", "For", "Recursion"])

checks that the function func1 in file foo.py does not contain any while or for constructs, and is not an overtly recursive function (i.e., one in which a function contains a call to itself by name.)

Several doctests refer to these one-argument functions:

from operator import add, mul

def square(x):
    return x * x

def triple(x):
    return 3 * x

def identity(x):
    return x

def increment(x):
    return x + 1

Q1: Product

The summation(n, term) function from lecture adds up term(1) + ... + term(n). Write a similar product(n, term) function that returns term(1) * ... * term(n). Show how to define the factorial function in terms of product. Hint: try using the identity function for factorial.

def product(n, term):
    """Return the product of the first n terms in a sequence.

    n    -- a positive integer
    term -- a function that takes one argument

    >>> product(3, identity) # 1 * 2 * 3
    6
    >>> product(5, identity) # 1 * 2 * 3 * 4 * 5
    120
    >>> product(3, square)   # 1^2 * 2^2 * 3^2
    36
    >>> product(5, square)   # 1^2 * 2^2 * 3^2 * 4^2 * 5^2
    14400
    """
    "*** YOUR CODE HERE ***"

# The identity function, defined using a lambda expression!
identity = lambda k: k

def factorial(n):
    """Return n factorial for n >= 0 by calling product.

    >>> factorial(4)
    24
    >>> factorial(6)
    720
    >>> from construct_check import check
    >>> check(HW_SOURCE_FILE, 'factorial', ['Recursion', 'For', 'While'])
    True
    """
    "*** YOUR CODE HERE ***"
    return _______

Use Ok to test your code:

python3 ok -q product
python3 ok -q factorial

Q2: Make Adder with a Lambda

Implement the make_adder function below using a single return statement that returns the value of a lambda expression.

def make_adder(n):
    """Return a function that takes an argument K and returns N + K.

    >>> add_three = make_adder(3)
    >>> add_three(1) + add_three(2)
    9
    >>> make_adder(1)(2)
    3
    """
    "*** YOUR CODE HERE ***"
    return lambda ________________

Use Ok to test your code:

python3 ok -q make_adder