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:

• Section 1.7

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