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

MCS 260 Fall 2021 Homework 11 Solutions

  • Course instructor: Emily Dumas
  • Solutions prepared by: Johnny Joyce

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

Solution

In [3]:
def k(n):
    '''A recursive function to find the nth entry in the sequence k_n'''
    
    # Base case where n is 0, 1, or 2
    if n == 0 or n == 1 or n == 2:
        return n
    
    # Case where k(n-1) is a multiple of n
    elif k(n-1) % n == 0:
        return k(n-1) + n-1
    
    # Final case where neither of the above cases hold
    else:
        return k(n-1) + k(n-3)
In [5]:
# This block of code goes directly together with the definition of k(n) above.
# Depending on one's computer/setup, it may take a while to run.

# Use range 26 so that we end on n=25
for n in range(26):
    print(n, k(n))
0 0
1 1
2 2
3 2
4 3
5 5
6 7
7 13
8 18
9 26
10 39
11 57
12 83
13 122
14 179
15 262
16 384
17 563
18 825
19 1209
20 1772
21 2597
22 3806
23 5578
24 8175
25 8199

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__

Solution

In [2]:
class Pair:
    '''Represents a pair of values x and y in the form [x,y]'''
    
    def __init__(self, x, y):
        '''Initialize an instance of Pair with attributes x and y'''
        self.x = x
        self.y = y

    def __len__(self):
        '''The length of any Pair is always 2.'''
        return 2
        
    def __getitem__(self, idx):
        '''Overload __getitem__ so that the x is located at index 0 
        and y is located at index 1'''
        if idx == 0:
            return self.x
        elif idx == 1:
            return self.y
        else:
            raise IndexError("The class Pair only supports requesting indices 0 or 1.")
            
    def __setitem__(self, idx, value):
        '''Overload __setitem__ so that x is changed by changing
        index 0, and y is changed by changing index 1'''
        if idx == 0:
            self.x = value
        elif idx == 1:
            self.y = value
        else:
            raise IndexError("The class Pair only supports assignment for indices 0 or 1.")

Revision history

  • 2021-11-09 Initial release of solutions