\documentclass{article}
\input{6046preamble}


\begin{document}
\pset{5-1}{Dan Ports}{No collab}{Recitation \#8}

\begin{ppart}{Part a}
\paragraph{Algorithm}
First, we convert the given currencies and rates of exchange into a graph whose vertices represent currencies and whose edges have weights given by $w(i,j)=-\lg(r_{i,j})$. Building this graph requires time $\Theta(V+E)$, where $V=n$ is the number of vertices/currencies and $E$ is the number of edges in the graph ($E=O(n^2)$). Next we apply the Bellman-Ford algorithm to find the shortest path from vertex representing the starting currency to the vertex representing the desired currency. We return the sequence of currency exchanges that corresponds to this path. The Bellman-Ford algorithm requires time $O(VE) = O(n^3)$, so the algorithm runs in time $O(n^3)$.
\paragraph{Proof of correctness}
We will justify correctness by arguing a bijection between the currency exchanges and our graph. 
For a sequence of exchanges between currencies $x_1, x_2, ... , x_n$, the overall exchange rate is the product of the individual exchange rates: $\prod_{i=1}^{n-1}{r_{x_i,x_{i+1}}}$. This equals $2^{\lg\prod_{i=1}^{n-1}{r_{x_i,x_{i+1}}}} = 2^{\sum_{i=1}^{n-1}{\lg r_{x_{i,i+1}}}} = 2^{-{\sum_{i=1}^{n-1}{w(x_i,x_{i+1})}}}$, applying the properties of logarithms and the definition of $w(i,j)$.

\paragraph{}
Therefore, to maximize the currency we end up with, we need to maximize the rate $2^{-{\sum_{i=1}^{n-1}{w(x_i,x_{i+1})}}}$. To do this, we minimize $\sum_{i=1}^{n-1}{w(x_i,x_{i+1})}$, which is the total cost of a path $x_1, x_2, ... x_n$ leading from the zlotys vertex to the dollars vertex in our graph. 
We assume the Bellman-Ford algorithm is correct and provides us the lowest-cost path from the starting vertex to the target vertex. The only necessary condition is that there are no negative-weight cycles in our graph. We know that this is the case. By contradiction: suppose there were a cycle with weight $-x$ ($x>0$). 
Then, by the above weight-rate bijection, the net exchange rate for following that cycle of currency exchanges is $2^{-(-x)} = 2^x > 1$. This means that following this directed trades makes a profit, which violates one of our given assumptions. So there can be non negative-weight cycles and the Bellman-Ford algorithm gives the correct result.

\end{ppart}


\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: