def check_test(actual, expected):
if expected != actual:
print(f"Function should return the value {expected}, it is returning the value {actual}")
else:
print(f"Congratulations, the test case passed!")
You are climbing a staircase. It takes n
steps to reach the top. Each time you can either climb 1
or 2
steps. In how many distinct ways can you climb to the top?
Write a recursive function climbing_stairs(n)
that takes an integer n
and returns the number of distinct ways you can climb to the top.
def climbing_stairs(n):
# Your code here
pass
# Test your code
print(climbing_stairs(10)) # This should give 89
print(climbing_stairs(35)) # This should give 14930352
You might notice that the computation of climbing_stairs(35)
takes a few seconds.
Add print("Calculating value for " + str(n))
at the beginning of your function (make it the first line), run it, and run the cell below :
climbing_stairs(10)
How many times does it print 3
?
Answer here:
What did you learn from the number?
Answer here:
def check_test(actual, expected):
if expected != actual:
print(f"Function should return the value {expected}, it is returning the value {actual}")
else:
print(f"Congratulations, the test case passed!")
check_test(climbing_stairs(2), 2)
check_test(climbing_stairs(5), 8)
check_test(climbing_stairs(6), 13)
We are going to store things we have computed before in a list mem
such that
$$
mem[i] = \begin{cases}-1 \text{ if we haven't computed } climbing\_stairs_i \text{ before }\\
climbing\_stairs_i \text{ if we have already computed it}
\end{cases}
$$
Write a function create_memory(n)
that takes an integer n
and returns a list L of length n
that contains the integer -1
repeated n
times.
def create_memory(n):
# Your code here
Write a function check(i, mem)
that takes an index i
and a list mem
and returns True
if mem[i]
is not equal to -1
:
def check(i, mem):
# Your code here
Write a function add(mem, i, value)
that takes a list mem
, an index i
and an integer value
and that stores the integer value
in the list mem
at index i
:
def add(mem, i, value):
# Your code here
Write a recursive function memo_climbing_stairs(n, mem)
that takes an integer n
and a list mem
.
Here is how it should work :
mem[n]
is not equal to -1
, it should return mem[n]
mem[n]
is equal to -1
, it should compute the value recursively and store it in mem[n]
before returning it.def memo_climbing_stairs(n, mem):
# Your code here
Write a function climbing_stairs(n)
that takes an integer n
. It should use create_memory(n)
and memo_climbing_stairs(n, mem)
.
Hint: Remember that we are storing values from 0 to n
def climbing_stairs(n):
# Your code here
# Check your answer here
check_test(climbing_stairs(2), 2)
check_test(climbing_stairs(5), 8)
check_test(climbing_stairs(6), 13)
check_test(climbing_stairs(35), 14930352)
Do you notice any difference in how long it takes to compute climbing_stairs(35)
?
your answer here
The fibonnacci sequence is defined as below :
$$ \Large f_n = \begin{cases}n \text{ if } \leq 1\\ f_{n-1} + f_{n-2} \text{ if } n > 1 \end{cases} $$For example, the first eight Fibonnacci numbers are:
0,1,1,2,3,5,8,13 . . .
Write a recursive function fib(n)
that takes an integer n
and returns $f_n$.
def fib(n):
# Your code here
Write a memoized version of the above function.
def memo_fib(n, mem):
# Your code here
Write a function fib(n)
that takes an integer n
. It should use create_memory(n)
and memo_fib(n, mem)
.
Hint: Remember that we are storing fibs from 0 to n
def fib(n):
# Your code here
check_test(fib(7), 13)
check_test(fib(0), 0)
check_test(fib(1), 1)
Do you think fibonnacci sequence
and climbing stairs
are related? If so, how?
YOUR ANSWER GOES HERE
You have n
classmates. You want to create a team of k
players. How many different teams can you create ?
You may have seen in math class that the number we are looking for is : $$ \Large \binom{n}{k} $$
To choose your team, you can either pick the tallest classmate and then pick the remaining k-1
players, or you can decide to leave out your tallest classmate and pick a team among n-1
classmates.
This yields the recursive formula : $$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} $$
Write a recursive function binom(n, k)
that takes two integers n
and k
and returns $\binom{n}{k}$ :
Hint : Think of your base case carefully. What is $\binom{n}{0}$ ? What is $\binom{0}{k}$ if $k \neq 0$ ?
We're going to create a list of lists called mem
such that :
$$
mem[i][j] =
\begin{cases}
-1 \text{ if }\binom{i}{j} \text{ has not been computed before}\\
\binom{i}{j} \text{ if it has}
\end{cases}
$$
Write a function create_memory(r, c)
that takes two integers r
and c
and returns a list of lists with r
rows and c
colums where all entries are -1.
For example, the code below does NOT work:
lst = [ [-1] * 4 ] * 3
If you now modify an entry, for example list[0][0] = 5
, the whole first column will change to 5, because all rows point to the same list. If you have internet, you can use pythontutor.com
to visualize this!
Instead, use a list comprehension or for loop to create the rows.
def create_memory(r, c):
# Your code here
# Check your answer here
matrix = create_memory(3, 2)
check_test(matrix, [[-1, -1], [-1, -1], [-1, -1]])
matrix[0][0] = 5 # Make sure only one entry changes
check_test(matrix, [[5, -1], [-1, -1], [-1, -1]])
Write a function memo_binom(n, k, mem)
that takes two integers n
, k
and a list of lists mem
and that returns $\binom{n}{k}$.
As before, this function should check in mem
if $\binom{n}{k}$ has been computed before, and if not, compute it recursively and add the answer to mem
.
Write a function binom(n, k)
that returns $\binom{n}{k}$. It should use create_memory(r, c)
and memo_binom(n, k, mem)
.
We want to find the number of paths that go from A
to Z
in the grid below :
Two examples paths are drawn below in red:
We number the points in the grid like so :
Let $T(a,b)$ denote the number of ways of getting from (0,0) to (a, b). For example $T(0,1) = 1$ and $T(1,1) = 3$
If you know $T(a-1, b)$, $T(a, b-1)$ and $T(a-1, b-1)$, how can you find $T(a,b)$ ?
Your answer here
Write a recursive function T(a,b)
that takes two integers a
and b
and returns the number of ways of getting from (0,0) to (a,b):
# Answer here
Following the previous exercise's procedure, write a function memo_T(a,b)
that takes integers a
and b
and returns $T(a,b)$:
Write a function T(a, b)
that takes two integers a
and b
and returns the number of ways of getting from (0,0) to (a,b). It should use memo_T(a, b)
:
Suppose you live in a country whose coin denominations are in the list L
. For example, in Ethiopia we would have L = [1,5,10,50,100,200]
, but other countries have different coin systems. Implement a function makeChange(n, L)
which returns the minimum number of coins needed to make change for n
cents using the coins in L
.
For example, makeChange(14, [1,5,10,50,100,200])
should return 5
, since you can make change for 14
cents by giving one 10
cent piece and four 1
cent pieces, for a total of 5
coins (you could also give two 5
cent pieces and four 1
cent pieces, or 14
1
cent pieces, but those options would each require more coins). If it is impossible to make change for n
cents using L
, you should return -1
. For example, makeChange(3, [2, 5])
should return -1
since there is no way to make change for 3
cents using 2
cent and 5
cent pieces.
First implement a function makeChange
that takes as input an integer $n$ and a list $L$ (with coin values sorted in increasing order) and returns the minimum number of ways to make change using plain recursion.
def make_change(n, L):
# Your code here
pass
check_test(make_change(14, [1,5,10,25,50,100]), 5)
check_test(make_change(12,[1,4,6,8,10,12]), 1)
check_test(make_change(11,[4,6,8]), -1)
Implement a faster version or your solution using memoization in makeChange_memo(n, L)
.
def make_change_memo(n, L):
# Your code here
pass
check_test(make_change_memo(14, [1,5,10,25,50,100]), 5)
check_test(make_change_memo(50,[1,4,6,8,10,12]), 5)
check_test(make_change_memo(11,[4,6,8]), -1)
Can you modify your code so that it returns the list of coins that sum up to the amount you want (or None
if no solution exists)?
Hint: In your memoization table, store lists of coins rather than the amount of coins.