CS577-Homework 8 Solved

1.    Your friends are attending a convention and want to ask questions to the panelists. They worked together to create a set S of n different topics they would like to ask about. Each of your m friends has a VIP pass that guarantees them the ability to ask at most three questions each.

Unfortunately, due to the dense subject matter of the convention, not all of your friends understand every topic well enough to ask about it. For each friend i = 1,2,...,m, they have a set Si of topics they are capable of asking about. Finally, to make sure each topic is thoroughly addressed, the friends want to ask at least k different questions about each of the n topics (Note that one person should not ask about the same topic more than once). They are having trouble figuring out who should ask about which topics.

(a)    Design a polynomial-time algorithm that takes the input to an instance of this problem (the n topics, the sets Si for each of the m friends, and the parameter k) and decides whether there is a way to ask k questions about each of the n topics, while each friend asks at most three questions each.

(b)   You show your friends a solution computed by your algorithm from (a), but to your surprise, one of them exclaims, “That won’t do at all– the first topic is only asked about by Optimists!” You hadn’t heard anything about optimists; this is an extra wrinkle they neglected to mention earlier.

Each of your friends is either an Optimist or a Pessimist. This refers to their general attitude- they each fall into exactly one of these two categories and will behave that way for the entire convention, regardless of the topic they are asking about. To keep the panel’s responses as fair as possible, your friends agree that there should be no topic for which all k questions come from people with the same attitude.

Describe how to modify your algorithm from (a) into a new polynomial-time algorithm that decides whether there exists a solution satisfying all of the conditions from (a), plus the new requirements about optimists and pessimists.

2.    The Packers are playing the Bears tonight, and you’d like to invite some of your friends to watch the game at your place. All of your friends love football, and are either Packers or Bears fans, but some of them are known not to get along very well. In order to avoid possible trouble, you do not want to invite two people who are on bad terms with each other and root for a different team. (Having people who are on bad terms but root for the same team is OK, as is any of the other two combinations.) Also, although you like all of your friends, you like some better than others, and you have assigned a positive value to each of your friends.

Design a polynomial-time algorithm to figure out which friends to invite so as to maximize their total value under the above constraints.

Regular problems
3.    [You’re a homeowner who wants to revitalize your backyard. You make a list of n landscaping projects you want completed. There are two local landscaping companies that can do these jobs for you: Abed’s Azaleas and Britta’s Botanical Boutique. You can designate any subset of the tasks to each company, but every job should be done exactly once. Abed charges ai to do job i, and Britta charges bi for the same job. You’d like to spend as little money as possible, but you also need to account for the incompatibilities between the styles of the different suppliers. If you get jobs i and j done by different companies, there is an incompatibility cost of c(i,j).

(a)    Design an efficient algorithm to determine which landscaper should do each task so as to minimize the sum of the purchase costs and incompatibility costs.

(b)   It’s a slow season for the gardening industry, so these two companies are competing hard for your business. You’ll be completing the jobs in the order of your list, and Abed and Britta both have a copy. They’re also fiercely staking out each other’s businesses, so they’ll know when you purchase a service from their competitor. To try to win you back and keep the industry competitive, they both start offering you the same discount: if you recently hired their competitor, they’ll offer you a discount d off your next purchase. More formally, if you purchase job i from one company, the competing company will subtract d from their price to complete job (i + 1). They aren’t being too generous, though: you can assume d is less than the cost of all jobs, and is also less than all c(i,j).

Describe what efficient modification you can make to your algorithm from (a) so that your minimum sum of purchase costs and incompatibility costs accounts for this discount.

4.    Some of your friends with jobs out West decide they really need some extra time each day to sit in front of their laptops, and the morning commute from Woodside to Palo Alto seems like the only option. So they decide to carpool to work.

Unfortunately, they all hate to drive, so they want to make sure that any carpool arrangement they agree upon is fair, and doesn’t overload any individual with too much driving. Some sort of simple round-robin scheme is out, because none of them goes to work every day, and so the subset of them in the car varies from day to day.

Here’s one way to define fairness. Let the people be labeled S = {p1,...,pk}. We say that the total driving obligation of pj over a set of days is the expected number of times that pj would have driven, had a driver been chosen uniformly at random from among the people going to work each day. More concretely, suppose the carpool plan lasts for d days, and on the ith day a subset Si ⊆ S of the people go to work. Then the above definition of the total driving obligation ∆j for pj can be written as ∆ . Ideally, we’d like to require that pj drives at most ∆j times; however, ∆j may not be an integer.

So let’s say that a driving schedule is a choice of a driver for each day -— i.e., a sequence pi1,pi2,...,pid with pit ∈ St -— and that a fair driving schedule is one in which each pj is chosen as the driver on at most d∆je days.

(a)    Prove that for any sequence of sets S1, ..., Sd, there exists a fair driving schedule.

(b)   Design an algorithm to compute a fair driving schedule in time polynomial in k and d.

5.    A vertex cover of a graph G = (V,E) is a collection of vertices C ⊆ V such that every edge e ∈ E has at least one vertex in C.

Show that for bipartite graphs, the minimum size of a vertex cover equals the maximum size of a matching.

Challenge problem
6. Here is a variant of the game “Six Degrees of Kevin Bacon.”

You start with a set X of n actresses and a set Y of n actors, and two players P0 and P1. Player P0 names an actress x1 ∈ X, player P1 names an actor y1 who has appeared in a movie with x1, player P0 names an actress x2 who has appeared in a movie with y1, and so on. Thus, P0 and P1 collectively generate a sequence x1,y1,x2,y2,... such that each actor/actress in the sequence has costarred with the actress/actor immediately preceding. A player Pi(i = 0,1) loses when it is Pi’s turn to move, and she cannot name a member of her set who hasn’t been named before.

Suppose you are given a specific pair of such sets X and Y , with complete information on who has appeared in a movie with whom. A strategy for Pi in our setting is an algorithm that takes a current sequence x1,y1,x2,y2,... and generates a legal next move for Pi (assuming it’s Pi’s turn to move). Design a polynomial-time algorithm that, given some instance of the game, decides at the start of the the game which of the two players can force a win.

Programming problem
7. SPOJ problem Bank robbery (problem code BANKROB).