Problem Set 9

1. (10 pts) Let G = (V; E) be a graph with an edge-weight function w, and let the tree

    • 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) 2 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 modi ed graph G0.

To get started, let k be a positive number and de ne the weight function w0 as

w(x; y)
k  if (u; v) = (x; y)
:
w0(u; v) =
w(u; v)
if (u; v) 6= (x; y)


Now, prove that the tree T is a minimum spanning tree for G0, whose edge weights are given by w0.

    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 single-source 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 di erent from the order in which Kruskal’s algorithm adds them.

Boruvka’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 Boruvka’s algorithm, be sure to denote which edges are added simultaneously in a single round.)



b    e



a    d  f



c    g





1

    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 nally 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% pro t! 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 e cient 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(n3). Recall that Bellman-Ford can be used to detect negative-weight cycles in a graph.

        (b) For an arbitrary R, explain how varying changes the set of arbitrage opportu-nities that exist and that your algorithm might identify.

    4. (40 pts) Bidirectional breadth- rst search is a variant of standard BFS for nding a shortest path between two vertices s; t 2 V (G). The idea is to run two breadth- rst 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 signi cantly better.

Throughout this problem, all graphs are unweighted, undirected, simple graphs.

2


    (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 in nite family of examples (Gn; sn; tn) such that sn; tn 2 V (Gn), the asymptotic running time of BFS and bidirectional BFS are the same on inputs (Gn; sn; tn), and jV (Gn)j ! 1 as n ! 1.

    (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 nd 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 o 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 bidi-rectional 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 o 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



 


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