Algorithm Design and Analysis
Final Assessment (Weightage: 50%)
Due Wednesday 11 December 2020
Submission Instructions
Create a single .zip archive containing the following components:
• For all Software development tasks, please include .java files in the cor-
rect folder format. Please ensure code files do not contain any non-English
characters (such as comments in Chinese) because my AUT computer can-
not display these characters. Worse, these code files do not compile for
me.
• For demonstration videos, please include video files in .mp4 format, of no
more than 30 MB in size (for each video).
Please submit the .zip file on Blackboard→Assessment→Final Assessment.
Part 1
A persistent dynamic set is a set which maintains past versions of itself
as it gets updated. One simple implementation of a persistent dynamic set
would be to copy the entire data structure whenever it gets modified, but this
approach becomes Θ(n) and may require substantial memory, so instead the
data structure just keeps track of changes made.
The purpose of this assignment is to develop an efficient data structure for
a persistent dynamic set of Comparable elements.
The assignment should include the following components, each with some
suitable test examples:
Binary Search Tree which is a binary search tree with add, contains, and
remove methods. Each node contains a Comparable element, and links to
its left and right children (or null if it doesn’t have a child). Note that
each node will NOT have a link to its parent (to simplify effort later in the
assignment). It is suggested that the binary search tree class be arranged
to be extensible, and hook methods included that get called whenever a
node is visited during add or remove. Please include a suitable way to
visualise the tree. (10 marks)
1
Persistent Dynamic Set which is an implementation of a persistent dynamic
set for Comparable elements which utilises the binary search tree. When
an element is added or removed only the nodes that are affected from the
root down to that element are copied and links made to unaffected nodes
from the previous version of the binary search tree.
For example if “dog” is added to the tree on the left a second tree with four
new nodes is created on the right, including a new root node to represent
the updated version.
Please include some suitable way to visualise the different version of the
tree. (20 marks)
Balanced Persistent Dynamic Set which is a red-black tree subclass of the
binary search tree that keeps the tree balanced so the persistent dynamic
set is guaranteed to have O (log n) operations. It should utilise the tree’s
hook methods to avoid traversing the tree multiple times during rebalanc-
ing, and care should be used during left and right rotations to correctly
update the version. The eight cases to be considered in the remove method
will be limited to a maximum four marks. (15 marks)
Demonstration video ( 3 minutes) showing the test cases and features of the
programs. (5 marks)
2
Part 2
A currency exchange graph is a graph whose n nodes represent different cur-
riencies, and whose directed edges represent exchange rates ruv between those
currencies (for example re$ ≈ 1.78 for exchanging Euro to New Zealand dol-
lars).
For convenience the edges can be weighted using wuv = log
1
ruv
(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)
Arbitrage Finder which accepts an n×n table of exchange rates and efficiently
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 arbitrage, curren-
cies v0, v1, v2, . . . , vk−1 for which rv0v1 · rv1v2 · . . . · rvk−1v0 > 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
3
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.
a
d
b
c e
f g
h i
j
k
l
m
For example, if in the illustrated diagram a depth-first search starting at
a might visit the vertices in the following order:
v a b c d e f g h i j k l m
d(v) 0 1 2 3 4 5 6 7 8 9 10 11 12
and when finished with each vertex the following values of m(v) would be
calculated:
v a b c d e f g h i j k l m
m(v) 0 1 1 1 4 4 4 7 8 9 9 9 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 video of the programs with sufficient test cases. (5 marks)
4