{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# MCS 275 Spring 2022 Homework 6 Solutions\n",
"\n",
"* Course Instructor: David Dumas\n",
"* Solutions prepared by: Johnny Joyce"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Instructions:\n",
"\n",
"* Complete the problems below, which ask you to write Python scripts.\n",
"* 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.)\n",
"\n",
"### Deadline\n",
"\n",
"This homework assignment must be submitted in Gradescope by **Noon central time on Tuesday 22 February 2022**.\n",
"\n",
"### Collaboration\n",
"\n",
"**Collaboration is prohibited**, and you may only access resources (books, online, etc.) listed below.\n",
"\n",
"### Resources you may consult\n",
"\n",
"The course materials you may refer to for this homework are:\n",
"\n",
"* [Worksheet 6 Solutions](https://www.dumas.io/teaching/2022/spring/mcs275/nbview/worksheets/worksheet6soln.html)\n",
"* [Lecture 12 - Recursion](https://www.dumas.io/teaching/2022/spring/mcs275/slides/lecture12.html)\n",
"* [Lecture 13 - Recursion vs iteration](https://www.dumas.io/teaching/2022/spring/mcs275/slides/lecture13.html)\n",
"* [Lecture 14 - Recursion vs iteration and backtracking](https://www.dumas.io/teaching/2022/spring/mcs275/slides/lecture14.html)\n",
"* [MCS 275 Python Tour](https://www.dumas.io/teaching/2022/spring/mcs275/nbview/samplecode/python_tour.html)\n",
"* [Downey's book](https://greenteapress.com/thinkpython2/html/)\n",
"* MCS 260 course materials from Fall 2021:\n",
" * [Slides, homework, worksheets, and projects](https://www.dumas.io/teaching/2021/fall/mcs260/)\n",
" * [Sample programs](https://github.com/daviddumas/mcs260fall2021/tree/main/samplecode)\n",
"\n",
"### Point distribution\n",
"\n",
"This homework assignment has a single problem, numbered 2. The grading breakdown is:\n",
"\n",
"| Points | Item |\n",
"| --- | --- |\n",
"| 2 | Autograder |\n",
"| 4 | Problem 2 |\n",
"| **6** | Total |\n",
"\n",
"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.\n",
"\n",
"### What to do if you're stuck\n",
"\n",
"Ask your instructor or TA a question by email, in office hours, or on discord."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Problem 1 doesn't exist\n",
"\n",
"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."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Problem 2: Sum half of previous\n",
"\n",
"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:\n",
"\n",
"$$ 0, 1, 1, 2, 3, 6, 11, 22, 42, 84 $$\n",
"\n",
"Using this definition, do the following:\n",
"\n",
"A. Write a **memoized recursive function** `shop(n)` that takes a nonnegative integer `n` and returns $S_n$. (The function name `shop` stands for **s**um **h**alf **o**f **p**revious.)\n",
"\n",
"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.)\n",
"\n",
"Save your work in a file `hwk6prob2.py` and upload it to gradescope."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Solution\n",
"\n",
"Before memoization:"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"def shop(n):\n",
" '''Non-memoized version of recursive function, HW6 Q2'''\n",
" \n",
" if n == 0 or n == 1: # Base case\n",
" return n\n",
" \n",
" S_n = 0\n",
" for k in range(n//2,n):\n",
" S_n += shop(k) # Make recursive call\n",
" return S_n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"After memoization:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"200722441406816771158434999852\n"
]
}
],
"source": [
"cache = {0: 0,\n",
" 1: 1} # Store the base cases\n",
"\n",
"# shop(100) = 200722441406816771158434999852\n",
"def shop(n):\n",
" '''Memoized version of recursive function, HW6 Q2'''\n",
" \n",
" # We don't need the base cases anymore since they are in the cache\n",
" \n",
" S_n = 0\n",
" for k in range(n//2,n):\n",
" if k not in cache:\n",
" # If we haven't yet cached `k`, we must make recursive call and store the result\n",
" cache[k] = shop(k)\n",
" S_n += cache[k]\n",
" return S_n\n",
"\n",
"print(shop(100))"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.8.10"
}
},
"nbformat": 4,
"nbformat_minor": 4
}