Problem Set 4

due by 10 p.m. on Friday, September 15, 2023 Suggested self-deadline: Wednesday September 13, 2023

Preliminaries

In your work on this assignment, make sure to abide by the collaboration policies of the course.

If you have questions while working on this assignment, please post them on Piazza or come to TA Help Hours.

Make sure to submit your work on Gradescope.

Problem 1: Thinking recursively, recursively again

50 points; pair-optional or group-optional

Create a new Jupyter Notebook file, save it using the the name ps4pr1.ipynb. Inside, create an appropriate title cell using Markdown, containing the problem set information, your name, the date.

This start of this problem is nearly identical to Problem Set 3, Problem 1, except that you will create your answers and trace table in a Jupyter Notebook.

For a refresher, we suggest you watch this video on recursive function tracing first.

Below is an example trace from the video using a Markdown table. You can modify this template, or here is a tool to generate aligned table

|  a  |  b  | multiply(a - 1, b)  |              return              |
| ---- | ---- | ------------------- | -------------------------------- |
|  3  |  5  | multiply(2, 5) = 10 | multiply(2, 5) + 5 = 10 + 5 = 15 |
|  2  |  5  | multiply(1, 5) = 5  | multiply(1, 5) + 5 = 5 + 5 = 10  |
|  1  |  5  | multiply(0, 5) = 0  | multiply(0, 5) + 5 = 0 + 5 = 5   |
|  0  |  5  | not executed        | 0                                |

This will be rendered as:

Consider the following recursive function:

def mystery(s):
    if len(s) % 5 == 0:
        return s

    rest = mystery(s[1:])
    return "#" + rest

1. Trace the execution of the following call to this function

   mystery("Hello, World")
   

   To do so, create a table in a Markdown cell. In particular, you should:

   • Fill in the “frame” for each call. You should add frames for additional calls as needed, until you reach the base case.

   • Each frame should show the values assigned to the parameter.

   • If the call is a base case, you can simply show the value that is returned ( noting that rest is not executed). If the call is a recursive case, you should show the recursive call for rest.

   • Once you have reached the base case, you should work your way back through the frames for the previous calls. Add in both the results of the recursive call (i.e, the value assigned to rest) and the value returned by the call itself.

2. What is the value returned by mystery("Hello, World")?

3. During the execution of mystery("Hello, World"), stack frames are added and then removed from the stack. How many stack frames are on the stack when the base case is reached? You should assume that the initial call to mystery("Hello, World") is made from the global scope, and you should include the stack frame for the global scope in your count.

4. Include the mystery function in a code block. Conduct at least 3 more experiments with inputs of various lengths.

5. Use Markdown cells to explain each experiment and its output, alternating between Code cells and Markdown cells.

6. Create a final Markdown cell with an explanation of what the function does and how it does it. Use a Markdown list to discuss the meanings of the base case and recursive case.

7. Format your entire Notebook so that it’s beautiful and the flow from start to the end makes sense.

Problem 2: Choose your own Jupyter Notebook adventure

50 points; pair-optional or group-optional

Create a new Jupyter Notebook file, save it using the the name ps4pr2.ipynb

This part of the assignment is a “choose your own adventure”.

Choose a topic from a math or science course an equation that models something interesting, and where you can write a function or a few lines of code to help explore the topic computationally.

For example, maybe you explored static friction with an inclined-plane experiment in a Physics class. You could use your lab report for the basis of your Jupyter Notebook. Or balanced chemical equations in Chemistry. Or looked at gene expression probabilities in Biology. Or modeled supply and demand in Economics. Feel free to use something from an old high school class.

Create a Jupyter Notebook that explains the concept, using a combination of Markdown cells and code cells to explore it computationally. Try to render the key equations in LaTeX if you can. Feel free to include images/pictures, but note that we will not see them on Gradescope when you upload the file. (You can optionally upload a PDF of the notebook as well if you want us to see your images).

Requirements:

• Your notebook must have at least 10 cells, a mix of Markdown and code cells.

• You should typeset at least one equation.

• Use a Markdown Table or List.

• Begin with an introduction to the topic, and then provide a narrative of what the notebook explains.

• Images are optional but encouraged (please try to also submit a PDF copy - google for how to do it!)

• It’s ok and encouraged to Google for how to do any part of this assignment. E.g. how to use LaTeX to create a certain symbol.

• You must cite any sources you access, and give credit to any class work you have done previously and are duplicating here.

• Your Notebook and code are forms of communication. Take care in your work so that the work communicates effectively.

Submitting Your Work

You should use Gradesope to submit the following files:

• your ps4pr1.ipynb file containing your solution for Problem 1
• your ps4pr2.ipynb file containing your solution for Problem 2
• Optionally: a ps4pr2.pdf file containing a PDF version of Problem 2 (if you want us to see images).