Homework 2: Recursion, Tree Recursion, Sequences, and Python Lists

Due by 11:59pm on Thursday, July 10

Instructions

Download hw02.zip. Inside the archive, you will find a file called hw02.py, along with a copy of the ok autograder.

Submission: When you are done, submit the assignment by uploading all code files you've edited to Gradescope. 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 Gradescope. See Lab 0 for more instructions on submitting assignments.

Using Ok: If you have any questions about using Ok, please refer to this guide.

Readings: You might find the following references useful:

Grading: Homework is graded based on correctness. Each incorrect problem will decrease the total score by one point. This homework is out of 2 points.

Required Questions


Getting Started Videos

These videos may provide some helpful direction for tackling the coding problems on this assignment.

To see these videos, you should be logged into your berkeley.edu email.

YouTube link


Recursion

Q1: Num Eights

Write a recursive function num_eights that takes a positive integer n and returns the number of times the digit 8 appears in n.

Important: Use recursion; the tests will fail if you use any assignment statements or loops. (You can define new functions, but don't put assignment statements there either.)

def num_eights(n):
    """Returns the number of times 8 appears as a digit of n.

    >>> num_eights(3)
    0
    >>> num_eights(8)
    1
    >>> num_eights(88888888)
    8
    >>> num_eights(2638)
    1
    >>> num_eights(86380)
    2
    >>> num_eights(12345)
    0
    >>> num_eights(8782089)
    3
    >>> from construct_check import check
    >>> # ban all assignment statements
    >>> check(SOURCE_FILE, 'num_eights',
    ...       ['Assign', 'AnnAssign', 'AugAssign', 'NamedExpr', 'For', 'While'])
    True
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q num_eights

Q2: Interleaved Sum

Write a function interleaved_sum, which takes in a number n and two one-argument functions: f_odd and f_even. It returns the sum of applying f_odd to every odd number and f_even to every even number from 1 to n inclusive.

For example, executing interleaved_sum(5, lambda x: x, lambda x: x * x) returns 1 + 2*2 + 3 + 4*4 + 5 = 29.

Important: Implement this function without using any loops or directly testing if a number is odd or even (no using %). Instead of directly checking whether a number is even or odd, start with 1, which you know is an odd number.

Hint: Introduce an inner helper function that takes an odd number k and computes an interleaved sum from k to n (including n). Alternatively, you can use mutual recursion.

def interleaved_sum(n, f_odd, f_even):
    """Compute the sum f_odd(1) + f_even(2) + f_odd(3) + ..., up
    to n.

    >>> identity = lambda x: x
    >>> square = lambda x: x * x
    >>> triple = lambda x: x * 3
    >>> interleaved_sum(5, identity, square) # 1   + 2*2 + 3   + 4*4 + 5
    29
    >>> interleaved_sum(5, square, identity) # 1*1 + 2   + 3*3 + 4   + 5*5
    41
    >>> interleaved_sum(4, triple, square)   # 1*3 + 2*2 + 3*3 + 4*4
    32
    >>> interleaved_sum(4, square, triple)   # 1*1 + 2*3 + 3*3 + 4*3
    28
    >>> from construct_check import check
    >>> check(SOURCE_FILE, 'interleaved_sum', ['While', 'For', 'Mod']) # ban loops and %
    True
    >>> check(SOURCE_FILE, 'interleaved_sum', ['BitAnd', 'BitOr', 'BitXor']) # ban bitwise operators, don't worry about these if you don't know what they are
    True
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q interleaved_sum

Q3: Count Dollars

Given a positive integer total, a set of dollar bills makes change for total if the sum of the values of the dollar bills is total. Here we will use standard US dollar bill values: 1, 5, 10, 20, 50, and 100. For example, the following sets make change for 15:

  • 15 1-dollar bills
  • 10 1-dollar, 1 5-dollar bills
  • 5 1-dollar, 2 5-dollar bills
  • 5 1-dollar, 1 10-dollar bills
  • 3 5-dollar bills
  • 1 5-dollar, 1 10-dollar bills

Thus, there are 6 ways to make change for 15. Write a recursive function count_dollars that takes a positive integer total and returns the number of ways to make change for total using 1, 5, 10, 20, 50, and 100 dollar bills.

Use next_smaller_dollar in your solution: next_smaller_dollar will return the next smaller dollar bill value from the input (e.g. next_smaller_dollar(5) is 1). The function will return None if the next dollar bill value does not exist.

Important: Use recursion; the tests will fail if you use loops.

Hint: Refer to the implementation of count_partitions for an example of how to count the ways to sum up to a final value with smaller parts. If you need to keep track of more than one value across recursive calls, consider writing a helper function.

def next_smaller_dollar(bill):
    """Returns the next smaller bill in order."""
    if bill == 100:
        return 50
    if bill == 50:
        return 20
    if bill == 20:
        return 10
    elif bill == 10:
        return 5
    elif bill == 5:
        return 1

def count_dollars(total):
    """Return the number of ways to make change.

    >>> count_dollars(15)  # 15 $1 bills, 10 $1 & 1 $5 bills, ... 1 $5 & 1 $10 bills
    6
    >>> count_dollars(10)  # 10 $1 bills, 5 $1 & 1 $5 bills, 2 $5 bills, 10 $1 bills
    4
    >>> count_dollars(20)  # 20 $1 bills, 15 $1 & $5 bills, ... 1 $20 bill
    10
    >>> count_dollars(45)  # How many ways to make change for 45 dollars?
    44
    >>> count_dollars(100) # How many ways to make change for 100 dollars?
    344
    >>> count_dollars(200) # How many ways to make change for 200 dollars?
    3274
    >>> from construct_check import check
    >>> # ban iteration
    >>> check(SOURCE_FILE, 'count_dollars', ['While', 'For'])
    True
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q count_dollars

Sequences and Python Lists

Q4: Shuffle

Implement shuffle, which takes a sequence s (such as a list or range) with an even number of elements. It returns a new list that interleaves the elements of the first half of s with the elements of the second half.

To interleave two sequences s0 and s1 is to create a new list containing the first element of s0, the first element of s1, the second element of s0, the second element of s1, and so on. For example, if s = [1, 2, 3, 4, 5, 6] then s0 = [1, 2, 3] and s1 = [4, 5, 6], and interleaving s0 and s1 would result in [1, 4, 2, 5, 3, 6].

Challenge: Try to implement shuffle in less lines using a list comprehension!

def shuffle(s):
    """Return a shuffled list that interleaves the two halves of s.

    >>> shuffle(range(6))
    [0, 3, 1, 4, 2, 5]
    >>> letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
    >>> shuffle(letters)
    ['a', 'e', 'b', 'f', 'c', 'g', 'd', 'h']
    >>> shuffle(shuffle(letters))
    ['a', 'c', 'e', 'g', 'b', 'd', 'f', 'h']
    >>> letters  # Original list should not be modified
    ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
    """
    assert len(s) % 2 == 0, 'len(seq) must be even'
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q shuffle

Q5: Merge

Implement merge, which takes 2 sorted lists of numbers s and t in ascending order. It returns a new list that contains all the elements from both s and t in sorted order. Do not remove duplicates; the length of the returned list should be len(s) + len(t). Use only recursion; while or for loops are not allowed.

def merge(s, t):
    """Merges two sorted lists.

    >>> s1 = [1, 3, 5]
    >>> s2 = [2, 4, 6]
    >>> merge(s1, s2)
    [1, 2, 3, 4, 5, 6]
    >>> s1
    [1, 3, 5]
    >>> s2
    [2, 4, 6]
    >>> merge([], [2, 4, 6])
    [2, 4, 6]
    >>> merge([1, 2, 3], [])
    [1, 2, 3]
    >>> merge([5, 7], [2, 4, 6])
    [2, 4, 5, 6, 7]
    >>> merge([2, 3, 4], [2, 4, 6])
    [2, 2, 3, 4, 4, 6]
    >>> from construct_check import check
    >>> check(SOURCE_FILE, 'merge', ['While', 'For'])    # ban iteration
    True
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q merge

Check Your Score Locally

You can locally check your score on each question of this assignment by running

python3 ok --score

This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

Submit Assignment

Submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions.

[Optional] Exam Practice

Here are some related questions from past exams for you to try. These are optional. There is no way to submit them.

  1. Fall 2021 MT2 Q2: Doctor Change [Recursion]
  2. Spring 2021 MT1 Q7: Measure Twice, Cup Once [Tree Recursion]