We can find opportunities for arbitrage using graphs. Given the right mathematical transformation, a graph of exchange rates can be modified so that any negative cycle is a path of currency exchange where I can start with $1M in US dollars, exchange into another currency, exchange from that currency into another, and so on until I reach a point where I can exchange back into US dollars and have more than $1M. It's free money!

Your task is to write a program that will examine a table of exchange rates and see if there is an opportunity to make money via arbitrage. I have given you much of the code (below) and a couple of tables of exchange rates (attached). Do the following:

1. Enter the code below as a new Java class. It reads a currency exchange rate table, contained in a .csv file.

2. Determine if the resulting graph has any negative cycles. Refer to the textbook website for some classes that may be useful. As discussed in class, any place where there is a cycle where the product of all weights is less than 1, will become a negative cycle if we replace each weight w (exchange rates) with log(w). You will see that I have done this.

3. If you find an opportunity to make money in either of these currency exchange tables, tell me how much money you could make on one million dollars, in one set of exchanges.

Your report will consist of:

1. Your Java source code for the final program;

2. a brief statement of your approach to the problem;

3. a list of the edges in any arbitrage cycles that you find; and

4. a paragraph in which you describe the results.

Code:

/* * CSC312 SP16  Arbitrage starting code CF Jones CBU * this program reads some currency exchange information from a * comma-separated file and checks to see if there is an opportunity * to make some money via arbitrage */ import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.util.ArrayList; import java.util.Scanner; import edu.princeton.cs.algs4.In; import java.io.IOException; import java.lang.Math; /**  *  * @author crjones  */ public class Arbitrage { private static int currToIdx(String S) { if (S.equals("AUD")) return 0; else if (S.equals("CAD")) return 1; else if (S.equals("CHF")) return 2; else if (S.equals("CNY")) return 3; else if (S.equals("GBP")) return 4; else if (S.equals("ILS")) return 5; else if (S.equals("INR")) return 6; else if (S.equals("JPY")) return 7; else if (S.equals("USD")) return 8; else  return -1; } private static void readRates(EdgeWeightedDigraph G, String fname) { int curr1 = 0, curr2 = 0; double currWt = 0; int i, j; // read file line by line  File Fin = new File(fname); In in = new In(Fin); String[] edgeStrings = in.readAllLines(); for (String s : edgeStrings) { String[] strPieces = s.split(","); curr1 = currToIdx(strPieces[0]); curr2 = currToIdx(strPieces[1]); currWt = Double.parseDouble(strPieces[2]); double EdgeWeight = -java.lang.Math.log(currWt); int EWround = (int)(EdgeWeight*1000); EdgeWeight = (double)EWround; DirectedEdge DE = new DirectedEdge(curr1, curr2, EdgeWeight); G.addEdge(DE); } } public static void main(String[] args) { EdgeWeightedDigraph G = new EdgeWeightedDigraph(9); readRates(G, "/Users/cjones/Desktop/Data/ExchangeRates.csv"); System.out.print(G.toString()); // Fill in your code here  if (Fill in your code here) { System.out.println("This graph has a negative cycle - arbitrage  opportunity!");  for (DirectedEdge DE : Path.negativeCycle()) { System.out.println(DE.toString()); } } } }