This worksheet focuses on three small topics from week 4 lectures: the Jupyter notebook interface, context managers, and our first lecture 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.
To get some experience using the notebook interface, work on this assignment in 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)lab5.ipynbnetid@uic.edu account (or any other google account)lab5There 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$.
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.
Can you determine a formula that gives $c_n$, perhaps as a sum of previous terms?
Sometimes, a program will read or write files that 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 files at certain times so that it can make changes or process data without concern that it will be
There are a lot of mechanisms for handling this situation. One of the oldest approaches involves a cooperative agreement between all the programs that might need to touch a certain file that:
To make this precise, imagine there might be a file called keyring.dat that is used by a password manager system. The system might include a Python program that lets users add, list, edit, and remove passwords from the database. It might also include a browser extension that allows passwords to be pasted directly into login forms. Both the Python client and the browser extension may need exclusive access to keyring.dat at various times. Without that, the browser extension might try to read a password that is in the process of being changed or removed by the Python client. 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!
It would be nice if the lock file 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.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.