Solution Found!
Arbitrage Arbitrage is the use of discrepancies in
Chapter 24, Problem 24-3(choose chapter or problem)
Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 U.S. dollar buys 49 Indian rupees, 1 Indian rupee buys 2 Japanese yen, and 1 Japanese yen buys 0:0107 U.S. dollars. Then, by converting currencies, a trader can start with 1 U.S. dollar and buy \(49 \times 2 \times 0.0107=1.0486\) U.S. dollars, thus turning a profit of 4.86 percent.
Suppose that we are given n currencies \(c_{1}, c_{2}, \ldots, c_{n}\) and a \(n \times n\) table R of exchange rates, such that one unit of currency \(c_{i}\) buys \(R[i, j]\) units of currency \(c_{j}\).
a. Give an efficient algorithm to determine whether or not there exists a sequence of currencies \(\left\langle c_{i_{1}}, c_{i_{2}}, \ldots, c_{i_{k}}\right\rangle\) such that \(R\left[i_{1}, i_{2}\right] \cdot R\left[i_{2}, i_{3}\right] \cdots R\left[i_{k-1}, i_{k}\right] \cdot R\left[i_{k}, i_{1}\right]>1 .\).
Analyze the running time of your algorithm.
b. Give an efficient algorithm to print out such a sequence if one exists. Analyze the running time of your algorithm.
Questions & Answers
QUESTION:
Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 U.S. dollar buys 49 Indian rupees, 1 Indian rupee buys 2 Japanese yen, and 1 Japanese yen buys 0:0107 U.S. dollars. Then, by converting currencies, a trader can start with 1 U.S. dollar and buy \(49 \times 2 \times 0.0107=1.0486\) U.S. dollars, thus turning a profit of 4.86 percent.
Suppose that we are given n currencies \(c_{1}, c_{2}, \ldots, c_{n}\) and a \(n \times n\) table R of exchange rates, such that one unit of currency \(c_{i}\) buys \(R[i, j]\) units of currency \(c_{j}\).
a. Give an efficient algorithm to determine whether or not there exists a sequence of currencies \(\left\langle c_{i_{1}}, c_{i_{2}}, \ldots, c_{i_{k}}\right\rangle\) such that \(R\left[i_{1}, i_{2}\right] \cdot R\left[i_{2}, i_{3}\right] \cdots R\left[i_{k-1}, i_{k}\right] \cdot R\left[i_{k}, i_{1}\right]>1 .\).
Analyze the running time of your algorithm.
b. Give an efficient algorithm to print out such a sequence if one exists. Analyze the running time of your algorithm.
ANSWER:Problem 24-3
Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 U.S. dollar buys 49 Indian rupees, 1 Indian rupee buys 2 Japanese yen, and 1 Japanese yen buys 0:0107 U.S. dollars. Then, by converting currencies, a trader can start with 1 U.S. dollar and buy 
a. Give an efficient algorithm to determine whether or not there exists a sequence of currencies 
Analyze the running time of your algorithm.
b. Give an efficient algorithm to print out such a sequence if one exists. Analyze the running time of your algorithm.
Step by Step Solution
Step 1 of 9
a.
We can design the problem as a directed graph with currencies as nodes and their converting rate as edges between them. Then our focus is to find out the cycle in which the product of edge weights is >1.