Solution Files

You can find the solutions in hw01.py.

Required Questions

Functions and Control

Q1: A Plus Abs B

Python's operator module contains two-argument functions such as add and sub for Python's built-in arithmetic operators. For example, add(2, 3) evalutes to 5, just like the expression 2 + 3.

Fill in the blanks in the following function to add a to the absolute value of b, without calling the abs function. You may not modify any of the provided code other than the two blanks.

def a_plus_abs_b(a, b):
    """Return a+abs(b), but without calling abs.

    >>> a_plus_abs_b(2, 3)
    5
    >>> a_plus_abs_b(2, -3)
    5
    >>> a_plus_abs_b(-1, 4)
    3
    >>> a_plus_abs_b(-1, -4)
    3
    """
    if b < 0:
        f = sub
    else:
        f = add
    return f(a, b)

Use Ok to test your code:

python3 ok -q a_plus_abs_b
Copy
✂️

Use Ok to run the local syntax checker (which checks that you didn't modify any of the provided code other than the two blanks):

python3 ok -q a_plus_abs_b_syntax_check

Q2: Hailstone

Douglas Hofstadter's Pulitzer-prize-winning book, Gödel, Escher, Bach, poses the following mathematical puzzle.

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.

The number n will travel up and down but eventually end at 1 (at least for all numbers that have ever been tried—nobody has ever proved that the sequence will terminate). Analogously, a hailstone travels up and down in the atmosphere before eventually landing on earth.

This sequence of values of n is often called a Hailstone sequence. Write a function that takes a single argument with formal parameter name n, prints out the hailstone sequence starting at n, and returns the number of steps in the sequence:

def hailstone(n):
    """Print the hailstone sequence starting at n and return its
    length.

    >>> a = hailstone(10)
    10
    5
    16
    8
    4
    2
    1
    >>> a
    7
    >>> b = hailstone(1)
    1
    >>> b
    1
    """
    length = 1
    while n != 1:
        print(n)
        if n % 2 == 0:
            n = n // 2      # Integer division prevents "1.0" output
        else:
            n = 3 * n + 1
        length = length + 1
    print(n)                # n is now 1
    return length

Hailstone sequences can get quite long! Try 27. What's the longest you can find?

Note that if n == 1 initially, then the sequence is one step long.
Hint: If you see 4.0 but want just 4, try using floor division // instead of regular division /.

Use Ok to test your code:

python3 ok -q hailstone
Copy
✂️

Curious about hailstone sequences? Take a look at this article:

• In 2019, there was a major development in understanding how the hailstone conjecture works for most numbers!

Higher-Order Functions

Several doctests refer to these functions:

from operator import add, mul

def square(x):
    return x * x

def identity(x):
    return x

def triple(x):
    return 3 * x

def increment(x):
    return x + 1

A previous version of this assignment included versions of these functions written with lambda expressions, which were slated to be covered in Monday's lecture videos. If you downloaded the old version of this assignment, you can pretend that square, identity, triple, and increment are defined as above. The code you need to write will be the same either way, and submitting an old version of the assignment will not affect your autograder score.

Q3: Product

Write a function called product that returns the product of the first n terms of a sequence. Specifically, product takes in an integer n and term, a single-argument function that determines a sequence. (That is, term(i) gives the ith term of the sequence.) product(n, term) should return term(1) * ... * term(n).

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

    n: a positive integer
    term: a function that takes an index as input and produces a term

    >>> 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
    >>> product(3, increment) # (1+1) * (2+1) * (3+1)
    24
    >>> product(3, triple)    # 1*3 * 2*3 * 3*3
    162
    """
    prod, k = 1, 1
    while k <= n:
        prod, k = term(k) * prod, k + 1
    return prod

Use Ok to test your code:

python3 ok -q product
Copy
✂️

Q4: Make Repeater

Implement the function make_repeater which takes a one-argument function f and a positive integer n. It returns a one-argument function so that make_repeater(f, n)(x) returns the value of f(f(...f(x)...)), in which f is applied n times to x. For example, make_repeater(square, 3)(5) squares 5 three times and returns 390625, just like square(square(square(5))).

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

    >>> 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, 3)(5) # square(square(square(5)))
    390625
    """
    def repeater(x):
        k = 0
        while k < n:
            x, k = f(x), k + 1
        return x
    return repeater

Use Ok to test your code:

python3 ok -q make_repeater
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.

[Optional] Exam Practice

Here are some related questions from past exams for you to try. These are optional. There is no way to submit them.

1. Fall 2019 MT1 Q3: You Again [Higher-Order Functions]
2. Fall 2021 MT1 Q1b: tik [Functions and Expressions]