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

MCS 275 Spring 2023 Worksheet 5

  • Course instructor: Emily Dumas

Topics

This worksheet focuses on three small topics from week 4 lectures: the Jupyter notebook interface, context managers, and our first lecture on recursion.

Resources

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.

1. Work in a notebook

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:

  • If you plan to work locally (on your own computer):
    • Install the notebook interface (usually python3 -m pip install notebook will do it)
    • Check that you can start it up (usually python3 -m notebook in the directory where you want your notebook files to go)
    • Create a new Python 3 notebook, giving it a name like lab5.ipynb
  • If you want to avoid installing anything:
    • Log in to Google Colab with your netid@uic.edu account (or any other google account)
    • Create a new Python 3 notebook in Colab, giving it a name like lab5

2. Sequence

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

A. Recursive implementation

Write a recursive function that calculates $T_n$.

B. Iterative implementation

Write an iterative function that calculates $T_n$.

C. Call counts

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

D. Theoretical analysis (optional challenge)

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?

3. Lockfile context manager

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:

  • When one of the programs needs exclusive access, it creates another file (the "lock file") that indicates the need for such exclusivity
  • If such a file already exists, then the program knows another one is using the file, and it must wait
  • When the program is finished using a file, it removes the lock file so that it becomes possible for other programs to use it exclusively when needed.

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:

  • When any program wants exclusive access to keyring.dat, it checks to see whether a different file named locked-keyring.dat already exists
    • If so, the program pauses for 0.1 seconds and tries again
    • If not, the program creates an empty file named locked-keyring.dat and considers its exclusive access to keyring.dat to be obtained
  • When a program that is exclusively using keyring.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.

A. Basic version

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

  • Wait 0.1 seconds repeatedly until there is no file named "locked-"+fn exists
  • Create (i.e. open and then close) an empty file called "locked-"+fn
  • Open the file named fn in mode mode and return the file object

And when exiting the with-block, this context manager will

  • Close fn
  • Delete "locked-"+fn

You might use this context manager as follows:

In [ ]:
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.")

Something to think about

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!

B. Refined version (as time allows)

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:

In [1]:
import os
os.getpid()
Out[1]:
21256

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:

  • Use 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 module
  • Use os.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.

4. Parentheses

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)
  • and more

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:

In [2]:
put_parens([2,1,5,8]) # find all ways to put parentheses in the expression 2+1+5+8
Out[2]:
[[2, [1, [5, 8]]],
 [2, [[1, 5], 8]],
 [[2, 1], [5, 8]],
 [[2, [1, 5]], 8],
 [[[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)

Hints

  1. Why is this a natural candidate for recursion?
  2. Unlike the recursion examples in Lecture 9, this one will involve a loop of recursive calls. That is, the function put_parens may call itself many times, with the exact number of times depending on its argument.