# Algorithms (CS 331H)

Posted by Ashwin Madavan on April 6, 2016

# Workshop Selection

Let $$D$$ be the set of all possible days to hold a workshop and let $$P$$ be the set of people interested in attending the workshop such that each person $$p_{i}$$ wants to attend during $$[s_{i}, f_{i}] \subset D$$. Each day $$d_{i}$$ costs $$c_{i}$$, but each person $$p_{i}$$ will willing pay $$v_{i}$$ to attend. Suppose there is no limit to the number of people that can attend on a particular day, what days should you select to maximize profit?

Constrct a flow network $$N = (V, E)$$ as follows:

• Create a source vertex $$s \in V$$ and a sink vertex $$t \in V$$
• Create a vertex for each person $$p_{i} \in P$$
• Create a vertex for each day $$d_{j} \in D$$
• Create a directed edge $$(s, p_{i})$$ of capacity $$v_{i}$$ for all $$p_{i} \in P$$
• Create a directed edge $$(d_{i}, t)$$ of capacity $$c_{i}$$ for all $$d_{i} \in D$$
• Create a directed edge $$(p_{i}, d_{j})$$ of capacity $$\infty$$ for all $$p_{i}$$ such that $$d_{j} \in [s_{i}, f_{i}]$$

For some subset $$U \subset V$$, let $$rev(U) = \sum\nolimits_{p_{i} \in U} v_{p}$$ and $$cost(U) = \sum\nolimits_{d_{i} \in U} c_{i}$$. Clearly, $$profit(U) = rev(U) - cost(U)$$.

Find the minimum cut $$S, T$$ of $$N$$. Because all $$s-t$$ paths contain edges of finite capacity by construction, the minimum cut must always be finite. Therefore, the cut-set of the minimum cut $$S, T$$ may only contain edges of the form $$(s, p_{i})$$ or $$(d_{i}, t)$$. Because no edges may cross the cut, all the desired days for each person in $$S$$ must be in $$S$$. Consequently, the cut capacity is defined as:

$c(S, T) = \sum\nolimits_{p_{i} \in T} v_{i} + \sum\nolimits_{d_{j} \in S} c_{j} = rev(T) + cost(S)$

Therefore,

\begin{align*}profit(S) &= rev(S) - cost(S) \\ &= rev(V) - (rev(T) + cost(S)) \\ &= rev(V) - c(S, T)\end{align*}

Because $$c(S, T)$$ is minimal, $$profit(S)$$ must be maximal. Therefore, the days $$d_{i} \in S$$ generate the maximal profit of $$rev(V) - c(S, T)$$.

# Detecting Arbitrage

Let $$C$$ be a set of currencies and let the $$R$$ be the set of exchange rates between currencies such that $$r(c_{i}, c_{j}) \in R$$ is the exchange rate between currencies $$c_{i}$$ and $$c_{j}$$. Clearly, $$r(c_{i}, c_{j}) = \frac{1}{r(c_{j}, c_{i})}$$. Arbitrage occurs when there are opportunities for riskless profit. How do you detect arbitrage opportunities between currencies?

In the graph $$G = (C, R)$$ arbitrage occurs where there exists a cycle of currencies $$c_{1},c_{2},\ldots,c_{k},c_{1}$$ such that:

\begin{align*}r(c_{1}, c_{2}) r(c_{2}, c_{3}) \ldots r(c_{k-1}, c_{k}) r(c_{k}, c_{1}) &> 1\\ \log r(c_{1}, c_{2}) + \log r(c_{2}, c_{3}) + \ldots + \log r(c_{k-1}, c_{k}) + \log r(c_{k}, c_{1}) &> 0\\ \log \frac{1}{r(c_{1}, c_{2})} + \log \frac{1}{r(c_{2}, c_{3})} + \ldots + \log \frac{1}{r(c_{k-1}, c_{k})} + \log \frac{1}{r(c_{k}, c_{1})} &< 0\end{align*}

