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

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 :

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

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

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

How many ways are there of getting from `A`

to `Z`

?

In [12]:

```
# 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 string`s`

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`

.