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

  • 相关阅读:
    C语言：动态内存（一篇拿捏动态内存！）
    详解MySQL索引
    Antivirus Zap Pro ：苹果 mac 电脑全面的系统安全解决方案
    qmake eval(string) 函数
    传奇世界版本修改方法需要注意什么
    怎样正确做 Web 应用的压力测试？
    初识Cpp之 七、流程控制
    资源有限的大型语言模型的全参数微调
    UnityEditor之GUI
    为什么说PMP+软考“1+1＞2”？
  • 原文地址：https://blog.csdn.net/qq_37064135/article/details/128088938