14
$\begingroup$

I found a really interesting problem and I wanted to hear people's opinion.

It has to do with currency exchange rate.

If we are give some coins $c_1,c_2,\dots,c_n$ and an array $R$ that keeps the selling price, where $R[i,j]$ is the selling price of one unit of currency $c_i$ to currency $c_j$.

a) We are trying to design an algorithm that will find a sequence of coins $(c_{i_1}, c_{i_2}, \dots, c_{i_k})$ ,$R[i_1, i_2] \cdot R[i_2, i_3] \cdots R[i_{k-1}, i_k] \cdot R[i_k, i_1] >1$.

b) Show how the algorithm you designed can find and print fast such a sequence $(c_{i_1}, c_{i_2}, \dots, c_{i_k})$ (if there is one).

If someone dives into that problem it would be also interesting to know the execution time of the algorithm.

Sorry if I did mistakes with the terminology of this scientific field.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Sorry, this problem has little -- if at all -- to do with economics (and I retagged the post to reflect this). This problem is about finding positive (or negative) weight cycles in a directed graph, which can be solved using Bellman-Ford (e.g.). $\endgroup$ – Srivatsan Dec 27 '11 at 11:09
  • $\begingroup$ @Srivatsan Is this problem related with graph theory? $\endgroup$ – tasmer_k Dec 27 '11 at 11:09
  • 2
    $\begingroup$ This question is a trivial modification of Exercise 24-3 of Introduction to Algorithms by CLRS, 2nd ed., Chap. 24 Single Source Shortest Paths. $\endgroup$ – Srivatsan Dec 27 '11 at 11:17
  • $\begingroup$ @Srivatsan Thank you. I will try to borrow this book. It must be very interesting to read. $\endgroup$ – tasmer_k Dec 27 '11 at 11:21
  • 1
    $\begingroup$ @tasmer_k May I assume that this is not homework? If so, then I can give you the "reduction" to a standard graph theoretic algorithm, namely Bellman-Ford. $\endgroup$ – Srivatsan Dec 27 '11 at 11:24
18
$\begingroup$

Conceptually, it is easier to think of the “log-exchange rates” defined by $L[i, j] = - \log R [i, j]$. (The negative sign is just for the sake of convention.) Now imagine a directed graph with the currencies as the vertices where the weight of the edge $(i, j)$ is $L[i, j]$. In terms of the new quantity we just introduced, we are seeking a cycle $(i_1, i_2, \ldots, i_k)$ such that $$ \sum_{t = 1}^{k-1} L[i_t, i_{t+1}] + L[i_k, i_1] \lt 0. $$ This equation is obtained by just taking the log of the given equation, and reversing the sign. That is, we are seeking a “negative weight cycle” in the graph, where the weight of a cycle is just the sum of the edges in the cycle.

Negative cycle detection is a standard problem in algorithmic graph theory, conventionally studied along with the shortest path problem. [The shortest path problem is the following: given a directed graph with a source and a sink terminal, find the path of least cost from the source to the sink.] A number of algorithms have been designed to solve these problems. The simplest one (in general graphs) is the Bellman-Ford algorithm which runs in $O(|V||E|)$.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.