Algorithm Design and Analysis S2 2023
Software Assignment
Solving Currency Exchange Problems
Group work by 3-4 students.
Due Date 08 Dec 2023.
Background: A currency exchange graph is a graph whose n nodes represent different currencies, and whose directed edges represent exchange rates ruv
between those currencies.
In financial markets, arbitrage opportunities arise when one can buy a set
of currencies and sell them in a sequence to end up with more of the starting currency, without any net investment. In a currency exchange graph,
this translates to finding a cycle where the product of the exchange rates is
greater than 1. For example if we have three currencies A, B and C, with
rates rAB = 0.651, rBC = 0.952, rCA = 1.711, then the product of the rates
rAB × rBC × rCA = 0.651 × 0.952 × 1.711 ≈ 1.060, which means 6% profit if
trading through the cycle A-B-C-A.
A currency exchange graph with negative logarithm is a currency exchange graph with each edge associated with the negative logarithm of the
exchange rates as the weights, e.g.,
w(A, B) = −log(rAB) ≈ 0.186,
w(B, C) = −log(rBC ) ≈ 0.021,
w(C, A) = −log(rCA) ≈ −0.233.
We then have
w(A, B) + w(B, C) + w(C, A) = −log(rAB × rBC × rCA) ≈ −0.025 < 0,
as rAB × rBC × rCA ≈ 1.060 > 1. This means if the sum of the weights
is negative (i.e., there is a cycle of negative weights), there is an arbitrage
opportunity.
Note that a currency exchange graph can be represented as n × n adjacency
matrix with currency exchange rates. You don’t have to consider the case where
there is no direct exchange rate between two currencies.
Tasks: To use shortest path algorithms in dynamic programming for solving
the Currency Exchange Problem:
• Detecting arbitrage opportunities in a currency exchange system
1
The input: n × n adjacency matrix for currency exchange rates
The output: whether there is arbitrage in the system, and if so, give the
currency sequence v0, v1, v2, ..., vk−1 for which rv0v1 ×rv1v2 ×...×rvk−1v0 >
1.
Instructions: Some extra details on how the tasks can be achieved and what
are expected.
• Currency Exchange Graph representation and Test Cases generation.
– Create at least two currency tables such as Table 1 and convert
them into Currency Exchange Graphs with negative logarithm as
test cases.
From/To A B C
A 1 0.651 0.581
B 1.531 1 0.952
C 1.711 1.049 1
Table 1: Sample exchange rates
– Gather real-world currency exchange rates (can include digital currencies). You can use APIs like exchangeratesapi.io or other financial
data services. Convert these exchange rates to a graph representation.
• Task: Add functionality to not only detect the presence of an arbitrage
cycle but also to retrieve and print the cycle. This will need the predecessor
info for each node when computing the shortest path associated with the
recurrence:
dk+1(u) = min{dk(u), min{dk(v) + w(v, u) | (v, u) ∈ E}}
• Any programming languages can be used.
• This is a group work by 3-4 students.
• Submission Guidelines:
The submission shall include the following in a zip file with student ID(s)
– A code file(s).
– A report detailing (1) the program design to achieve the task; and (2)
findings, including any identified arbitrage opportunities, potential
gains, and sample inputs used for testing, alongside expected and
observed outputs (screenshots).
– A small video showing the working of your program.
2
The report should include student name(s), ID(s) and signature(s). In a
group of 3-4 students, just nominate one student to do the submission via
Canvas.
• Marking Guides:
– Pass with distinction (>= 80%): All functionalities achieved, code
well-commented, the report is clear and detailed.
– Pass with merit (>= 65% and < 80%): Majority of the required
functionalities are implemented with few minor issues. Adequate
commenting in the code but might lack in some areas. The report
provides a basic explanation but might lack clarity in some sections.
– Pass (>= 50% and < 65%): Basic functionalities are present, but
some might be flawed or missing. Minimal commenting in the code,
making certain parts hard to understand. The report provides a basic
explanation but might lack clarity in some sections.
– Not pass (< 50%): Significant portions of the required functionalities
are missing or flawed. Code is poorly commented, making it difficult
to understand. The report is unclear, too brief, or missing major
sections.