Add print("Calculating fib of " + str(n))
at the beginning of your function, and run the cell below :
fib(7)
How many times does it calculate fib of 1
?
# Answer here
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 fib(i) before }\\
f_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.
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
:
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
:
Write a recursive function memo_fib(n, mem)
that takes an integer n
and a list mem
and returns $f_n$.
Here is how it should work :
Write a function fib(n)
that takes an integer n
and returns $f_n$. It should use create_memory(n)
and memo_fib(n, mem)
:
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}
$$
The code below generates a list of lists lst
with 3 rows and 4 columns that contains -1
s:
[python]
lst = [ [-1] * 4 ] * 3
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.
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}$.
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)$ ?
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)
:
You saw in lecture how to get the number of ways to make change using recursion and memoization. Now, we are going to change the question a bit, and get minimum number of ways to make change.
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,25,50,100]
, 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,25,50,100])
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 makeChange
using plain recursion.
Implement a faster version of makeChange
using memoization.
Write a function lis(L)
which takes as input a list of integers L
and outputs the length of the longest increasing subsequence (lis) of L
. A subsequence of L
is a sublist of L
that does not have to be contiguous. For example, [1,5,9]
is a subsequence of the list L = [1,2,3,4,5,6,7,8,9]
since 1,5,9
appear in the list L
in the same order (though just not in a row). 9,5,1
is not a subsequence of L
since it does not appear in L
in that order.
First implement lis
using plain recursion.
Implement a faster version of lis
using memoization.
Write the function lcs(s1, s2)
which takes as an input two strings and outputs the length of the longest common substring between the two. A subsequence of strings
is a set of letters that does not have to be contiguous. For example, the longest common subsequence of 'apple'
and 'pimple'
is 'pple'
, so the function would return 4
.