# 1. Map coloring

- 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).
Since each country can have three different colors, there are 3

^{n}possible colorings, for a total cost of Theta(3^{n}m).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 2

^{n-1}colorings, which gives a cost of O(2^{n-1}m) = O(2^{n}m). This is much better than Theta(3^{n}m), since it's easy to show that it's o(3^{n}m).*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 2*^{n-1}colorings anyway, because it has no mechanism to exclude bad colorings except the test at the end.

# 2. Suspicion

It's not clear that we can do much better than BruteForce for this. The simplest BruteForce approach generates all n

^{k}possible conspiracies (or, strictly speaking, all n choose k, but this is Theta(n^{k})) and tests each one by probing each of k(k-1)/2 links in Theta(k^{2}) = Theta(1) time, for a total cost of Theta(n^{k}) in the worst case.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(n

^{k}).

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.