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

MCS 275 Spring 2022 Homework 6

  • Course Instructor: Emily Dumas

Instructions:

  • 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.)

Deadline

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

Collaboration

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.