# 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 46.4 Indian rupees, 1 Indian rupee buys 2.5 Japanese yen, and 1 Japanese yen buys 0.0091 U.S. dollars. Then, by converting currencies, a trader can start with 1 U.S. dollar and buy 46.4 × 2.5 × 0.0091 = 1.0556 U.S. dollars, thus turning a profit of 5.56 percent. Suppose that we are given n currencies c1, c2,..., cn and an n × n table R of exchange rates, such that one unit of currency ci buys R[i, j] units of currency cj.

a. Give an efficient algorithm to determine whether or not there exists a sequence of currencies (Ci1, Ci2, . . ., Cik) such that R[i1, i2] · R[i2, i3] R[ik-1, ik] · R[ik, i1] > 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.

a. Give an efficient algorithm to determine whether or not there exists a sequence of currencies (Ci1, Ci2, . . ., Cik) such that R[i1, i2] · R[i2, i3] R[ik-1, ik] · R[ik, i1] > 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 to relevant Questions

b. Describe an efficient method to determine whether or not one d-dimensional box nests inside another.c. Suppose that you are given a set of n d-dimensional boxes {B1, B2,..., Bn}. Describe an efficient algorithm to ...Professor Green street claims that there is a simpler way to re-weight edges than the method used in Johnson's algorithm. Letting w* = min (u, v)E {w(u, v)}, just define w(u, v) = w(u, v) - w* for all edges (u, v) E. What ...The edge connectivity of an undirected graph is the minimum number k of edges that must be removed to disconnect the graph. For example, the edge connectivity of a tree is 1, and the edge connectivity of a cyclic chain of ...Let G = (V, E) be a flow network with source s, sink t, and an integer capacity c (u, v) on each edge (u, v) ¬ E. Let C = max (u, v) Ec (u, v). a. Argue that a minimum cut of G has capacity at most C ...There are two types of professional wrestlers: "good guys" and "bad guys." Between any pair of professional wrestlers, there may or may not be a rivalry. Suppose we have n professional wrestlers and we have a list of r pairs ...Post your question

0