1. Do problem 24-3 (Arbitrage). Hint: This is related to Exercise 24.1-6.

2. Given a graph G with weight set W, which might contain negative edges, we can produce a non-negative edge weight set W' as follows. Let x be a least edge weight in W, so that x<=y for all y in W. If x>=0, W' = W. If x<0, add (-x) to all edge weights in W to form W'. If we run Dijkstra's algorithm on G, using W' instead of W, we correctly find a shortest path with respect to W'. Is this always a shortest path with respect to W? Explain why or why not in a few sentences.

3. (From Kleinberg and Tardos) An independant set in a graph is a set of vertices, no two of which are connected by an edge. We will consider only very simple graphs, for which the whole graph is a single path. So G has vertex set V= {v₁,v₂,...,v_n}, and edge set E = {(v₁,v₂),(v₂,v₃),...(v_n-1,v_n) }. For the case n=6, an example of an independent set is { v₂,v₅ }.

Now say every vertex has a weight w_i. The weight of an independent set is the sum of the weights of the vertices in the set. Give the most efficient algorithm you can to find an independent set with maximum weight. Prove that your algorithm is correct, and analyze the running time of your algorithm.

Hint: There are some obvious ideas that don't work, so be careful.

The edge weights might be negative. If all the edge weights are negative, then the maximum weight independent set is empty.