Algorithms Problem Set 7

CSCI 3104: Algorithms
Problem Set 7 (110 total points)

1. (30 points) Grog gives you the following unweighted graph and asks you to construct
a weight function w on the edges, using positive integer weights only, such that the
following conditions are true regarding minimum spanning trees (MST) and singlesource shortest path trees (SSSP):
• The MST is distinct from any of the seven SSSP trees.
• The order in which Jarn´ık/Prim’s algorithm adds the safe edges is different from
the order in which Kruskal’s algorithm adds them.
Justify your solution by (i) giving the edges weights, (ii) showing the corresponding
MST and all the SSSP trees, and (iii) giving the order in which edges are added by
each of the two algorithms.
1
CSCI 3104: Algorithms
Problem Set 7 (110 total points)
Instructor Buxton
Summer 2019, CU-Boulder
2. (25 points) Harry and Shadow think they have come up with a way to get rich by
exploiting the ore market. Their idea is to exploit exchange rates in order to transform
one unit of gold into more than one unit of gold, through a sequence of exchanges. For
instance, suppose 1 unit of gold buys 0.82 silver units, 1 silver unit buys 129.7 ethereum
units, 1 ethereum unit buys 12 doge units, and finally 1 doge unit buys 0.0008 gold
units. By converting their loot, Harry and Shadow think they could start with 1 gold
unit and buy 0.82×129.7×12×0.0008 ≈ 1.02 gold units, thereby making a 2% profit!
The problem is that those dwarves at Rocky Mountain Bank charge a transaction cost
for each exchange.
Suppose that Harry and Shadow start with knowledge of n ores c1, c2, . . . , cn and an
n × n table R of exchange rates, such that one unit of ore ci buys R[i, j] units of
ore cj
. A traditional arbitrage opportunity is thus a cycle in the induced graph such
that the product of the edge weights is greater than unity. That is, a sequence of
ores hci1
, ci2
, . . . , cik
i such that R[i1, i2] × R[i2, i3] × · · · × R[ik−1, ik] × R[ik, i1] 1.
Each transaction, however, must pay Rocky Mountain Bank a fraction α of the total
transaction value, e.g., α = 0.01 for a 1% rate.
(a) When given R and α, give an efficient algorithm that can determine if an arbitrage
opportunity exists. Analyze the running time of your algorithm.
Thormund’s hint: It is possible to solve this problem in O(n
3
).
(b) For an arbitrary R, explain how varying α changes the set of arbitrage opportunities that exist and that your algorithm might identify.
2
CSCI 3104: Algorithms
Problem Set 7 (110 total points)
Instructor Buxton
Summer 2019, CU-Boulder
3. (55 points) Bidirectional breadth-first search is a variant of standard BFS for finding
a shortest path between two vertices s, t ∈ V (G). The idea is to run two breadth-first
searches simultaneously, one starting from s and one starting from t, and stop when
they “meet in the middle” (that is, whenever a vertex is encountered by both searches).
“Simultaneously” here doesn’t assume you have multiple processors at your disposal;
it’s enough to alternate iterations of the searches: one iteration of the loop for the BFS
that started at s and one iteration of the loop for the BFS that started at t.
As we’ll see, although the worst-case running time of BFS and Bidirectional BFS are
asymptotically the same, in practice Bidirectional BFS often performs significantly
better.
Throughout this problem, all graphs are unweighted, undirected, simple graphs.
(a) Implement from scratch a function BFS(G,s,t) that performs an ordinary BFS
in the (unweighted, directed) graph G to find a shortest path from s to t. Assume
the graph is given as an adjacency list; for the list of neighbors of each vertex,
you may use any data structure you like (including those provided in standard
language libraries). Have your function return a pair (d, k), where d is the distance
from s to t (-1 if there is no s to t path), and k is the number of nodes popped
off the queue during the entire run of the algorithm.
(b) Implement from scratch a function BidirectionalBFS(G,s,t) that takes in an
unweighted, directed graph G, and two of its vertices s, t, and performs a bidirectional BFS. As with the previous function, this function should return a pair
(d, k) where d is the distance from s to t (-1 if there is no path from s to t) and k
is the number of vertices popped off of both queues during the entire run of the
algorithm.
(c) For each of the following families of graphs Gn, write code to execute BFS and
BidirectionalBFS on these graphs, and produce the following output:
• In text, the pairs (n, d1, k1, d2, k2) where n is the index of the graph, (d1, k1)
is the output of BFS and (d2, k2) is the output of BidirectionalBFS.
• a plot with n on the x-axis, k on the y-axis, and with two line charts, one for
the values of k1 and one for the values of k2:
i. Grids. Gn is an n×n grid, where each vertex is connected to its neighbors in
the four cardinal directions (N,S,E,W). Vertices on the boundary of the grid
will only have 3 neighbors, and corners will only have 2 neighbors. Let sn
be the midpoint of one edge of the grid, and tn the midpoint of the opposite
edge. For example, for n = 3 we have:
3
CSCI 3104: Algorithms
Problem Set 7 (110 total points)
Instructor Buxton
Summer 2019, CU-Boulder
(When n is even sn and tn can be either “midpoint,” since there are two.)
Produce output for n = 3, 4, 5, . . . , 20.
ii. Trees. Gn is a complete binary tree of depth n. sn is the root and tn is any
leaf. Produce output for n = 3, 4, 5, . . . , 15. For example, for n = 3 we have:
iii. Random graphs. Gn is a graph on n vertices constructed as follows. For each
pair of of vertices (i, j), get a random boolean value; if it is true, include
the edge (i, j), otherwise do not. Let sn be vertex 1 and tn be vertex 2 (food
for thought: why does it not matter, on average, which vertices we take s, t
to be?) For each n, produce 50 such random graphs and report just the
average values of (d1, k1, d2, k2) over those 50 trials. Produce this output for
n = 3, 4, 5, . . . , 20.
4