A document from MCS 260 Fall 2021, instructor Emily Dumas.
You can also get the notebook file.

- Course instructor: Emily Dumas

- 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 10am CST on Tuesday, November 9, 2021.

This homework assignment focuses on **recursion** and the additional aspects of **object-oriented programming** that were covered last week.

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

The main course materials to refer to for this homework are:

- Worksheet 11 solutions
- Sample programs
- Especially fgs.py and factorial.py

- Lecture 27 - OOP 3 (inheritance)
- Lecture 28 - OOP 4 (protocols)
- Lecture 29 - Recursion
- Downey's book

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

This homework assignment has 2 problems, numbered 2 and 3. Thus the grading breakdown is:

Points | Item |
---|---|

2 | Autograder |

4 | Problem 2 |

4 | Problem 3 |

10 |
Total |

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

Gradescope will show the results of the automated syntax check of all submitted files as the score for problem 1.

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:

$$ K_n = \begin{cases} n & \text{ if $n=0$, $1$, or $2$}\\ K_{n-1} + n - 1 & \text{ if $K_{n-1}$ is a multiple of $n$}\\ K_{n-1} + K_{n-3} & \text{otherwise} \end{cases} $$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:

```
0 0
1 1
2 2
3 2
4 3
5 5
6 7
7 13
[... more lines here, continuing up to n=25 ...]
```

In this table, the left column shows `n`

and the right column shows `k(n)`

. The exact spacing of the table is not important.

If your function is working correctly, the last value in the table (i.e. `k(25)`

) will be `8199`

.

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.

We're told $K_0=0$, $K_1=1$, and $K_2=2$.

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: $$K_3 = K_2 + K_0 = 2 + 0 = 2.$$

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.

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: $$K_7 = K_6 + 7 - 1 = 7 + 7 - 1 = 13$$

- You must not import any modules
- You must make essential use of recursion
- You can only use Python features and syntax we've discussed in MCS 260

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.

Make it so that the constructor arguments `x`

and `y`

are stored as attributes of the object with the same names.

In addition, make it so that `Pair`

supports the **mutable sequence protocol** as follows:

- The length of any
`Pair`

object should be equal to 2 - Requesting the value at index 0 returns
`x`

- Requesting the value at index 1 returns
`y`

- Requesting the value at any other index raises an
`IndexError`

- Assigning a value to the item at index 0 changes
`x`

- Assigning a value to the item at index 1 changes
`y`

- Assigning a value at any other index raises an
`IndexError`

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`

.)

- You must not import any modules
- You can only use Python features and syntax we've discussed in MCS 260

- No need to implement
`__eq__`

,`__str__`

, or`__repr__`

In [38]:

```
P = Pair(15,37) # Creates a new Pair object, using first arg as x and second as y
```

In [39]:

```
P.x
```

Out[39]:

In [40]:

```
P.y
```

Out[40]:

In [41]:

```
P[0] # another way to get P.x
```

Out[41]:

In [42]:

```
P[1] # another way to get P.y
```

Out[42]:

In [43]:

```
P[0] = 999 # changes P.x
```

In [44]:

```
P.x
```

Out[44]:

In [45]:

```
P.y
```

Out[45]:

In [46]:

```
P[0]
```

Out[46]:

In [47]:

```
P[-1] # should raise IndexError
```

In [48]:

```
P[2] # should raise IndexError
```

In [49]:

```
P[3] = 72 # should raise IndexError
```

- 2021-11-04 Initial release