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 × 2 × 0.0107 = 1.0486 U.S. dollars, thus turning a profit of 4.86 percent.

Suppose that we are given n currencies c₁, c₂, . . . , c_n and an n × 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 〈c_i1, c_i2, . . . , c_ik〉 such that R[i₁, i₂]. R[i₂, i₃] . . . R[i_{k - 1}, i_k] . R[i_k, i₁] > 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.