.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.
The course materials you may refer to for this homework are:
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.
Ask your instructor or TA a question by email, in office hours, or on discord.
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.
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:
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:
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
print(shop(100))