Nesting boxes A d-dimensional box with dimensions .x1;

Yens improvement to Bellman-Ford Suppose that we order the edge relaxations in each pass of the Bellman-Ford algorithm as follows. Before the first pass, we assign an arbitrary linear order 1; 2;:::;jV j to the vertices of the input graph G D .V; E/. Then, we partition the edge set E into Ef [ Eb, where Ef D f.i; j / 2 E W ij g. (Assume that G contains no self-loops, so that every edge is in either Ef or Eb.) Define Gf D .V; Ef / and Gb D .V; Eb/. a. Prove that Gf is acyclic with topological sort h1; 2;:::;jV ji and that Gb is acyclic with topological sort hjV j; jV j1;:::;1i. Suppose that we implement each pass of the Bellman-Ford algorithm in the following way. We visit each vertex in the order 1; 2;:::;jV j, relaxing edges of Ef that leave the vertex. We then visit each vertex in the order jV j; jV j1;:::;1, relaxing edges of Eb that leave the vertex. b. Prove that with this scheme, if G contains no negative-weight cycles that are reachable from the source vertex s, then after only djV j =2e passes over the edges, :d D .s; / for all vertices 2 V . c. Does this scheme improve the asymptotic running time of the Bellman-Ford algorithm?

Nesting boxes A d-dimensional box with dimensions .x1; x2;:::;xd / nests within another box with dimensions .y1; y2;:::;yd / if there exists a permutation  on f1; 2; : : : ; dg such that x.1/ < y1, x.2/ < y2,..., x.d / < yd . a. Argue that the nesting relation is transitive. b. Describe an efficient method to determine whether or not one d-dimensional box nests inside another. c. Suppose that you are given a set of n d-dimensional boxes fB1; B2;:::;Bng. Give an efficient algorithm to find the longest sequence hBi1; Bi2 ;:::;Bik i of boxes such that Bij nests within BijC1 for j D 1; 2; : : : ; k  1. Express the running time of your algorithm in terms of n and d.

Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 U.S. dollar buys 49 Indian rupees, 1 Indian rupee buys 2 Japanese yen, and 1 Japanese yen buys 0:0107 U.S. dollars. Then, by converting currencies, a trader can start with 1 U.S. dollar and buy 49 x 2 x 0.0107 = 1.0486 U.S. dollars, thus turning a profit of 4.86 percent. Suppose that we are given n currencies c1,c2,...cn and a n x n table R of exchange rates, such that one unit of currency c1 buys R[i,j] units of currency cj. a. Give an efficient algorithm to determine whether or not there exists a sequence of currencies (ci1,ci2,...,cik) such that R[i1,i2].R[i2,i2]...R[ik-1,i3].R[ik,i1] > 1. Analyze the running time of your algorithm. b. Give an efficient algorithm to print out such a sequence if one exists. Analyze the running time of your algorithm.

Gabows scaling algorithm for single-source shortest paths A scaling algorithm solves a problem by initially considering only the highestorder bit of each relevant input value (such as an edge weight). It then refines the initial solution by looking at the two highest-order bits. It progressively looks at more and more high-order bits, refining the solution each time, until it has examined all bits and computed the correct solution. In this problem, we examine an algorithm for computing the shortest paths from a single source by scaling edge weights. We are given a directed graph G D .V; E/ with nonnegative integer edge weights w. Let W D max.u;/2E fw.u; /g. Our goal is to develop an algorithm that runs in O.E lg W / time. We assume that all vertices are reachable from the source. The algorithm uncovers the bits in the binary representation of the edge weights one at a time, from the most significant bit to the least significant bit. Specifically, let k D dlg.W C 1/e be the number of bits in the binary representation of W , and for i D 1; 2; : : : ; k, let wi.u; / D w.u; /=2ki . That is, wi.u; / is the scaled-down version of w.u; / given by the i most significant bits of w.u; /. (Thus, wk.u; / D w.u; / for all .u; / 2 E.) For example, if k D 5 and w.u; / D 25, which has the binary representation h11001i, then w3.u; / D h110i D 6. As another example with k D 5, if w.u; / D h00100i D 4, then w3.u; / D h001i D 1. Let us define i.u; / as the shortest-path weight from vertex u to vertex using weight function wi. Thus, k.u; / D .u; / for all u; 2 V . For a given source vertex s, the scaling algorithm first computes the shortest-path weights 1.s; / for all 2 V , then computes 2.s; / for all 2 V , and so on, until it computes k.s; / for all 2 V . We assume throughout that jEj  jV j 1, and we shall see that computing i from i1 takes O.E/ time, so that the entire algorithm takes O.kE/ D O.E lg W / time. a. Suppose that for all vertices 2 V , we have .s; / jEj. Show that we can compute .s; / for all 2 V in O.E/ time. b. Show that we can compute 1.s; / for all 2 V in O.E/ time. Let us now focus on computing i from i1. c. Prove that for i D 2; 3; : : : ; k, we have either wi.u; / D 2wi1.u; / or wi.u; / D 2wi1.u; / C 1. Then, prove that 2i1.s; / i.s; / 2i1.s; / C jV j 1 for all 2 V . d. Define for i D 2; 3; : : : ; k and all .u; / 2 E, wyi.u; / D wi.u; / C 2i1.s; u/ 2i1.s; / : Prove that for i D 2; 3; : : : ; k and all u; 2 V , the reweighted value wyi.u; / of edge .u; / is a nonnegative integer. e. Now, define yi.s; / as the shortest-path weight from s to using the weight function wyi. Prove that for i D 2; 3; : : : ; k and all 2 V , i.s; / D yi.s; / C 2i1.s; / and that yi.s; / jEj. f. Show how to compute i.s; / from i1.s; / for all 2 V in O.E/ time, and conclude that we can compute .s; / for all 2 V in O.E lg W / time.

Karps minimum mean-weight cycle algorithm Let G D .V; E/ be a directed graph with weight function w W E ! R, and let n D jV j. We define the mean weight of a cycle c D he1; e2;:::;eki of edges in E to be .c/ D 1 k X k iD1 w.ei/ : Let D minc .c/, where c ranges over all directed cycles in G. We call a cycle c for which .c/ D a minimum mean-weight cycle. This problem investigates an efficient algorithm for computing . Assume without loss of generality that every vertex 2 V is reachable from a source vertex s 2 V . Let .s; / be the weight of a shortest path from s to , and let k.s; / be the weight of a shortest path from s to consisting of exactly k edges. If there is no path from s to with exactly k edges, then k.s; / D 1. a. Show that if D 0, then G contains no negative-weight cycles and .s; / D min0 k n1 k.s; / for all vertices 2 V . b. Show that if D 0, then max 0 k n1 n.s; / k.s; / n k 0 for all vertices 2 V . (Hint: Use both properties from part (a).) c. Let c be a 0-weight cycle, and let u and be any two vertices on c. Suppose that D 0 and that the weight of the simple path from u to along the cycle is x. Prove that .s; / D .s; u/ C x. (Hint: The weight of the simple path from to u along the cycle is x.) d. Show that if D 0, then on each minimum mean-weight cycle there exists a vertex such that max 0 k n1 n.s; / k.s; / n k D 0 : (Hint: Show how to extend a shortest path to any vertex on a minimum meanweight cycle along the cycle to make a shortest path to the next vertex on the cycle.) e. Show that if D 0, then min 2V max 0 k n1 n.s; / k.s; / n k D 0 : f. Show that if we add a constant t to the weight of each edge of G, then increases by t. Use this fact to show that D min 2V max 0 k n1 n.s; / k.s; / n k : g. Give an O.VE/-time algorithm to compute .

Bitonic shortest paths A sequence is bitonic if it monotonically increases and then monotonically decreases, or if by a circular shift it monotonically increases and then monotonically decreases. For example the sequences h1; 4; 6; 8; 3; 2i, h9; 2; 4; 10; 5i, and h1; 2; 3; 4i are bitonic, but h1; 3; 12; 4; 2; 10i is not bitonic. (See Problem 15-3 for the bitonic euclidean traveling-salesman problem.) Suppose that we are given a directed graph G D .V; E/ with weight function w W E ! R, where all edge weights are unique, and we wish to find single-source shortest paths from a source vertex s. We are given one additional piece of information: for each vertex 2 V , the weights of the edges along any shortest path from s to form a bitonic sequence. Give the most efficient algorithm you can to solve this problem, and analyze its running time.