WPI Worcester Polytechnic Institute

Computer Science Department
------------------------------------------

CS4123 Theory of Computation 
Homework 4 - D 2002

PROF. CAROLINA RUIZ 

Due Date: Friday, April 26th at 3 pm. 
Help session: Thursday, April 25th, 3:00-4:15 p FL232
Late Policy: No late homework will be accepted

------------------------------------------

Problems

  1. (20 points) Consider the Edge Cover problem:

    Show that this problem is in the class P. That is, show that there is a deterministic Turing machine that decides this problem in polynomial time in the size of the input.


  2. (20 points) Consider the Shortest path between two vertices problem:

    Note that a simple path is one that doesn't visit a vertex more than once; and the cost of a path is the sum of the cost of each edge in the path.

    Show that this problem is in the class P. That is, show that there is a deterministic Turing machine that decides this problem in polynomial time in the size of the input.


  3. (40 points) Consider the Longest path between two vertices problem:

    1. (20 points) Show that this problem is in the class NP.
    2. (20 points) Show that this problem is NP-complete.


  4. (40 points) Consider problem 7.26 in the textbook (p. 274).

    1. (20 points) Show that this problem is in the class NP.
    2. (20 points) Show that this problem is NP-complete.

Additional Problem for Students taking the course for Graduate Credit

None this time. Just do your best on the problems above :-)

Homework Submission