Describe the problem as a graph problem. What are your nodes
*Data Structures and
In economics, arbitrage is the practice of taking advantage of a difference in prices in two or more markets; striking a combination of matching deals to capitalize on the difference, the profit being the difference between the market prices at which the unit is traded.
Arbitrage can become a source of gain when applied to currency exchanges. Consider the fol- lowing currency exchange ratios as an example: 1 U.S. dollar buys 0.7292 euros, 1 euro buys 105.374 Japanese yen, 1 Japanese yen buys 0.3931 Russian rubles, 1 Russian ruble buys 0.0341 U.S. dollars.
Then you could take 1 U.S. dollar and buy 0.7292 euros with it, with which you can buy 76.8387 yen (because 0.7292 * 105.374 = 76.8387). Then take the 76.8387 yen and buy 30.2053 rubles (because 76.8387 * 0.3931 = 30.2053), and finally take the 30.2053 rubles and buy 1.03 dollars (because 30.2053 * 0.0341 = 1.0300).
Assume that you are given the pairwise trading ratios among n currencies and answer the following questions about arbitrage accordingly.
(a) Describe the problem as a graph problem. What are your nodes? What are the edges? Is this a weighted graph? Is the graph directed? What is the goal over this graph?
(b) Suggest an algorithm in plain English that evaluate whether an arbitrage exists among these n currencies.
(c) Expand your algorithm so that it prints the chain of arbitrage and analyze the running time of your algorithm.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
