Description
1. (10 pts) Let G = (V, E) be a graph with an edge-weight function w, and let the tree
T ⊆ E be a minimum spanning tree on G. Now, suppose that we modify G slightly by
decreasing the weight of exactly one of the edges in (x, y) ∈ T in order to produce a
new graph G0
. Here, you will prove that the original tree T is still a minimum spanning
tree for the modified graph G0
.
To get started, let k be a positive number and define the weight function w
0 as
w
0
(u, v) =
w(u, v) if (u, v) 6= (x, y)
w(x, y) − k if (u, v) = (x, y) .
Now, prove that the tree T is a minimum spanning tree for G0
, whose edge weights are
given by w
0
.
2. (20 pts) Professor Snape 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 and singlesource shortest path trees:
• 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.
• Bor ˙uvka’s algorithm takes at least two rounds to construct the MST.
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 three algorithms. (For Bor ˙uvka’s algorithm, be sure to denote which edges
are added simultaneously in a single round.)
a
b
d f
c
e
g
1
CSCI 3104
Problem Set 9
3. (10 pts extra credit) Crabbe and Goyle think they have come up with a way to get
rich by playing the foreign exchange markets in the wizarding world. Their idea is to
exploit these exchange rates in order to transform one unit of British wizarding money
into more than one unit of British wizarding money, through a sequence of money
exchanges. For instance, suppose 1 British wizarding penny buys 0.82 French wizarding
pennies, 1 French wizarding penny buys 129.7 Russian wizarding pennies, and finally 1
Russian wizarding penny buys 0.0008 British wizarding pennies. By converting these
coins, Crabbe and Goyle think they could start with 1 British wizarding penny and
buy 0.82 × 129.7 × 12 × 0.0008 ≈ 1.02 British wizarding pennies, thereby making a
2% profit! The problem is that those goblins at Gringots charge a transaction cost for
each exchange.
Suppose that Crabbe and Goyle start with knowledge of n wizard monies c1, c2, . . . , cn
and an n × n table R of exchange rates, such that one unit of wizard money ci buys
R[i, j] units of wizard money 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 currencies 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 Gringots 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.
Hermione’s hint: It is possible to solve this problem in O(n
3
). Recall that BellmanFord can be used to detect negative-weight cycles in a graph.
(b) For an arbitrary R, explain how varying α changes the set of arbitrage opportunities that exist and that your algorithm might identify.
4. (40 pts) 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.
2
CSCI 3104
Problem Set 9
(a) Give examples to show that, in the worst case, the asymptotic running time of
bidirectional BFS is the same as that of ordinary BFS. Note that because we are
asking for asymptotic running time, you actually need to provide an infinite family
of examples (Gn, sn, tn) such that sn, tn ∈ V (Gn), the asymptotic running time of
BFS and bidirectional BFS are the same on inputs (Gn, sn, tn), and |V (Gn)| → ∞
as n → ∞.
(b) Recall that in ordinary BFS we used a state array (see Lecture Notes 8) to keep
track of which nodes had been visited before. In bidirectional BFS we’ll need two
state arrays, one for the BFS from s and one for the BFS from t. Why? Give an
example to show what can go wrong if there’s only one state array. In particular,
give a graph G and two vertices s, t such that some run of a bidirectional BFS
says there is no path from s to t when in fact there is one.
(c) 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.
(d) Implement from scratch a function BidirectionalBFS(G,s,t) that takes in a(n
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.
(e) 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
Problem Set 9
• • •
s3 • t3
• • •
(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:
s3
• •
• • t3 •
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
