Assignment 3¶

Due Wednesday Oct 23

Problem 1: Optimal paths in snakes and ladders¶

There are a variety of game boards called "snakes and ladders" or "chutes and ladders", but all work like this: the board has 100 squares, some of which are connected by arrows (an arrow that goes from a smaller number to a larger number is a "ladder"; one that goes the other way is a "chute" or "snake"). Each player takes a turn to roll a six-sided die and advance their token the number of squares shown on the die; if their final location is at the base of an arrow then they move to the end of the arrow. The game is begun on square "zero", and finishes when square 100 is reached; a rolls that would move a player past 100 does not move the player. One version of the board has arrows with [start, end] as follows:

sladders = [[1, 38], [4, 14], [9, 31], [21, 42], [28, 84], [36, 44], [51, 67], [71, 91], [80, 100],
            [16, 6], [48, 26], [49, 11], [56, 53], [62, 19], [64, 60], [87, 24], [93, 73], [95, 75], [98, 78]]

For instance, on the first roll, the player could end up in the squares 38, 2, 3, 14, 5, or 6. If a player in square 14 rolled a 2, they'd end up at square 6.

(a) Represent possible moves on the board as a directed graph on 101 vertices. Use the adjacency matrix to find the number of distinct paths of length $k$ from 0 to 100 for each $1 \le k \le 50$.

(b) For $1 \le k \le 50$, find the number of distinct paths of length $k$ that start from 0 and have not yet hit 100, and combine this answer with (a) to get the probability of not having yet finished after $k$ moves (Hint: every possible path is equally likely.) Plot a graph of this probability. You might consider using a log scale, since I imagine that the probability gets pretty small pretty fast.

(c) Let $\alpha(j)$ be the length of the shortest path from square $j$ to square 100, for each $0 \le j \le 100$. Write a program that finds $\alpha(j)$. (Hint: start at $j=100$ and work backwards.)

Note: If you read carefully, I'm not asking you to simulate a game of snakes and ladders! But, if you're unsure about whether you've done these problems correctly then, it is pretty easy to simulate a game and see whether your simulation is in line with your computations.

Also note: This problem is tailor-made for numpy's matrices, not sympy's matrices!

Problem 2: trees on n vertices¶

(a) Let $G(x)$ be the exponential generating function for rooted trees on $n$ vertices. We saw in class that $G(x) = x \exp G(x)$. Use Lagrange inversion for formal Laurent series to verify that there are $n^{n-1}$ rooted trees on $n$ vertices. Note: there's also a theorem in analysis called "Lagrange inversion", related to the inverse function theorem - we want the formal power series one I've linked above.

(b) Let $G_0(x) = x$ and, recursively, let $G_m(x) = x \exp G_{m-1}(x)$ for $m \geq 1$. I optimistically asserted in class that the $G_m(x)$ "probably converge" to the power series in (a). With a computer experiment, explore whether or not I was correct; then, prove or disprove a rigorous version of my statement (make sure to say what "converge" means).

Problem 3: A minimal spanning tree algorithm¶

Consider the following greedy algorithm to find a minimal spanning tree $T$ of a weighted graph (i.e. a graph G=(V,E) equipped with a weight function $w:E \rightarrow \mathbb{R}_{\geq 0}$ by adding edges to $T$ one at a time (note: here we are changing $T$)

  1. Add the smallest edge (i.e. the edge $e$ for which $w(e)$ is smallest).
  2. Consider the next smallest edge. If adding it does not create a cycle, add it. Otherwise, do not add it.
  3. Repeat step 2 until you have a tree.

What named algorithm is this? Cite your sources; sketch a proof that it works, and implement it efficiently (you can get it to run in time $O(m \log m)$, where there are $m$ edges).

Problem 4: hypercube¶

  1. Let $\otimes$ be the Kronecker Product on matrices and let $A$, $B$ be square matrices. Describe the eigenvalues and eigenvectors of $A \otimes B$ in terms of the eigenvalues and eigenvectors of $A$ and of $B$.

  2. Show that the adjacency matrix of the Cartesian product of two graphs is $A \otimes I_n + I_m \otimes B$, where $A$ and $B$ are the adjacency matrices of the two graphs, and $m$ and $n$ are the number of vertices of the two graphs.

  3. Find the eigenvalues and eigenvectors of the adjacency matrix of the $n$-cube graph, whose vertices are $\{0,1\}^n$ and whose edges are $\{(u,v):|u-v|=1\}$.

Problem 5: spanning trees on hypercubes¶

This continues on from Problem 4, but gets its own problem number so I can continue grading out of 50.

  1. Suppose $G$ is a $d$-regular graph (meaning that all vertices of $G$ have degree $d$. Relate the eigenvalues/eigenvectors of $G$'s adjacency matrix to those of $G$'s Laplacian. Is the hypothesis of $d$-regularity actually needed?

  2. Now find the number of spanning trees of the $n$-cube graph, using facts from linear algebra about determinants and eigenvalues.