Algorithm程序写作、辅导Python

” Algorithm程序写作、辅导PythonAlgorithm Design and AnalysisFinal Assessment (Weightage: 50%)Due Wednesday 16 December 2020Submission InstructionsCreate a single .zip archive containing the following components: For all Software development tasks, please include .java files in the correctfolder format. Please Ensure code files do not contain any non-Englishcharacters (such as comments in Chinese) because my AUT computer cannotdisplay these characters. Worse, these code files do not compile forme. For demonstration videos, please include video files in .mp4 format, of nomore than 30 MB in size (for each video).Please submit the .zip file on BlackboardAssessmentFinal Assessment.Part 1A persistent dynamic set is a set which maintains past versions of itselfas it gets updated. One simple implementation of a persistent dynamic setwould be to copy the entire data structure whenever it gets modified, but thisapproach becomes (n) and may require substantial memory, so instead thedata structure just keeps track of changes made.The purpose of this assignment is to develop an efficient data structure fora persistent dynamic set of Comparable elements.The assignment Should include the following components, each with somesuitable test examples:Binary Search Tree which is a binary search tree with add, contains, andremove methods. Each node contains a Comparable element, and links toits left and right children (or null if it doesnt have a child). Note thateach node will NOT have a link to its parent (to simplify effort later in theassignment). It is suggested that the binary search tree class be arrangedto be extensible, and hook methods included that get called whenever anode is visited during add or remove. Please include a suitable way tovisualise the tree. (10 marks)1Persistent Dynamic Set which is an implementation of a persistent dynamicset for Comparable elements which utilises the binary search tree. Whenan element is added or removed only the nodes that are affected from theroot down to that element are copied and links made to unaffected nodesfrom the previous version of the binary search tree.For example if dog is added to the tree on the left a second tree with fournew nodes is created on the right, including a new root node to representthe updated version.Please include some suitable way to visualise the different version of thetree. (20 marks)Balanced Persistent Dynamic Set which is a red-black tree subclass of thebinary search tree that keeps the tree balanced so the persistent dynamicset is Guaranteed to have O (log n) operations. It should utilise the treeshook methods to avoid traversing the tree multiple times during rebalancing,and care should be used during left and right rotations to correctlyupdate the version. The eight cases to be considered in the remove methodwill be limited to a maximum four marks. (15 marks)Demonstration video ( 3 minutes) showing the test cases and features of theprograms. (5 marks)2Part 2A currency exchange graph is a graph whose n nodes represent different curriencies,and whose directed edges represent exchange rates ruv between thosecurrencies (for example re$ 1.78 for exchanging Euro to New Zealand dollars).For Convenience the edges can be weighted using wuv = log 1ruv(for examplewe$ 0.58), allowing the weight of adjacent edges to be added together tofind combined exchange rates, and shorter paths result in higher exchange rates.The purpose of this assignment is to develop useful graph tools for currencytrading.The assignment should include the following components, each with somesuitable test examples:Best Conversion Finder which accepts an n n connectivity table of exchangerates (where 0 denotes no direct exchange rate between two currencies),and can calculate the best conversion rate between any two specifiedcurrencies (both ways), and how that rate can be obtained both ways assequences of exchanges. (10 marks)Arbitrage Finder which accepts an nn table of exchange rates and efficientlyfinds whether there is arbitrage in the system, a closed loop of exchangesthat results in a Profit. If so then all the occurrences of arbitrage, currenciesv0, v1, v2, . . . , vk1 for which rv0v1 rv1v2 . . . rvk1v0 1 should befound (allowing a currency trader to exploit a price differential to make aprofit). (20 marks)Bridge Exchange Finder which accepts an nn table of exchange rates andforms an undirected (and unweighted) graph which has edges betweencurrencies if those two currencies can be directly exchanged. It then findsany exchanges (called bridge edges in the graph) which if were unavailable(its edge removed from graph) would mean some currencies could no longerbe traded with each other via a sequence of exchanges (the graph wouldbe disconnected).The bridges can be found by first performing a depth first search of theundirected graph, labelling each vertex u with a counter d(u) as the vertexis discovered, and With a value m(u) as the search is finished with the3vertex. The value m(u) is taken to be the smallest value between d(u), thevalues of m(v) found while visiting each adjacent currently black (child)vertex v, and the value of d(v) for any adjacent currently grey (alreadydiscovered) vertex v other than its parent u.For example, if in the illustrated diagram a depth-first search starting ata might visit the vertices in the following order:v a b c d e f g h i j k l md(v) 0 1 2 3 4 5 6 7 8 9 10 11 12and when finished With each vertex the following values of m(v) would becalculated:v a b c d e f g h i j k l mm(v) 0 1 1 1 4 4 4 7 8 9 9 9 9An edge between u and v is a bridge if and only if it is included in thedepth first tree from u to v And m(v) d(u). (15 marks)Demonstration video of the programs with sufficient test cases. (5 marks)如有需要，请加QQ：99515681 或邮箱：99515681@qq.com

“