Thor's CS Problem of the Fortnight

Barrel rolling through the gunfire of Computer Science

Last Fortnight's Question: Imagine that you look in your kitchen, and you notice that you have three ingredients for your next recipe: eggs, milk, and sugar. Assuming that a "dish" is a combination of ingredients, list the dishes that you can produce using these ingredients (don't forget the empty dish!). In general, what is an efficient way to generate all of the dishes for a set of ingredients?

Its Answer: The problem described here is subset generation, and it's a pretty important one (I was asked this in a big-name interview last year, actually). You've got a set, and you want to generate all subsets of it. There's a really easy way to do this - it's the famous "binary counter" approach. Just count up in binary, like so: 000, 001, 010, 011, 100, 101, 110, 111. Then go through your set items and put them in the subset if there's a "1" in their place, and leave them out if there's a "0". Easy and fast! This is also a quick way to figure out how many subsets there are of a given set - it's obviously 2ⁿ, where n is the size of the set. Another way to do this, of course, is with the Gray Code method of writing down set elements one at a time, and then appending the element you just wrote to everything above it. This will generate minimal changes between iterative steps as well, which is useful for some applications.

This Fortnight's Question: Imagine that you work for an air travel planning company. You have a big map that has the airports of the world on it, and which shows which airports have direct flights between them. Your job is simple: You need to write a web app that allows your customers to figure out if it?s possible to get between two airports of their choice. How would you efficiently solve this problem for your application?

Thor