Homework 1: Functions, Control, Higher-Order Functions
Due by 11:59pm on Tuesday, July 1
Instructions
Download hw01.zip.
Submission: When you are done, submit the assignment by uploading all code files you've edited 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:
Grading: Homework is graded based on
correctness. Each incorrect problem will decrease the total score by one point.
This homework is out of 2 points.
Getting Started Videos
These videos may provide some helpful direction for tackling the problems on this assignment.
To see these videos, you should be logged into your berkeley.edu email.
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 = _____
else:
f = _____
return f(a, b)Use Ok to test your code:
python3 ok -q a_plus_abs_bUse 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_checkQ2: Hailstone
Douglas Hofstadter's Pulitzer-prize-winning book, Gödel, Escher, Bach, poses the following mathematical puzzle.
- Pick a positive integer
nas the start. - If
nis even, divide it by 2. - If
nis odd, multiply it by 3 and add 1. - Continue this process until
nis 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
"""
"*** YOUR CODE HERE ***"
Hailstone sequences can get quite long! Try 27. What's the longest you can find?
Note that if
n == 1initially, 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 hailstoneCurious 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 + 1A 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
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q productQ4: 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
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q make_repeaterCheck Your Score Locally
You can locally check your score on each question of this assignment by running
python3 ok --scoreThis 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.