代写data编程、代做Python，c++程序

日期：2023-12-07 09:22

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.

3