Therefore, detecting arbitrage opportunities in $$G$$ is equivalent to finding negative cost cycles in the graph $$G' = (C, \{ \log \frac{1}{r} : r \in R\})$$, which can be found in $$O(\lvert C \rvert ^{3})$$ using the Floyd-Warshall Algorithm.

# Tiling

How many ways can one tile a 3 x n rectangle using 2 x 1 tiles? It is immediately clear that $$n$$ must be even, because it is impossible to tile an odd area with even area tiles. Therefore, $$n = 2 \cdot k$$ and $$k \in \mathbb{N}$$. By enumerating the various ways to tile 2 x 1 tiles on a 3 x $$2 \cdot k$$ rectangle for $$k \in \{1, 2, 3\}$$, I determined that the number of tilings:

$\begin{equation*}T(k) = 3 \cdot T(k - 1) + 2 \cdot T(k - 2) + 2 \cdot T(k - 3) + ... + 2 \cdot T(0)\end{equation*}$ $\begin{equation*}T(k - 1) = 3 \cdot T(k - 2) + 2 \cdot T(k - 3) + ... + 2 \cdot T(0)\end{equation*}$

By subtraction of these two equations,

\begin{align*} T(k) - T(k - 1) &= [3 \cdot T(k - 1) + 2 \cdot T(k - 2) + ... + 2 \cdot T(0)] - \\ &\ \qquad [3 \cdot T(k - 2) + 2 \cdot T(k - 3) + ... + 2 \cdot T(0)] \\ &= 3 \cdot T(k - 1) - T(k - 2)\end{align*}

Therefore, $$T(k) = 4 \cdot T(k - 1) - T(k - 2)$$. The characteristic equation of this linear homogeneous recurrence relation is $$r^{2} = 4 \cdot r - 1$$. The roots of this characteristic equation are $$a_{1} = \frac{4 + \sqrt{12}}{2} = 2 + \sqrt{3}$$ and $$a_{2} = \frac{4 - \sqrt{12}}{2} = 2 - \sqrt{3}$$. Suppose the closed-form solution of the recurrence relation is of the form

$T(k) = c_{1} a_{1}^{k} + c_{2} a_{2}^{k} = c_{1} (2 + \sqrt{3})^{k} + c_{2} (2 - \sqrt{3})^{k}$ \begin{align*}T(0) = 1 \implies 1 &= c_{1} + c_{2} \implies c_{2} = 1 - c_{1} \\ T(1) = 3 \implies 3 &= c_{1} (2 + \sqrt{3}) + c_{2} (2 - \sqrt{3}) \\ &= c_{1} (2 + \sqrt{3}) + (1 - c_{1}) (2 - \sqrt{3}) \\ &= 2 \sqrt{3} c_{1} + 2 - \sqrt{3}\end{align*}

Consequently, $$c_{1} = \frac{1 + \sqrt{3}}{2 \sqrt{3}}$$ and $$c_{2} = 1 - \frac{1 + \sqrt{3}}{2 \sqrt{3}} = \frac{\sqrt{3} - 1}{2 \sqrt{3}}$$. Therefore, the closed-form solution to the recurrence relation is $$T(k) = \frac{1 + \sqrt{3}}{2 \sqrt{3}} (2 + \sqrt{3})^{k} + \frac{\sqrt{3} - 1}{2 \sqrt{3}} (2 - \sqrt{3})^{k}$$ and solves the problem in $$O(1)$$ time and $$O(1)$$ space.

How many ways can one tile a k x n rectangle using 2 x 1 tiles? Assuming we can tile the first n-1 columns of the rectangle, how many ways are there to tile the last column? We can either tile elements in the last column one-at-a-time using a horizontal tile or two-at-a-time using a vertical tile. Therefore, the number of ways to tile the last column $$f(k) = f(k-2) + f(k-1)$$. Because the $$n^{th}$$ Fibonnaci number $$F(n) = \frac{\phi^{n}}{\sqrt{5}}$$, the number of ways to tile the last column grows exponentially with $$k$$. Because there are $$n$$ columns in the matrix, the complexity of the algorithm is $$O(\phi^{nk})$$.

Cover photograph by aspireblog.