Project 3: Arbitrage Solution

In this project, you will implement Bellman-Ford to detect arbitrage opportunities given a set of exchange rates between currencies. You will be required to implement your solutions in their respective locations in the provided project3.py le.







Pair Programming



You are allowed to work in pairs for this project. If you elect to work with a partner:




You should submit only one version of your nal code. Have one partner upload the code on their Sakai site. Make sure that both partner's names are clearly indicated at the top of the code.




When work is being done on this project, both partners are required to be physically present at the machine in question, with one partner typing (`driving') and the other partner watching (`navigating').




You should split your time equally between driving and navigating to ensure that both partners spend time coding.




You are allowed to discuss this project with other students in the class, but the code you submit must be written by you and your partner alone.







Style Points



Part of your grade for this project will be `style points'. The idea here is that the code you turn in must be well commented and readable. A reasonable user aught to be able to read through your provided code and be able to understand what it is you have done, and how your functions work. This means that a grader should be able to read over your code and tell that your algorithms are implemented correctly.




The guidelines for these `style points':




Your program le should have a header stating the name of the program, the author(s), and the date.




All functions need a comment stating: the name of the function, what the function does, what the inputs are, and what the outputs are.




Every major block of code should have a comment explaining what the block of code is doing. This need not be every line, and it is left to your discretion to determine how frequently you place these comments. However, you should have enough comments to clearly explain the behavior of your code.




Please limit yourself to 80 characters in a line of code. In python, you can use the symbol n to indicate a line break/continuation.




1
Provided Code



Your goal in this project will be to implement Bellman-Ford to detect arbitrage opportunities given a set of exchange rates. To aid you in this, you have been provided with several fully functioning classes and functions for creating and testing the exchange rates.




3.1 Vertex Class




The rst of the fully functioning classes is the Vertex class. This class has 4 class attributes:




rank: the rank (label) of the given vertex




neigh: the list of the neighboring vertices




dist: the distance from the start vertex




prev: the previous vertex in the path




Along with these are three implemented member functions:




init : this is the constructor function for the Vertex class. It requires an input rank for the vertex, and sets all of the attributes to have reasonable starting values. You will create a new Vertex with a call: v = Vertex(rank).




repr : this function is called whenever a Vertex is printed, i.e. when the call print(v) is made. It simply prints the rank of the vertex.




isEqual: this takes in a second Vertex as an input, and compares the rank of the two vertices, returning True if they are equal rank (i.e., if they had the same label). This function can be called using: v.isEqual(u).







3.2 Currencies Class




You have also been provided with a fully functioning Currencies class with 5 class attributes:




rates: a 2D array representing the exchange rates




currs: a list of the currency names as strings




adjList: the adjacency list of Vertex objects




adjMat: the adjacency matrix (stored as a 2D list)




negCyc: what will ultimately contain the negative cost cycle, stored as a list of ranks (not a list of vertices)



The Currencies class has 6 member functions:




init : this is the constructor for the Currencies class. It has one optional input: the exchangeNum which selects which set of exchange rates to use (options: 0,1,2,3 - default: 0). This initialization function correctly creates the adjacency list. The negCyc attribute is initialized as an empty list. A new Currencies object can be created with the call c = Currencies(exchangeNum).







NOTE: the adjacency matrix is created using the rates2mat function. You will have to correctly implement this function (described later).




repr : this function is called when a Currencies object is printed. It will simply print all of the exchange rates.




printList: this function can be used to aid with debugging. It prints the adjacency list in a more readable format.




printMat: this function can be used to aid with debugging. It prints the adjacency matrix in a more readable format.




printArb: this function is used to print the currencies listed in the negative cycle stored in negCyc.




arbitrage: this function calls the function detectArbitrage on the Currencies to obtain the potential negative cost cycle. You will be responsible for implementing the detectArbitrage function (described later). It will then check to ensure that the reported arbitrage (if one was reported) was successful: that it was a cycle where arbitrage occurred. If the arbitrage was successful, it will report the monetary gain per unit input.







3.3 getRates and testRates




You have also been provided with two functions that create the Currencies and test your code:




getRates: this function takes in 0, 1, 2, or 3 and outputs the 2D array of exchange rates. The scenarios are:




The small arbitrage example from class.



A set of actual exchange rates between 14 currencies as of 11/12/18.



EUR = Euro, GBP = British Pound, CHF = Swiss Franc, USD = US Dollar, AUD = Australian Dollar, CAD = Canadian Dollar, HKD = Hong Kong Dollar, INR = Indian Rupee, JPY = Japanese Yen, SAR = Saudi Riyal,




SGD = Singapore Dollar, ZAR = South African Rand, SEK = Swedish Krona, AED = U.A.E. Dirham




The same set of actual exchange rates, but with the US Dollar underpriced with respect to the British Pound.


The same set of actual exchange rates, but with the US Dollar underpriced with respect to the British Pound, the Japanese Yen overpriced with respect to the Indian Rupee, and the Saudi Riyal overpriced with respect to the Hong Kong Dollar.



testRates: this function will allow you to test your code on the entire set of exchange rates.







Problem Statement


You will have two primary tasks in this project:




Correctly create the adjacency matrix given the exchange rates in the function rates2mat.



Implement Bellman-Ford to detect and report a negative cost cycle in the resulting graph in the function detectArbitrage.



4.1 rates2mat




You have been provided with a placeholder code that currently just copies each element from the rates matrix directly into the returned adjacency matrix. With only a very minor modi cation to this single line of code, you should be able to return the adjacency matrix with the correctly weighted edges. The function math.log may be useful here.




4.2 detectArbitrage




The function detectArbitrage will comprise the bulk of your work for this project. It will output a single list of vertex ranks corresponding to the negative cost cycle. This list needs to start and end at the same rank. This function will take 2 inputs:




currencies: the Currencies object for the exchange rates.




tol: this is a value that is set at 1e-15 as default, and should not be altered.




4.2.1 Tolerance and Machine Epsilon




The value tol will be used to deal with one very important problem. Consider what happens when there is an exchange rate where 1 Yen is 12 Lira. Then clearly 1 Lira is 1/12 Yen. But how is this represented on the computer? This is an in nitely repeating decimal, and so we must truncate its value. But this means that, on the computer,




R(Yen,Lira) R(Lira,Yen) 6= 1 ) log[R(Yen,Lira)] log[R(Lira,Yen)] 6= 0;




