{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# MCS 260 Fall 2021 Homework 11 Solutions\n",
"\n",
"* Course instructor: Emily 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",
"This homework assignment must be submitted in Gradescope by 10am CST on Tuesday, November 9, 2021.\n",
"\n",
"### Topic\n",
"\n",
"This homework assignment focuses on **recursion** and the additional aspects of **object-oriented programming** that were covered last week.\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 main course materials to refer to for this homework are:\n",
"\n",
"* [Worksheet 11 solutions](https://www.dumas.io/teaching/2021/fall/mcs260/nbview/worksheets/worksheet11soln.html)\n",
"* [Sample programs](https://github.com/emilydumas/mcs260fall2021/tree/main/samplecode)\n",
" * Especially [fgs.py](https://github.com/emilydumas/mcs260fall2021/blob/main/samplecode/oop/fgs.py) and [factorial.py](https://github.com/emilydumas/mcs260fall2021/blob/main/samplecode/factorial.py)\n",
"* [Lecture 27 - OOP 3 (inheritance)](https://www.dumas.io/teaching/2021/fall/mcs260/slides/lecture27.html)\n",
"* [Lecture 28 - OOP 4 (protocols)](https://www.dumas.io/teaching/2021/fall/mcs260/slides/lecture28.html)\n",
"* [Lecture 29 - Recursion](https://www.dumas.io/teaching/2021/fall/mcs260/slides/lecture29.html)\n",
"* [Downey's book](https://greenteapress.com/thinkpython2/html/)\n",
"\n",
"(Lecture videos are not linked on worksheets, but are also useful to review while working on worksheets. Video links can be found in the course [course Blackboard site](https://uic.blackboard.com/ultra/courses/_202683_1/cl/outline).)\n",
"\n",
"### Point distribution\n",
"\n",
"This homework assignment has 2 problems, numbered 2 and 3. Thus the grading breakdown is:\n",
"\n",
"| Points | Item |\n",
"| --- | --- |\n",
"| 2 | Autograder |\n",
"| 4 | Problem 2 |\n",
"| 4 | Problem 3 |\n",
"| **10** | Total |\n",
"\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": [
"## ( 1. There's no problem 1 )\n",
"\n",
"Gradescope will show the results of the automated syntax check of all submitted files as the score for problem 1."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 2. Fibonacci-like, but with a special case\n",
"\n",
"Consider the following definition of a sequence $K_n$ that is similar in spirit to the Fibonacci sequence studied on the last worksheet, but where the rule for computing the next term involves a decision:\n",
"\n",
"$$\n",
"K_n = \\begin{cases}\n",
"n & \\text{ if $n=0$, $1$, or $2$}\\\\\n",
"K_{n-1} + n - 1 & \\text{ if $K_{n-1}$ is a multiple of $n$}\\\\\n",
"K_{n-1} + K_{n-3} & \\text{otherwise}\n",
"\\end{cases}\n",
"$$\n",
"\n",
"Write a **recursive** function `k(n)` that calculates and returns the value of $K_n$. Then, use it to make a program `hwk11prob2.py` that prints the values of `k(n)` for `n=0, 1, ..., 25` in a table that uses the format shown below:\n",
"```\n",
"0 0\n",
"1 1\n",
"2 2\n",
"3 2\n",
"4 3\n",
"5 5\n",
"6 7\n",
"7 13\n",
"[... more lines here, continuing up to n=25 ...]\n",
"```\n",
"\n",
"In this table, the left column shows `n` and the right column shows `k(n)`. The exact spacing of the table is not important.\n",
"\n",
"If your function is working correctly, the last value in the table (i.e. `k(25)`) will be `8199`.\n",
"\n",
"### Additional help with the definition of $K_n$\n",
"\n",
"The definition above tells you everything you need to know, but in case it is unclear, here's a more detailed explanation of a few values.\n",
"\n",
"We're told $K_0=0$, $K_1=1$, and $K_2=2$.\n",
"\n",
"For $K_3$, to apply the definition we need to check whether $K_2=2$ is a multiple of $3$. It is not, so we use the last row of the definition:\n",
"$$K_3 = K_2 + K_0 = 2 + 0 = 2.$$\n",
"\n",
"Moving ahead, if we use the definition we can determine that $K_3=2$, $K_4=3$, $K_5=5$, and $K_6=7$ as shown in the table above. Let's use that information to compute the next term.\n",
"\n",
"For $K_7$, we need to check whether $K_6=7$ is a multiple of $7$. It is, so we use the middle row of the definition:\n",
"$$K_7 = K_6 + 7 - 1 = 7 + 7 - 1 = 13$$\n",
"\n",
"### Methods restriction\n",
"\n",
"* You must not import any modules\n",
"* You must make essential use of recursion\n",
"* You can only use Python features and syntax we've discussed in MCS 260"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Solution"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"def k(n):\n",
" '''A recursive function to find the nth entry in the sequence k_n'''\n",
" \n",
" # Base case where n is 0, 1, or 2\n",
" if n == 0 or n == 1 or n == 2:\n",
" return n\n",
" \n",
" # Case where k(n-1) is a multiple of n\n",
" elif k(n-1) % n == 0:\n",
" return k(n-1) + n-1\n",
" \n",
" # Final case where neither of the above cases hold\n",
" else:\n",
" return k(n-1) + k(n-3)"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0 0\n",
"1 1\n",
"2 2\n",
"3 2\n",
"4 3\n",
"5 5\n",
"6 7\n",
"7 13\n",
"8 18\n",
"9 26\n",
"10 39\n",
"11 57\n",
"12 83\n",
"13 122\n",
"14 179\n",
"15 262\n",
"16 384\n",
"17 563\n",
"18 825\n",
"19 1209\n",
"20 1772\n",
"21 2597\n",
"22 3806\n",
"23 5578\n",
"24 8175\n",
"25 8199\n"
]
}
],
"source": [
"# This block of code goes directly together with the definition of k(n) above.\n",
"# Depending on one's computer/setup, it may take a while to run.\n",
"\n",
"# Use range 26 so that we end on n=25\n",
"for n in range(26):\n",
" print(n, k(n))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 3. Pair sequence\n",
"\n",
"In a file `hwk11prob3.py`, write a class called `Pair` in Python that stores a mutable pair of values, which we'll call `x` (the first value) and `y` (the second value). The constructor should accept `x` and `y` as its arguments, in that order.\n",
"\n",
"Make it so that the constructor arguments `x` and `y` are stored as attributes of the object with the same names.\n",
"\n",
"In addition, make it so that `Pair` supports the **mutable sequence protocol** as follows:\n",
"* The length of any `Pair` object should be equal to 2\n",
"* Requesting the value at index 0 returns `x`\n",
"* Requesting the value at index 1 returns `y`\n",
"* Requesting the value at any other index raises an `IndexError`\n",
"* Assigning a value to the item at index 0 changes `x`\n",
"* Assigning a value to the item at index 1 changes `y`\n",
"* Assigning a value at any other index raises an `IndexError`\n",
"\n",
"The code below shows some tests of how the class should behave. (These examples refer to the class as `Pair` alone, so if you put them in a test script that imports `hwk11prob3`, you might need to change `Pair` to `hwk11prob3.Pair`.)\n",
"\n",
"\n",
"### Methods restriction\n",
"\n",
"* You must not import any modules\n",
"* You can only use Python features and syntax we've discussed in MCS 260\n",
"\n",
"### Things you don't need to do\n",
"\n",
"* No need to implement `__eq__`, `__str__`, or `__repr__`"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Solution"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"class Pair:\n",
" '''Represents a pair of values x and y in the form [x,y]'''\n",
" \n",
" def __init__(self, x, y):\n",
" '''Initialize an instance of Pair with attributes x and y'''\n",
" self.x = x\n",
" self.y = y\n",
"\n",
" def __len__(self):\n",
" '''The length of any Pair is always 2.'''\n",
" return 2\n",
" \n",
" def __getitem__(self, idx):\n",
" '''Overload __getitem__ so that the x is located at index 0 \n",
" and y is located at index 1'''\n",
" if idx == 0:\n",
" return self.x\n",
" elif idx == 1:\n",
" return self.y\n",
" else:\n",
" raise IndexError(\"The class Pair only supports requesting indices 0 or 1.\")\n",
" \n",
" def __setitem__(self, idx, value):\n",
" '''Overload __setitem__ so that x is changed by changing\n",
" index 0, and y is changed by changing index 1'''\n",
" if idx == 0:\n",
" self.x = value\n",
" elif idx == 1:\n",
" self.y = value\n",
" else:\n",
" raise IndexError(\"The class Pair only supports assignment for indices 0 or 1.\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Revision history\n",
"\n",
"* 2021-11-09 Initial release of solutions"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"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.9.6"
}
},
"nbformat": 4,
"nbformat_minor": 4
}