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

MCS 260 Fall 2021 Homework 11

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

Topic

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

Collaboration

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

Resources you may consult

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

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

Point distribution

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

What to do if you're stuck

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

( 1. There's no problem 1 )

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

2. Fibonacci-like, but with a special case

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.

Additional help with the definition of $K_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.

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$$

Methods restriction

  • 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

3. Pair sequence

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

Methods restriction

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

Things you don't need to do

  • 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]:
15
In [40]:
P.y
Out[40]:
37
In [41]:
P[0]  # another way to get P.x
Out[41]:
15
In [42]:
P[1]  # another way to get P.y
Out[42]:
37
In [43]:
P[0] = 999 # changes P.x
In [44]:
P.x
Out[44]:
999
In [45]:
P.y
Out[45]:
37
In [46]:
P[0]
Out[46]:
999
In [47]:
P[-1] # should raise IndexError

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-47-3cbd6ef325d8> in <module>
----> 1 P[-1] # should raise IndexError

<ipython-input-37-58385b663681> in __getitem__(self, idx)
     18             return self.y
     19         else:
---> 20             raise IndexError("invalid index")

IndexError: invalid index
In [48]:
P[2] # should raise IndexError

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-48-50ae223681dc> in <module>
----> 1 P[2] # should raise IndexError

<ipython-input-37-58385b663681> in __getitem__(self, idx)
     18             return self.y
     19         else:
---> 20             raise IndexError("invalid index")

IndexError: invalid index
In [49]:
P[3] = 72  # should raise IndexError

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-49-98e227093604> in <module>
----> 1 P[3] = 72  # should raise IndexError

<ipython-input-37-58385b663681> in __setitem__(self, idx, val)
     11             self.y = val
     12         else:
---> 13             raise IndexError("invalid index")
     14     def __getitem__(self,idx):
     15         if idx==0:

IndexError: invalid index

Revision history

  • 2021-11-04 Initial release