Homework Guidelines

Collaboration policy   Collaboration on homework problems, with the exception of programming assignments and reading quizzes, is permitted, but not encouraged. If you choose to collaborate on some problems, you are allowed to discuss each problem with at most 3 other students currently enrolled in the class. Before working with others on a problem, you should think about it yourself for at least 45 minutes.  Finding answers to problems on the Web or from other outside sources (these include anyone not enrolled in the class) is strictly forbidden.

You must write up each problem solution by yourself without assistance, even if you collaborate with  others  to  solve  the problem.  You must also identify your collaborators.  If you did not work with anyone, you should write ”Collaborators:  none.” It is a violation of this policy to submit a problem solution that you cannot orally explain to an instructor or TA.

Typesetting   Solutions should be typed and submitted as a PDF file on Gradescope.  You may use any program you like to type your solutions. LATEX, or “Latex”, is commonly used for technical writing (overleaf.com is a free web-based platform for writing in Latex) since it handles math very well. Word, Google Docs, Markdown or other software are also fine.

Solution guidelines   For problems that require you to provide an algorithm, you must provide:

1. pseudocode and, if helpful, a precise description of the algorithm in English.   As always, pseudocode should include

● A clear description of the inputs and outputs

● Any assumptions you are making about the input (format, for example)

● Instructions that are clear enough that a classmate who hasn’t thought about the prob- lem yet would understand how to turn them into working code.  Inputs and outputs of any subroutines should be clear, data structures should be explained, etc.

If the algorithm is not clear enough for graders to understand easily, it may not be graded.

2.  a proof of correctness

3.  an analysis of running time and space

You may use algorithms from class, discussions, textbook, past assignments as subroutines.  (You may also call algorithms that you designed as part of the same problem.  )You may also use facts – such as correctness, running times – that we proved in class.

You should be as clear and concise  as possible in your write-up of solutions.  A simple, direct description or analysis is worth more points than a convoluted one, both because it is simpler and less prone to error and because it is easier to read and understand.  (Please make use of algorithms already studied, don’t write them down again.)

Figure 11.10. A positive instance of the escape problem, and its solution.

Figure 1: Escape Routes

Problem 1  (10 points) Escape routes

An n × n grid is an undirected graph with n2  vertices organized into n rows and n columns. We denote the vertex in the ith row and the jth column by (i, j).  Every vertex (i, j) has exactly four neighbors (i _ 1, j), (i + 1, j), (i, j _ 1), and (i, j + 1), except the boundary vertices, for which i = 1, i = n, j = 1, or j = n. Let (x1 , y1 ), (x2 , y2 ), ..., (xm, ym) be distinct vertices, called terminals, in the n × n grid.  The escape problem is to determine whether there are m vertex-disjoint paths in the grid that connect the terminals to any m distinct boundary vertices.

Describe and analyze an efficient algorithm to solve the escape problem.  The running time of your algorithm should be a small polynomial function of n.

Bonus, not to be handed in: For those of you interested, here is a variant of the problem that is more difficult to solve; Now suppose the input to the escape problem consists of a single integer n and the list of m terminal vertices.  If m is very small, the previous running time is actually exponential in the input size!  Describe and analyze an algorithm to solve the escape problem in time polynomial in m.

Problem 2  (10 points)  Train stations

You are leading a major police operation to capture a famous mafia boss. You know that the boss spends his summers in Boston but then moves to Miami for the winter. You are planning to capture him during his trip south.  It is well-known that the boss dislikes flying and always takes the train down to Florida.  You will assign undercover agents to train stations to search all the trains passing through that station. Unfortunately you have a limited budget and because of that you need to make sure that you dispatch agents to  as few  locations  as possible.  Your job is to decide which stations to send the inspectors to based on the map of the rail network (stations and tracks).

1.  Design an algorithm to identify the stations to dispatch the agents.

2. When you’ve finally finished selecting the locations your boss comes to you with a list of stations at which you cannot have inspections.  Design an algorithm to select the minimum set of stations so that each train is inspected at least once, but you don’t use the stations on the list.

Problem 3  (10 points) reductions, P, NP, NP- C

For each of the following statements, indicate whether it is true, false, or  “unknown”, where “unknown” indicates that scientists have not conclusively determined whether the statement is true or false.  For example, the correct answer for the statement  “P = NP” is  “unknown” .  But the correct answer for  “the best algorithm for the maximum flow problem in n-vertex graphs takes time at least 2n ” is “false” .

Give a short justification for your answer (i.e.  explain why the statement is true, or false, or not known to be either true or false).

1.  MINIMUM-cUT is NP-complete.

2.  MINIMUM-cUT is in NP.

3.  MINIMUM-cUT is in P.

4. If X is in NP, then there does not exist a polynomial-time algorithm for X.

5. If X is NP-complete, then there is no polynomial-time algorithm for X.

6. Every problem in P is in NP .

7. Every NP-complete problem is in NP .

8.  Some NP-complete problems have polynomial time algorithms, but some others do not.

9. If X is in P and X reduces to Y, then Y is in P.

10. If Y is in P and X reduces to Y, then X is in P.

11. If X is NP-C , Y is in NP, and X reduces to Y, then Y is NP-C.

12. If Y is NP-C, X is in NP, and X reduces to Y, then X is NP-C.

13. If we can find a polynomial algorithm for some NP-C problem that means that all NP-C problems can be solved in polynomial time.

14. If we can find a cubical algorithm  (meaning that it runs in time  O(n3 )) for some NP-C problem that means that all NP-C problems can be solved in cubical time.

15.  Suppose Y is NP-C. Then it is possible that some instances of Y can be solved in polynomial time.

Problem 4  (10 points) Forest problems

The Enchanted Forest is home to many magical beings.  King Arthur likes to pose riddles to the forest dwellers, whoever can solve them first is treated to a royal feast!  (The creatures quickly decided to solve all the problems together so that they can all celebrate together.)

This time King Arthur posed two particularly difficult riddles. After long hours of thinking the creatures realized that neither problem is likely to be solved in polynomial time.  However, they have to convince King Arthur that they are right. Help them by answering the following questions for both problems:

Describe a quick greedy algorithm that returns a solution (that is possible not optimal) to the problem.  (Your description should be  a few sentences  describing the  algorithm at a high level.   You  don’t  need  to prove  its  correctness  –  which  you  can’t  –  nor  analyze  its  running time .)

Describe a specific problem instance where the greedy algorithm does not yield the optimal solution.   Describe the input, what your greedy algorithm would return and the optimal solution.

Prove that the problem is NP-Complete.