CSE 102 – Midterm Exam

General instructions (original)

Post-exam instructions

Now that the exam is over, you can upload your solution file below to the submission server and get feedback from the automated tests. Each problem of the exam was evaluated using several partial correctness tests, and a green checkmark will appear under the “Status” field just in case you passed all of them. You can look at the Log to see the results of all of the partial correctness tests.

Section 1: generalized Fibonacci numbers

The Tribonacci numbers \(T_n\) are defined by the recurrence

\[ T_{n} = T_{n-3} + T_{n-2} + T_{n-1} \]

for all \(n \geq 3\), with initial values \(T_0=0, T_1=0, T_2=1\).

Thus, the Tribonacci sequence starts with

\[ 0, 0, 1, 1, 2, 4, 7, 13, \dots \]

We generalize Tribonacci numbers further to k-bonacci numbers \((k\geq 2)\), which are recursively defined by taking \(K^k_n = K^k_{n-k} + \dots + K^k_{n-1}\) to be the sum over the \(k\) preceeding k-bonacci numbers for \(n \ge k\), together with the initial values \(K^k_0 = K^k_1 = \dots = K^k_{k-2} = 0\) and \(K^k_{k-1} = 1\).

Here are some more examples to test your implementation:

kbonacci(30,2) = 832040
kbonacci(30,3) = 15902591
kbonacci(30,4) = 28074040
kbonacci(100,5) = 8196759338261258264777004033

Section 2: random graphs

In this section, we are going to study the connectedness of random graphs.

Recall the adjacency list representation of graphs. We consider only symmetric graphs with node labels \(0..n-1\). (As usual, symmetric means that if there is an edge from \(i\) to \(j\) then there is also an edge from \(j\) to \(i\).)

For example, here are two symmetric graphs with \(10\) nodes in this representation:

example_graph1 = {0: [3], 1: [], 2: [7], 3: [0, 7], 4: [8, 9], 5: [9], 6: [], 7: [2, 3], 8: [4], 9: [4, 5]}
example_graph2 = {0: [2, 5], 1: [8], 2: [0, 3, 7, 8], 3: [2, 9], 4: [7], 5: [0, 6], 6: [5], 7: [2, 4], 8: [1, 2, 9], 9: [3, 8]}

We consider the random graph model proposed by Edgar Gilbert. In this model, given an integer \(n\) and a probability \(p\), a symmetric random graph with \(n\) nodes is produced by deciding with probability \(p\) whether to include an edge \(i \leftrightarrow j\) between any pair of distinct nodes \(i \ne j\). (Note the resulting graph is simple, meaning that it has no loops or parallel edges.)

For plausibility-checking your implementation, we can compute the expected number of edges in such a random graph. The following test function should return about \(50\).

def random_graph_test():
    edges=0
    for _ in range(10):
        g = gilbert_random_graph(100,0.01)
        edges += sum(len(g[k]) for k in g)//2  # divide by 2 since g is symmetric
    return edges/10

More generally, we can use the random graph model to test the expected properties of graphs of a given size \(n\), for a given edge probability \(p\), such as whether or not they are connected.

Finally, we can visualize the dependency between edge probability and the probability of being connected using pyplot.

steps = 25
pmax = 0.5
xs = [ ((x+1)/steps)*pmax for x in range(steps) ]
ys = [connected_probability(20, p, 500) for p in xs]

from matplotlib import pyplot as plt
plt.plot(xs,ys)
plt.show()

The resulting plot shows an interesting phase transition!

Section 3: self-avoiding lattice walks

In this section, we are going to generate self-avoiding walks on \(\mathbb{Z}^2\), also called walks over a square lattice.

We define a n-step walk \(w\) as a sequence of \(n\) moves going right (R), left (L), up (U), or down (D), corresponding to a choice of vectors in \(\mathcal{M} = \{(1,0),(-1,0),(0,1),(0,-1)\}\). We can represent an \(n\)-step walk by a list of \(n+1\) integer coordinates \((x_0,y_0),\dots,(x_{n},y_{n})\), where the displacement vectors \((x_{i+1},y_{i+1}) - (x_i,y_i) = (x_{i+1}-x_i,y_{i+1}-y_i)\) are in \(\mathcal{M}\) for all \(0\leq i < n\).

We call a walk self-avoiding if all of its points \((x_i,y_i)\) are distinct.

As an example, we illustrate a 10-step self-avoiding walk (SAW) below, which starts at the origin \((0,0)\) and then takes a series of steps R, U, R, U, L, L, L, D, D, D:

And here is its Python representation as a list of distinct coordinates:

example_saw = [(0,0),(1,0),(1,1),(2,1),(2,2),(1,2),(0,2),(-1,2),(-1,1),(-1,0),(-1,-1)]

We are interested in generating random self-avoiding walks, for a given number of steps \(n\) and starting point \((x_0,y_0)\).

First, we consider a strategy that repeatedly selects moves in \(\mathcal{M}\) at random, each with the same probability, in order to determine the next coordinate \((x_{i+1},y_{i+1})\) from its predecessor \((x_i, y_i)\). In this strategy the newly selected point can clash with a previous point in the walk, in the sense that \((x_{i+1},y_{i+1}) = (x_j,y_j)\) for some \(j\) between \(0\) and \(i-1\). In this case the whole procedure simply restarts from the initial point \((x_0,y_0)\), which is why we call it the restart strategy.

Since the restart strategy is inefficient for longer walks, it looks attractive to avoid restarting from scratch and rather find a random SAW by backtracking.

Like the restart strategy, this strategy extends the walk step-by-step. However, in case of a clash the backtracking strategy systematically tries extending the walk by a different step in \(\mathcal{M}\), and if none of those work backtracks to a previous point, until an \(n\)-step self-avoiding walk is produced. The randomness comes from trying the four possible moves in \(\mathcal{M}\) in a random order.

Interestingly, the backtracking strategy does not generate \(n\)-step SAWs uniformly at random. To observe this (and test your implementations) let us define the displacement of a walk \(w = [(x_0,y_0),\dots,(x_n,y_n)]\) as the end-to-end Euclidean distance between the first and last point: \[d(w) = \sqrt{(x_n-x_0)^2 + (y_n-y_0)^2}\] The function expected_displacement(random_saw, n, trials) below takes as first argument a function for generating random SAWs under some strategy, and then repeatedly calls it to generate \(n\)-step SAWs for some number of trials to get an estimate of the average displacement:

def expected_displacement(random_saw, n, trials):
    def d(walk):
        return ((walk[-1][0] - walk[0][0])**2 + (walk[-1][1] - walk[0][0])**2)**0.5
    return sum(d(random_saw(0,0,n)) for _ in range(trials)) / trials

By instantiating expected_displacement appropriately, you can get an estimate of the expected displacement under the two different strategies. For example, assuming you have implemented the restart strategy correctly, calling

expected_displacement(random_saw_restart, 21, 1000)

should give a value slightly higher than 8 most of the time (but perhaps sometimes slightly lower), whereas assuming you have implemented the backtracking strategy correctly, calling

expected_displacement(random_saw_backtrack, 21, 10000)

should give a value around 6.7 (again with slight variation). This shows that the backtracking strategy preferentially produces self-avoiding walks that are more compact!

Finally, the backtracking strategy can be easily adapted to perform exhaustive enumeration of all SAWs of length \(n\).

(One may be tempted to use exhaustive backtracking to perform uniform random generation by exhaustively enumerating all \(n\)-step SAWs and then selecting one uniformly at random, but this strategy is even more inefficient than the restart strategy. The problem is that the number of SAWs grows too quickly!)