Course instructor: Emily Dumas
Contributors to this document: Johnny Joyce, Kylash Viswanathan
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?
def T(n):
"""Returns n-th entry in sequence T"""
if n == 0 or n == 1 or n == 2:
return n
elif n > 0:
return T(n-1) + T(n-2) + T(n-3)
else:
raise ValueError("Please enter a positive number.")
def T_iterative(n):
"""Iterative version of T_n"""
T_vals = [0,1,2]
while len(T_vals) <= n:
vals.append(T_vals[-1] + T_vals[-2] + T_vals[-3])
return T_vals[-1]
def T_count(n):
"""Returns number of times T calls itself when calculating T_n"""
if n == 0 or n == 1 or n == 2:
return 1
else:
return count(n-1) + count(n-2) + count(n-3) + 1
The following recursive formula can be used:
$$\begin{split} c_0 &= 1\\ c_1 &= 1\\ c_2 &= 1\\ c_{n} &= c_{n-1} + c_{n-2} + c_{n-3} + 1 \; \text{ if } n \geq 3\end{split}$$We have $c_0 = c_1 = c_2 = 1$ because only one call is needed. For the recursive step, we add up the number of calls made for $n-1$, $n-2$, and $n-3$, then add 1 because we already made another call with input $n$.
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.class OpenWithLock:
"""Context manager for locking a file when in use"""
def __init__(self, fn, mode):
"""Save file name and file opening mode as attributes"""
self.fn = fn
self.mode = mode
def __enter__(self):
"""Wait until lockfile no longer exists, then create lockfile and open given file"""
# Wait until lockfile no longer exists
while os.path.exists("locked-" + self.fn):
time.sleep(0.1)
# Create lockfile by opening and closing
open("locked-" + self.fn, "a").close()
self.file = open(self.fn, self.mode)
return self.file
def __exit__(self, exc_type, exc, tb):
"""When finished, close file and remove lockfile."""
self.file.close()
os.remove("locked-" + self.fn)
class OpenWithLock:
"""Context manager for locking a file when in use"""
def __init__(self, fn, mode):
"""Save file name and file opening mode as attributes"""
self.fn = fn
self.mode = mode
def is_locked(self):
"""Helper function. Checks whether a lockfile exists."""
for filename in os.listdir():
if filename.startswith("locked-") and filename.endswith(self.fn):
return True
return False
def __enter__(self):
"""Wait until lockfile no longer exists, then create lockfile and open given file"""
while self.is_locked():
time.sleep(0.1)
# Create lockfile by opening and closing
open("locked-" + os.getpid() + self.fn, "a").close()
self.file = open(self.fn, self.mode)
return self.file
def __exit__(self, exc_type, exc, tb):
"""When finished, close file and remove lockfile."""
self.file.close()
os.remove("locked-" + os.getpid() + self.fn, "a")
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.In the solution below, the for loop uses the range(len(..)) constructor.
If we want to avoid this, we can use the enumerate function instead, which iterates over both the indices and the list entries at the same time. This means we'd change the for loop into the following:
for i, val in enumerate(L[1:], 1):
(Note here that the ", 1" means that we should start counting from 1)
def put_parens(L):
"""Finds all ways to put parentheses"""
if len(L) == 1: # No way to put parentheses
return L
if len(L) == 2: # Only one way to put parentheses
return [L]
output = []
# At each index `i`, split the list into two halves
for i in range(1, len(L)):
# Make a recursive call on each half
first_halves = put_parens(L[:i])
second_halves = put_parens(L[i:])
# Then for every possible combination of parentheses from the first half, ...
# ... match them with a possible combination from the second half.
# This gives us every combination of parentheses for the whole list `L`.
for first in first_halves:
for second in second_halves:
output.append([first, second])
return output
put_parens([2,1,5,8]) # find all ways to put parentheses in the expression 2+1+5+8