Thor's CS Problem of the Fortnight

Pro CS Job Interview Prep

Last Fortnight's Question: The Math Society wants to start a Clubs Council. They want to get representatives of each of the Math Clubs to show up at the council. However, MathSoc president Will doesn't want to have too many people on the council. Given a list of Math students and the clubs they belong to, how can you figure out which people he should invite to minimize attendence and still have every club represented? Remember, students can be in more than one club.

Its Answer: This is an example of the hitting set problem, which is closely related to the better known set cover problem. In this problem, we seek a set of set elements that are representative of the subsets in a given population. It can be trivially transformed to set cover by replacing each element of the set (person in this case) with a set of the subsets that that person is in. Set cover is an NP-complete problem.

There is hope in terms of a greedy algorithm, though. Simply select the student who is in the most clubs, and delete those clubs from the list. Then select the student who is in the largest number of the remaining clubs and repeat. This solution is simple, and will always give a cover using at most ln(n) sets as many as optimal, and might do a lot better in practice.

This Fortnight's Question: Suppose a town employs you as their snowplow driver. One day, a huge blizzard strikes the town, and all of the streets need to be plowed posthaste. You are faced with a map of the town, and tasked with planning your route. You need to plow every street, and you want to get it done quickly, so you look for a route through the town that will minimize the number of streets you need to drive down. How do you find this route? Note that it is acceptable to drive down streets more than once.

Thor