because there will be an error in the smallest digit. We are promised one important fact about the size of this error: it is smaller than the value known as machine epsilon (the smallest representable number using the given number of bits). For python's float type, machine epsilon is about 2.2e-16. This means that we cannot trust any updates of a

size on the order of 1e-16. Therefore, we will ignore any updates that are smaller than our tolerance value, tol=1e-15. This will change the Bellman-Ford implementation very slightly. When we make an o er during an update step, if the update is smaller than tol we ignore it. So, we originally had the code:




Check each neighbor of u.



Update predictions and previous vertex. for neigh of u:



Only update if the new value is better! if neigh.dist u.dist + length(u, neigh):



neigh.dist = u.dist + length(u, neigh) neigh.prev = u




But now we will have the code:




Check each neighbor of u.



Update predictions and previous vertex. for neigh of u:



Only update if the new value is better!



if neigh.dist u.dist + length(u, neigh) + tol: neigh.dist = u.dist + length(u, neigh) neigh.prev = u




Your implementation of the Bellman-Ford algorithm will have to include this change.




4.2.2 Tasks for detectArbitrage




Your implementation of detectArbitrage will have to perform 4 major tasks:




Perform the jV j 1 iterations of Bellman-Ford, taking the tol value into account.



Perform the extra iteration and track changes in the vertex.dist values.



Choose a single vertex that had a change and follow its path backwards (using the vertex.prev values) until you nd a cycle. Note that this cycle does not necessarily include the changed vertex you started with.



Once you have this path, remove any vertices that are not part of the cycle, and make sure that the list is in the correct order (hint: you traced the path backwards). This cycle will be your return value.



Note: this process does not guarantee that you will nd the best negative cost cycle to choose. However, I am only asking that you nd any arbitrage opportunity. You do not need to nd the best arbitrage opportunity.







Submission



You must submit your project3.py code online on Sakai. If you worked with a partner, only submit one version of your completed project and indicate clearly the names and NetIDs of both partners.







5