Upcoming Prelim: Our second prelim takes place on Tuesday, April 10, at 7:30pm in Hollister B14. If you have a scheduling conflict, please let our Course Administrator (Kelly Patwell) know as soon as possible.
Reminder: Please include your Cornell NetID on your each part of your homework. We have been taking off points for those who neglect to include their NetID.
[Finding Cycles] For each of the following problems either show the problem is NP-complete or describe the best (least-time) polynomial time algorithm that you can find. For problems that are NP-complete, you are welcome to make use of any of the NP-complete problems discussed in class or in the text. For an algorithm, you should state the algorithm's runtime. It is not necessary to prove that your algorithm works. Describe your algorithm at a very high level, with just enough detail for someone familiar with this course to understand how the algorithm works (i.e., we don't want to see code). You are welcome to make use of any of the algorithms discussed in class or in the text.
[Genome Assembly] Do Problem 32 in Chapter 8 of the text.
[Avoiding Pamphleteers] Now that the weather is warm, more people are outside, including more people trying to hand pamphlets to passers-by. Your friend Otto has developed an aversion to pamphleteers (i.e., people trying to give him pamphlets). His goal is to pass few pamphleteers as he moves around campus, but at the same time, he doesn't want to do too much extra walking. Poor Otto has never had the benefit of CS482 and has asked for your help.
Here's one way to model this problem: Given an undirected graph G where each edge e is labeled with two integers (1) ye, the distance along that edge in yards, and (2) pe, the number of pamphleteers along that edge, and given a source node s, a destination node t, and bounds Y and P, is there an s-to-t path in G that takes less than or equal to Y yards and passes less than or equal to P pamphleteers?
Prove that APP (the Avoiding Pamphleteers Problem) is NP-complete.