#
Homework 2

*Due at 11:59:59 pm on 2/12/2021.*

## 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 --submit`

## Questions

### 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 *n*th
element is defined as *F _{n} = F_{n-1} +
F_{n-2}*.

Implement the `fib`

function, which takes an integer `n`

and returns
the `n`

th 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 fib`

### Question 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_num`

### Question 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_derivative`

### Question 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 n
```

The 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_cond`

### Question 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`

, return`x`

`n = 1`

, apply`f1`

to`x`

, or return`f1(x)`

`n = 2`

, apply`f1`

to`x`

and then`f2`

to the result of that, or return`f2(f1(x))`

`n = 3`

, apply`f1`

to`x`

,`f2`

to the result of applying`f1`

, and then`f3`

to the result of applying`f2`

, or`f3(f2(f1(x)))`

`n = 4`

, start the cycle again applying`f1`

, then`f2`

, then`f3`

, then`f1`

again, or`f1(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 cycle`

## Submit

Make sure to submit this assignment by running:

`python3 ok --submit`