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.

/Solutions are available.

1. Tallest path

Suppose that each edge uv in a graph G represents a one-way section of the US Interstate highway system spanned by an easily-damaged bridge with clearance c_uv. Suppose further that you wish to drive a truck full of heating oil from vertex s to vertex t in G, and that a truck with height h can only safely pass under a bridge with clearance c_uv ≥ h. Give the most efficient algorithm you can that computes for each vertex t≠s the height of the tallest truck that can reach t from s.

2. Exchange rates

A currency exchange offers to trade currencies at various exchange rates, giving a table where one unit on the left-hand side of each row buys some number of units on the right-hand side:

1 US Dollar	0.52 British Pounds
1 US Dollar	1.31 Canadian Dollars
1 US Dollar	1920.00 Venezuelan Bolivars
1 British Pound	1.83 US Dollars
1 Canadian Dollar	32.13 Indian Rupees
etc...

Give the most efficient algorithm you can that determines whether it is possible to make a profit by exchanging money at these rates, where you can start with any currency you like and go through as many intermediate currencies as you like as long as you end with the same currency you started with. Compute its running time as a function of the number of currencies n. Hint: consider taking logarithms.