Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

# 1. Tallest path

Here is a modified version of Dijkstra's algorithm that runs in time O(V log V + E) if implemented with Fibonacci heaps, and slightly more time if implemented in a reasonable way:

{{{TallDijkstra:

• h[s] = +infinity, h[t] = 0 for all t != s. put all vertices in a priority Q supporting EXTRACT-MAX while Q is not empty:
• u = EXTRACT-MAX(Q) for each edge uv:
• h[v] = max(h[v], min(h[u], c(u,v))
return h

}}}

This is basically Dijkstra's algorithm with the order reversed and + replaced by min. The proof of correctness is essentially the same: the nodes come out of the queue in order of decreasing height, and the height of each node u is correct when it leaves because if there were a better path to u whose penultimate node was still in the queue than the one whose penultimate node set h[u] when it left, some earlier node q from this path would have h[q] > h[u] while still being in the queue and would thus have been extracted instead.

# 2. Exchange rates

Let rij be the number of units of currency cj that can be bought with one unit of currency ci. Then the return from a sequence of trades going through a sequence of currencies c1, c2, ..., ck is r12r23...rk-1,k, and we make a profit if c1 = ck,, and this product is greater than 1. Take a logarithm of the product and negate it; now we have

• -log(r12r23...rk-1,k) = -&#8721;log(ri,i+1) = &#8721; -log(ri,i+1,,),

and we now make a profit if the sum is less than zero and c1 = ck. Since we can't assume that all currencies are reachable from a single starting currency, we use Floyd-Warshall to detect the existence of any negative cycle by looking for some i with d(i,i) < 0. This takes O(n3) time, where n is the number of currencies.

2014-06-17 11:58