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. Map coloring

1. We have to test each adjacent pair to see if colors of the two countries are the same; each such test takes Theta(1) time, so the total is Theta(m).
2. Since each country can have three different colors, there are 3n possible colorings, for a total cost of Theta(3nm).

3. Now each country after the first has at most two possible colorings (since one is excluded by an earlier neighbor). So there are at most 2n-1 colorings, which gives a cost of O(2n-1m) = O(2nm). This is much better than Theta(3nm), since it's easy to show that it's o(3nm).

• This upper bound is in fact the best we can do without further optimizations: Consider a map in which every country is adjacent to every other. With n > 3, this clearly can't be colored with only three colors. But the algorithm will try 2n-1 colorings anyway, because it has no mechanism to exclude bad colorings except the test at the end.

# 2. Suspicion

1. It's not clear that we can do much better than BruteForce for this. The simplest BruteForce approach generates all nk possible conspiracies (or, strictly speaking, all n choose k, but this is Theta(nk)) and tests each one by probing each of k(k-1)/2 links in Theta(k2) = Theta(1) time, for a total cost of Theta(nk) in the worst case.

2. The above algorithm can be trivially modified to find all conspiracies; the only additional cost is the cost of generating the output, but this is again bounded by Theta(nk).

Faster algorithms are welcome! Correct algorithms that run in time bounded by a polynomial whose exponent does not depend on k qualify for substantial extra credit.

2014-06-17 11:58