#
Homework 7

*Due at 11:59:59 pm on Friday, 10/22/2021.*

## Instructions

Download hw07.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:

### Question 1: Create Number from Lists

Write a recursive function `create_num_from_lsts`

that creates a number with the elements from `lst1`

and `lst2`

as digits in that order.

```
def create_num_from_lsts(lst1, lst2):
""" Create a number with the elements from lst1 and lst2 as digits in that order.
>>> create_num_from_lsts([1, 2, 3], [4, 5, 6])
123456
>>> create_num_from_lsts([5, 4, 2, 4], [1, 7])
542417
>>> create_num_from_lsts([3], [9, 8])
398
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q create_num_from_lsts`

### Question 2: Partition

The number of partitions of a positive integer `n`

is the number of
ways in which `n`

can be expressed as the sum of positive integers in
increasing order. For example, the number `5`

has `7`

partitions.

```
5 = 5
5 = 1 + 4
5 = 2 + 3
5 = 1 + 1 + 3
5 = 1 + 2 + 2
5 = 1 + 1 + 1 + 2
5 = 1 + 1 + 1 + 1 + 1
```

Write a tree-recursive function `part(n)`

that returns the number of
partitions of `n`

.

Hint: Introduce a helper function that computes partitions of`n`

using only a subset of the integers less than or equal to`n`

. Once you have done so, you can use very similar logic to the`count_change`

function from the lecture notes:

```
def part(n):
"""Return the number of partitions of positive integer n.
>>> part(5)
7
>>> part(10)
42
>>> part(15)
176
>>> part(20)
627
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q part`

### Question 3: Count Change

A set of coins makes change for `n`

if the sum of the values of the
coins is `n`

. For example, if you have 1-cent, 2-cent and 4-cent
coins, the following sets make change for `7`

:

- 7 1-cent coins
- 5 1-cent, 1 2-cent coins
- 3 1-cent, 2 2-cent coins
- 3 1-cent, 1 4-cent coins
- 1 1-cent, 3 2-cent coins
- 1 1-cent, 1 2-cent, 1 4-cent coins

Thus, there are 6 ways to make change for `7`

. Write a function
`count_change`

that takes a positive integer `n`

and a list of
the coin denominations and returns the number of ways to make change
for `n`

using these coins (Hint: You will need to use tree recursion):

```
def count_change(amount, denominations):
"""Returns the number of ways to make change for amount.
>>> denominations = [50, 25, 10, 5, 1]
>>> count_change(7, denominations)
2
>>> count_change(100, denominations)
292
>>> denominations = [16, 8, 4, 2, 1]
>>> count_change(7, denominations)
6
>>> count_change(10, denominations)
14
>>> count_change(20, denominations)
60
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q count_change`

## Submit

Make sure to submit this assignment by running:

`python3 ok --submit`