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. Frustration sort

1. For the upper bound, observe that each time i resets to 1 the algorithm removes one inversion, and that at most O(n) work occurs between each such removal. Since the initial state of the array as O(n2) inversions, this gives an upper bound of O(n3).

2. For the lower bound, consider an input consisting of 3n/4 ones followed by n/4 zeroes. Each zero must be brought across the 3n/4 ones. For the first n/4 swaps at least, it starts in position n/2 or greater. So we have a cost of at least (n/4 zeroes) * (n/4 swaps) * (n/2 comparisons) = Omega(n3).

# 2. Triathlon routing

Here is an algorithm that calls DepthFirstSearch once on a newly-constructed graph. Given the input graph G = (V,E), construct a new graph G' with vertices of the form vi where v is a vertex of G and i is 1, 2, or 3, depending on how many different modes of locomotion have been used to reach v. Let the edges of G' consist of

• An edge (v1,v2) and an edge (v2,v3) for each v in V.

• An edge (u1,v1) for each swimmable edge uv in E, (u2,v2) for each bikable edge uv in E, and (u3,v3) for each runnable edge uv in E.

Now run DepthFirstSearch on G' starting at s1 and return all nodes v for which v3 is reachable in G'.

Observe first that any path through G' consists of swimmable edges, bikable edges, and runnable edges, joined by two utility edges (v1,v2) and (v'2,v'3). So the reachable v3 nodes in G' correspond precisely to the nodes of G reachable by permitted paths.

To compute the running time, observe that G' has exactly 3|V| vertices and up to 2|V|+3|E| edges. So DepthFirstSearch takes O(3|V| + 2|V| + 3|E|) = O(|V|+|E|) time. The cost of constructing the graph should be the same; we just have to loop over all vertices and edges in G and spit out a constant number corresponding vertices or edges of G' for each. We can't expect to do better than this (as DepthFirstSearch reduces to this problem by labelling all edges as swimmable only), so in fact we have a Theta(|V|+|E|) algorithm.

2014-06-17 11:58