Example problems with polynomial and exponential solutions, and tiny footprint?

Question

I'm planning on running an “experiment” when teaching my algorithms class this fall, with one very old, limited computer (main limiting factor is probably memory—possibly as low as 16KB) and one modern/standard one. The idea being to solve a problem with a polynomial one, running on the slow computer, and an exponential one on the fast one (and, of course, have the slow one win).

The problem is finding a suitable problem—one where the running times will be really different for instances of very limited size (and, preferably, where the data structures are quite simple; the primitive computer is … primitive). I originally thought about sorting algorithms (e.g., quadratic vs. linear), but that would require far too large instances (unless I went with bogosort, for example).

At the moment, the only (rather boring) example I've thought of is computing Fibonacci numbers the smart and the stupid way. It would be nice to have something a little less tired/overused, and preferably something (semi-)obviously useful. Any ideas/suggestions?

Answer 1

An answer that somewhat generalizes Neel's comment is to look in the area of search and dynamic programming, which is full of wonderful algorithms that perform great if you memoize and terribly if you do not - even the boring factorial function you were thinking of falls in this category.

Of course, you will be limited by the memory ceiling on the slow computer, but I think that just means you have to be careful that you're sufficiently "mean" to the fast computer. Here are some specific ideas:

• Given a large undirected graph, find a path between two points. The fast computer implements a (fair, or it might not terminate!) randomized search through the graph, whereas the slow computer calmly performs a breadth-first or depth-first search. You'd probably need to run this on multiple trials to ensure that the performance difference is noticable.
• Get a directed graph and try to find the shortest path between two points: fast computer enumerates all acyclical paths (using the tortoise-and-hare cycle detection algorithm at every step, bwahahahaha) first, and the slow computer patiently runs single-source shortest path.
• The edit distance algorithm? Any more-naive-than-dynamic-programming algorithm is probably going to completely choke here.

One last idea is that you could try some algorithms in Prolog with and without an (unnecessary) occurs-check. But if you show those students how wonderful it is that Prolog without a semantically meaningful occurs-check is faster, I will cry. Also, this is usually a linear-vs-quadratic not polynomial-versus-exponential.

Answer 2

You could do regular expression matching. A naive backtracking matcher can easily be pushed into exponential behavior on inputs that a smarter matcher can handle in linear time.

Answer 3

Try counting perfect matchings in planar graphs, a problem that should be easy to explain. In the planar case, the Fisher-Kastelyen-Temperley algorithm solves it in polynomial time, whereas for general graphs the problem is #P-complete, i.e. probably no faster way than to do brute force counting. Simply run FKT on the slow machine and brute force counting on the fast one.

(This is also a related question.)

Answer 4

If you are teaching algorithms I think you should do something simple, that illustrates the idea. I think that your sorting algorithm idea is a very good one and probably work if you try non-recursive algorithms in the primitive computer.

I'm currently comparing sorting algorithms and I have Heap Sort running with 17,000 elements on a computer with 32kb ram.

I would try insertion sort vs Heap Sort.