ECE590-Project 3 Solved

Contents

1 Problem Statement.................................................................................................................. 1

1.1 rates2mat.................................................................................................................................. 1

1.2 detectArbitrage......................................................................................................................... 2

1.2.1 Tolerance and Machine Epsilon.......................................................................................... 2

1.2.2 Tasks for detectArbitrage..................................................................................................... 3

2 Provided Code........................................................................................................................... 3

2.1 Vertex Class (p3vertex.py)....................................................................................................... 3

2.2 Currencies Class (p3currencies.py)......................................................................................... 4

2.3 getRates and testRates............................................................................................................. 5

3 Submission................................................................................................................................ 5

4 Pair Programming................................................................................................................... 5

5 Style Points................................................................................................................................ 6

 

1.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 3 inputs:

•     adjList: the adjacency list representing the currencies graph.

•     adjMat: the adjacency matrix representing the exchange rates, as generated by the rates2mat function.

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

1.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 equal to 12 Lira. Then clearly 1 Lira is equal to 1/12 Yen. But how is this represented on the computer? This is an infinitely 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 offer 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.

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

1.    Perform the |V | − 1 iterations of Bellman-Ford, taking the tol value into account.

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

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

4.    Once you have this path, remove any vertices that are not part of the cycle, and makesure 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 find the best negative cost cycle to choose. However, I am only asking that you find any arbitrage opportunity. You do not need to find the best arbitrage opportunity.

2             Provided Code
To aid you in these tasks, you have been provided with several fully functioning classes and functions for creating and testing the exchange rates.

2.1           Vertex Class (p3vertex.py)
The first 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).

2.2           Currencies Class (p3currencies.py)
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 above).

•      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 above). 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.

2.3           getRates and testRates
You have also been provided with two functions that create the Currencies graph (adjacency list and matrix) and test your code. The function getRates can be found in p3currencies.py, while testRates is in p3tests.py.

•     getRates: takes in 0, 1, 2, or 3 and outputs the exchange rates for each scenario:

0.    The small arbitrage example from class.

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

2.    The same set of exchange rates, but with the US Dollar underpriced with respectto the British Pound.

3.    The same set of exchange rates, but with the US Dollar underpriced with respectto 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 test your code on the entire set of exchange rates.