This worksheet focuses on the Jupyter notebook interface, context managers, and the start of our unit on recursion.
These things might be helpful while working on the problems. Remember that for worksheets, we don't strictly limit what resources you can consult, so these are only suggestions.
Project 1 is due on Friday February 9 at 11:59pm central time. To prepare for working on it, please download and extract ths starter pack, which is a ZIP file:
You don't just want to view the contents of the ZIP file in Windows explorer or a Finder window; it's important to actually extract the files so they exist in a directory where you can do your project work. You'll know you've done this if you can find and list those files (e.g. simulation.py, routing.py) in a terminal.
The point of asking you to do it during lab is to ensure the TA can help you if you run into any problems.
To get some experience using the notebook interface, work on this assignment in a notebook. (Similarly, Homework 4 will require you to submit a notebook.)
For this problem, just get that set up as follows:
python3 -m pip install notebook will do it)python3 -m notebook in the directory where you want your notebook files to go)lab4.ipynbnetid@uic.edu account (or any other google account)lab5These instructions will have you start with a blank notebook. If you'd instead like to start with a copy of the worksheet notebook, you can do that by downloading the .ipynb file of the worksheet (from github or using the "notebook file" link at the very top if this is the web page). If you use Colab, you will also need to upload that file to Colab after you save it to your computer.
But if you prepare your solutions in a copy of this worksheet notebook, please delete all the cells except the numbered problems and your answers.
There is a sequence of integers $T_n$ defined by the conditions
$$\begin{split} T_0 &= 0\\ T_1 &= 1\\ T_2 &= 2\\ T_{n} &= T_{n-1} + T_{n-2} + T_{n-3} \text{ if } n \geq 3\end{split}$$This sequence begins $0, 1, 2, 3, 6, 11, 20, 37, 68, 125, 230, 423, 778, 1431, 2632, \ldots$.
Write a recursive function that calculates $T_n$.
Write an iterative function that calculates $T_n$.
Add code to the recursive function that will allow you to count how many times the function is called in any single computation. (You probably want to have a global dictionary in which every function call changes the value associated with a certain key.)
Make a table of how many calls are involved for $n=1,2,3,\ldots,15$.
Sometimes, a program will read or write a data file which might also be accessed by another program at the same time. In such cases, it may be necessary for one program to have exclusive access to the file at certain times (e.g. to make changes without fear another program will read partially updated or corrupted data).
There are a lot of mechanisms for handling this situation. One of the oldest approaches is to use a second file, a lockfile, that will be created when a program needs exclusive access to the data file and removed when the period of exclusive access ends.
To make this precise, imagine there might be a file called keyring.dat that is used by a password manager system. It might be used by a Python program that lets you view or edit passwords stored there, and by a web application that integrates the password database with a browser. Each of these programs may need exclusive access to keyring.dat at various times. A lockfile system for this purpose might look like this:
keyring.dat, it checks to see whether a different file named locked-keyring.dat already existslocked-keyring.dat and considers its exclusive access to keyring.dat to be obtainedkeyring.dat is finished using it, it removes locked-keyring.dat, allowing other programs to claim exclusive use of it.While there can be problems with lock files in general, this structure is a good candidate for implementation using a context manager.
Make a context manager class OpenWithLock whose constructor accepts a filename fn (such as keyring.dat) and a mode (such as "w" or "r" or "a", specifying the type of access to a file). When entering an associated with-block, this context manager will
"locked-"+fn exists"locked-"+fnfn in mode mode and return the file objectAnd when exiting the with-block, this context manager will
fn"locked-"+fnYou might use this context manager as follows:
print("I'm about to attempt to open reserved-seats.txt for exclusive use.")
print("If another process already has it locked, there may be a delay.")
with OpenWithLock("reserved-seats.txt","r") as fp:
print("Ok, I have exclusive access to reserved-seats.txt")
print("A lock file named 'locked-reserved-seats.txt' was created so other programs know that.")
x = fp.read()
# maybe do things with x...
print("I have relinquished my exclusive access to reserved-seats.txt")
print("The lock file has been removed.")
How can you test that this context manager behaves as expected? If you haven't tested the behavior when the lock file already exists, it is hard to know whether the context manager is working!
If we write a+b+c+d, then we are using the associativity of addition to avoid the need for any parentheses.
There are lots of ways to put parentheses into the expression so that each time we use addition, it is a binary operation. For example:
((a+b)+(c+d)) (i.e. first add a+b, then add c+d, then sum the results)(a+(b+(c+d))) (i.e. first add c+d, then add b to that, then add a to that)Write a Python function that takes a list of integers and returns all possible ways of parenthesizing the sum fully.
This requires a choice of how to represent the input sum and output parenthesized sums. Instead of using strings, make your function so it expects a list of summands as input and returns a list of possible parenthesized versions that use nested Python lists to represent the parentheses, as in the following example:
put_parens([2,1,5,8]) # find all ways to put parentheses in the expression 2+1+5+8
The return value is a list of length 5, which means there are five ways to add parentheses. Each item in the list describes one of the ways in to add parentheses, with nested lists instead of nested parentheses. So the five items shown above represent the expressions:
(2+(1+(5+8)))
(2+((1+5)+8))
(2+1)+(5+8)
((2+(1+5))+8)
(((2+1)+5)+8)put_parens may call itself many times, with the exact number of times depending on its argument.Work on this if you have extra time. No solutions will be given. Feel free to ask the instructor if you work on this outside of lab and have questions!
It would be nice if the lock file created by the context manager from problem didn't just capture the fact that some program was using a file, but also which program.
The module os contains a function os.getpid() which returns a numerical identifier (process ID or PID) that the operating system gives to the currently-running program, like so:
import os
os.getpid()
Modify the OpenWithLock class so that the lock file's name is not fixed, but instead incorporates the PID of the program that locked it. Thus if process 21256 locks keyring.dat, it would do so by creating a file named locked-21256-keyring.dat
But when the class is checking whether or not the file is already locked, it needs to look for any file whose name begins with "locked-" and ends with "-keyring.dat". If any such file exists, then it waits until that file is gone before creating its own lock file.
To check whether a file whose name matches a certain pattern exists, you have a couple of choices:
glob.glob, a function built for enumerating all files whose names match a pattern; read how to use it in Python documentation of the glob moduleos.listdir to get a listing of all files, and then check them one by one to see if they start with "locked-" and end with "-" + fn.This continues the work from problem 3.
Suppose we define a new sequence $c_n$ as follows: $c_n$ is the number of function calls that occur when calculating $T_n$ recursively. That is, $c_n$ is ths sequence of call counts you saw in part C of problem 3.
Can you determine a formula that gives $c_n$, perhaps as a sum of previous terms?