Algorithm Design and Analysis

Algorithm Design and Analysis

Assignment Four

Due Tuesday 25 October 2022

QQ1703105484

≈

A currency exchange graph is a graph whose n nodes represent different cur- riencies, and whose directed edges represent exchange rates r uv between those currencies (for example re$ 1 .78 for exchanging Euro to New Zealand dol-

lars).

ruv

≈ −

For convenience the edges can be weighted using w uv = log 1 (for example we$  0 .58),  allowing the weight of adjacent edges to be added together to   find combined exchange rates, and shorter paths result in higher exchange rates.

The purpose of this assignment is to develop useful graph tools for currency trading.

The assignment should include the following components, each with some suitable test examples:

×

Best Conversion Finder which accepts an n n connectivity table of ex- change rates (where 0 denotes no direct exchange rate between two curren- cies), and can calculate the best conversion rate between any two specified currencies (both ways), and how that rate can be obtained both ways as sequences of exchanges.                                                      (10 marks)

×

−                                        0  1 ·   1  2 ·    ·    k−1 0

Arbitrage Finder which accepts an n n table of exchange rates and eff- icently finds whether there is arbitrage in the system, a closed loop of exchanges that results in a profit. If so then all the occurrences of arbi- trage, currencies v0 , v1 , v2 , . . . , v k 1 for which r v v  r v   v  . . .  r v   v  > 1 should be found (allowing a currency trader to exploit a price differential to make a profit).                                                                                                                     (20 marks)

×

Bridge Exchange Finder which accepts an n n table of exchange rates and forms an undirected (and unweighted) graph which has edges between currencies if those two currencies can be directly exchanged. It then finds any exchanges (called bridge edges in the graph) which if were unavailable (its edge removed from graph) would mean some currencies could no longer be traded with each other via a sequence of exchanges (the graph would be disconnected).

The bridges can be found by first performing a depth first search of the undirected graph, labelling each vertex u with a counter d(u) as the vertex is discovered, and with a value m(u) as the search is finished with the

b

f

g

k

a

c

e

j

d

h

m

i

l

vertex. The value m(u) is taken to be the smallest value between d(u), the values of m(v) found while visiting each adjacent currently black (child) vertex v, and the value of d(v) for any adjacent currently grey (already discovered) vertex v other than its parent u.

For example, if in the illustrated diagram a depth-first search starting at

a might visit the vertices in the following order:

v d(v)

a 0

b 1

c 2

d 3

e 4

f 5

g 6

h 7

i 8

j 9

k 10

l 11

m 12

and when finished with each vertex the following values of m(v) would be calculated:

v m(v)

a 0

b 1

c 1

d 1

e 4

f 4

g 4

h 7

i 8

j 9

k 9

l 9

m 9

An edge between u and v is a bridge if and only if it is included in the depth first tree from u to v and m(v) > d(u).                                                                             (15 marks)

Demonstration of the programs with a 3-5 minute video.                (5 marks)