Homework 11

Groups

• 第二組
• 第三組
• 第八組
• 第九組
• 第十三組
• 第十七組
• 第二十組

Problems

1. Exercises 24.4-2
   Find a feasible solution or determine that no feasible solution exists for the following system of difference constraints:

   x₁ - x₂ ≤ 4,
   x₁ - x₅ ≤ 5,
   x₂ - x₄ ≤ -6,
   x₃ - x₂ ≤ 1,
   x₄ - x₁ ≤ 3,
   x₄ - x₃ ≤ 5,
   x₄ - x₅ ≤ 10,
   x₅ - x₃ ≤ -4,
   x₅ - x₄ ≤ -8.

2. Problem 24-3 Arbitrage
   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 × 2 × 0.0107 = 1.0486 U.S. dollars, thus turning a profit of 4.86 percent.
   Suppose that we are given n currencies c₁, c₂, … , c_n and an n × n table R of exchange rates, such that one unit of currency c_i buys R[i, j] units of currency c_j.

   • Give an efficient algorithm to determine whether or not there exists a sequence of currencies [ c_i1, c_i2, … , c_ik ] such that R[i₁, i₂] ⋅ R[i₂, i₃] ⋅⋅⋅ R[i_k-1, i_k] ⋅ R[i_k, i₁] > 1 . Analyze the running time of your algorithm.
   • Give an efficient algorithm to print out such a sequence if one exists. Analyze the running time of your algorithm.

3. Exercises 25.1-10
   Give an efficient algorithm to find the length (number of edges) of a minimum-length negative-weight cycle in a graph.

4. Show whether the Floyd-Warshall algorithm can detect negative-weight cycles. If yes, show how to find one of them.

5. Exercises 25.2-1
   Run the Floyd-Warshall algorithm on the weighted, directed graph of figure below. and answer the following questions:

   • Show the matrix d^(k) that results for each iteration of the outer loop.
   • List the vertices of one such shortest path from v₆ to v₁.

6. Exercises 25.3-1
   Use Johnson's algorithm to find the shortest paths between all pairs of vertices in the graph of figure below. Show the values of h and w' computed by the algorithm.

7. Problem 25-1: Transitive closure of a dynamic graph
   Suppose that we wish to maintain the transitive closure of a directed graph G = (V, E) as we insert edges into E. That is, after each edge has been inserted, we want to update the transitive closure of the edges inserted so far. Assume that the graph G has no edges initially and that we represent the transitive closure as a Boolean matrix.
   • Show how to update the transitive closure G^*= (V, E^*) of a graph G = (V, E) in O(V²) time when a new edge is added to G.
   • Give an example of a graph G and an edge e such that O(V²) time is required to update the transitive closure after the insertion of e into G, no matter what algorithm is used.
   • Describe an efficient algorithm for updating the transitive closure as edges are inserted into the graph. For any sequence of n insertions, your algorithm should run in total time , where t_i is the time to update the transitive closure upon inserting the ith edge. Prove that your algorithm attains this time bound.