A document from MCS 275 Spring 2023, instructor Emily Dumas. You can also get the notebook file.

MCS 275 Spring 2023 Homework 5

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

Deadline

This homework assignment must be submitted in Gradescope by Noon central time on Tuesday February 14, 2023.

Collaboration

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

Content

This assignment is about recursion and Python notebooks. (Worksheet 5 also included material on context managers, but that isn't explicitly tested in this assignment.)

Resources you may consult

Most relevant:

Less likely to be relevant, but also allowed:

Point distribution

This homework assignment has 3 problems, numbered 2, 3, and 4. The grading breakdown is:

Points Item
3 Autograder
4 Problem 2
4 Problem 3
4 Problem 4
15 Total

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.

What to do if you're stuck

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

Problem 2: Submit your homework as a notebook

As with worksheet 5, for this homework assignment you'll be asked to complete all of your work in a Python notebook.

Submit everything as a single file called mcs275hw5.ipynb.

If you work in Jupyter (as installed with python3 -m pip install notebook), just name the notebook mcs275hw5 and it will be saved with the .ipynb extension in the directory where you started Jupyter.

If you work in Colab, you can download the .ipynb file to your computer using the menu bar that Colab displays at the top of the notebook. Select File, then Download, and in the submenu, Download .ipynb.

This problem score reflects notebook format

When your assignment is graded, this problem's score will reflect whether your notebook follows the notebook format guidelines below. The other problems contain coding exercises and the scores on those problems will look for correctness of your work.

Notebook format guidelines

  • Title and name at top: Include a markdown cell at the top containing a title (top-level heading, single # as the formatting directive) and your name
  • Labeled solutions: The solution to each problem should be in a series of code and/or markdown cells, but should be labeled with a level-2 header in a markdown cell (e.g. ## Problem 3 in Markdown which renders as Problem 3 in large bold text).
  • No extraneous stuff: There shouldn't be anything in the notebook other than your solutions to the problems and any explanatory text or output from the code cells that is required by the problems. The statements of the problems shouldn't be there.

Advice

  1. If you want to, you can begin your work by making a copy of the notebook file used to create this assignment and editing it on your own computer. However, if you do that, there will be a lot of stuff you need to delete before submitting. It's not clear to me whether that's easier than starting from scratch, so do whatever you prefer.
  2. Don't submit a .py file, and don't just rename a Python source file from .py to .ipynb. The way to make a .ipynb file is to use the Python notebook interface.

Picture of expected layout

Finally, here's a rough picture of what the notebook you submit might look like (but obviously this one doesn't contain solutions:

Problem 3: Tower factorial

Let $n$ be a positive integer. Let's define the tower factorial of $n$ to be

$$ n^{(n-1)^{(n-2)^{(n-3)^{\cdots^{2^1}}}}} $$

That is, you raise $n$ to a certain power. The exponent is $(n-1)$ raised to a certain power, etc., until you end up at $1$.

By convention, we'll say the tower factorial of $1$ is $1$ and that the tower factorial of $0$ or of a negative integer doesn't exist.

Write two functions:

  • towerfact(n) that computes the tower factorial using recursion
  • towerfact_iterative(n) that computes the tower factorial using iteration (no recursion).

Each function should raise a ValueError if the given integer is zero or negative. Otherwise it should return the answer.

You can put these functions in a single notebook cell or in separate cells, as you prefer.

Also add cells to your notebook that show both functions being tested. At a minimum your tests should include

  • Code generating a table of n and towerfact(n) for 1 <= n <= 5
  • Code generating a table of n and towerfact_iterative(n) for 1 <= n <= 5
  • Code that confirms the values returned by the two functions are equal for 1 <= n <= 5
  • Manual confirmation that the return value of towerfact(4) is correct, where the return value is compared to an expression that you enter manually to calculate the tower factorial.

Be careful about the order of operations

Note that the tower factorial of $4$ is the rather large number $$ 4^{3^{2^1}} = 4^{\left ( 3^{\left ( 2^1 \right)} \right )} = 4^{3^2} = 4^9$$

This is quite different from $$ \left ( \left(4^3 \right )^2 \right )^1$$ which is much smaller and which is more simply written as as $ 4^{3 \times 2 \times 1}$.

Warning about big numbers

The number towerfact(6) is so astronomically large that you should not expect it to be possible to compute on your computer. Python integers are limited in range only by available memory and time, so if you try to compute towerfact(6) you'll probably just end up waiting forever or exhausting your computer's memory (which would make the Python interpreter stop).

Problem 4: More complicated 2-step recurrence

Define an integer sequence $a_n$ as follows:

  • $a_0 = 1$
  • $a_1 = 3$
  • If $n>1$ and is even, then $a_n$ is equal to $n\, a_{n-1} - a_{n-2}$.
  • If $n>1$ and is odd, then $a_n$ is $1 + (a_{n-2})^2$

Thus it is similar in spirit to the Fibonacci sequence, but the rule is slightly different and depends on the parity (odd/even) of $n$.

To illustrate the definition, this sequence begins: $$ \begin{split} a_0 &= 1\\ a_1 &= 3\\ a_2 &= 5 = 2 a_1 - a_0\\ a_3 &= 10 = 1 + (a_1)^2\\ a_4 &= 35 = 4 a_3 - a_2\\ a_5 &= 101 = 1 + (a_3)^2 a_6 &= 571 = 6 a_5 - a_4 \end{split} $$

Write a recursive function aseq(n) that computes and returns $a_n$. (If given a negative value of n, the function should raise ValueError.)

Include cells showing that you tested your function's return value for all $n$ from $0$ to $15$.

Revision history

  • 2023-02-09 Initial publication