Memoization Exercises

1. Fibonnacci Sequence

The fibonnacci sequence is defined as below :

$$ \Large f_n = \begin{cases}n \text{ if } n \leq 1\\ f_{n-1} + f_{n-2} \text{ if } n > 1 \end{cases} $$

1.1

Write a recursive function fib(n) that takes an integer n and returns $f_n$.

1.2

Add print("Calculating fib of " + str(n)) at the beginning of your function, and run the cell below :

In [ ]:
fib(7)

How many times does it calculate fib of 1 ?

In [11]:
# Answer here

2. Fibonacci Sequence - Memoized

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} $$

2.1

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.

2.2

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:

2.3

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 :

2.4

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 :

  • If `mem[n]` is **not** equal to `-1`, it should return `mem[n]`
  • If `mem[n]` is equal to `-1`, it should compute $f_n$ recursively and store it in `mem[n]` before returning it.

2.5

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):

3. Making Basketball Teams

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} $$

3.1

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$ ?

3.2

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 -1s:

[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.

3.3

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}$.

3.4

Write a function binom(n, k) that returns $\binom{n}{k}$. It should use create_memory(r, c) and memo_binom(n, k, mem).

4. Moving in a grid

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 : <img src = "numbered.png" width = "300px">

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$

Recursive formula :

If you know $T(a-1, b)$, $T(a, b-1)$ and $T(a-1, b-1)$, how can you find $T(a,b)$ ?

4.1

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):

4.2

How many ways are there of getting from A to Z ?

In [12]:
# Answer here

4.3

Following the previous exercise's procedure, write a function memo_T(a,b) that takes integers a and b and returns $T(a,b)$:

4.4

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) :

Optional Exercises

5. Min Number of Ways to Make Change

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.

5.1

First implement makeChange using plain recursion.

5.2

Implement a faster version of makeChange using memoization.

6. Longest Increasing Subsequence

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.

6.1

First implement lis using plain recursion.

6.2

Implement a faster version of lis using memoization.

7. Longest Common Subsequence

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.