A document from MCS 275 Spring 2022, instructor David Dumas. You can also get the notebook file.

MCS 275 Spring 2022 Homework 6 Solutions

  • Course Instructor: David Dumas
  • Solutions prepared by: Johnny Joyce


  • Complete the problems below, which ask you to write Python scripts.
  • Upload your python code directly to gradescope, i.e. upload the .py files containing your work. (If you upload a screenshot or other file format, you won't get credit.)


This homework assignment must be submitted in Gradescope by Noon central time on Tuesday 22 February 2022.


Collaboration is prohibited, and you may only access resources (books, online, etc.) listed below.

Resources you may consult

The course materials you may refer to for this homework are:

Point distribution

This homework assignment has a single problem, numbered 2. The grading breakdown is:

Points Item
2 Autograder
4 Problem 2
6 Total

The part marked "autograder" reflects points assigned to your submission based on some simple automated checks for Python syntax, etc.. The result of these checks is shown immediately after you submit.

What to do if you're stuck

Ask your instructor or TA a question by email, in office hours, or on discord.

Problem 1 doesn't exist

In Gradescope, the score assigned to your homework submission by the autograder (checking for syntax and docstrings) will be recorded as "Problem 1". Therefore, the numbering of the actual problems begins with 2.

Problem 2: Sum half of previous

The Fibonacci sequence calculates the next term as the sum of the two previous terms. Similarly, we can define a sequence $S_n$ where $S_0=0$, $S_1=1$, and where for $n>1$ the term $S_n$ is defined as the sum of the most recent "half" of the previous terms, rounding the number of summands up in case an odd number are present. That is, $S_n$ is the sum of the terms $S_k$ as $k$ goes from $n//2$ to $n-1$. You can check that the first 10 terms of this sequence ($S_0$ to $S_9$) are:

$$ 0, 1, 1, 2, 3, 6, 11, 22, 42, 84 $$

Using this definition, do the following:

A. Write a memoized recursive function shop(n) that takes a nonnegative integer n and returns $S_n$. (The function name shop stands for sum half of previous.)

B. Calculate $S_{100}$ and write its value as a comment above your function definition. (This will be fast with a memoized function, but impractically slow with a naive recursion.)

Save your work in a file hwk6prob2.py and upload it to gradescope.


Before memoization:

In [1]:
def shop(n):
    '''Non-memoized version of recursive function, HW6 Q2'''
    if n == 0 or n == 1: # Base case
        return n
    S_n = 0
    for k in range(n//2,n):
        S_n += shop(k) # Make recursive call
    return S_n

After memoization:

In [4]:
cache = {0: 0,
         1: 1} # Store the base cases

# shop(100) = 200722441406816771158434999852
def shop(n):
    '''Memoized version of recursive function, HW6 Q2'''
    # We don't need the base cases anymore since they are in the cache
    S_n = 0
    for k in range(n//2,n):
        if k not in cache:
            # If we haven't yet cached `k`, we must make recursive call and store the result
            cache[k] = shop(k)
        S_n += cache[k]
    return S_n