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.

  • 0
    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.).2011-12-27
  • 0
    @Srivatsan Is this problem related with graph theory?2011-12-27
  • 2
    This question is a trivial modification of Exercise 24-3 of _[Introduction to Algorithms_ by CLRS](http://en.wikipedia.org/wiki/Introduction_to_Algorithms), 2nd ed., Chap. 24 _Single Source Shortest Paths_.2011-12-27
  • 0
    @Srivatsan Thank you. I will try to borrow this book. It must be very interesting to read.2011-12-27
  • 1
    @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.2011-12-27
  • 0
    @Srivatsan No it is not my homework. I am studying economics. I don't know what Bellman-Ford is but I will.2011-12-27
  • 0
    Related question/answer: http://stackoverflow.com/q/2282427/10336472011-12-27

1 Answers 1