[Solved] CSCI 3104 Problem Set 9

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 G⁰. Here, you will prove that the original tree T is still a minimum spanning tree for the modified graph G⁰.

To get started, let k be a positive number and define the weight function w⁰ as

) if (u,v) 6= (x,y)

(u,v) =

w(x,y) k if (u,v) = (x,y) .

Now, prove that the tree T is a minimum spanning tree for G⁰, whose edge weights are given by w⁰.

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 Jarnk/Prims algorithm adds the safe edges is different from the order in which Kruskals algorithm adds them.
   • Boruvkas 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 Boruvkas algorithm, be sure to denote which edges are added simultaneously in a single round.)

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 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 c₁,c₂,,c_n and an n n table R of exchange rates, such that one unit of wizard money c_i buys R[i,j] units of wizard money c_j. 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 hc_i1,c_i2,,c_iki such that R[i₁,i₂] R[i₂,i₃] R[i_k1,i_k] R[i_k,i₁] > 1. Each transaction, however, must pay Gringots a fraction of the total transaction value, e.g., = 0.01 for a 1% rate.

• When given R and , give an efficient algorithm that can determine if an arbitrage opportunity exists. Analyze the running time of your algorithm.

Hermiones hint: It is possible to solve this problem in O(n³). Recall that BellmanFord can be used to detect negative-weight cycles in a graph.

• 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 doesnt assume you have multiple processors at your disposal; its 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 well 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.

• Give examples to show that, in the worst case, the asymptotic running time ofbidirectional 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 (G_n,s_n,t_n) such that s_n,t_n V (G_n), the asymptotic running time of BFS and bidirectional BFS are the same on inputs (G_n,s_n,t_n), and |V (G_n)| as n .
• 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 well 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 theres only one state 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.
• 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.
• 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.
• For each of the following families of graphs G_n, write code to execute BFS and BidirectionalBFS on these graphs, and produce the following output:
  • In text, the pairs (n,d₁,k₁,d₂,k₂) where n is the index of the graph, (d₁,k₁) is the output of BFS and (d₂,k₂) 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 k₁ and one for the values of k₂:

1. G_n is an nn 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 s_n be the midpoint of one edge of the grid, and t_n the midpoint of the opposite edge. For example, for n = 3 we have:

(When n is even s_n and t_n can be either midpoint, since there are two.) Produce output for n = 3,4,5,,20.

1. G_n is a complete binary tree of depth n. s_n is the root and t_n is any

leaf. Produce output for n = 3,4,5,,15. For example, for n = 3 we have:

• t₃

iii. Random graphs. G_n 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 s_n be vertex 1 and t_n 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 (d₁,k₁,d₂,k₂) over those 50 trials. Produce this output for n = 3,4,5,,20.