(b) Describe how to modify Bellman-Ford so that it can perform this task. Your algorithm can be described in English (pseudo-code is not necessary). Explain why your algorithm is correct and its running time.

(c) Describe how to modify Johnson’s algorithm so that it can perform this task. Your algorithm can be described in English (pseudo-code is not necessary). Explain why your algorithm is correct and its running time.

(d) Finally, describe how you could modify your algorithms to determine if its possible to profit from arbitrage for a given set of currencies and exchange rates.
 

The illustrious and not at all sketchy firm of Weil, Proffet, and Howe have entered the arbitrage business. Arbitrage is a money-making scheme involving anomalies in international currency exchange rates. For example, imagine that 1 U.S. dollar buys 0.8 Zambian kwachas, 1 kwacha buys 10 Mongolian tugriks, and 1 tugrik buys 0.15 U.S. dollars. Then, by converting currencies, a trader can start with 1 U.S. dollar and buy 0.8 10 0.15 = 1.2 U.S. dollars. By capitalizing on such anomalies very very (very very) quickly (before they're detected and corrected by the markets), huge amounts of money can be made (Note: as of today's rates, this path only nets you $0.997 per $1, so stay in your seats!). You're given n currencies and the exchange rate between every pair of currencies. That is, we are given currencies C,..., Cn and an n x n table R such that one unit of currency c, buys R[i, j] units of currency cj. (The values for all the diagonal elements are one; if one were to exchange a currency with itself one gains or looses nothing. Further, negative values for R[i, j] never occur.) (a) Lets begin with the following problem. Given a list of currencies and exchange rates and a particular currency c-i.e. a single source determine the maximum amount of each currency that you can obtain, beginning with 1 unit of currency c. For this part of the problem, assume that there exist no cycles that allow you to get arbitrarily rich via arbitrage.