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 11 U. S. dollar buys 4949 Indian rupees, 11 Indian rupee buys 22 Japanese yen, and 11 Japanese yen buys 0.01070.0107 U. S. dollars. Then, by converting currencies, a trader can start with 11 U. S. dollar and buy 49 \times 2 \times 0.0107 = 1.048649×2×0.0107=1.0486 U. S. dollars, thus turning a profit of 4.864.86 percent.

Suppose that we are given nn currencies c_1, c_2, \ldots, c_nc
1

,c
2

,…,c
n

and an n \times nn×n table RR of exchange rates, such that one unit of currency c_ic
i

buys R[i, j]R[i, j] units of currency c_jc
j

.

a. Give an efficient algorithm to determine whether or not there exists a sequence of currencies \langle c_{i_1}, c_{i_2}, \ldots, c_{i_k} \rangle⟨c
i
1



,c
i
2



,…,c
i
k



⟩ such that

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.
R[i
1

,i
2

]⋅R[i
2

,i
3

]⋯R[i
k−1

,i
k

]⋅R[i
k

,i
1

]>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.