Homework 2
Due at 11:59:59 pm on 2/12/2021.
⚠️ This content is archived as of March 2026 and is retained exclusively for reference. Find the most current offering here.
Instructions
Download hw02.zip. Inside the archive, you will find starter files for the questions in this homework, 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 this article for more instructions on okpy and submitting assignments.
Readings: This homework relies on following references:
To submit: run ok with the --submit option:
python3 ok --submitQuestions
Question 1: Fibonacci
The Fibonacci sequence is a famous sequence in mathematics. The first element in the sequence is 0 and the second element is 1. The nth element is defined as Fn = Fn-1 + Fn-2.
Implement the fib function, which takes an integer n and returns
the nth Fibonacci number. Use a while loop in your solution.
def fib(n):
"""Returns the nth Fibonacci number.
>>> fib(0)
0
>>> fib(1)
1
>>> fib(2)
1
>>> fib(3)
2
>>> fib(4)
3
>>> fib(5)
5
>>> fib(6)
8
>>> fib(100)
354224848179261915075
"""
"*** YOUR CODE HERE ***"Use OK to test your code:
python3 ok -q fibQuestion 2: Mul_by_num
Using higher order functions, complete the mul_by_num function. This
function should take an argument and return a one argument function
that multiplies any value passed to it by the original number.
def mul_by_num(factor):
"""
Returns a function that takes one argument and returns num
times that argument.
>>> x = mul_by_num(5)
>>> y = mul_by_num(2)
>>> x(3)
15
>>> y(-4)
-8
"""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python3 ok -q mul_by_numQuestion 3: This Question is so Derivative
Define a function make_derivative that returns a function: the derivative of a
function f. Assuming that f is a single-variable mathematical function, its
derivative will also be a single-variable function. When called with a number
a, the derivative will estimate the slope of f at point (a, f(a)).
Recall that the formula for finding the derivative of f at point a is:
where h approaches 0. We will approximate the derivative by choosing a very
small value for h. The closer h is to 0, the better the estimate of the
derivative will be.
def make_derivative(f):
"""Returns a function that approximates the derivative of f.
Recall that f'(a) = (f(a + h) - f(a)) / h as h approaches 0. We will
approximate the derivative by choosing a very small value for h.
>>> def square(x):
... # equivalent to: square = lambda x: x*x
... return x*x
>>> derivative = make_derivative(square)
>>> result = derivative(3)
>>> round(result, 3) # approximately 2*3
6.0
"""
h=0.00001
"*** YOUR CODE HERE ***"Use OK to test your code:
python3 ok -q make_derivativeQuestion 4: Count van Count
Consider the following implementations of count_factors and count_primes:
def count_factors(n):
"""Return the number of positive factors that n has."""
i, count = 1, 0
while i <= n:
if n % i == 0:
count += 1
i += 1
return count
def count_primes(n):
"""Return the number of prime numbers up to and including n."""
i, count = 1, 0
while i <= n:
if is_prime(i):
count += 1
i += 1
return count
def is_prime(n):
return count_factors(n) == 2 # only factors are 1 and nThe implementations look quite similar! Generalize this logic by writing a
function count_cond, which takes in a two-argument predicate function mystery_function(n,
i). count_cond returns a count of all the numbers from 1 to n that satisfy
condition.
Note: A predicate function is a function that returns a boolean (True or False).
def count_cond(mystery_function, n):
"""
>>> def divisible(n, i):
... return n % i == 0
>>> count_cond(divisible, 2) # 1, 2
2
>>> count_cond(divisible, 4) # 1, 2, 4
3
>>> count_cond(divisible, 12) # 1, 2, 3, 4, 6, 12
6
>>> def is_prime(n, i):
... return count_cond(divisible, i) == 2
>>> count_cond(is_prime, 2) # 2
1
>>> count_cond(is_prime, 3) # 2, 3
2
>>> count_cond(is_prime, 4) # 2, 3
2
>>> count_cond(is_prime, 5) # 2, 3, 5
3
>>> count_cond(is_prime, 20) # 2, 3, 5, 7, 11, 13, 17, 19
8
"""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python3 ok -q count_condQuestion 5: I Heard You Liked Functions...
Define a function cycle that takes in three functions f1, f2,
f3, as arguments. cycle will return another function that should
take in an integer argument n and return another function. That
final function should take in an argument x and cycle through
applying f1, f2, and f3 to x, depending on what n
was. Here's the what the final function should do to x for a few
values of n:
n = 0, returnxn = 1, applyf1tox, or returnf1(x)n = 2, applyf1toxand thenf2to the result of that, or returnf2(f1(x))n = 3, applyf1tox,f2to the result of applyingf1, and thenf3to the result of applyingf2, orf3(f2(f1(x)))n = 4, start the cycle again applyingf1, thenf2, thenf3, thenf1again, orf1(f3(f2(f1(x))))- And so forth.
Hint: most of the work goes inside the most nested function.
def cycle(f1, f2, f3):
""" Returns a function that is itself a higher order function
>>> def add1(x):
... return x + 1
>>> def times2(x):
... return x * 2
>>> def add3(x):
... return x + 3
>>> my_cycle = cycle(add1, times2, add3)
>>> identity = my_cycle(0)
>>> identity(5)
5
>>> add_one_then_double = my_cycle(2)
>>> add_one_then_double(1)
4
>>> do_all_functions = my_cycle(3)
>>> do_all_functions(2)
9
>>> do_more_than_a_cycle = my_cycle(4)
>>> do_more_than_a_cycle(2)
10
>>> do_two_cycles = my_cycle(6)
>>> do_two_cycles(1)
19
"""
"*** YOUR CODE HERE ***"Use OK to test your code:
python3 ok -q cycleSubmit
Make sure to submit this assignment by running:
python3 ok --submit